Изменения

'''Бустинг''' (англ. ''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'«мешок слов»''', с помощью локальных описателей, таких как '''SIFT''', и так далее) или 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))