WikiSort.ru - Не сортированное

Машинное обучение и data mining

Задачи Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение

Обучение с учителем Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей (Бэггинг, Бустинг, Random forest) Метод релевантных векторов

Кластерный анализ Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift

Снижение размерности Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE

Структурное прогнозирование Графовая вероятностная модель (Байесовская сеть, Скрытая марковская модель, CRF)

Выявление аномалий Метод k-ближайших соседей Локальный уровень выброса

Графовые вероятностные модели Байесовская сеть Марковская сеть Скрытая марковская модель

Искусственные нейронные сети Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации (Сигмоида, Softmax, Радиально-базисная функция) Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть (Долгая краткосрочная память, Управляемый рекуррентный блок) Свёрточная нейронная сеть (U-Net) Автокодировщик

Обучение с подкреплением Марковский процесс Уравнение Беллмана Жадный алгоритм Q-learning SARSA Temporal difference (TD)

Теория Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения

Журналы и конференции NIPS ICML ML JMLR ArXiv:cs.LG

Глоссарий Глоссарий по машинному обучению

Статьи по теме List of datasets for machine-learning research Outline of machine learning

AdaBoost (сокращение от Adaptive Boosting) — алгоритм машинного обучения, предложенный Йоавом Фройндом^[en] и Робертом Шапире^[en]. Этот алгоритм может использоваться в сочетании с несколькими алгоритмами классификации для улучшения их эффективности. Алгоритм усиливает классификаторы, объединяя их в «комитет». AdaBoost является адаптивным в том смысле, что каждый следующий комитет классификаторов строится по объектам, неверно классифицированным предыдущими комитетами. AdaBoost чувствителен к шуму в данных и выбросам. Однако он менее подвержен переобучению по сравнению с другими алгоритмами машинного обучения.

AdaBoost вызывает слабые классификаторы в цикле ${\displaystyle t=1,\ldots ,T}$ . После каждого вызова обновляется распределение весов ${\displaystyle D_{t}}$ , которые отвечают важности каждого из объектов обучающего множества для классификации. На каждой итерации веса каждого неверно классифицированного объекта возрастают, таким образом новый комитет классификаторов «фокусирует своё внимание» на этих объектах.

Алгоритм для задачи построения бинарного классификатора

Дано: ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{m},y_{m})}$ где ${\displaystyle x_{i}\in X,\,y_{i}\in Y=\{-1,+1\}}$

Инициализируем ${\displaystyle D_{1}(i)={\frac {1}{m}},i=1,\ldots ,m.}$

Для каждого ${\displaystyle t=1,\ldots ,T}$ :

• Находим классификатор ${\displaystyle h_{t}:X\to \{-1,+1\}}$ который минимизирует взвешенную ошибку классификации: ${\displaystyle h_{t}=\arg \min _{h_{j}\in {\mathcal {H}}}\epsilon _{j}}$ , где ${\displaystyle \epsilon _{j}=\sum _{i=1}^{m}D_{t}(i)[y_{i}\neq h_{j}(x_{i})]}$
• Если величина ${\displaystyle \epsilon _{t}\geqslant 0.5}$ , то останавливаемся.
• Выбираем ${\displaystyle \alpha _{t}\in \mathbf {R} }$ , обычно ${\displaystyle \alpha _{t}={\frac {1}{2}}{\textrm {ln}}{\frac {1-\epsilon _{t}}{\epsilon _{t}}}}$ где ${\displaystyle \epsilon _{t}}$ взвешенная ошибка классификатора ${\displaystyle h_{t}}$ .
• Обновляем:

${\displaystyle D_{t+1}(i)={\frac {D_{t}(i)\,e^{-\alpha _{t}y_{i}h_{t}(x_{i})}}{Z_{t}}}}$

где ${\displaystyle Z_{t}}$ является нормализующим параметром (выбранным так, чтобы ${\displaystyle D_{t+1}}$ являлось распределением вероятностей, то есть ${\displaystyle \sum _{i=1}^{m}D_{t+1}(i)=1}$ ).

Строим результирующий классификатор:

${\displaystyle H(x)={\textrm {sign}}\left(\sum _{t=1}^{T}\alpha _{t}h_{t}(x)\right)}$

Выражение для обновления распределения ${\displaystyle D_{t}}$ должно быть сконструировано таким образом, чтобы выполнялось условие:

${\displaystyle e^{-\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}}}$

Таким образом, после выбора оптимального классификатора ${\displaystyle h_{t}}$ для распределения ${\displaystyle D_{t}}$ , объекты ${\displaystyle x_{i}}$ , которые классификатор ${\displaystyle h_{t}}$ идентифицирует корректно, имеют веса меньшие, чем те, которые идентифицируются некорректно. Следовательно, когда алгоритм тестирует классификаторы на распределении ${\displaystyle D_{t+1}}$ , он будет выбирать классификатор, который лучше идентифицирует объекты неверно распознаваемые предыдущим классификатором.

Ссылки

• AdaBoost (англ.) Презентация, посвящённая Adaboost.
• A Short Introduction to Boosting (англ.) Введение в Adaboost, Freund и Schapire, 1999
• A decision-theoretic generalization of on-line learning and an application to boosting Journal of Computer and System Sciences, no. 55. 1997 (англ.) (Оригинальная работа Yoav Freund и Robert E.Schapire, где впервые был предложен Adaboost.)
• An applet demonstrating AdaBoost (англ.)
• Ensemble Based Systems in Decision Making, R. Polikar, IEEE Circuits and Systems Magazine, vol.6, no.3, pp. 21-45, 2006 (недоступная ссылка) (англ.) Учебник, дающий общее представление об AdaBoost, включая псевдокод, схемы алгоритмов, вопросы реализации и других алгоритмах распознавания образов.
• A Matlab Implementation of AdaBoost (англ.)
• Additive logistic regression: a statistical view of boosting. Jerome Friedman, Trevor Hastie, Robert Tibshirani (англ.) Обсуждаются вероятностные аспекты AdaBoost, описывается GentleBoost.
• Boosting — Усиление простых классификаторов. (недоступная ссылка) Александр Вежневец, Владимир Вежневец. Компьютерная графика и мультимедиа. Выпуск № 2(12)/2006.

Для улучшения этой статьи желательно: Проверить достоверность указанной в статье информации. Проставив сноски, внести более точные указания на источники.

Эту статью следует сделать более понятной широкому кругу читателей. Пожалуйста, попытайтесь изложить эту статью так, чтобы она была понятна неспециалисту. Вам могут помочь советы в этом эссе. Подробности могут быть на странице обсуждения.