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

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

LogitBoost

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

Проблема AdaBoost — если модель сильно разреженная, есть какое-то количество выбросов в данных, то у модели будет большая ошибка и слабая обощающая способность. Основной принцип адаптивных бустингов — стремимся увеличить веса объектов, которые предсказаны плохо, чтобы они попали в следующую выборку данных. В AdaBoost это делается при помощи домножения на экспоненту. Мы хотим, чтобы неверные предсказания быстрее попали в верную область. Для этого вместо экспоненты можно использовать логистическую функцию. У нее более крутой изгиб, она сильнее изменяется, поэтому веса неверных объектов будут больше увеличиваться, а верные объекты наоборот быстрее перестанут учитываться. Такая модель лучше работает с обучением, так как быстрее получается выделить не совсем характерные данные и обучить ансамбль на них. В случае LogitBoost алгоритма мы минимизируем логистическую функцию потерь: $-log(1 + e^{-2yH})$.

Рассмотрим алгоритм сразу для классификации на несколько классов: пусть у нас есть $N$ объектов-векторов размера $p$ и $J$ классов. Заведем матрицу $W: \; w_{ij} = \frac{1}{N}$ — веса объектов. Изначально $F_j(x) = 0, \; p_j(x) = 0$.

Алгоритм

function LogitBoost():
   for $t = 1,\ldots,T$:
      for $j = 1,\ldots,J$:
         //Пересчитываем веса и нормализацию для j-ого класса
         [math]w_{ij}=p_i(x_i)(1-p_i(x_i))[/math]
         [math]z_{ij}=\frac{y_{ij}-p_i(x_i)}{w_{ij}}[/math]
         При помощи взвешенного МНК строим линейную регрессию $z$ от $x$ с весами $w$ на $f_{tj}$
      [math]h_{tj}(x) = \frac{J-1}{J} (h_{tj}(x) - \frac{1}{J}\sum_{k=1}^{J}h_{tk}(x))[/math]
      [math]H_{j}(x) = H_j(x)+h_{tj}[/math]
      [math]p_{j}(x) = \frac{e^{H_j(x)}}{\sum_{k=1}^{J} e^{H_k(x)}}[/math]
   return [math]\underset {x}{\operatorname {argmax}}H_j(x)[/math]

fuf

BrownBoost

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

Расмотренные ранее AdaBoost и LogitBoost плохо работают при наличии шума в данных, что может приводить к переобучению. На каждой итерации бустинга объектам присваиваются веса, и большой вес у объекта показывает, что алгоритм плохо отработал на нем. Это может быть индикатором того, что этот объект шумовой. В случае Ada- и 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 матрице.

См. также

• Бустинг, AdaBoost
• Виды ансамблей
• XGBoost
• CatBoost