Изменения

Перейти к: навигация, поиск

Бустинг, AdaBoost

7272 байта добавлено, 17:23, 8 апреля 2019
Нет описания правки
==Описание==
'''Бустинг''' (англ. ''boosting'') — это композиционный {{---}} [[Мета-обучение|мета-алгоритм машинного обучения машин]]<sup>[на 18.01.19 не создан]</sup>. Его основной Основной идеей бустинга является комбинирование слабых функций, которые строятся в ходе итеративного процесса, где на каждом шаге новая модель обучается с использованием данных об ошибках предыдущих. В отличие от слабого алгоритма, сильный Сильный обучающий алгоритм является классификатором, хорошо [[Корреляция случайных величин|коррелирующим]] с верной классификацией, в отличие от слабого. Наравне с бустингом в мета-обучении также рассматривают такие понятия, как [[Виды ансамблей|бэггинг]] (англ. ''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>,
Основное расхождение между многими алгоритмами Большая часть алгоритмов бустинга заключается основывается на итеративном обучении слабых классификаторов с дальнейшей сборкой их в методах определения весовых коэффициентов точек сильный классификатор. Когда они добавляются, им обычно приписываются веса, обычно связанные с [[Общие понятия|тренировочных данных]точностью обучения]<sup>[на 18.01.19 не создан]</sup> и гипотез. Первым алгоритмомПосле добавления слабого классификатора, который смог адаптироваться к слабому обучению был веса пересчитываются ('''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>, построенные позволяют избежать переобучения на основе некоторых признаков изображения объектаданных с большим количеством "шума", обычно оказываются малоэффективными в классификации. Использование методов бустинга для классификации объектов — это путь объединения слабых классификаторов специальным образом для улучшения общей возможности классификацииоткидывая зашумленные элементы.
==Прикладное использование алгоритмов бустинга==
===Задача классификации объектов===
Классификация признаков является типичной задачей компьютерного зренияЕсли даны изображения, где определяетсясодержащие различные известные в мире объекты, содержит ли изображение некоторую категорию классификатор может быть обучен на основе них для автоматической классификации объектов или нетв будущих неизвестных изображениях. Идея тесно связана с распознаваниемПростые классификаторы, идентификацией и обнаружением. Классификация по обнаружению построенные на основе некоторых признаков изображения объекта , обычно содержит выделение [[Общие понятия|признаков]]<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>, смесь гауссиан и [[Нейронные сети, перцептрон|нейронные сети]]. Однако исследования показали, что категории объектов и их положение в изображениях могут быть обнаружены также с помощью обучения без учителяспециальным образом для улучшения общей возможности классификации.
Распознавание категорий объектов в изображениях Классификация признаков является сложной типичной задачей в компьютерном зрениикомпьютерного зрения, где определяется, содержит ли изображение некоторую категорию объектов или нет. Идея тесно связана с распознаванием, особенно если число категорий великоидентификацией и обнаружением. Это является следствием высокой внутренней изменчивости классов Классификация по обнаружению объекта обычно содержит выделение [[Общие понятия|признаков]], обучение классификатора и необходимости обобщения различных понятий внутри классаприменение классификатора к новым данным. Объекты в одной Есть много способов представления категории могут выглядеть совершенно различнымиобъектов, например по анализу формы, с помощью модели '''«мешок слов»''', с помощью локальных описателей, таких как '''SIFT'''<ref>[https://en.wikipedia. Даже один org/wiki/Scale-invariant_feature_transform Wikipedia {{---}} Scale-invariant feature transform]</ref>, и тот же предмет может выглядеть непохожим так далее. Примерами классификаторов с различных точек обзораучителем служат наивные [[Байесовская классификация|байесовские классификаторы]]<sup>[на 28.01.19 не создан]</sup>, при другом мастшабе или освещении[[Метод опорных векторов (SVM)|методы опорных векторов]]<sup>[на 28. Шум заднего плана и частичные наложения также добавляют сложности в распознавание01. Люди способны распознавать тысячи типов объектов19 не создан]</sup>, в то время как большинство существующих систем распознавания объектов тренируются для распознавания лишь несколькихсмесь гауссиан и [[Нейронные сети, например человеческих лицперцептрон|нейронные сети]]. Однако исследования показали, автомобилей, простых что категории объектов и тих положение в изображениях могут быть обнаружены также с помощью обучения без учителя.д ===Задача ранжирования выдачи поисковых систем===Благодаря AdaBoost в мире появился [[CatBoost|градиентный бустинг]] (англ.''gradient boosting'') или GBM. Увеличению числа категорий и возможности добавления новых категорий достигаетсяЗадачу ранжирования выдачи поисковых запросов рассмотрели с точки зрения функции потерь, которая штрафует за ошибки в частностипорядке выдачи, с помощью совместного использования признаков и бустингапоэтому было удобно внедрить GBM в ранжирование.
==AdaBoost==
Алгоритм может использоваться в сочетании с несколькими алгоритмами классификации для улучшения их эффективности. Алгоритм усиливает классификаторы, объединяя их в «комитет». AdaBoost является адаптивным в том смысле, что каждый следующий комитет классификаторов строится по объектам, неверно классифицированным предыдущими комитетами. AdaBoost чувствителен к шуму в данных и выбросам. Однако он менее подвержен переобучению по сравнению с другими алгоритмами машинного обучения.
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$ принимают наибольшие значения.'''Недостатки:'''# Склонен к переобучению при наличии значительного уровня шума в данных;# Требует достаточно длинных обучающих выборок. Другие методы линейной коррекции, в частности, бэггинг, способны строить алгоритмы сопоставимого качества по меньшим выборкам данных.
===Пример кода на python для scikit-learn===
Классификатор 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$. Снижение этого параметра будет означать, что весовые коэффициенты буду увеличиваться или уменьшаться в небольшой степени, вынуждая модель дольше обучаться (но иногда повышается производительность).
'''from''' sklearn.ensemble '''import''' AdaBoostClassifier
Accuracy: 0.9555555555555556
 
===Пример на языке Scala===
SBT зависимость:
libraryDependencies '''+= ''' "com.github.haifengl" '''%% ''' "smile-scala" '''% ''' "1.5.2"
Пример классификации датасета и вычисления F1 меры<ref>[https://en.wikipedia.org/wiki/F1_score F1 мера]</ref> используя smile.classification.adaboost<ref>[https://haifengl.github.io/smile/classification.html#adaboost Smile, AdaBoost]</ref>:
'''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)
plot(x, y, ada)
 
===Пример на языке Java===
Пример классификации с применением <code>smile.classification.AdaBoost</code><ref>[https://haifengl.github.io/smile/api/java/smile/classification/AdaBoost.html/ Smile, AdaBoost]</ref>
 
<code>Maven</code> зависимость:
<dependency>
<groupId>com.github.haifengl</groupId>
<artifactId>smile-core</artifactId>
<version>1.5.2</version>
</dependency>
 
'''import''' smile.classification.AdaBoost;
'''import''' smile.data.parser.ArffParser;
'''import''' smile.validation.Accuracy;
'''import''' smile.validation.ClassificationMeasure;
'''import''' smile.validation.FMeasure;
'''import''' java.util.Arrays;
 
<font color="green">// load train and test datasets</font>
'''var''' arffParser = new ArffParser();
arffParser.setResponseIndex(0);
'''var''' train = arffParser.parse(this.getClass().getResourceAsStream("train.arff"));
'''var''' test = arffParser.parse(this.getClass().getResouceAsStream("test.arff"));
<font color="green">// create adaboost classifier</font>
'''var''' forest = new AdaBoost(train.attributes(), train.x(), train.labels(), 200, 4);
<font color="green">// measure accuracy and F1-measure on test dataset</font>
'''var''' measures = new ClassificationMeasure[]{new FMeasure(), new Accuracy()};
'''var''' results = forest.test(test.x(), test.labels(), measures);
System.out.println(Arrays.deepToString(results));
== См. также ==
*[[Метод опорных векторов (SVM)|Метод опорных векторов]]<sup>[на 28.01.19 не создан]</sup>*[[Байесовская классификация|Байесовская классификация]]<sup>[на 28.01.19 не создан]</sup>
*[[Мета-обучение|Мета-обучение]]
*[[Нейронные сети, перцептрон|Нейронные сети]]
== Источники информации ==
# [https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.AdaBoostClassifier.html#sklearn.ensemble.AdaBoostClassifier AdaBoostClassifier] {{---}} документация scikit-learn
# [http://www.machinelearning.ru/wiki/index.php?title=AdaBoost AdaBoost] {{---}} статья на machinelearning.ru
# [http://cmp.felk.cvut.cz/~sochmj1/adaboost_talk.pdf AdaBoost] {{---}} презентация по AdaBoost
# [https://ru.coursera.org/lecture/ml-classification/example-of-adaboost-in-action-um0cX Example of AdaBoost in action] {{---}} презентация на coursera.org# [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_(%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_%D0%9A.%D0%92.%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D1%86%D0%BE%D0%B2) Курс лекций по машинному обучению] {{---}} Воронцов К.В.
[[Категория: Автоматическое машинное обучение]]
[[Категория: Машинное обучение]]
[[Категория: Ансамбли]]
Анонимный участник

Навигация