Изменения

'''Бустинг''' (англ. ''boosting'') — это композиционный {{---}} [[Мета-обучение|мета-алгоритм машинного обучения машин]]^{[на 18.01.19 не создан]}, не использующий параллельное обучение базовых классификаторов как бэггинг (англ. ''bagging''). Бустинг также схож со стэкингом (англ. ''stacking''), но стэкинг комбинирует результаты различных алгоритмов, получая тем самым более точный ответ. Основной идеей бустинга является комбинирование слабых функций, которые строятся в ходе итеративного процесса, где на каждом шаге новая модель обучается с использованием данных об ошибках предыдущих. В отличие от слабого алгоритма, сильный Сильный обучающий алгоритм является классификатором, хорошо [[Корреляция случайных величин|коррелирующим]] с верной классификацией, в отличие от слабого. Наравне с бустингом в мета-обучении также рассматривают такие понятия, как [[Виды ансамблей|бэггинг]] (англ. ''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<sup/tex>[на 18.01.19 не создан], где <tex>R</suptex>{{---}} пространство оценок,<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>,

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

Алгоритмы Основное расхождение между многими алгоритмами бустинга могут основываться на выпуклых или невыпуклых алгоритмах оптимизации. Выпуклые алгоритмы, такие как AdaBoost и LogitBoost<ref>заключается в методах определения весовых коэффициентов точек [[https://en.wikipedia.org/wiki/LogitBoost Wikipedia {{---}} LogitBoostОбщие понятия|тренировочных данных]]</ref>, могут «потерпеть крушение» из-за случайного шума, так как не могут обучить базовым и поддающимся научению комбинациям слабых гипотез. Алгоритмы бустингаПервым алгоритмом, основанные на невыпуклой оптимизации, такие как BrownBoostкоторый смог адаптироваться к слабому обучению был '''AdaBoost'''<ref>[httpshttp://rurob.wikipediaschapire.orgnet/wikipapers/BrownBoost Википедия {{explaining---}} BrownBoost]</ref>, могут быть обучены из данных с шумами и лежащий в основе классификатор Лонг–Серведио<ref>[http://phillong.info/publications/LS10_potentialadaboost.pdf Philip M. Long, Rocco A. Servedio Explaining AdaBoost {{---}} Random Classification Noise Defeats All Convex Potential BoostersRobert E. Schapire]</ref> для набора данных может быть обучен(сокр. ''Adaptive Boosting''), предложенный Шапире и Фройндом.

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

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

Распознавание категорий объектов в изображениях Классификация признаков является сложной типичной задачей в компьютерном зрениикомпьютерного зрения, где определяется, содержит ли изображение некоторую категорию объектов или нет. Идея тесно связана с распознаванием, особенно если число категорий великоидентификацией и обнаружением. Это является следствием высокой внутренней изменчивости классов Классификация по обнаружению объекта обычно содержит выделение [[Общие понятия|признаков]], обучение классификатора и необходимости обобщения различных понятий внутри классаприменение классификатора к новым данным. Объекты в одной Есть много способов представления категории могут выглядеть совершенно различнымиобъектов, например по анализу формы, с помощью модели '''«мешок слов»''', с помощью локальных описателей, таких как '''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$. Снижение этого параметра будет означать, что весовые коэффициенты буду увеличиваться или уменьшаться в небольшой степени, вынуждая модель дольше обучаться (но иногда повышается производительность).

libraryDependencies '''+= ''' "com.github.haifengl" '''%% ''' "smile-scala" '''% ''' "1.5.2"

'''import '''smile.classification._ '''import '''smile.data._ '''import '''smile.plot._ '''import '''smile.read '''import '''smile.validation.FMeasure

'''val '''iris: AttributeDataset = read.table("iris.csv", delimiter = ",", response = Some(('''new '''NumericAttribute("class"), 2))) '''val '''x: Array[Array['''Double''']] = iris.x() '''val '''y: Array['''Int'''] = iris.y().map(_.toInt) '''val '''ada: AdaBoost = adaboost(x, y, ntrees = 500, maxNodes = 2) '''val '''predictions: Array['''Int'''] = x.map(ada.predict) '''val '''f1Score = '''new '''FMeasure().measure(predictions, y)

*[[Метод опорных векторов (SVM)|Метод опорных векторов]]^{[на 28.01.19 не создан]}*[[Байесовская классификация|Байесовская классификация]]^{[на 28.01.19 не создан]}