BrownBoost (BrownBoost)

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

Мотивировка

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

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

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

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

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

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

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

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

Алгоритм

Вход:

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

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

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

Пока $s>0$:

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

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

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

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

См. также

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