Изменения
Нет описания правки
==Описание==
'''Бустинг''' (англ. ''boosting'') — это композиционный {{---}} [[Мета-обучение|мета-алгоритм машинного обучения машин]]<sup>[на 18.01.19 не создан]</sup>. ПрименяетсяОсновной идеей бустинга является комбинирование слабых функций, главным образомкоторые строятся в ходе итеративного процесса, для уменьшения смещениягде на каждом шаге новая модель обучается с использованием данных об ошибках предыдущих. Сильный обучающий алгоритм является классификатором, а также хорошо [[Дисперсия случайной величиныКорреляция случайных величин|дисперсиикоррелирующим]] с верной классификацией, в отличие от слабого. Наравне с бустингом в мета-обучении с учителем. Также семейство алгоритмов обучения машинтакже рассматривают такие понятия, преобразующих слабые обучающие алгоритмы к сильным. Слабый обучающий алгоритм определяется как [[Общие понятияВиды ансамблей|классификаторбэггинг]](англ. ''bagging'') и стэкинг<supref>[на 18https://dyakonov.01.19 не создан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 Стекинг {{---}} Дьяконов Александр]</supref>, который слабо коррелирует с правильной классификацией (может пометить примеры лучше, чем случайное угадываниеангл. ''stacking''). В отличие Бэггинг, в отличии от слабого алгоритмабустинга, использует параллельное обучение базовых классификаторов. Стэкинг же комбинирует результаты различных алгоритмов, сильный обучающий алгоритм получая тем самым более точный ответ. Одним из недостатков бустинга является классификаторомто, что он может приводить к построению громоздких композиций, состоящих из сотен алгоритмов. Такие композиции исключают возможность содержательной интерпретации, хорошо [[Корреляция случайных величин|коррелирующим]] с верной классификациейтребуют больших объёмов памяти для хранения базовых алгоритмов и существенных затрат времени на вычисление классификаций.
==Алгоритмы бустинга==
==AdaBoost==
Алгоритм может использоваться в сочетании с несколькими алгоритмами классификации для улучшения их эффективности. Алгоритм усиливает классификаторы, объединяя их в «комитет». AdaBoost является адаптивным в том смысле, что каждый следующий комитет классификаторов строится по объектам, неверно классифицированным предыдущими комитетами. AdaBoost чувствителен к шуму в данных и выбросам. Однако он менее подвержен переобучению по сравнению с другими алгоритмами машинного обучения.
AdaBoost вызывает слабые классификаторы <tex>h_i^t</tex> в цикле <tex>t = 1,...,T</tex>. После каждого вызова обновляется распределение весов <tex>D_t</tex>, которые отвечают важности каждого из объектов обучающего множества для классификации. На каждой итерации веса каждого неверно классифицированного объекта возрастают, таким образом новый комитет классификаторов «фокусирует своё внимание» на этих объектах.
===Алгоритм для задачи построения двоичного классификатораОписание алгоритма===Пакет AdaBoost может быть использован для распознавания лиц как пример двоичной классификации. Две категории — это лица и фон. Общий алгоритм выглядит следующим образом:
Таким образом, после выбора оптимального классификатора <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
y_pred = model.'''predict'''(X_test)
'''print'''("Accuracy:",metrics.'''accuracy_score'''(y_test, y_pred))
Accuracy: 0.8888888888888888
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 меры<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) Курс лекций по машинному обучению] {{---}} Воронцов К.В.
[[Категория: Автоматическое машинное обучение]]
[[Категория: Машинное обучение]]
[[Категория: Ансамбли]]