Skip to content
Назад к результатам поиска

Бэггинг (Бутстрэп-агрегирование)

Автор метода
Breiman, L.
Год
1996
Тип
Ensemble meta-algorithm (variance reduction via bootstrap aggregation)

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Бэггинг, сокращение от Bootstrap Aggregating, — это ансамблевый метаалгоритм, представленный Лео Брейманом в 1996 году, который обучает несколько копий базового ученика на независимо отобранных бутстрэп-выборках обучающих данных и объединяет их предсказания — путем усреднения для регрессии или голосования большинством для классификации — для получения окончательного предиктора со значительно меньшей дисперсией, чем у любого отдельного базового ученика.

Интуиция метода

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

История

Лео Брейман опубликовал «Bagging Predictors in Machine Learning» в 1996 году, исходя из наблюдения, что нестабильные ученики — те, чьи выходные данные существенно меняются при небольших возмущениях данных — могут быть стабилизированы путем усреднения по бутстрэп-репликам обучающего набора. Теоретическое обоснование основано на разложении по смещению-дисперсии: усреднение снижает дисперсию, оставляя смещение неизменным. Брейман продемонстрировал последовательное улучшение точности по сравнению с отдельными деревьями решений на ряде эталонных задач классификации и регрессии. Бэггинг быстро стал основополагающей ансамблевой техникой и напрямую вдохновил Random Forest (Breiman, 2001), который добавляет случайную субвыборку признаков при каждом разделении для дальнейшей декорреляции деревьев и достижения еще большего снижения дисперсии. Сегодня бэггинг служит концептуальной основой для широкого семейства ансамблевых методов и является стандартной темой в учебных программах магистерского уровня по машинному обучению.

Когда применять

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

Ограничения и замечания

  • Не снижает смещение: если базовый ученик недообучается, бэггинг не может это исправить.
  • Предсказания ансамбля труднее интерпретировать, чем предсказания одной модели; нет аналога визуальной структуры одного дерева решений.
  • Память и хранение масштабируются линейно с B: хранение сотен больших моделей в памяти может быть непомерным.
  • Прирост быстро уменьшается по мере роста B; производительность обычно стабилизируется задолго до B = 500.
  • При применении к стабильным базовым ученикам (например, линейной регрессии с корректной спецификацией) бэггинг дает незначительное улучшение.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Напрямую снижает дисперсию оценщика без увеличения смещения, давая более стабильные предсказания, чем любая отдельная базовая модель.
  • Тривиально распараллеливается: каждая бутстрэп-итерация независима, что делает большие ансамбли вычислительно осуществимыми.
  • Встроенная оценка ошибки OOB обеспечивает честную оценку обобщения без дополнительных затрат на данные.
  • Метаалгоритм, не зависящий от модели: совместим с любым достаточно нестабильным базовым учеником (деревья, нейронные сети, ближайшие соседи).
  • Устойчив к выбросам в обучающем наборе: любое отдельное необычное наблюдение отсутствует в большинстве бутстрэп-выборок.

Применение

  • Построение стабильных моделей классификации и регрессии на зашумленных табличных данных, где одно дерево решений переобучится.
  • Генерация доверительных интервалов путем анализа разброса предсказаний между B базовыми учениками.
  • Оценка важности признаков путем снижения точности OOB при перестановке каждого признака по всему ансамблю.
  • Базовый ансамбль: быстрая эталонная проверка для количественной оценки того, насколько более сложный метод (бустинг, стекинг) улучшает простой агрегат.

Как это работает

Как это работает

1

Из исходного обучающего набора размером n выбираются B независимых бутстрэп-выборок. Каждая выборка генерируется путем выбора n наблюдений с возвращением из исходных данных, поэтому в среднем каждая выборка содержит около 63,2% уникальных обучающих экземпляров; оставшиеся ~36,8% исключаются и формируют набор вне выборки (OOB) для данной итерации.

Формула
\mathcal{D}_b = \{(\mathbf{x}_i^*, y_i^*)\}_{i=1}^{n}, \quad (\mathbf{x}_i^*, y_i^*) \overset{\text{i.i.d.}}{\sim} \hat{F}_n, \quad b = 1, \dots, B
2

Базовый алгоритм обучения — чаще всего дерево решений, выращенное до полной глубины, но подходит любой достаточно нестабильный ученик — подгоняется независимо на каждой бутстрэп-выборке, что дает B различных моделей. Ключевым требованием является нестабильность: если небольшие возмущения данных вызывают большие изменения модели, бэггинг дает наибольшее снижение дисперсии.

Формула
\hat{f}_b = \mathcal{A}(\mathcal{D}_b)
3

Для задач регрессии усредняются B выходных данных модели. Этот шаг усреднения является основным механизмом снижения дисперсии: при предположениях о независимости дисперсия среднего B одинаково распределенных моделей составляет 1/B от дисперсии одной модели, и даже при положительной корреляции снижение существенно.

Формула
\hat{f}_{\text{bag}}(\mathbf{x}) = \frac{1}{B} \sum_{b=1}^{B} \hat{f}_b(\mathbf{x})
4

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

Формула
\hat{y}(\mathbf{x}) = \underset{k}{\operatorname{arg\,max}} \sum_{b=1}^{B} \mathbf{1}\!\left[\hat{f}_b(\mathbf{x}) = k\right]
5

Поскольку каждый базовый ученик обучается примерно на 63,2% данных, оставшиеся наблюдения могут служить честным тестовым набором для этого ученика. Усреднение этих предсказаний OOB по всем ученикам, которые не видели каждое наблюдение, дает почти несмещенную оценку ошибки обобщения без необходимости отдельной валидационной выборки или перекрестной проверки.

Формула
\widehat{\text{Err}}_{\text{OOB}} = \frac{1}{n} \sum_{i=1}^{n} L\!\left(y_i,\; \frac{1}{|\mathcal{B}_i^c|} \sum_{b \in \mathcal{B}_i^c} \hat{f}_b(\mathbf{x}_i)\right)

Частые ошибки

  • Применение бэггинга к базовому ученику с низкой дисперсией (например, гребневой регрессии) и ожидание большого прироста точности.
  • Установка B слишком маленьким (например, B < 10), так что агрегат все еще шумит, а оценки OOB ненадежны.
  • Игнорирование дисбаланса классов: бэггинг сохраняет распределение классов исходных данных в каждой бутстрэп-выборке, поэтому сильный дисбаланс реплицируется во всех учениках.
  • Смешение бэггинга с бустингом: бэггинг обучает модели параллельно на независимых выборках для снижения дисперсии, в то время как бустинг обучает модели последовательно для снижения смещения — они решают разные источники ошибок.
  • Рассмотрение ошибки OOB как замены надлежащей оценки на отложенном наборе при очень маленьком наборе данных, поскольку оценки OOB могут быть оптимистичными в этом режиме.

Часто задаваемые вопросы

Сколько бутстрэп-выборок B следует использовать?

Брейман (1996) обнаружил, что производительность стабилизируется относительно быстро; B = 50–100 часто достаточно для деревьев решений. Увеличение B сверх нескольких сотен дает убывающую отдачу. Отслеживайте ошибку OOB по мере роста B и останавливайтесь, когда она стабилизируется.

В чем разница между бэггингом и Random Forest?

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

Можно ли применять бэггинг к ученикам, отличным от деревьев решений?

Да. Любой ученик, который является нестабильным — чьи предсказания существенно меняются при небольших изменениях обучающих данных — может выиграть от бэггинга. Нейронные сети, k-ближайших соседей и необрезанные деревья регрессии подходят. Стабильные ученики, такие как линейная регрессия с хорошо специфицированной моделью, мало выигрывают, поскольку дисперсия невелика для снижения.

Является ли ошибка OOB надежной заменой перекрестной проверки?

Для умеренных и больших наборов данных ошибка OOB является почти несмещенной оценкой ошибки обобщения и вычислительно бесплатна, поскольку не требуется дополнительных подгонок модели. На очень маленьких наборах данных (n менее примерно 50) оценки OOB могут быть оптимистичными, и предпочтительнее перекрестная проверка.

Похожие методы

Источники

  1. Breiman, L. (1996). Bagging Predictors. Machine Learning, 24(2), 123–140.

    Открыть ссылку DOI
    Скопировано.
  2. Hastie, T., Tibshirani, R. & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 8.7). Springer.

    ISBN: 978-0-387-84857-0
    Скопировано.
  3. James, G., Witten, D., Hastie, T. & Tibshirani, R. (2013). An Introduction to Statistical Learning (Ch. 8.2). Springer.

    ISBN: 978-1-4614-7138-7
    Скопировано.