Бустинг, AdaBoost — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример кода на python для scikit-learn)
(не показано 90 промежуточных версий 13 участников)
Строка 1: Строка 1:
 
==Описание==
 
==Описание==
'''Бустинг''' (англ. ''boosting'') — это композиционный мета-алгоритм обучения машин. Применяется, главным образом, для уменьшения смещения, а также дисперсии в обучении с учителем. Также семейство алгоритмов обучения машин, преобразующих слабые обучающие алгоритмы к сильным. Слабый обучающий алгоритм определяется как классификатор, который слабо коррелирует с правильной классификацией (может пометить примеры лучше, чем случайное угадывание). В отличие от слабого алгоритма, сильный обучающий алгоритм является классификатором, хорошо коррелирующим с верной классификацией.
+
'''Бустинг''' (англ. ''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'') – адаптивный алгоритм бустинга.
+
Большая часть алгоритмов бустинга основывается на итеративном обучении слабых классификаторов с дальнейшей сборкой их в сильный классификатор. Когда они добавляются, им обычно приписываются веса, обычно связанные с [[Общие понятия|точностью обучения]]. После добавления слабого классификатора, веса пересчитываются ('''«пересчёт весовых коэффициентов»'''). Неверно классифицированные входные данные получают больший вес, а правильно классифицированные экземпляры теряют вес. Таким образом, дальнейшее слабое обучение фокусируется на примерах, где предыдущие слабые обучения дали ошибочную классификацию.
  
Только алгоритмы, для которых можно доказать, что они являются алгоритмами бустинга в формулировке приближённо правильного обучения, могут быть точно названы алгоритмами бустинга. Другие алгоритмы, близкие по духу алгоритмам бустинга, иногда называются '''«алгоритмами максимального использования»''' (англ. ''leveraging algorythms''), хотя они иногда также неверно называются алгоритмами бустинга.
+
Основное расхождение между многими алгоритмами бустинга заключается в методах определения весовых коэффициентов точек [[Общие понятия|тренировочных данных]] и гипотез. Первым алгоритмом, который смог адаптироваться к слабому обучению был '''AdaBoost'''<ref>[http://rob.schapire.net/papers/explaining-adaboost.pdf Explaining AdaBoost {{---}} Robert E. Schapire]</ref> (сокр. ''Adaptive Boosting''), предложенный Шапире и Фройндом.
  
Основное расхождение между многими алгоритмами бустинга заключается в методах определения весовых коэффициентов точек тренировочных данных и гипотез. Алгоритм '''AdaBoost''' очень популярен и исторически наиболее знаменателен, так как он был первым алгоритмом, который смог адаптироваться к слабому обучению.
+
Алгоритмы бустинга могут использовать выпуклую или невыпуклую функцию потерь. Алгоритмы с выпуклой функцией, такие как 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>, и так далее. Примерами классификаторов с учителем служат наивные [[Байесовская классификация|байесовские классификаторы]]<sup>[на 28.01.19 не создан]</sup>, [[Метод опорных векторов (SVM)|методы опорных векторов]]<sup>[на 28.01.19 не создан]</sup>, смесь гауссиан и [[Нейронные сети, перцептрон|нейронные сети]]. Однако исследования показали, что категории объектов и их положение в изображениях могут быть обнаружены также с помощью обучения без учителя.
Если даны изображения, содержащие различные известные в мире объекты, классификатор может быть обучен на основе них для автоматической классификации объектов в будущих неизвестных изображениях. Простые классификаторы, построенные на основе некоторых признаков изображения объекта, обычно оказываются малоэффективными в классификации. Использование методов бустинга для классификации объектов — это путь объединения слабых классификаторов специальным образом для улучшения общей возможности классификации.
 
  
===Задача классификации объектов===
+
===Задача ранжирования выдачи поисковых систем===
Классификация признаков является типичной задачей компьютерного зрения, где определяется, содержит ли изображение некоторую категорию объектов или нет. Идея тесно связана с распознаванием, идентификацией и обнаружением. Классификация по обнаружению объекта обычно содержит выделение признаков, обучение классификатора и применение классификатора к новым данным. Есть много способов представления категории объектов, например по анализу формы, с помощью модели '''«мешок слов»''', с помощью локальных описателей, таких как '''SIFT''', и так далее. Примерами классификаторов с учителем служат наивные байесовские классификаторы, методы опорных векторов, смесь гауссиан и нейронные сети. Однако исследования показали, что категории объектов и их положение в изображениях могут быть обнаружены также с помощью обучения без учителя.
+
Благодаря AdaBoost в мире появился [[CatBoost|градиентный бустинг]] (англ. ''gradient boosting'') или GBM. Задачу ранжирования выдачи поисковых запросов рассмотрели с точки зрения функции потерь, которая штрафует за ошибки в порядке выдачи, поэтому было удобно внедрить GBM в ранжирование.
Распознавание категорий объектов в изображениях является сложной задачей в компьютерном зрении, особенно если число категорий велико. Это является следствием высокой внутренней изменчивости классов и необходимости обобщения различных понятий внутри класса. Объекты в одной категории могут выглядеть совершенно различными. Даже один и тот же предмет может выглядеть непохожим с различных точек обзора, при другом мастшабе или освещении. Шум заднего плана и частичные наложения также добавляют сложности в распознавание. Люди способны распознавать тысячи типов объектов, в то время как большинство существующих систем распознавания объектов тренируются для распознавания лишь нескольких, например человеческих лиц, автомобилей, простых объектов и т.д.. Увеличению числа категорий и возможности добавления новых категорий достигается, в частности, с помощью совместного использования признаков и бустинга.
 
  
 
==AdaBoost==
 
==AdaBoost==
Строка 24: Строка 29:
 
Алгоритм может использоваться в сочетании с несколькими алгоритмами классификации для улучшения их эффективности. Алгоритм усиливает классификаторы, объединяя их в «комитет». AdaBoost является адаптивным в том смысле, что каждый следующий комитет классификаторов строится по объектам, неверно классифицированным предыдущими комитетами. AdaBoost чувствителен к шуму в данных и выбросам. Однако он менее подвержен переобучению по сравнению с другими алгоритмами машинного обучения.
 
Алгоритм может использоваться в сочетании с несколькими алгоритмами классификации для улучшения их эффективности. Алгоритм усиливает классификаторы, объединяя их в «комитет». AdaBoost является адаптивным в том смысле, что каждый следующий комитет классификаторов строится по объектам, неверно классифицированным предыдущими комитетами. AdaBoost чувствителен к шуму в данных и выбросам. Однако он менее подвержен переобучению по сравнению с другими алгоритмами машинного обучения.
  
AdaBoost вызывает слабые классификаторы в цикле <tex>t = 1,...,T</tex>. После каждого вызова обновляется распределение весов <tex>D_t</tex>, которые отвечают важности каждого из объектов обучающего множества для классификации. На каждой итерации веса каждого неверно классифицированного объекта возрастают, таким образом новый комитет классификаторов «фокусирует своё внимание» на этих объектах.
+
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>, он будет выбирать классификатор, который лучше идентифицирует объекты неверно распознаваемые предыдущим классификатором.
Пакет AdaBoost может быть использован для распознавания лиц как пример двоичной классификации. Две категории — это лица и фон. Общий алгоритм выглядит следующим образом:
 
  
Дано: <tex>(x_1,y_1),...,(x_m,y_m)</tex>, где <tex>x_i \in X, y_i \in Y = \{-1,+1\}</tex>
+
===Пример работы===
Инициализируем <tex>D_1(i) = \frac{1}{m},i=1,...,m</tex>.
+
Рассмотрим набор данных, которые пометим как $-$ и $+$.
Для каждого <tex>t=1,...,T</tex> пока не выполнен критерий останова:
+
[[Файл:Adaboost1.jpg|600px|thumb|center|Результат после первой итерации]]
  1. Находим классификатор <tex>h_t:X\to \{-1,+1\}</tex> который минимизирует взвешенную ошибку классификации: <tex>h_t = \arg \min_{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>
+
[[Файл:Adaboost2.jpg|1000px|thumb|center|Результат после пересчета весов и второй итерации]]
  2. Если величина <tex>\epsilon_t \geqslant 0.5</tex>, то останавливаемся.
+
Рассмотрим результат после $2$-х итераций:
  3. Выбираем <tex>\alpha_t \in \mathbf{R}</tex>, обычно <tex>\alpha_t = \frac{1}{2}\mathcal{ln}\frac{1-\epsilon_t}{\epsilon_t}</tex>, где <tex>\epsilon_t</tex> взвешенная ошибка классификатора
+
[[Файл:Adaboost_result12.jpg|1000px|thumb|center|Итоговый результат после $2$-х итераций]]
      <tex>h_t</tex>
+
Как видно из последнего изображения, все, что находиться в "цветной" зоне, мы можем однозначно классифицировать, но тогда у нас появляются ошибки и "белые" зоны, которые мы не можем однозначно классифицировать. Рассмотрим алгоритм после $30$-ти итераций:
  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_{t+1}</tex> являлось распределением вероятностей, то есть <tex>\sum\limits_{i-1}^{m} D_{t+1}(i) = 1</tex>).
+
[[Файл:Adaboost_resultfinal.jpg|300px|thumb|center|Результат работы алгоритма после $30$-ти итераций]]
Строим результирующий классификатор:
+
Теперь у нас все объекты классифицируются верно и число ошибок на выборке равно нулю.
  <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>
 
  
Таким образом, после выбора оптимального классификатора <tex>h_t</tex> для распределения <tex>D_t</tex>, объекты <tex>x_i</tex>, которые классификатор <tex>h_t</tex> идентифицирует корректно, имеют веса меньшие, чем те, которые идентифицируются некорректно. Следовательно, когда алгоритм тестирует классификаторы на распределении <tex>D_{t+1}</tex>, он будет выбирать классификатор, который лучше идентифицирует объекты неверно распознаваемые предыдущим классификатором.
+
===Достоинства и недостатки===
 +
'''Достоинства:'''
 +
# Простота реализации;
 +
# Хорошая обобщающая способность. В реальных задачах удаётся строить композиции, превосходящие по качеству базовые алгоритмы. Обобщающая способность может улучшаться по мере увеличения числа базовых алгоритмов;
 +
# Время построения композиции практически полностью определяется временем обучения базовых алгоритмов;
 +
# Возможность идентифицировать выбросы. Это наиболее «трудные» объекты $x_i$, для которых в процессе наращивания композиции веса $w_i$ принимают наибольшие значения.
 +
'''Недостатки:'''
 +
# Склонен к переобучению при наличии значительного уровня шума в данных;
 +
# Требует достаточно длинных обучающих выборок. Другие методы линейной коррекции, в частности, бэггинг, способны строить алгоритмы сопоставимого качества по меньшим выборкам данных.
  
 
===Пример кода на python для scikit-learn===
 
===Пример кода на python для scikit-learn===
Классификатор sklearn.ensemble.'''AdaBoostClassifier''' имеет 5 параметров: '''base_estimator''', '''n_estimators''', '''learning_rate''', '''algorithm''', '''random_state'''.
+
Классификатор 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''', '''n_estimators''' и '''learning_rate'''.
+
Наиболее важными являются:
 +
# '''base_estimator''' {{---}} базовый алгоритм. По умолчанию используется DecisionTreeClassifier(max_depth=1);
 +
# '''n_estimators''' {{---}} максимальное количество оценок, после которого бустинг прекращается. Если произойдет полное совпадение, то закончится раньше;
 +
# '''learning_rate''' {{---}} вклад каждой модели в весовые коэффициенты и значение по умолчанию равно $1$. Снижение этого параметра будет означать, что весовые коэффициенты буду увеличиваться или уменьшаться в небольшой степени, вынуждая модель дольше обучаться (но иногда повышается производительность).
  
 
  '''from''' sklearn.ensemble '''import''' AdaBoostClassifier
 
  '''from''' sklearn.ensemble '''import''' AdaBoostClassifier
Строка 60: Строка 94:
 
   
 
   
 
  X_train, X_test, y_train, y_test = train_test_split(X, y, test_size='''0.3''')
 
  X_train, X_test, y_train, y_test = train_test_split(X, y, test_size='''0.3''')
+
 
 
  abc = AdaBoostClassifier(n_estimators='''50''', learning_rate='''1''')
 
  abc = AdaBoostClassifier(n_estimators='''50''', learning_rate='''1''')
 
   
 
   
Строка 67: Строка 101:
 
  y_pred = model.'''predict'''(X_test)
 
  y_pred = model.'''predict'''(X_test)
 
   
 
   
  print("Accuracy:",metrics.'''accuracy_score'''(y_test, y_pred))
+
  '''print'''("Accuracy:",metrics.'''accuracy_score'''(y_test, y_pred))
  
 
  Accuracy: 0.8888888888888888
 
  Accuracy: 0.8888888888888888
Строка 82: Строка 116:
 
  y_pred = model.'''predict'''(X_test)
 
  y_pred = model.'''predict'''(X_test)
 
   
 
   
  print("Accuracy:",metrics.'''accuracy_score'''(y_test, y_pred))
+
  '''print'''("Accuracy:",metrics.'''accuracy_score'''(y_test, y_pred))
  
 
  Accuracy: 0.9555555555555556
 
  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>
 +
*[[Мета-обучение|Мета-обучение]]
 +
*[[Нейронные сети, перцептрон|Нейронные сети]]
 +
*[[Оценка качества в задаче кластеризации|Оценка качества в задаче кластеризации]]
 +
*[[CatBoost|CatBoost]]
 +
 +
== Примечания==
 +
<references />
 +
 +
== Источники информации ==
 +
# [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) Курс лекций по машинному обучению] {{---}} Воронцов К.В.
 +
[[Категория: Автоматическое машинное обучение]]
 +
[[Категория: Машинное обучение]]
 +
[[Категория: Ансамбли]]

Версия 17:23, 8 апреля 2019

Описание

Бустинг (англ. boosting) — мета-алгоритм машинного обучения. Основной идеей бустинга является комбинирование слабых функций, которые строятся в ходе итеративного процесса, где на каждом шаге новая модель обучается с использованием данных об ошибках предыдущих. Сильный обучающий алгоритм является классификатором, хорошо коррелирующим с верной классификацией, в отличие от слабого. Наравне с бустингом в мета-обучении также рассматривают такие понятия, как бэггинг (англ. bagging) и стэкинг[1] (англ. stacking). Бэггинг, в отличии от бустинга, использует параллельное обучение базовых классификаторов. Стэкинг же комбинирует результаты различных алгоритмов, получая тем самым более точный ответ.

Одним из недостатков бустинга является то, что он может приводить к построению громоздких композиций, состоящих из сотен алгоритмов. Такие композиции исключают возможность содержательной интерпретации, требуют больших объёмов памяти для хранения базовых алгоритмов и существенных затрат времени на вычисление классификаций.

Алгоритмы бустинга

Определение:
Композицией $T$ алгоритмов [math]a_t(x) = C(b_t(x)),\ t = 1,...,T[/math] называется суперпозиция алгоритмических операторов [math]b_t\ :\ X\to R[/math], корректирующей операции [math]F\ :\ R^T\to R[/math] и решающего правила [math] C\ :\ R\to Y[/math], где [math]R[/math] — пространство оценок,
[math]a(x) = C(F(b_1(x),...,b_T(x))), x \in X[/math]

, Алгоритмы $a_t$ называют базовыми алгоритмами.

Бустинг представляет собой композицию алгоритмов, в которых ошибки отдельных алгоритмов взаимно компенсируются. Например, в задаче классификации на два класса $Y = {-1, +1}$ в качестве пространства оценок принимают $R = \mathbb{R}$ и [math]C(b(x)) = \textrm{sign}(b(x))[/math]. Тогда базовые алгоритмы возвращают ответы $−1, 0, +1$. Ответ $b_t(x) = 0$ означает, что базовый алгоритм $b_t$ отказывается от классификации объекта $x$, и ответ $b_t(x)$ не учитывается в композиции. Получаем искомую композицию:

[math]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[/math]
,

Большая часть алгоритмов бустинга основывается на итеративном обучении слабых классификаторов с дальнейшей сборкой их в сильный классификатор. Когда они добавляются, им обычно приписываются веса, обычно связанные с точностью обучения. После добавления слабого классификатора, веса пересчитываются («пересчёт весовых коэффициентов»). Неверно классифицированные входные данные получают больший вес, а правильно классифицированные экземпляры теряют вес. Таким образом, дальнейшее слабое обучение фокусируется на примерах, где предыдущие слабые обучения дали ошибочную классификацию.

Основное расхождение между многими алгоритмами бустинга заключается в методах определения весовых коэффициентов точек тренировочных данных и гипотез. Первым алгоритмом, который смог адаптироваться к слабому обучению был AdaBoost[2] (сокр. Adaptive Boosting), предложенный Шапире и Фройндом.

Алгоритмы бустинга могут использовать выпуклую или невыпуклую функцию потерь. Алгоритмы с выпуклой функцией, такие как AdaBoost и LogitBoost[3], могут некорректно классифицировать из-за случайного шума, так как не могут обучить базовым и поддающимся научению комбинациям слабых гипотез. Алгоритмы бустинга, основанные на невыпуклой функции потерь, такие как BrownBoost[4], позволяют избежать переобучения на данных с большим количеством "шума", откидывая зашумленные элементы.

Прикладное использование алгоритмов бустинга

Задача классификации объектов

Если даны изображения, содержащие различные известные в мире объекты, классификатор может быть обучен на основе них для автоматической классификации объектов в будущих неизвестных изображениях. Простые классификаторы, построенные на основе некоторых признаков изображения объекта, обычно оказываются малоэффективными в классификации. Использование методов бустинга для классификации объектов — путь объединения слабых классификаторов специальным образом для улучшения общей возможности классификации.

Классификация признаков является типичной задачей компьютерного зрения, где определяется, содержит ли изображение некоторую категорию объектов или нет. Идея тесно связана с распознаванием, идентификацией и обнаружением. Классификация по обнаружению объекта обычно содержит выделение признаков, обучение классификатора и применение классификатора к новым данным. Есть много способов представления категории объектов, например по анализу формы, с помощью модели «мешок слов», с помощью локальных описателей, таких как SIFT[5], и так далее. Примерами классификаторов с учителем служат наивные байесовские классификаторы[на 28.01.19 не создан], методы опорных векторов[на 28.01.19 не создан], смесь гауссиан и нейронные сети. Однако исследования показали, что категории объектов и их положение в изображениях могут быть обнаружены также с помощью обучения без учителя.

Задача ранжирования выдачи поисковых систем

Благодаря AdaBoost в мире появился градиентный бустинг (англ. gradient boosting) или GBM. Задачу ранжирования выдачи поисковых запросов рассмотрели с точки зрения функции потерь, которая штрафует за ошибки в порядке выдачи, поэтому было удобно внедрить GBM в ранжирование.

AdaBoost

Описание

Алгоритм может использоваться в сочетании с несколькими алгоритмами классификации для улучшения их эффективности. Алгоритм усиливает классификаторы, объединяя их в «комитет». AdaBoost является адаптивным в том смысле, что каждый следующий комитет классификаторов строится по объектам, неверно классифицированным предыдущими комитетами. AdaBoost чувствителен к шуму в данных и выбросам. Однако он менее подвержен переобучению по сравнению с другими алгоритмами машинного обучения.

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

Описание алгоритма

//[math]x_i \in X, y_i \in Y = \{-1,+1\}, size(x) = size(y) = m[/math]
function AdaBoost($X$, $Y$, $m$):
   //Инициализируем
  for i = 1..m do:
    [math]D_i^1 = \frac{1}{m}[/math]
  end for
  
  for t = 1..T do:
    [math]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)〛[/math]  //$\epsilon$ — Взвешенная ошибка классификации, классификатор [math]h_t:X\to \{-1,+1\}[/math]
    [math]\alpha_t = \frac{1}{2}\ln\frac{1-\epsilon_t}{\epsilon_t}[/math]
    for i = 1..m do:
      //[math]Z_t[/math] — нормализующий параметр, выбранный так, чтобы [math]D^{t+1}[/math] являлось распределением вероятностей, то есть [math]\sum\limits_{i-1}^{m} D_i^{t+1} = 1[/math], для [math]t=1,...,T[/math] 
      [math]D_i^{t+1} = \dfrac{D_i^t \textrm{exp}(-\alpha_t y_i h_t(x_i))}{Z_t}[/math] 
    end for
  end for
  [math]H(x) = \textrm{sign}\left(\sum\limits_{t=1}^{T} \alpha_t h_t(x)\right)[/math]  //$H(x)$ — результирующий классификатор
  return $H$

Выражение для обновления распределения [math]D^t[/math] должно быть сконструировано таким образом, чтобы выполнялось условие:

[math]\exp^{\alpha_t y_i h_t(x_i)} \begin{cases}\lt 1,\ y(i) = h_t(x_i) \\ \gt 1,\ y(i) \neq h_t(x_i)\end{cases}[/math]
,

Таким образом, после выбора оптимального классификатора [math]h_t[/math] для распределения [math]D^t[/math], объекты [math]x_i[/math], которые классификатор [math]h_t[/math] идентифицирует корректно, имеют веса меньшие, чем те, которые идентифицируются некорректно. Следовательно, когда алгоритм тестирует классификаторы на распределении [math]D^{t+1}[/math], он будет выбирать классификатор, который лучше идентифицирует объекты неверно распознаваемые предыдущим классификатором.

Пример работы

Рассмотрим набор данных, которые пометим как $-$ и $+$.

Результат после первой итерации

Для всех ошибочно классифицированных объектов увеличим веса, а для верно классифицированных уменьшим

Результат после пересчета весов и второй итерации

Рассмотрим результат после $2$-х итераций:

Итоговый результат после $2$-х итераций

Как видно из последнего изображения, все, что находиться в "цветной" зоне, мы можем однозначно классифицировать, но тогда у нас появляются ошибки и "белые" зоны, которые мы не можем однозначно классифицировать. Рассмотрим алгоритм после $30$-ти итераций:

Результат работы алгоритма после $30$-ти итераций

Теперь у нас все объекты классифицируются верно и число ошибок на выборке равно нулю.

Достоинства и недостатки

Достоинства:

  1. Простота реализации;
  2. Хорошая обобщающая способность. В реальных задачах удаётся строить композиции, превосходящие по качеству базовые алгоритмы. Обобщающая способность может улучшаться по мере увеличения числа базовых алгоритмов;
  3. Время построения композиции практически полностью определяется временем обучения базовых алгоритмов;
  4. Возможность идентифицировать выбросы. Это наиболее «трудные» объекты $x_i$, для которых в процессе наращивания композиции веса $w_i$ принимают наибольшие значения.

Недостатки:

  1. Склонен к переобучению при наличии значительного уровня шума в данных;
  2. Требует достаточно длинных обучающих выборок. Другие методы линейной коррекции, в частности, бэггинг, способны строить алгоритмы сопоставимого качества по меньшим выборкам данных.

Пример кода на python для scikit-learn

Классификатор sklearn.ensemble.AdaBoostClassifier[6] имеет 5 параметров: base_estimator, n_estimators, learning_rate, algorithm, random_state. Наиболее важными являются:

  1. base_estimator — базовый алгоритм. По умолчанию используется DecisionTreeClassifier(max_depth=1);
  2. n_estimators — максимальное количество оценок, после которого бустинг прекращается. Если произойдет полное совпадение, то закончится раньше;
  3. learning_rate — вклад каждой модели в весовые коэффициенты и значение по умолчанию равно $1$. Снижение этого параметра будет означать, что весовые коэффициенты буду увеличиваться или уменьшаться в небольшой степени, вынуждая модель дольше обучаться (но иногда повышается производительность).
from sklearn.ensemble import AdaBoostClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn import metrics

iris = datasets.load_iris()

X = iris.data
y = iris.target

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)
abc = AdaBoostClassifier(n_estimators=50, learning_rate=1)

model = abc.fit(X_train, y_train)

y_pred = model.predict(X_test)

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

Теперь рассмотрим алгоритм с SVC в качестве базы:

from sklearn.svm import SVC

svc=SVC(probability=True, kernel='linear')

abc = AdaBoostClassifier(base_estimator=svc, n_estimators=50, learning_rate=1)

model = abc.fit(X_train, y_train)

y_pred = model.predict(X_test)

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

Пример на языке Scala

SBT зависимость:

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

Пример классификации датасета и вычисления F1 меры[7] используя smile.classification.adaboost[8]:

 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

Пример классификации с применением smile.classification.AdaBoost[9]

Maven зависимость:

 <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;
 // load train and test datasets
 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"));
 // create adaboost classifier
 var forest   = new AdaBoost(train.attributes(), train.x(), train.labels(), 200, 4);
 // measure accuracy and F1-measure on test dataset
 var measures = new ClassificationMeasure[]{new FMeasure(), new Accuracy()};
 var results  = forest.test(test.x(), test.labels(), measures);
 System.out.println(Arrays.deepToString(results));

См. также

Примечания

Источники информации

  1. AdaBoost — статья на machinelearning.ru
  2. AdaBoost — презентация по AdaBoost
  3. Example of AdaBoost in action — презентация на coursera.org
  4. Курс лекций по машинному обучению — Воронцов К.В.