Изменения

'''Бустинг''' (англ. ''boosting'') — это композиционный {{---}} [[Мета-обучение|мета-алгоритм машинного обучения машин. Применяется, главным образом, для уменьшения смещения, а также [[Дисперсия случайной величины|дисперсии]] в обучении с учителем. Также семейство алгоритмов обучения машинОсновной идеей бустинга является комбинирование слабых функций, преобразующих слабые обучающие алгоритмы к сильным. Слабый обучающий алгоритм определяется как классификаторкоторые строятся в ходе итеративного процесса, который слабо коррелирует где на каждом шаге новая модель обучается с правильной классификацией (может пометить примеры лучше, чем случайное угадывание)использованием данных об ошибках предыдущих. В отличие от слабого алгоритма, сильный Сильный обучающий алгоритм является классификатором, хорошо [[Корреляция случайных величин|коррелирующим]] с верной классификацией, в отличие от слабого. Наравне с бустингом в мета-обучении также рассматривают такие понятия, как [[Виды ансамблей|бэггинг]] (англ. ''bagging'') и стэкинг<ref>[https://dyakonov.org/2017/03/10/c%D1%82%D0%B5%D0%BA%D0%B8%D0%BD%D0%B3-stacking-%D0%B8-%D0%B1%D0%BB%D0%B5%D0%BD%D0%B4%D0%B8%D0%BD%D0%B3-blending/#more-4558 Стекинг {{---}} Дьяконов Александр]</ref> (англ. ''stacking''). Бэггинг, в отличии от бустинга, использует параллельное обучение базовых классификаторов. Стэкинг же комбинирует результаты различных алгоритмов, получая тем самым более точный ответ.  Одним из недостатков бустинга является то, что он может приводить к построению громоздких композиций, состоящих из сотен алгоритмов. Такие композиции исключают возможность содержательной интерпретации, требуют больших объёмов памяти для хранения базовых алгоритмов и существенных затрат времени на вычисление классификаций.

Большинство {{Определение|definition='''Композицией''' $T$ '''алгоритмов бустинга состоит из итеративного обучения слабых классификаторов с целью сборки их в сильный классификатор''' <tex>a_t(x) = C(b_t(x)),\ t = 1,... Когда они добавляются, им обычно приписываются некоторым образом весаT</tex> называется [[Суперпозиции|суперпозиция]] алгоритмических операторов <tex>b_t\ :\ X\to R</tex>, которыекорректирующей операции <tex>F\ :\ R^T\to R</tex> и решающего правила <tex> C\ :\ R\to Y</tex>, обычногде <tex>R</tex> {{---}} пространство оценок,<br><center><tex>a(x) = C(F(b_1(x), связаны с точностью обучения. После того.., как слабый классификатор добавленb_T(x))), веса пересчитываютсяx \in X</tex></center><br>, что известно как ''Алгоритмы $a_t$ называют '«пересчёт весовых коэффициентов»'базовыми алгоритмами''. Неверно классифицированные входные данные получают больший вес}}Бустинг представляет собой композицию алгоритмов, а правильно классифицированные экземпляры теряют весв которых ошибки отдельных алгоритмов взаимно компенсируются. Тем самым последующее слабое обучение фокусируется больше Например, в задаче классификации на примерахдва класса $Y = {-1, +1}$ в качестве пространства оценок принимают $R = \mathbb{R}$ и <tex>C(b(x)) = \textrm{sign}(b(x))</tex>. Тогда базовые алгоритмы возвращают ответы $−1, 0, где предыдущие слабые обучения дали ошибочную классификацию+1$. Ответ $b_t(x) = 0$ означает, что базовый алгоритм $b_t$ отказывается от классификации объекта $x$, и ответ $b_t(x)$ не учитывается в композиции. Получаем искомую композицию:<center><tex>a(x) = C(F(b_1(x),...,b_T(x))) = \textrm{sign}\left(\sum\limits_{t=1}^T \alpha_t b_t(x)\right),\ x\in X</tex></center>,

Исходные алгоритмыБольшая часть алгоритмов бустинга основывается на итеративном обучении слабых классификаторов с дальнейшей сборкой их в сильный классификатор. Когда они добавляются, им обычно приписываются веса, обычно связанные с [[Общие понятия|точностью обучения]]. После добавления слабого классификатора, предложенные Робертом Шапире веса пересчитываются ('''рекурсивное доминирование«пересчёт весовых коэффициентов»'''). Неверно классифицированные входные данные получают больший вес, англа правильно классифицированные экземпляры теряют вес. ''recursive majority gate formulation'') и Йоавом Фройндом (бустинг по доминированию)Таким образом, дальнейшее слабое обучение фокусируется на примерах, не были адаптивными и не могли дать полного преимущества слабых обучений. Шапире и Фройнд затем разработали '''AdaBoost''' (сокр. ''Adaptive Boosting'') {{---}} адаптивный алгоритм бустингагде предыдущие слабые обучения дали ошибочную классификацию.

Только алгоритмы, для которых можно доказать, что они являются Основное расхождение между многими алгоритмами бустинга заключается в формулировке приближённо правильного обучения, могут быть точно названы алгоритмами бустингаметодах определения весовых коэффициентов точек [[Общие понятия|тренировочных данных]] и гипотез. Другие алгоритмыПервым алгоритмом, близкие по духу алгоритмам бустинга, иногда называются который смог адаптироваться к слабому обучению был '''«алгоритмами максимального использования»AdaBoost''' <ref>[http://rob.schapire.net/papers/explaining-adaboost.pdf Explaining AdaBoost {{---}} Robert E. Schapire]</ref> (англсокр. ''leveraging algorythmsAdaptive Boosting''), хотя они иногда также неверно называются алгоритмами бустингапредложенный Шапире и Фройндом.

Основное расхождение между многими алгоритмами Алгоритмы бустинга заключается в методах определения весовых коэффициентов точек тренировочных данных и гипотезмогут использовать выпуклую или невыпуклую функцию потерь. Алгоритм '''Алгоритмы с выпуклой функцией, такие как AdaBoost''' очень популярен и исторически наиболее знаменателенLogitBoost<ref>[https://en.wikipedia.org/wiki/LogitBoost Wikipedia {{---}} LogitBoost]</ref>, могут некорректно классифицировать из-за случайного шума, так как он был первым алгоритмомне могут обучить базовым и поддающимся научению комбинациям слабых гипотез. Алгоритмы бустинга, основанные на невыпуклой функции потерь, такие как BrownBoost<ref>[https://ru.wikipedia.org/wiki/BrownBoost Википедия {{---}} BrownBoost]</ref>, позволяют избежать переобучения на данных с большим количеством "шума", который смог адаптироваться к слабому обучениюоткидывая зашумленные элементы.

Алгоритмы ==Прикладное использование алгоритмов бустинга могут основываться на выпуклых или невыпуклых алгоритмах оптимизации. Выпуклые алгоритмы, такие как AdaBoost и LogitBoost, могут «потерпеть крушение» из-за случайного шума, так как не могут обучить базовым и поддающимся научению комбинациям слабых гипотез. Алгоритмы бустинга, основанные на невыпуклой оптимизации, такие как BrownBoost, могут быть обучены из данных с шумами и лежащий в основе классификатор Лонг–Серведио для набора данных может быть обучен.====Классификация признаков в компьютерном зрении=Задача классификации объектов===Если даны изображения, содержащие различные известные в мире объекты, классификатор может быть обучен на основе них для автоматической классификации объектов в будущих неизвестных изображениях. Простые классификаторы, построенные на основе некоторых признаков изображения объекта, обычно оказываются малоэффективными в классификации. Использование методов бустинга для классификации объектов — это {{---}} путь объединения слабых классификаторов специальным образом для улучшения общей возможности классификации.

===Задача классификации объектов===Классификация признаков является типичной задачей компьютерного зрения, где определяется, содержит ли изображение некоторую категорию объектов или нет. Идея тесно связана с распознаванием, идентификацией и обнаружением. Классификация по обнаружению объекта обычно содержит выделение [[Общие понятия|признаков]], обучение классификатора и применение классификатора к новым данным. Есть много способов представления категории объектов, например по анализу формы, с помощью модели '''«мешок слов»''', с помощью локальных описателей, таких как '''SIFT'''<ref>[https://en.wikipedia.org/wiki/Scale-invariant_feature_transform Wikipedia {{---}} Scale-invariant feature transform]</ref>, и так далее. Примерами классификаторов с учителем служат наивные [[Байесовская классификация|байесовские классификаторы]]^{[на 28.01.19 не создан]}, [[Метод опорных векторов (SVM)|методы опорных векторов]]^{[на 28.01.19 не создан]}, смесь гауссиан и [[Нейронные сети, перцептрон|нейронные сети]]. Однако исследования показали, что категории объектов и их положение в изображениях могут быть обнаружены также с помощью обучения без учителя.

Распознавание категорий объектов ===Задача ранжирования выдачи поисковых систем===Благодаря AdaBoost в изображениях является сложной задачей в компьютерном зрении, особенно если число категорий великомире появился [[CatBoost|градиентный бустинг]] (англ. Это является следствием высокой внутренней изменчивости классов и необходимости обобщения различных понятий внутри класса. Объекты в одной категории могут выглядеть совершенно различными''gradient boosting'') или GBM. Даже один и тот же предмет может выглядеть непохожим Задачу ранжирования выдачи поисковых запросов рассмотрели с различных точек обзора, при другом мастшабе или освещении. Шум заднего плана и частичные наложения также добавляют сложности в распознавание. Люди способны распознавать тысячи типов объектовточки зрения функции потерь, которая штрафует за ошибки в то время как большинство существующих систем распознавания объектов тренируются для распознавания лишь нескольких, например человеческих лиц, автомобилей, простых объектов и т.д.. Увеличению числа категорий и возможности добавления новых категорий достигаетсяпорядке выдачи, поэтому было удобно внедрить GBM в частности, с помощью совместного использования признаков и бустингаранжирование.

AdaBoost вызывает слабые классификаторы <tex>h_i^t</tex> в цикле <tex>t = 1,...,T</tex>. После каждого вызова обновляется распределение весов <tex>D_t</tex>, которые отвечают важности каждого из объектов обучающего множества для классификации. На каждой итерации веса каждого неверно классифицированного объекта возрастают, таким образом новый комитет классификаторов «фокусирует своё внимание» на этих объектах.

===Алгоритм для задачи построения двоичного классификатораОписание алгоритма===Пакет AdaBoost может быть использован для распознавания лиц как пример двоичной классификации. Две категории — это лица и фон. Общий алгоритм выглядит следующим образом:

Дано: <texfont color=green>(x_1,y_1),...,(x_m,y_m)</tex>, где /<tex>x_i \in X, y_i \in Y = \{-1,+1\}, size(x) = size(y) = m</tex></font> '''function''' AdaBoost($X$, $Y$, $m$): <font color=green>//Инициализируем </font> '''for''' i = 1..m '''do''': <tex>D_1(i) D_i^1 = \frac{1}{m},i=1,...,m</tex>. Для каждого <tex> '''end''' '''for''' '''for''' t=1,...,T</tex> пока не выполнен критерий останова'''do''': 1. Находим классификатор <tex>h_t:X\to \{-1,+1\}</tex> который минимизирует взвешенную ошибку классификации: <tex>h_t = \arg \min_min\limits_{h_j \in \mathcal{H}} \epsilon_j</tex>, где <tex>\epsilon_j = \sum\limits_{i=1}^{m} D_t(i) [y_iD_i^t〚y_i\neq h_j(x_i)]〛</tex> 2. Если величина <texfont color=green>//$\epsilon_t \geqslant 0.5</tex>epsilon$ {{---}} Взвешенная ошибка классификации, то останавливаемся. 3. Выбираем классификатор <tex>h_t:X\alpha_t to \in {-1,+1\mathbf{R}</tex>, обычно </font> <tex>\alpha_t = \frac{1}{2}\mathcal{ln}\frac{1-\epsilon_t}{\epsilon_t}</tex>, где '''for''' i = 1..m '''do''': <texfont color=green>\epsilon_t</tex> взвешенная ошибка классификатора /<tex>h_tZ_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_D^{t+1}</tex> являлось распределением вероятностей, то есть <tex>\sum\limits_{i-1}^{m} D_D_i^{t+1}(i) = 1</tex>, для <tex>t=1,...,T</tex></font> <tex>D_i^{t+1} = \dfrac{D_i^t \textrm{exp}(-\alpha_t y_i h_t(x_i)).}{Z_t}</tex> '''end''' '''for''' Строим результирующий классификатор: '''end''' '''for''' <tex>H(x) = \textrm{sign}\left(\sum\limits_{t=1}^{T} \alpha_t h_t(x)\right)</tex> <font color=green>//$H(x)$ {{---}} результирующий классификатор</font> '''return''' $H$Выражение для обновления распредления распределения <tex>D_tD^t</tex> должно быть сконструировано таким образом, чтобы выполнялось условие: <center><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></center>,

Таким образом, после выбора оптимального классификатора <tex>h_t</tex> для распределения <tex>D_tD^t</tex>, объекты <tex>x_i</tex>, которые классификатор <tex>h_t</tex> идентифицирует корректно, имеют веса меньшие, чем те, которые идентифицируются некорректно. Следовательно, когда алгоритм тестирует классификаторы на распределении <tex>D_D^{t+1}</tex>, он будет выбирать классификатор, который лучше идентифицирует объекты неверно распознаваемые предыдущим классификатором. ===Пример работы===Рассмотрим набор данных, которые пометим как $-$ и $+$.[[Файл: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$ принимают наибольшие значения.'''Недостатки:'''# Склонен к переобучению при наличии значительного уровня шума в данных;# Требует достаточно длинных обучающих выборок. Другие методы линейной коррекции, в частности, бэггинг, способны строить алгоритмы сопоставимого качества по меньшим выборкам данных.

Классификатор sklearn.ensemble.'''AdaBoostClassifier''' <ref>[https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.AdaBoostClassifier.html Документация AdaBoostClassifier]</ref> имеет 5 параметров: '''base_estimator''', '''n_estimators''', '''learning_rate''', '''algorithm''', '''random_state'''.Наиболее важными являются : # '''base_estimator''', {{---}} базовый алгоритм. По умолчанию используется DecisionTreeClassifier(max_depth=1);# '''n_estimators''' и {{---}} максимальное количество оценок, после которого бустинг прекращается. Если произойдет полное совпадение, то закончится раньше;# '''learning_rate'''{{---}} вклад каждой модели в весовые коэффициенты и значение по умолчанию равно $1$. Снижение этого параметра будет означать, что весовые коэффициенты буду увеличиваться или уменьшаться в небольшой степени, вынуждая модель дольше обучаться (но иногда повышается производительность).

'''print'''("Accuracy:",metrics.'''accuracy_score'''(y_test, y_pred))

'''print'''("Accuracy:",metrics.'''accuracy_score'''(y_test, y_pred))