BrownBoost

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Мотивировка[править | править вики-текст]

Алгоритм AdaBoost показал свою эффективность на множестве наборов данных. Тем не менее, можно показать, что AdaBoost не эффективен на зашумленных наборах данных[2]. Это следствие того, что 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 [3].) В этом пункте мы численно находим 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.[4] Реализацию BrownBoos можно найти в open source пакете JBoost.

Примечания[править | править вики-текст]

  1. Yoav Freund. An adaptive version of the boost by majority algorithm. Machine Learning, 43(3):293—318, June 2001.
  2. Dietterich, T. G., (2000). An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization. Machine Learning, 40 (2) 139—158.
  3. Robert Schapire and Yoram Singer. Improved Boosting Using Confidence-rated Predictions. Journal of Machine Learning, Vol 37(3), pages 297—336. 1999
  4. Ross A. McDonald, David J. Hand, Idris A. Eckley. An Empirical Comparison of Three Boosting Algorithms on Real Data Sets with Artificial Class Noise. Multiple Classifier Systems, In Series Lecture Notes in Computer Science, pages 35-44, 2003.

См. также[править | править вики-текст]