Алгоритмы бустинга

Бустинг — это композиция алгоритмов, где на каждой итерации алгоритм пытается исправить все ошибки композиции предыдущих алгоритмов.

BrownBoost

Идея алгоритма

Расмотренные ранее AdaBoost и LogitBoost плохо работают при наличии шума в данных, что может приводить к переобучению. На каждой итерации бустинга объектам присваиваются веса, и большой вес у объекта показывает, что алгоритм плохо отработал на нем. Это может быть индикатором того, что этот объект шумовой. Тогда, если "откидывать" объекты с большим весом при работе алгоритма, на итоговый классификатор будут влиять незашумленные объекты. Из-за этого итоговая функция ошибки может улучшиться.

Пусть дана обучающая выборка [math]T[/math] длины [math]m: \; T = (x_1, y_1) \ldots (x_m, y_m), \; x_i \in X, y_i \in Y = \{-1,+1\}[/math]

Основная идея BrownBoost — на каждой итерации у найденного слабого классификатора есть вес [math] \alpha_i [/math] и количество прошедшего в течение итерации времени [math] t_i [/math] и эти величины напрямую связаны между собой. Они задаются системой нелинейных уравнений вида:

[math]\frac{dt}{d \alpha} = \frac{\sum\limits_{(x,y) \in T}exp(-\frac{1}{c}(r_i(x, y)+\alpha h_i(x)y +s_i-t)^2)h_i(x)y}{\sum\limits_{(x,y) \in T}exp(-\frac{1}{c}(r_i(x, y)+\alpha h_i(x)y +s_i-t)^2)}[/math]

Граничные условия: [math]t = 0, \; \alpha = 0[/math] Параметр t - аналогия к параметру T из AdaBoost

Алгоритм

function BrownBoost($T$, $c$):
   do:
      [math]W_i(x, y) = e^{-(r_i(x, y)+s)^2/c}[/math] //Задаем вес для каждого объекта
      Вызываем слабый алгоритм и находим классификатор [math]h_i: \; \sum_{(x, y)} W_i(x, y)h_i(x)y = \gamma_i \gt  0[/math] //[math]h_i: \; X \rightarrow Y[/math]
      [math]\alpha_i, t_i \leftarrow[/math] Решение системы уравнений [1]
      [math]r_{i+1}(x, y) = r_i(x, y) + \alpha_i h_i(x) y[/math] //Обновляем веса каждого объекта
      s = s - t //Обновляем время
   while [math]s \gt  0[/math]
   return [math]H(x) = \textrm{sign}\left(\sum\limits_{i=1} \alpha_i h_i(x)\right)[/math]  //$H(x)$ — результирующий классификатор