64
правки
Изменения
→Пример кода на python для scikit-learn
==Описание==
'''Бустинг''' (англ. ''boosting'') — это композиционный [[Мета-обучение|мета-алгоритм обучения машин]]<sup>[на 18.01.19 не создан]</sup>, не использующий параллельное обучение базовых классификаторов как бэггинг (англ. ''bagging''). Бустинг также схож со стэкингом (англ. Его основной ''stacking''), но стэкинг комбинирует результаты различных алгоритмов, получая тем самым более точный ответ. Основной идеей бустинга является комбинирование слабых функций, которые строятся в ходе итеративного процесса, где на каждом шаге новая модель обучается с использованием данных об ошибках предыдущих. В отличие от слабого алгоритма, сильный обучающий алгоритм является классификатором, хорошо [[Корреляция случайных величин|коррелирующим]] с верной классификацией. Одним из недостатков бустинга является то, что он может приводить к построению громоздких композиций, состоящих из сотен алгоритмов. Такие композиции исключают возможность содержательной интерпретации, требуют больших объёмов памяти для хранения базовых алгоритмов и существенных затрат времени на вычисление классификаций.
==Алгоритмы бустинга==
Большинство алгоритмов бустинга состоит из итеративного обучения слабых классификаторов с целью сборки их в сильный классификатор. Когда они добавляются, им обычно приписываются некоторым образом веса, которые, обычно, связаны с [[Общие понятия|точностью обучения]]<sup>[на 18.01.19 не создан]</sup>. После того, как слабый классификатор добавлен, веса пересчитываются, что известно как '''«пересчёт весовых коэффициентов»'''. Неверно классифицированные входные данные получают больший вес, а правильно классифицированные экземпляры теряют вес. Тем самым последующее слабое обучение фокусируется больше на примерах, где предыдущие слабые обучения дали ошибочную классификацию.
Алгоритмы бустинга могут основываться на выпуклых или невыпуклых алгоритмах оптимизации. Выпуклые алгоритмы, такие как AdaBoost и LogitBoost<ref>[https://en.wikipedia.org/wiki/LogitBoost Wikipedia {{---}} LogitBoost]</ref>, могут «потерпеть крушение» из-за случайного шума, так как не могут обучить базовым и поддающимся научению комбинациям слабых гипотез. Алгоритмы бустинга, основанные на невыпуклой оптимизации, такие как BrownBoost<ref>[https://ru.wikipedia.org/wiki/BrownBoost Википедия {{---}} BrownBoost]</ref>, могут быть обучены из данных с шумами и лежащий в основе классификатор Лонг–Серведио<ref>[http://phillong.info/publications/LS10_potential.pdf Philip M. Long, Rocco A. Servedio {{---}} Random Classification Noise Defeats All Convex Potential Boosters]</ref> для набора данных может быть обучен.
==Классификация признаков в компьютерном зренииПрикладное использование алгоритмов бустинга=====Задача классификации объектов===
Если даны изображения, содержащие различные известные в мире объекты, классификатор может быть обучен на основе них для автоматической классификации объектов в будущих неизвестных изображениях. Простые классификаторы, построенные на основе некоторых признаков изображения объекта, обычно оказываются малоэффективными в классификации. Использование методов бустинга для классификации объектов — это путь объединения слабых классификаторов специальным образом для улучшения общей возможности классификации.
Классификация признаков является типичной задачей компьютерного зрения, где определяется, содержит ли изображение некоторую категорию объектов или нет. Идея тесно связана с распознаванием, идентификацией и обнаружением. Классификация по обнаружению объекта обычно содержит выделение [[Общие понятия|признаков]]<sup>[на 18.01.19 не создан]</sup>, обучение классификатора и применение классификатора к новым данным. Есть много способов представления категории объектов, например по анализу формы, с помощью модели '''«мешок слов»''', с помощью локальных описателей, таких как '''SIFT'''<ref>[https://en.wikipedia.org/wiki/Scale-invariant_feature_transform Wikipedia {{---}} Scale-invariant feature transform]</ref>, и так далее. Примерами классификаторов с учителем служат наивные [[Байесовская классификация|байесовские классификаторы]]<sup>[на 18.01.19 не создан]</sup>, [[Метод опорных векторов (SVM)|методы опорных векторов]]<sup>[на 18.01.19 не создан]</sup>, смесь гауссиан и [[Нейронные сети, перцептрон|нейронные сети]]. Однако исследования показали, что категории объектов и их положение в изображениях могут быть обнаружены также с помощью обучения без учителя.
==AdaBoost==
AdaBoost вызывает слабые классификаторы в цикле <tex>t = 1,...,T</tex>. После каждого вызова обновляется распределение весов <tex>D_t</tex>, которые отвечают важности каждого из объектов обучающего множества для классификации. На каждой итерации веса каждого неверно классифицированного объекта возрастают, таким образом новый комитет классификаторов «фокусирует своё внимание» на этих объектах.
===Достоинства и недостатки===
'''Достоинства:'''
# Простота реализации
# Хорошая обобщающая способность. В реальных задачах удаётся строить композиции, превосходящие по качеству базовые алгоритмы. Обобщающая способность может улучшаться по мере увеличения числа базовых алгоритмов.
# Время построения композиции практически полностью определяется временем обучения базовых алгоритмов.
# Возможность идентифицировать выбросы. Это наиболее «трудные» объекты $x_i$, для которых в процессе наращивания композиции веса $w_i$ принимают наибольшие значения.
'''Недостатки:'''
# Склонен к переобучению при наличии значительного уровня шума в данных.
# Требует достаточно длинных обучающих выборок. Другие методы линейной коррекции, в частности, бэггинг, способны строить алгоритмы сопоставимого качества по меньшим выборкам данных.
===Алгоритм для задачи построения двоичного классификатора===
\sum\limits_{i=1}^{m} D_t(i) [y_i\neq h_j(x_i)]</tex>
2. Если величина <tex>\epsilon_t \geqslant 0.5</tex>, то останавливаемся.
3. Выбираем <tex>\alpha_t \in \mathbf{R}</tex>, обычно <tex>\alpha_t = \frac{1}{2}\mathcal{ln}\frac{1-\epsilon_t}{\epsilon_t}</tex>, где <tex>\epsilon_t</tex> взвешенная ошибка классификатора
<tex>h_t</tex>
4. Обновляем: <tex>D_{t+1}(i) = \frac{D_t(i)\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_t</tex> для распределения <tex>D_t</tex>, объекты <tex>x_i</tex>, которые классификатор <tex>h_t</tex> идентифицирует корректно, имеют веса меньшие, чем те, которые идентифицируются некорректно. Следовательно, когда алгоритм тестирует классификаторы на распределении <tex>D_{t+1}</tex>, он будет выбирать классификатор, который лучше идентифицирует объекты неверно распознаваемые предыдущим классификатором.
===Построение линейной комбинации классификаторов===
Пусть <tex>N(b,U^{l})</tex> {{---}} суммарный вес ошибочных классификаций, где $b$ {{---}} алгоритм классификации, <tex>U^l = (u_1,...,u_l)</tex> {{---}} нормированный вектор весов объектов обучающей выборки.
Дано: <tex>X^l, Y^l</tex> {{---}} обучающая выборка, $T$ {{---}} максимальное число базовых алгоритмов
1. инициализация весов объектов: <tex>w_i = 1/l,\ i = 1,...,l;</tex>
2. '''для всех''' <tex>t = 1,...,T</tex>, '''пока''' не выполнен критерий останова:
1. <tex>b_t = \arg \min_{b} N(b; W^l)</tex>;
2. <tex>\alpha_t = \frac{1}{2} \ln\frac{1 - N(b_t;W^l)}{N(b_t;W^l)}</tex>;
3. пересчет весов объектов: <tex>w_i = w_i\exp{-\alpha_t y_i b_t(x_i)},\ i = 1,...,l</tex>;
4. нормировка весов объектов: <tex>w_0 = \sum\limits_{j=1}^{l} w_j; w_i = \frac{w_i}{w_0},\ i = 1,...,l</tex>;
===Пример кода на python для scikit-learn===
Классификатор sklearn.ensemble.'''AdaBoostClassifier''' имеет 5 параметров: '''base_estimator''', '''n_estimators''', '''learning_rate''', '''algorithm''', '''random_state'''.
Наиболее важными являются : # '''base_estimator''', {{---}} базовый алгоритм. По умолчанию используется DecisionTreeClassifier(max_depth=1)# '''n_estimators''' и {{---}} максимальное количество оценок, после которого бустинг прекращается. Если произойдет полное совпадение, то закончится раньше.# '''learning_rate'''{{---}} вклад каждой модели в весовые коэффициенты и значение по умолчанию равно $1$. Снижение этого параметра будет означать, что весовые коэффициенты буду увеличиваться или уменьшаться в небольшой степени, вынуждая модель дольше обучаться (но иногда повышается производительность).
'''from''' sklearn.ensemble '''import''' AdaBoostClassifier
Accuracy: 0.9555555555555556
===Пример на языке Scala===
SBT зависимость:
