64
правки
Изменения
→AdaBoost
AdaBoost вызывает слабые классификаторы в цикле <tex>t = 1,...,T</tex>. После каждого вызова обновляется распределение весов <tex>D_t</tex>, которые отвечают важности каждого из объектов обучающего множества для классификации. На каждой итерации веса каждого неверно классифицированного объекта возрастают, таким образом новый комитет классификаторов «фокусирует своё внимание» на этих объектах.
===Пример кода на python для scikit-learn===
'''val '''f1Score = '''new '''FMeasure().measure(predictions, y)
plot(x, y, ada)
===Пример работы===
Рассмотрим набор данных, которые пометим как $-$ и $+$.
[[Файл:Adaboost1.jpg|600px|thumb|center|Результат после первой итерации]]
Для всех ошибочно классифицированных объектов увеличим веса, а для верно классифицированных уменьшим
[[Файл:Adaboost2.jpg|1000px|thumb|center|Результат после пересчета весов и второй итерации]]
Рассмотрим результат после $2$-х итераций:
[[Файл:Adaboost_result12.jpg|1000px|thumb|center|Итоговый результат после $2$-х итераций]]
Как видно из последнего изображения, все, что находиться в "цветной" зоне, мы можем однозначно классифицировать, но тогда у нас появляются ошибки и "белые" зоны, которые мы не можем однозначно классифицировать. Рассмотрим алгоритм после $30$-ти итераций:
[[Файл:Adaboost_resultfinal.jpg|300px|thumb|center|Результат работы алгоритма после $30$-ти итераций]]
Теперь у нас все объекты классифицируются верно и число ошибок на выборке равно нулю.
===Достоинства и недостатки===
'''Достоинства:'''
# Простота реализации
# Хорошая обобщающая способность. В реальных задачах удаётся строить композиции, превосходящие по качеству базовые алгоритмы. Обобщающая способность может улучшаться по мере увеличения числа базовых алгоритмов.
# Время построения композиции практически полностью определяется временем обучения базовых алгоритмов.
# Возможность идентифицировать выбросы. Это наиболее «трудные» объекты $x_i$, для которых в процессе наращивания композиции веса $w_i$ принимают наибольшие значения.
'''Недостатки:'''
# Склонен к переобучению при наличии значительного уровня шума в данных.
# Требует достаточно длинных обучающих выборок. Другие методы линейной коррекции, в частности, бэггинг, способны строить алгоритмы сопоставимого качества по меньшим выборкам данных.
===Алгоритм для задачи построения двоичного классификатора===
Пакет AdaBoost может быть использован для распознавания лиц как пример двоичной классификации. Две категории — это лица и фон. Общий алгоритм выглядит следующим образом:
Дано: <tex>(x_1,y_1),...,(x_m,y_m)</tex>, где <tex>x_i \in X, y_i \in Y = \{-1,+1\}</tex>
Инициализируем: <tex>D_1(i) = \frac{1}{m}</tex>, для <tex>i=1,...,m</tex>.
'''Для каждого''' <tex>t=1,...,T</tex> '''пока''' не выполнен критерий останова $(t = T)$:
1. Находим классификатор <tex>h_t:X\to \{-1,+1\}</tex> который минимизирует взвешенную ошибку классификации: <tex>h_t = \arg \min\limits_{h_j \in \mathcal{H}} \epsilon_j</tex>, где <tex>\epsilon_j =
\sum\limits_{i=1}^{m} D_t(i) [y_i\neq h_j(x_i)]</tex>
2. Выбираем <tex>\alpha_t = \frac{1}{2}\ln\frac{1-\epsilon_t}{\epsilon_t}</tex>, где <tex>\epsilon_t</tex> взвешенная ошибка классификатора <tex>h_t</tex>
3. Для каждого <tex>i=1,...,m</tex> обновляем:
<tex>D_{t+1}(i) = \dfrac{D_t(i)\textrm{exp}(-\alpha_t y_i h_t(x_i))}{Z_t}</tex>, где <tex>Z_t</tex> является нормализующим параметром (выбранным так, чтобы <tex>D_{t+1}</tex> являлось распределением вероятностей, то есть <tex>\sum\limits_{i-1}^{m} D_{t+1}(i) = 1</tex>).
Строим результирующий классификатор:
<tex>H(x) = \textrm{sign}(\sum\limits_{t=1}^{T} \alpha_t h_t(x))</tex>
Выражение для обновления распределения <tex>D_t</tex> должно быть сконструировано таким образом, чтобы выполнялось условие:
<tex>\exp^{\alpha_t y_i h_t(x_i)} \begin{cases}<1,\ y(i) = h_t(x_i) \\ >1,\ y(i) \neq h_t(x_i)\end{cases}</tex>
Таким образом, после выбора оптимального классификатора <tex>h_t</tex> для распределения <tex>D_t</tex>, объекты <tex>x_i</tex>, которые классификатор <tex>h_t</tex> идентифицирует корректно, имеют веса меньшие, чем те, которые идентифицируются некорректно. Следовательно, когда алгоритм тестирует классификаторы на распределении <tex>D_{t+1}</tex>, он будет выбирать классификатор, который лучше идентифицирует объекты неверно распознаваемые предыдущим классификатором.
== См. также ==
