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

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

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]. Мы можем задать время, которое будет работать алгоритм бустинга — $c$. Чем больше это время, тем дольше будет работать алгоритм, а значит тем меньше данных он будет считать зашумленными и "откидывать". Каждая итерация занимает $t_i$ времени, и мы считаем, сколько осталось работать времени — $s$.

Можно связать время работы алгоритма $c$ и итоговую ошибку:

[math]\epsilon = 1 - erf(\sqrt c)[/math]

где $erf$ — функция ошибок. Из этого следует, что мы можем получить любую желаемую итоговую ошибку, передав соответствующий параметр $c$ (это можно вычислить при помощи обратной функции ошибок).

Для всех объектов обучающий выборки хранятся веса на каждой итерации $r_i(x, y)$. Изначально они все равны 0. Чтобы избежать вырожденные случаи, введем константу $\nu > 0$.

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

[math][*]: \; \frac{dt}{d \alpha} = \gamma = \frac{\sum\limits_{(x,y) \in T}exp(-\frac{1}{c}(r_i(x, y)+\alpha h_i(x)y +s-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-t)^2)}[/math]

и граничными условиями: [math]t = 0, \; \alpha = 0[/math].

Решением системы будет считаться пара чисел [math]\alpha_i, t_i: \; t_i = s[/math] или $\gamma_i \leq \nu$. Решить данную систему можно методом Ньютона, как это было предложено автором BrownBoost'а Йоав Фройндом.

Алгоритм

function BrownBoost($T$, $c$):
   do:
      [math]W_i(x, y) = e^{\frac{-(r_i(x, y)+s)^2}{c}}[/math] //Задаем вес для каждого объекта
      Вызываем базовый алгоритм и находим классификатор [math]h_i: \; \sum_{(x, y)} W_i(x, y)h_i(x)y = \gamma \gt  0[/math] //[math]h_i: \; X \rightarrow Y[/math]
      [math]\alpha_i, t_i \leftarrow[/math] Решение системы уравнений [*]
      [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)$ — результирующий классификатор

Мультиклассовая классификация

Данный алгоритм можно обобщить с бинарной классификации на мультиклассовую при помощи метода Error-Correcting Output Codes (ECOC). Для этого введем ECOC матрицу

Для каждого элемента $(x_n, y_n)$ и класса $j$ будут пересчитываться следующим образом:

[math]r_{i+1, j}(x_n, y_n) = r_{i,j}(x_n, y_n) + \alpha_i h_{i,j}(x_n) \lambda_j^n[/math]

где $\lambda_j^n$ соответствует элементу класса $j$ в ECOC матрице.