Алгоритмы бустинга — различия между версиями
Wdywbac (обсуждение | вклад) (logitboost added) |
м (rollbackEdits.php mass rollback) |
||
(не показано 5 промежуточных версий 2 участников) | |||
Строка 6: | Строка 6: | ||
Проблема AdaBoost {{---}} если модель сильно разреженная, есть какое-то количество выбросов в данных, то у модели будет большая ошибка и слабая обощающая способность. Основной принцип адаптивных бустингов {{---}} стремимся увеличить веса объектов, которые предсказаны плохо, чтобы они попали в следующую выборку данных. В AdaBoost это делается при помощи домножения на экспоненту. Мы хотим, чтобы неверные предсказания быстрее попали в верную область. Для этого вместо экспоненты можно использовать логистическую функцию. У нее более крутой изгиб, она сильнее изменяется, поэтому веса неверных объектов будут больше увеличиваться, а верные объекты наоборот быстрее перестанут учитываться. Такая модель лучше работает с обучением, так как быстрее получается выделить не совсем характерные данные и обучить ансамбль на них. | Проблема AdaBoost {{---}} если модель сильно разреженная, есть какое-то количество выбросов в данных, то у модели будет большая ошибка и слабая обощающая способность. Основной принцип адаптивных бустингов {{---}} стремимся увеличить веса объектов, которые предсказаны плохо, чтобы они попали в следующую выборку данных. В AdaBoost это делается при помощи домножения на экспоненту. Мы хотим, чтобы неверные предсказания быстрее попали в верную область. Для этого вместо экспоненты можно использовать логистическую функцию. У нее более крутой изгиб, она сильнее изменяется, поэтому веса неверных объектов будут больше увеличиваться, а верные объекты наоборот быстрее перестанут учитываться. Такая модель лучше работает с обучением, так как быстрее получается выделить не совсем характерные данные и обучить ансамбль на них. | ||
− | В случае LogitBoost алгоритма мы минимизируем логистическую функцию потерь: $-log(1 + e^{-2yH})$. | + | В случае 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$. |
=== Алгоритм === | === Алгоритм === | ||
Строка 15: | Строка 15: | ||
'''for $t = 1,\ldots,T$:''' | '''for $t = 1,\ldots,T$:''' | ||
'''for $j = 1,\ldots,J$:''' | '''for $j = 1,\ldots,J$:''' | ||
− | <font color=green>//Пересчитываем веса и нормализацию для j- | + | <font color=green>//Пересчитываем веса и нормализацию для j-го класса</font> |
− | <tex>w_{ij}= | + | <tex>w_{ij}=p_j(x_i)(1-p_j(x_i))</tex> |
− | <tex>z_{ij}=\frac{y_{ij}- | + | <tex>z_{ij}=\frac{y_{ij}-p_j(x_i)}{w_{ij}}</tex> |
− | При помощи взвешенного МНК строим линейную регрессию $z$ от $x$ с весами $w$ на $ | + | При помощи взвешенного МНК строим линейную регрессию $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_{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>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> | <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> | '''return''' <tex>\underset {x}{\operatorname {argmax}}H_j(x)</tex> | ||
− | |||
− | |||
== BrownBoost == | == BrownBoost == | ||
Строка 30: | Строка 28: | ||
=== Идея алгоритма === | === Идея алгоритма === | ||
− | Расмотренные ранее AdaBoost и LogitBoost плохо работают при наличии шума в данных, что может приводить к переобучению. На каждой итерации бустинга объектам присваиваются веса, и большой вес у объекта показывает, что алгоритм плохо отработал на нем. Это может быть индикатором того, что этот объект шумовой. В случае Ada- и 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$, которое будет работать алгоритм бустинга. Чем больше это время, тем дольше будет работать алгоритм, а значит тем меньше данных он будет считать зашумленными и | + | Пусть дана обучающая выборка <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$ и итоговую ошибку: | Можно связать время работы алгоритма $c$ и итоговую ошибку: | ||
− | <center><tex>\epsilon = 1 - erf(\sqrt c)</tex></center> | + | <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$ (это можно вычислить при помощи обратной функции ошибок). | где $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$ (это можно вычислить при помощи обратной функции ошибок). | ||
Строка 41: | Строка 39: | ||
Основная идея BrownBoost {{---}} на каждой итерации у слабого классификатора есть вес <tex> \alpha_i </tex> и количество прошедшего в течение итерации времени <tex> t_i </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> | + | <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>. | и граничными условиями: <tex>t = 0, \; \alpha = 0</tex>. | ||
Текущая версия на 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-го классаПри помощи взвешенного МНК строим линейную регрессию $z$ от $x$ с весами $w$ на $h_{tj}$ return
BrownBoost
Идея алгоритма
Расмотренные ранее AdaBoost и LogitBoost плохо работают при наличии шума в данных, что может приводить к переобучению. На каждой итерации бустинга объектам присваиваются веса, и большой вес у объекта показывает, что алгоритм плохо отработал на нем. Это может быть индикатором того, что этот объект шумовой. В случае Ada- и LogitBoost модель будет пытаться обучиться на них и через несколько итераций останутся только шумовые данные. Однако, если «откидывать» объекты с большим весом при работе алгоритма, на итоговый классификатор будут влиять незашумленные объекты. Из-за этого итоговая функция ошибки может улучшиться.
Пусть дана обучающая выборка
длины . Мы можем задать время $c$, которое будет работать алгоритм бустинга. Чем больше это время, тем дольше будет работать алгоритм, а значит тем меньше данных он будет считать зашумленными и «откидывать». Каждая итерация занимает $t_i$ времени, и мы считаем, сколько осталось работать времени — $s$.Можно связать время работы алгоритма $c$ и итоговую ошибку:
где $erf$ — функция ошибок[1]. Из этого следует, что мы можем получить любую желаемую итоговую ошибку, передав соответствующий параметр $c$ (это можно вычислить при помощи обратной функции ошибок).
Для всех объектов обучающий выборки хранятся веса на каждой итерации $r_i(x, y)$. Изначально они все равны 0. Чтобы избежать вырожденные случаи, введем константу $\nu > 0$.
Основная идея BrownBoost — на каждой итерации у слабого классификатора есть вес
и количество прошедшего в течение итерации времени , и эти величины напрямую связаны между собой. Чтобы их найти, надо решить систему нелинейных уравнений. Она задана дифференциальным уравнениеми граничными условиями:
.Решением системы будет считаться пара чисел [2], как это было предложено автором BrownBoost'а Йоав Фройндом[3].
или $\gamma_i \leq \nu$. Решить данную систему можно методом НьютонаАлгоритм
function BrownBoost($T$, $c$): do://Задаем вес для каждого объекта Вызываем базовый алгоритм и находим классификатор // Решение системы уравнений [*] //Обновляем веса каждого объекта s = s - t //Обновляем оставшееся время while return //$H(x)$ — результирующий классификатор
Мультиклассовая классификация
Данный алгоритм можно обобщить с бинарной классификации на мультиклассовую при помощи метода Error-Correcting Output Codes (ECOC)[4]. Для этого введем ECOC матрицу. Для каждого элемента $(x_n, y_n)$ и класса $j$ вес будет пересчитываться следующим образом:
где $\lambda_j^n$ соответствует элементу класса $j$ в ECOC матрице.