Алгоритмы бустинга — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: « Бустинг {{---}} это композиция алгоритмов, где на каждой итерации алгоритм…»)
 
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
[[Бустинг, AdaBoost | Бустинг]] {{---}} это композиция алгоритмов, где на каждой итерации алгоритм пытается исправить все ошибки композиции предыдущих алгоритмов.  
 
[[Бустинг, AdaBoost | Бустинг]] {{---}} это композиция алгоритмов, где на каждой итерации алгоритм пытается исправить все ошибки композиции предыдущих алгоритмов.  
  
== LogitBoost ==  
+
== LogitBoost ==
  
 +
=== Идея алгоритма ===
 +
 +
Проблема AdaBoost {{---}} если модель сильно разреженная, есть какое-то количество выбросов в данных, то у модели будет большая ошибка и слабая обощающая способность. Основной принцип адаптивных бустингов {{---}} стремимся увеличить веса объектов, которые предсказаны плохо, чтобы они попали в следующую выборку данных. В AdaBoost это делается при помощи домножения на экспоненту. Мы хотим, чтобы неверные предсказания быстрее попали в верную область. Для этого вместо экспоненты можно использовать логистическую функцию. У нее более крутой изгиб, она сильнее изменяется, поэтому веса неверных объектов будут больше увеличиваться, а верные объекты наоборот быстрее перестанут учитываться. Такая модель лучше работает с обучением, так как быстрее получается выделить не совсем характерные данные и обучить ансамбль на них.
 +
В случае LogitBoost алгоритма мы на каждой итерации минимизируем логистическую функцию потерь: $-\log(1 + e^{-2yH})$, где $y$ {{---}} значение, $H$ {{---}} построенный классификатор.
 +
 +
Рассмотрим алгоритм сразу для классификации на несколько классов: пусть у нас есть $m$ объектов-векторов и $J$ классов. Заведем матрицу, в которой элемент $w_{ij} ${{---}} вес $i-$го объекта $j-$го класса. Изначально $w_{ij} = \frac{1}{m}, \; F_j(x) = 0, \; p_j(x) = 0$.
 +
 +
=== Алгоритм ===
 +
 +
'''function''' LogitBoost():
 +
    '''for $t = 1,\ldots,T$:'''
 +
      '''for $j = 1,\ldots,J$:'''
 +
          <font color=green>//Пересчитываем веса и нормализацию для j-го класса</font>
 +
          <tex>w_{ij}=p_j(x_i)(1-p_j(x_i))</tex>
 +
          <tex>z_{ij}=\frac{y_{ij}-p_j(x_i)}{w_{ij}}</tex>
 +
          При помощи взвешенного МНК строим линейную регрессию $z$ от $x$ с весами $w$ на $h_{tj}$
 +
      <tex>h_{tj}(x) = \frac{J-1}{J} (h_{tj}(x) - \frac{1}{J}\sum_{k=1}^{J}h_{tk}(x))</tex>
 +
      <tex>H_{j}(x) = H_j(x)+h_{tj}</tex>
 +
      <tex>p_{j}(x) = \frac{e^{H_j(x)}}{\sum_{k=1}^{J} e^{H_k(x)}}</tex>
 +
    '''return''' <tex>\underset {x}{\operatorname {argmax}}H_j(x)</tex>
  
 
== BrownBoost ==
 
== BrownBoost ==
Строка 8: Строка 28:
 
=== Идея алгоритма ===
 
=== Идея алгоритма ===
  
Расмотренные ранее AdaBoost и LogitBoost плохо работают при наличии шума в данных, что может приводить к переобучению. На каждой итерации бустинга объектам присваиваются веса, и большой вес у объекта показывает, что алгоритм плохо отработал на нем. Это может быть индикатором того, что этот объект шумовой. Тогда, если "откидывать" объекты с большим весом при работе алгоритма, на итоговый классификатор будут влиять незашумленные объекты. Из-за этого итоговая функция ошибки может улучшиться.
+
Расмотренные ранее AdaBoost и LogitBoost плохо работают при наличии шума в данных, что может приводить к переобучению. На каждой итерации бустинга объектам присваиваются веса, и большой вес у объекта показывает, что алгоритм плохо отработал на нем. Это может быть индикатором того, что этот объект шумовой. В случае Ada- и LogitBoost модель будет пытаться обучиться на них и через несколько итераций останутся только шумовые данные. Однако, если «откидывать» объекты с большим весом при работе алгоритма, на итоговый классификатор будут влиять незашумленные объекты. Из-за этого итоговая функция ошибки может улучшиться.
 +
 
 +
Пусть дана обучающая выборка <tex>T</tex> длины <tex>m: \; T = (x_1, y_1) \ldots (x_m, y_m), \; x_i \in X, y_i \in Y = \{-1,+1\}</tex>. Мы можем задать время $c$, которое будет работать алгоритм бустинга. Чем больше это время, тем дольше будет работать алгоритм, а значит тем меньше данных он будет считать зашумленными и «откидывать». Каждая итерация занимает $t_i$ времени, и мы считаем, сколько осталось работать времени {{---}} $s$.
 +
 
 +
Можно связать время работы алгоритма $c$ и итоговую ошибку:
 +
<center><tex>\epsilon = 1 - \operatorname {erf} (\sqrt c)</tex></center>
 +
где $erf$ {{---}} функция ошибок<ref>[https://ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%BE%D1%88%D0%B8%D0%B1%D0%BE%D0%BA Функция ошибок]</ref>. Из этого следует, что мы можем получить любую желаемую итоговую ошибку, передав соответствующий параметр $c$ (это можно вычислить при помощи обратной функции ошибок).
 +
 
 +
Для всех объектов обучающий выборки хранятся веса на каждой итерации $r_i(x, y)$. Изначально они все равны 0. Чтобы избежать вырожденные случаи, введем константу $\nu > 0$.
  
Пусть дана обучающая выборка <tex>T</tex> длины <tex>m: \; T = (x_1, y_1) \ldots (x_m, y_m), \; x_i \in X, y_i \in Y = \{-1,+1\}</tex>
+
Основная идея BrownBoost {{---}} на каждой итерации у слабого классификатора есть вес <tex> \alpha_i </tex> и количество прошедшего в течение итерации времени <tex> t_i </tex>, и эти величины напрямую связаны между собой. Чтобы их найти, надо решить систему нелинейных уравнений. Она задана дифференциальным уравнением
 +
<center><tex>[*]: \; \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)}</tex></center>
 +
и граничными условиями: <tex>t = 0, \; \alpha = 0</tex>.
  
Основная идея BrownBoost {{---}} на каждой итерации у найденного слабого классификатора есть вес <tex> \alpha_i </tex> и количество прошедшего в течение итерации времени <tex> t_i </tex> и эти величины напрямую связаны между собой. Они задаются системой нелинейных уравнений вида:
+
Решением системы будет считаться пара чисел <tex>\alpha_i, t_i: \; t_i = s</tex> или $\gamma_i \leq \nu$. Решить данную систему можно методом Ньютона<ref>[https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0 Метод Ньютона]</ref>, как это было предложено автором BrownBoost'а Йоав Фройндом<ref>[https://cseweb.ucsd.edu/~yfreund/papers/brownboost.pdf Yoav Freund {{---}} An adaptive version of the boost by majority algorithm]</ref>.
<center><tex>\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)}</tex></center>
 
Граничные условия: <tex>t = 0, \; \alpha = 0</tex>
 
Параметр t - аналогия к параметру T из AdaBoost
 
  
 
=== Алгоритм ===
 
=== Алгоритм ===
Строка 21: Строка 48:
 
  '''function''' BrownBoost($T$, $c$):
 
  '''function''' BrownBoost($T$, $c$):
 
     '''do:'''
 
     '''do:'''
       <tex>W_i(x, y) = e^{-(r_i(x, y)+s)^2/c}</tex> <font color=green>//Задаем вес для каждого объекта</font>
+
       <tex>W_i(x, y) = e^{\frac{-(r_i(x, y)+s)^2}{c}}</tex> <font color=green>//Задаем вес для каждого объекта</font>
       Вызываем слабый алгоритм и находим классификатор <tex>h_i: \; \sum_{(x, y)} W_i(x, y)h_i(x)y = \gamma_i > 0</tex> <font color=green>//<tex>h_i: \; X \rightarrow Y</tex></font>
+
       Вызываем базовый алгоритм и находим классификатор <tex>h_i: \; \sum_{(x, y)} W_i(x, y)h_i(x)y = \gamma > 0</tex> <font color=green>//<tex>h_i: \; X \rightarrow Y</tex></font>
       <tex>\alpha_i, t_i \leftarrow</tex> Решение системы уравнений [1]
+
       <tex>\alpha_i, t_i \leftarrow</tex> Решение системы уравнений [*]
 
       <tex>r_{i+1}(x, y) = r_i(x, y) + \alpha_i h_i(x) y</tex> <font color=green>//Обновляем веса каждого объекта</font>
 
       <tex>r_{i+1}(x, y) = r_i(x, y) + \alpha_i h_i(x) y</tex> <font color=green>//Обновляем веса каждого объекта</font>
       s = s - t <font color=green>//Обновляем время</font>
+
       s = s - t <font color=green>//Обновляем оставшееся время</font>
 
     '''while''' <tex>s > 0</tex>
 
     '''while''' <tex>s > 0</tex>
 
     '''return''' <tex>H(x) = \textrm{sign}\left(\sum\limits_{i=1} \alpha_i h_i(x)\right)</tex>  <font color=green>//$H(x)$ {{---}} результирующий классификатор</font>
 
     '''return''' <tex>H(x) = \textrm{sign}\left(\sum\limits_{i=1} \alpha_i h_i(x)\right)</tex>  <font color=green>//$H(x)$ {{---}} результирующий классификатор</font>
 +
 +
=== Мультиклассовая классификация ===
 +
Данный алгоритм можно обобщить с бинарной классификации на мультиклассовую при помощи метода Error-Correcting Output Codes (ECOC)<ref>[https://www.jmlr.org/papers/volume1/allwein00a/allwein00a.pdf E. L. Allwein, R. E. Schapire, and Y. Singer {{---}} Reducing multiclass to binary: A unifying approach for margin classifers]</ref>. Для этого введем ECOC матрицу. Для каждого элемента $(x_n, y_n)$ и класса $j$ вес будет пересчитываться следующим образом:
 +
<center><tex>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</tex></center>
 +
где $\lambda_j^n$ соответствует элементу класса $j$ в ECOC матрице.
 +
 +
== Примечания==
 +
<references />
 +
 +
== См. также ==
 +
*[[Бустинг, AdaBoost | Бустинг, AdaBoost]]
 +
*[[Виды ансамблей | Виды ансамблей]]
 +
*[[XGBoost | XGBoost]]
 +
*[[CatBoost | CatBoost]]

Текущая версия на 19:43, 4 сентября 2022

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

LogitBoost

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

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

Рассмотрим алгоритм сразу для классификации на несколько классов: пусть у нас есть $m$ объектов-векторов и $J$ классов. Заведем матрицу, в которой элемент $w_{ij} $— вес $i-$го объекта $j-$го класса. Изначально $w_{ij} = \frac{1}{m}, \; 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_j(x_i)(1-p_j(x_i))[/math]
         [math]z_{ij}=\frac{y_{ij}-p_j(x_i)}{w_{ij}}[/math]
         При помощи взвешенного МНК строим линейную регрессию $z$ от $x$ с весами $w$ на $h_{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]

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 - \operatorname {erf} (\sqrt c)[/math]

где $erf$ — функция ошибок[1]. Из этого следует, что мы можем получить любую желаемую итоговую ошибку, передав соответствующий параметр $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$. Решить данную систему можно методом Ньютона[2], как это было предложено автором BrownBoost'а Йоав Фройндом[3].

Алгоритм

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)[4]. Для этого введем 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 матрице.

Примечания

См. также