Изменения

'''Бустинг''' (англ. ''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> называется [[Общие понятияСуперпозиции|точностью обучениясуперпозиция]]алгоритмических операторов <suptex>[на 18b_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),..01.19 не создан],b_T(x))), x \in X</tex></supcenter><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«пересчёт весовых коэффициентов»'''<ref>[http://rob).schapireНеверно классифицированные входные данные получают больший вес, а правильно классифицированные экземпляры теряют вес.net/papers/explaining-adaboost.pdf Explaining AdaBoost {{---}} Robert E. Schapire]</ref> (сокр. ''Adaptive Boosting'')Таким образом, дальнейшее слабое обучение фокусируется на примерах, предложенный Шапире и Фройндомгде предыдущие слабые обучения дали ошибочную классификацию.

Основное расхождение между многими алгоритмами бустинга заключается в методах определения весовых коэффициентов точек [[Общие понятия|тренировочных данных]] и гипотез. Первым алгоритмом, который смог адаптироваться к слабому обучению был '''AdaBoost'''<ref>[http://rob.schapire.net/papers/explaining-adaboost.pdf Explaining AdaBoost {{---}} Robert 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>, и так далее. Примерами классификаторов с учителем служат наивные [[Байесовская классификация|байесовские классификаторы]]^{[на 1828.01.19 не создан]}, [[Метод опорных векторов (SVM)|методы опорных векторов]]^{[на 1828.01.19 не создан]}, смесь гауссиан и [[Нейронные сети, перцептрон|нейронные сети]]. Однако исследования показали, что категории объектов и их положение в изображениях могут быть обнаружены также с помощью обучения без учителя.

AdaBoost вызывает слабые классификаторы <tex>h_i^t</tex> в цикле <tex>t = 1,...,T</tex>. После каждого вызова обновляется распределение весов <tex>D_t</tex>, которые отвечают важности каждого из объектов обучающего множества для классификации. На каждой итерации веса каждого неверно классифицированного объекта возрастают, таким образом новый комитет классификаторов «фокусирует своё внимание» на этих объектах. ===Описание алгоритма===  <font color=green>//<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_i^1 = \frac{1}{m}</tex> '''end''' '''for''' '''for''' t = 1..T '''do''': <tex>h_t = \arg \min\limits_{h_j \in \mathcal{H}} \epsilon_j = \sum\limits_{i=1}^{m} D_i^t〚y_i\neq h_j(x_i)〛</tex> <font color=green>//$\epsilon$ {{---}} Взвешенная ошибка классификации, классификатор <tex>h_t:X\to \{-1,+1\}</tex></font> <tex>\alpha_t = \frac{1}{2}\ln\frac{1-\epsilon_t}{\epsilon_t}</tex> '''for''' i = 1..m '''do''': <font color=green>//<tex>Z_t</tex> {{---}} нормализующий параметр, выбранный так, чтобы <tex>D^{t+1}</tex> являлось распределением вероятностей, то есть <tex>\sum\limits_{i-1}^{m} D_i^{t+1} = 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^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^t</tex>, объекты <tex>x_i</tex>, которые классификатор <tex>h_t</tex> идентифицирует корректно, имеют веса меньшие, чем те, которые идентифицируются некорректно. Следовательно, когда алгоритм тестирует классификаторы на распределении <tex>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$ принимают наибольшие значения.'''Недостатки:'''# Склонен к переобучению при наличии значительного уровня шума в данных;# Требует достаточно длинных обучающих выборок. Другие методы линейной коррекции, в частности, бэггинг, способны строить алгоритмы сопоставимого качества по меньшим выборкам данных.

# '''base_estimator''' {{---}} базовый алгоритм. По умолчанию используется DecisionTreeClassifier(max_depth=1);# '''n_estimators''' {{---}} максимальное количество оценок, после которого бустинг прекращается. Если произойдет полное совпадение, то закончится раньше.;

===Пример работына языке Java===Рассмотрим набор данных, которые пометим как $-$ и $+$Пример классификации с применением <code>smile.classification.[AdaBoost</code><ref>[Файлhttps:Adaboost1//haifengl.jpg|600px|thumb|center|Результат после первой итерации]]Для всех ошибочно классифицированных объектов увеличим веса, а для верно классифицированных уменьшим[[Файл:Adaboost2github.jpg|1000px|thumb|center|Результат после пересчета весов и второй итерации]]Рассмотрим результат после $2$-х итераций:[[Файл:Adaboost_result12io/smile/api/java/smile/classification/AdaBoost.jpg|1000px|thumb|center|Итоговый результат после $2$-х итераций]]Как видно из последнего изображения, все, что находиться в "цветной" зонеhtml/ Smile, мы можем однозначно классифицировать, но тогда у нас появляются ошибки и "белые" зоны, которые мы не можем однозначно классифицировать. Рассмотрим алгоритм после $30$-ти итераций:[[Файл:Adaboost_resultfinal.jpg|300px|thumb|center|Результат работы алгоритма после $30$-ти итерацийAdaBoost]]Теперь у нас все объекты классифицируются верно и число ошибок на выборке равно нулю.</ref>

===Достоинства и недостатки==='''Достоинства<code>Maven</code> зависимость:'''# Простота реализации# Хорошая обобщающая способность. В реальных задачах удаётся строить композиции, превосходящие по качеству базовые алгоритмы. Обобщающая способность может улучшаться по мере увеличения числа базовых алгоритмов.# Время построения композиции практически полностью определяется временем обучения базовых алгоритмов. <dependency># Возможность идентифицировать выбросы <groupId>com. Это наиболее «трудные» объекты $x_i$, для которых в процессе наращивания композиции веса $w_i$ принимают наибольшие значенияgithub.haifengl</groupId>'''Недостатки:'''# Склонен к переобучению при наличии значительного уровня шума в данных. <artifactId>smile-core</artifactId># Требует достаточно длинных обучающих выборок <version>1. Другие методы линейной коррекции, в частности, бэггинг, способны строить алгоритмы сопоставимого качества по меньшим выборкам данных5.2</version>  ===Алгоритм для задачи построения двоичного классификатора===Пакет AdaBoost может быть использован для распознавания лиц как пример двоичной классификации. Две категории — это лица и фон. Общий алгоритм выглядит следующим образом: </dependency>

Дано: <tex>(x_1,y_1), '''import''' smile.classification..,(x_m,y_m)</tex>, где <tex>x_i \in X, y_i \in Y = \{-1,+1\}</tex>AdaBoost; Инициализируем: <tex>D_1(i) = \frac{1}{m}</tex>, для <tex>i=1,. '''import''' smile.data.,m</tex>parser.ArffParser; '''Для каждогоimport''' <tex>t=1,smile.validation..,T</tex> Accuracy; '''покаimport''' не выполнен критерий останова $(t = T)$: 1smile. Находим классификатор <tex>h_t:X\to \{-1,+1\}</tex> который минимизирует взвешенную ошибку классификации: <tex>h_t = \arg \min\limits_{h_j \in \mathcal{H}} \epsilon_j</tex>, где <tex>\epsilon_j = \sum\limits_{i=1}^{m} D_t(i) [y_i\neq h_j(x_i)]</tex> 2validation. Выбираем <tex>\alpha_t = \frac{1}{2}\ln\frac{1-\epsilon_t}{\epsilon_t}</tex>, где <tex>\epsilon_t</tex> взвешенная ошибка классификатора <tex>h_t</tex>ClassificationMeasure; 3. Для каждого <tex>i=1, '''import''' smile.validation.FMeasure; '''import''' java.,m</tex> обновляем: <tex>D_{t+1}(i) = \dfrac{D_t(i)\textrm{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>)util. Строим результирующий классификатор: <tex>H(x) = \textrm{sign}(\sum\limits_{t=1}^{T} \alpha_t h_t(x))</tex> Выражение для обновления распределения <tex>D_t</tex> должно быть сконструировано таким образом, чтобы выполнялось условие: <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>Arrays;

Таким образом, после выбора оптимального классификатора <texfont color="green">h_t// load train and test datasets</texfont> для распределения '''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")); <texfont color="green">D_t</tex>, объекты <tex>x_i</tex>, которые классификатор <tex>h_tcreate adaboost classifier</texfont> идентифицирует корректно '''var''' forest = new AdaBoost(train.attributes(), имеют веса меньшиеtrain.x(), чем теtrain.labels(), которые идентифицируются некорректно. Следовательно200, когда алгоритм тестирует классификаторы на распределении 4); <texfont color="green">D_{t+1}// measure accuracy and F1-measure on test dataset</texfont> '''var''' measures = new ClassificationMeasure[]{new FMeasure(), он будет выбирать классификаторnew Accuracy()}; '''var''' results = forest.test(test.x(), который лучше идентифицирует объекты неверно распознаваемые предыдущим классификаторомtest.labels(), measures); System.out.println(Arrays.deepToString(results));

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