BrownBoost

Алгоритм 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] Реализацию BrownBoost можно найти в open source пакете JBoost.