WikiSort.ru - Не сортированное

Машинное обучение и data mining

Задачи Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение

Обучение с учителем Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей (Бэггинг, Бустинг, Random forest) Метод релевантных векторов

Кластерный анализ Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift

Снижение размерности Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE

Структурное прогнозирование Графовая вероятностная модель (Байесовская сеть, Скрытая марковская модель, CRF)

Выявление аномалий Метод k-ближайших соседей Локальный уровень выброса

Графовые вероятностные модели Байесовская сеть Марковская сеть Скрытая марковская модель

Искусственные нейронные сети Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации (Сигмоида, Softmax, Радиально-базисная функция) Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть (Долгая краткосрочная память, Управляемый рекуррентный блок) Свёрточная нейронная сеть (U-Net) Автокодировщик

Обучение с подкреплением Марковский процесс Уравнение Беллмана Жадный алгоритм Q-learning SARSA Temporal difference (TD)

Теория Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения

Журналы и конференции NIPS ICML ML JMLR ArXiv:cs.LG

Глоссарий Глоссарий по машинному обучению

Статьи по теме List of datasets for machine-learning research Outline of machine learning

BrownBoost — алгоритм бустинга, который показал свою эффективность на зашумленных наборах данных. Как и все алгоритмы бустинга, BrownBoost используется в сочетании с другими алгоритмами машинного обучения. Алгоритм BrownBoost был предложен Йоавом Фройндом (en:Yoav Freund)^[1].

Мотивировка

Алгоритм AdaBoost показал свою эффективность на множестве наборов данных. Тем не менее, можно показать, что AdaBoost не эффективен на зашумленных наборах данных^[2]. Это следствие того, что AdaBoost фокусируется на элементах обучающей выборки, которые многократно ошибочно классифицированы. В отличие от него, BrownBoost просто «сдаётся» на таких элементах. В основе BrownBoost лежит предположение, что зашумленные элементы будут многократно ошибочно классифицированы базовыми классификаторами, а незашумленные элементы будут достаточно часто корректно классифицированы. Это позволит откинуть зашумленные элементы, а незашумленные элементы внесут свой вклад в итоговый классификатор. Таким образом итоговый классификатор будет обучаться на незашумленных элементах обучающей выборки, поэтому его обобщающая способность может быть лучше, чем у AdaBoost при обучении на обучающей выборке с шумом.

Описание алгоритма

BrownBoost использует невыпуклую функцию потерь, поэтому он не попадает в семейство алгоритмов AnyBoost. Невпуклая оптимизация позволяет избежать переобучения на зашумленных наборах данных. В отличие от алгоритмов бустинга (таких как AdaBoost и LogitBoost), которые минимизируют выпуклую функцию потерь, BrownBoost решает систему из 2 уравнений с двумя неизвестными, используя стандартные численные методы.

Единственный параметр алгоритма BrownBoost это ${\displaystyle c}$  — «время», которое алгоритм работает. Каждому слабому классификатору даётся время ${\displaystyle t}$ , которое напрямую связано с весом классификатора.

Большое значение ${\displaystyle c}$ означает, что BrownBoost будет считать данные менее зашумленными и отбросит меньше элементов обучающей выборки. Соответственно, малое значение ${\displaystyle c}$ означает, что BrownBoost будет считать данные более зашумленными и отбросит больше элементов обучающей выборки. На каждом шаге алгоритм выбирает базовый классификатор немного лучше, чем просто случайным образом. Вес этого классификатора ${\displaystyle \alpha }$ и количество прошедшего в течение итерации времени ${\displaystyle t}$ задаются решением системы 2 нелинейных уравнений (1. нескоррелированность базового классификатора и весов элементов обучающей выборки; 2. неизменность потенциала) с 2 неизвестными. Эта система может быть решена методом дихотомии, как реализовано в пакете JBoost, или методом Ньютона, как в оригинальной статье автора. После решения уравнений веса элементов обучающей выборки ${\displaystyle r_{i}(x_{j})}$ и количество оставшегося времени пересчитывается. Эта процедура повторяется, пока не кончится всё время.

Начальный потенциал определяется как ${\displaystyle {\frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}({\sqrt {c}})=1-{\mbox{erf}}({\sqrt {c}})}$ . Так как каждый шаг алгоритма не меняет потенциал, то верно равенство ${\displaystyle {\frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}(r_{i}(x_{j})/{\sqrt {c}})=1-{\mbox{erf}}({\sqrt {c}})}$ . Поэтому конечная ошибка вероятно близка к ${\displaystyle 1-{\mbox{erf}}({\sqrt {c}})}$ . Тем не менее, конечная функция потенциала не является бинарной функцией потерь.

Чтобы конечная функция потерь была в точности ${\displaystyle 1-{\mbox{erf}}({\sqrt {c}})}$ , дисперсия должна линейно убывать по времени, чтобы сформировать бинарную функцию потерь после окончания итераций бустинга. Этот момент еще не описан в литературе и отсутствует в определении алгоритма ниже.

Конечный классификатор является линейной комбинацией базовых классификаторов, и его качество может быть оценено так же как в большинстве других алгоритмов бустинга.

Алгоритм

Вход:

• ${\displaystyle m}$ обучающая выборка ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{m},y_{m})}$ где ${\displaystyle x_{j}\in X,\,y_{j}\in Y=\{-1,+1\}}$
• параметр ${\displaystyle c}$

Инициализация:

• ${\displaystyle s=c}$ . Значение ${\displaystyle s}$ это количество оставшегося времени работы алгоритма.
• ${\displaystyle r_{i}(x_{j})=0}$   ${\displaystyle \forall j}$ . Значения ${\displaystyle r_{i}(x_{j})}$ это веса на итерации ${\displaystyle i}$ для элемента обучающей выборки ${\displaystyle x_{j}}$ .

Пока ${\displaystyle s>0}$ :

• Установить вес каждого элемента обучающей выборки: ${\displaystyle W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}}$ , здесь ${\displaystyle r_{i}(x_{j})}$ вес элемента ${\displaystyle x_{j}}$
• Найти базовый классификатор ${\displaystyle h_{i}:X\to \{-1,+1\}}$ такой что ${\displaystyle \sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0}$
• Найти значения ${\displaystyle \alpha ,t}$ удовлетворяющие уравнению:
  ${\displaystyle \sum _{j}h_{i}(x_{j})y_{j}e^{-{\frac {(r_{i}(x_{j})+\alpha h_{i}(x_{j})y_{j}+s-t)^{2}}{c}}}=0}$ .
  (Заметим что это схоже условию${\displaystyle E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0}$ ^[3].) В этом пункте мы численно находим ${\displaystyle W_{i+1}=\exp({\frac {\ldots }{\ldots }})}$ such that ${\displaystyle E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0}$ .)
  Это изменение должно соответствовать ограничению
  ${\displaystyle \sum \left(\Phi \left(r_{i}(x_{j})+\alpha h(x_{j})y_{j}+s-t\right)-\Phi \left(r_{i}(x_{j})+s\right)\right)=0}$ ,
  здесь ${\displaystyle \Phi (z)=1-{\mbox{erf}}(z/{\sqrt {c}})}$ потери потенциала для точки с весом ${\displaystyle r_{i}(x_{j})}$
• Обновить веса для каждого элемента обучающей выборки: ${\displaystyle r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}}$
• Обновить оставшееся время: ${\displaystyle s=s-t}$

Выход: ${\displaystyle H(x)={\textrm {sign}}\left(\sum _{i}\alpha _{i}h_{i}(x)\right)}$

Эмпирические результаты

В предварительных экспериментах BrownBoost имеет меньшую ошибку обобщающей способности по сравнению с AdaBoost и имеет схожие результаты с LogitBoost.^[4] Реализацию BrownBoos можно найти в open source пакете JBoost.

Примечания

См. также

• AdaBoost
• Дерево принятия решений
• JBoost