Бэггинг

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

Описание техникиПравить

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

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

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

Для иллюстрации основных принципов бэггинга ниже приведён анализ связи между озоном и температурой (данные взяты из книги Peter Rousseeuw — версия статьи «Руссёв, Питер» на английском языке Руссёва (англ.) (рус. и Леруа ^[6]. Анализ осуществлён на языке программирования R).

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

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

ИсторияПравить

Бэггинг (от англ. Bagging = Bootstrap aggregating) предложил Лео Брейман в 1994 для улучшения классификации путём комбинирования классификации случайно сгенерированных тренировочных наборов. См. технический отчёт №421^[3].

См. такжеПравить

ПримечанияПравить

↑ Aslam, Popa, Rivest, 2007.
↑ ¹ ² Breiman, 1996, с. 123–140.
↑ ¹ ² Breiman, 1994.
↑ 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.

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

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

[_1b87fa4e0fa11bbc-3] ¹ ² Breiman, 1994.

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]