Бэггинг (>ziinui)

Бэггинг (от англ. bootstrap aggregating, бутстрэп-агрегирование) — ансамблевый метаалгоритм, предназначенный для улучшения стабильности и точности алгоритмов машинного обучения, используемых в задачах классификации и регрессии. Алгоритм также уменьшает дисперсию и помогает избежать переобучения. Хотя он обычно применяется к методам машинного обучения на основе деревьев решений, его можно использовать с любым видом метода. Бэггинг является частным видом усреднения модели.

Предложен Лео Брейманом в 1994 году^[1].

Описание техники

Если задан стандартный тренировочный набор^[англ.] $D$ размера $n$ , бэггинг образует $m$ новых тренировочных наборов $D_{i}$ , каждый размером $n'$ , путём выборки из $D$ равномерно и с возвратом. При семплинге с возвратом некоторые наблюдения могут быть повторены в каждой $D_{i}$ . Если $n'=n$ , то для больших $n$ ожидается, что множество $D_{i}$ имеет долю $1-1/e\approx 0{,}63$ уникальных экземпляров из $D$ , остальные будут повторениями^[2]. Этот вид семплинга известен как бутстрэп-семплинг. Эти $m$ моделей сглаживаются с помощью вышеупомянутых $m$ бутстрэп-выборок и комбинируются путём усреднения (для регрессии) или голосования (для классификации).

Бэггинг ведёт к «улучшению для нестабильных процедур»^[3], в которые входят, например, искусственные нейронные сети, деревья классификации и регрессий и выбор подмножеств в линейной регрессии^[1]. В 2011 году найдено применение бэггинга для обработки изображений^[4]^[5]. С другой стороны, метод может слегка ухудшить эффективность стабильных методов, таких как метод K-ближайших соседей^[3].

Пример: зависимость концентрации озона от температуры

Для иллюстрации основных принципов бэггинга ниже приведён анализ связи между озоном и температурой^[6]. Анализ осуществлён на языке программирования R.

Связь между температурой и озоном в этом наборе данных, очевидно, нелинейна. Чтобы описать эту связь, использовались сглаживатели LOESS^[англ.] (с полосой пропускания 0,5). Вместо построения единого сглаживателя из всего набора данных извлечено 100 выборок бутстрэпов данных. Каждая выборка отличается от исходного набора данных, но они, всё же, совпадают по распределению и дисперсии. Для каждой бутстрэп-выборки применялся сглаживатель LOESS. Затем сделано предсказание по данным на основе этих 100 сглаживаний. Первые 10 сглаживаний показаны серыми линиями на рисунке ниже. Линии, как видно, очень волнисты и страдают переподгонкой данных — результат полосы слишком мал.

Взяв среднее 100 сглаживателей, которые применялись к подмножествам оригинального набора данных, мы получаем сборный предсказатель (красная линия). Ясно, что среднее более устойчиво и не столь подвержено переобучению.

Примечания

↑ ¹ ² Breiman, 1994.
↑ Aslam, Popa, Rivest, 2007.
↑ ¹ ² Breiman, 1996, с. 123–140.
↑ Sahu, Runger, Apley, 2011, с. 1—7.
↑ Shinde, Sahu, Apley, Runger, 2014.
↑ Rousseeuw, Leroy, 1987, с. 84—93.

Литература

Rousseeuw P. J., Leroy A. M. Robust Regression and Outlier Detection. — New York, Chichester, Brisbane, Toronto, Singapure: John Willey & Sons, 1987. — ISBN 0-471-85233-3.
Javed A. Aslam, Raluca A. Popa, Ronald L. Rivest. On Estimating the Size and Confidence of a Statistical Audit // Proceedings of the Electronic Voting Technology Workshop (EVT '07). — Boston, MA, 2007.
Sahu A., Runger G., Apley D. Image denoising with a multi-phase kernel principal component approach and an ensemble version // IEEE Applied Imagery Pattern Recognition Workshop. — 2011. — С. 1—7.
Amit Shinde, Anshuman Sahu, Daniel Apley, George Runger. Preimages for Variation Patterns from Kernel PCA and Bagging // IIE Transactions. — 2014. — Т. 46, вып. 5.
Leo Breiman. Bagging predictors // Machine Learning. — 1996. — Т. 24, вып. 2. — С. 123–140. — doi:10.1007/BF00058655.
Breiman L. Bagging Predictors. Technical Report No. 421. — 1994.
Alfaro E., Gámez M., García N. adabag: An R package for classification with AdaBoost.M1, AdaBoost-SAMME and Bagging. — 2012.

[_1b87fa4e0fa11bbc-1] ¹ ² Breiman, 1994.

[_d9d44550359f3fa1-2] Aslam, Popa, Rivest, 2007.

[_1efb174c1ce43150-3] ¹ ² Breiman, 1996, с. 123–140.

[_b85c0cd323465de4-4] Sahu, Runger, Apley, 2011, с. 1—7.

[_0bc401c82fb96a06-5] Shinde, Sahu, Apley, Runger, 2014.

[_22f2986bff891cc5-6] Rousseeuw, Leroy, 1987, с. 84—93.

[1]

[2]

[3]

[4]

[5]

[6]

Машинное обучение и data mining
Задачи	Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение
Обучение с учителем	Метод k ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамблевое обучение Бэггинг Бустинг Метод случайного леса Метод релевантных векторов
Кластерный анализ	Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift
Снижение размерности	Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE
Структурное прогнозирование	Графовая вероятностная модель Байесовская сеть Скрытая марковская модель CRF
Выявление аномалий	Метод k ближайших соседей Локальный уровень выброса
Графовые вероятностные модели	Байесовская сеть Марковская сеть Скрытая марковская модель
Нейронные сети	Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации Сигмоида Softmax Радиально-базисная функция Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть Долгая краткосрочная память Управляемый рекуррентный блок Свёрточная нейронная сеть U-Net Автокодировщик
Обучение с подкреплением	Марковский процесс Уравнение Беллмана Жадный алгоритм Q-обучение SARSA Temporal difference (TD)
Теория	Размерность Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения
Журналы и конференции	NeurIPS ICML ML JMLR ArXiv:cs.LG