11
правок
Изменения
logitboost added
[[Бустинг, AdaBoost | Бустинг]] {{---}} это композиция алгоритмов, где на каждой итерации алгоритм пытается исправить все ошибки композиции предыдущих алгоритмов.
== 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$:'''
<font color=green>//Пересчитываем веса и нормализацию для j-ого класса</font>
<tex>w_{ij}=p_i(x_i)(1-p_i(x_i))</tex>
<tex>z_{ij}=\frac{y_{ij}-p_i(x_i)}{w_{ij}}</tex>
При помощи взвешенного МНК строим линейную регрессию $z$ от $x$ с весами $w$ на $f_{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>
fuf
== BrownBoost ==
=== Идея алгоритма ===
Расмотренные ранее 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$, которое будет работать алгоритм бустинга {{---}} $c$. Чем больше это время, тем дольше будет работать алгоритм, а значит тем меньше данных он будет считать зашумленными и "откидывать". Каждая итерация занимает $t_i$ времени, и мы считаем, сколько осталось работать времени {{---}} $s$.
Можно связать время работы алгоритма $c$ и итоговую ошибку:
=== Мультиклассовая классификация ===
Данный алгоритм можно обобщить с бинарной классификации на мультиклассовую при помощи метода 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: Aunifying approach for margin classi�ers.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 матрице.
