11
правок
Изменения
Новая страница: « Бустинг {{---}} это композиция алгоритмов, где на каждой итерации алгоритм…»
[[Бустинг, AdaBoost | Бустинг]] {{---}} это композиция алгоритмов, где на каждой итерации алгоритм пытается исправить все ошибки композиции предыдущих алгоритмов.
== LogitBoost ==
== BrownBoost ==
=== Идея алгоритма ===
Расмотренные ранее AdaBoost и 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>
Основная идея BrownBoost {{---}} на каждой итерации у найденного слабого классификатора есть вес <tex> \alpha_i </tex> и количество прошедшего в течение итерации времени <tex> t_i </tex> и эти величины напрямую связаны между собой. Они задаются системой нелинейных уравнений вида:
<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
=== Алгоритм ===
'''function''' BrownBoost($T$, $c$):
'''do:'''
<tex>W_i(x, y) = e^{-(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>\alpha_i, t_i \leftarrow</tex> Решение системы уравнений [1]
<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>
'''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>
== LogitBoost ==
== BrownBoost ==
=== Идея алгоритма ===
Расмотренные ранее AdaBoost и 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>
Основная идея BrownBoost {{---}} на каждой итерации у найденного слабого классификатора есть вес <tex> \alpha_i </tex> и количество прошедшего в течение итерации времени <tex> t_i </tex> и эти величины напрямую связаны между собой. Они задаются системой нелинейных уравнений вида:
<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
=== Алгоритм ===
'''function''' BrownBoost($T$, $c$):
'''do:'''
<tex>W_i(x, y) = e^{-(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>\alpha_i, t_i \leftarrow</tex> Решение системы уравнений [1]
<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>
'''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>
