Бутстрэп

Материал из MachineLearning.

Версия от 15:16, 18 июля 2026; Bogdan Kormalov (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Статья написана с использованием LLM DeepSeek-V3 и проверена участником Bogdan Kormalov 18:52, 18 июля 2026 (MSD)


Бутстрэп (англ. bootstrap), или бутстрэп-метод, — это мощный инструмент математической статистики и машинного обучения, основанный на многократном извлечении выборок с возвращением из исходного набора данных. Название метода отсылает к идиоме «to pull oneself over a fence by one's bootstraps» (вытащить себя за шнурки ботинок), подчеркивая идею извлечения информации о распределении статистики из единственной имеющейся выборки без априорных предположений о виде распределения генеральной совокупности.

Основополагающей работой считается статья Брэдли Эфрона 1979 года «Bootstrap Methods: Another Look at the Jackknife»Efron, B. (1979). Bootstrap methods: Another look at the jackknife. The Annals of Statistics, 7(1), 1-26., хотя исторические корни метода прослеживаются к более ранним работам по jackknife-процедурам. В современном машинном обучении бутстрэп служит статистическим фундаментом для создания ансамблевых методов, оценки стабильности моделей и построения доверительных интервалов.

Содержание

Интуитивное объяснение и формальная постановка

Пусть имеется независимая выборка \mathcal{D} = {x_1, x_2, \dots, x_n} из неизвестного распределения F. Цель состоит в том, чтобы оценить выборочное распределение некоторой статистики \hat{\theta} = s(\mathcal{D}) (например, среднего, медианы, коэффициента корреляции или предсказания сложной модели). Аналитический расчет стандартной ошибки и доверительных интервалов часто требует знания вида распределения F или применения асимптотической теории, которая может плохо работать на малых выборках.

Бутстрэп решает эту проблему, используя эмпирическое распределение \hat{F}, которое приписывает вероятность 1/n каждому наблюдению в исходной выборке. Из \hat{F} генерируется B независимых бутстрэп-выборок, каждая размером n, путем случайного отбора элементов с возвращением (resampling with replacement).

Каждая b-я бутстрэп-выборка \mathcal{D}^{b} содержит некоторые элементы исходной выборки несколько раз, в то время как другие не содержит вовсе. Для каждой из B выборок вычисляется значение статистики \hat{\theta}^{b} = s(\mathcal{D}^{b}). Эмпирическое распределение множества {\hat{\theta}^{1}, \dots, \hat{\theta}^{*B}} служит аппроксимацией истинного выборочного распределения статистики \hat{\theta}.

Стандартная ошибка оценки вычисляется как стандартное отклонение бутстрэп-статистик:

\widehat{SE}B = \sqrt{\frac{1}{B-1} \sum{b=1}^{B} \left( \hat{\theta}^{b} - \bar{\theta}^ \right)^2}

Бэггинг: бутстрэп-агрегирование моделей

Принцип агрегирования

Бэггинг (англ. bagging, сокращение от Bootstrap AGGregatING) — это техника построения ансамблей моделей, предложенная Лео Брейманом в 1996 годуBreiman, L. (1996). Bagging predictors. Machine learning, 24(2), 123-140.. Основная идея заключается в том, что усреднение предсказаний группы нестабильных, но слабо коррелированных моделей приводит к значительно меньшей дисперсии, чем у каждой отдельной модели.

Алгоритм бэггинга состоит из трех шагов:

Из исходной обучающей выборки генерируется B бутстрэп-выборок. На каждой b-й бутстрэп-выборке независимо обучается базовая модель f_b(\mathbf{x}) (как правило, это «сильный» ученик с высокой дисперсией). Финальное предсказание для задачи регрессии получается усреднением, а для классификации — голосованием (majority voting).

\hat{f}{\text{bag}}(\mathbf{x}) = \frac{1}{B} \sum{b=1}^{B} f_b(\mathbf{x}) (для регрессии)

Бэггинг максимально эффективен для «нестабильных» алгоритмов, то есть таких, чьи результаты сильно меняются при небольших изменениях обучающих данных. Деревья решений без прунинга (глубокие до переобучения) являются идеальными кандидатами.

Случайный лес как развитие бэггинга

Случайный лес (Random Forest) — наиболее широко известный и используемый алгоритм, основанный на бэггинге, предложенный Брейманом в 2001 годуBreiman, L. (2001). Random forests. Machine learning, 45(1), 5-32.. Случайный лес можно определить как бэггинг над деревьями решений с дополнительным источником случайности: в процессе построения каждого узла дерева выбор очередной переменной для разбиения происходит не из всех p признаков, а лишь из случайного подмножества размера m \approx \sqrt{p} (для классификации) или m \approx p/3 (для регрессии). Эта декорреляция базовых деревьев усиливает эффект бэггинга, дополнительно снижая дисперсию ансамбля без существенного увеличения смещения.

Формально, каждое дерево T_b обучается на бутстрэп-выборке \mathcal{D}^{*b}, и для каждого разбиения выбирается оптимальный признак только из m случайно отобранных кандидатов. Предсказание леса строится как большинство голосов (классификация) или среднее (регрессия).

Out-of-bag-оценивание

Одним из наиболее элегантных свойств методов на основе бутстрэпа является возможность out-of-bag-оценивания (OOB, вне-сумки). При генерации бутстрэп-выборки размера n каждый объект исходной выборки имеет вероятность не попасть в нее, равную (1 - 1/n)^n. При n \to \infty эта вероятность стремится к e^{-1} \approx 0.368. Таким образом, для каждого базового алгоритма в среднем около 36.8% данных остаются неиспользованными в обучении. Эти наблюдения и называются out-of-bag.

Агрегируя предсказания модели только по тем деревьям, для которых наблюдение было в OOB-выборке, можно получить несмещенную оценку ошибки обобщения без необходимости выделения отдельной валидационной выборки и без перекрестной проверки (кросс-валидации). В случайных лесах OOB-ошибка является стандартным критерием качества и часто асимптотически стремится к ошибке leave-one-out кросс-валидацииHastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning. Springer. (Глава 7.3)..

Формально, OOB-предсказание для объекта \mathbf{x}_i вычисляется как агрегация по подмножеству деревьев \mathcal{B}i, которые обучались без этого объекта: \hat{f}_{OOB}(\mathbf{x}_i) = aggr_{b \in \mathcal{B}_i} \, f_b(\mathbf{x}_i)

Доверительные интервалы и оценка неопределенности модели

Помимо агрегирования моделей, бутстрэп активно применяется для квантификации неопределенности (uncertainty quantification) предсказаний любых моделей «черного ящика». Поскольку современные нейронные сети и градиентный бустинг не являются вероятностными по своей природе (в отличие от линейной регрессии), стандартные формулы для расчета доверительных интервалов неприменимы.

Методология построения бутстрэп-доверительных интервалов для предсказаний:

Из исходного набора данных генерируется B бутстрэп-выборок. На каждой выборке b заново обучается полная модель f_b (это вычислительно дорого, но возможно для ансамблей или небольших нейросетей). Для новой точки \mathbf{x}_{\text{new}} вычисляется предсказание каждой из B моделей. Полученный вектор { \hat{y}^{1}, \dots, \hat{y}^{B} } аппроксимирует выборочное распределение предсказания. На основе этого распределения строятся эмпирические доверительные интервалы, например, перцентильный метод, где границами 95% интервала служат 2.5-й и 97.5-й перцентили бутстрэп-распределения.

Аналогичный подход используется для оценки стабильности отбираемых признаков (feature selection stability). В задачах с высокой размерностью (геномика, анализ текстов) важно понять, насколько итоговый набор отобранных моделью признаков воспроизводим при малых флуктуациях данных. Анализируя частоту, с которой конкретный признак X_j попадает в топ-K важных или с ненулевым коэффициентом в лассо-моделях, обученных на разных бутстрэп-выборках, можно отличить стабильно значимые предикторы от шумаMeinshausen, N., & Bühlmann, P. (2010). Stability selection. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 72(4), 417-473..

Ограничения и предостережения

Несмотря на универсальность, бутстрэп имеет принципиальные ограничения, которые должен учитывать инженер:

Зависимые данные. Классический бутстрэп предполагает независимость и одинаковую распределенность (i.i.d.) наблюдений. Применение к временным рядам или пространственным данным без модификаций приводит к некорректным оценкам дисперсии. Для таких случаев существуют специализированные версии: блочный бутстрэп, стационарный бутстрэп.

Выбросы и «тяжелые хвосты». Поскольку бутстрэп-выборки извлекаются из эмпирического распределения, статистики, чувствительные к экстремальным значениям (например, размах выборки), могут вести себя нестабильно.

Вычислительная стоимость. Обучение B сложных моделей с нуля может быть крайне ресурсоемким. В связи с этим для глубоких нейронных сетей чаще применяют более легковесные методы вроде MCMC-вариантов Dropout (MC Dropout)Gal, Y., & Ghahramani, Z. (2016). Dropout as a bayesian approximation: Representing model uncertainty in deep learning. International conference on machine learning. или ансамблирования небольшого числа моделей, обученных с разных начальных инициализаций.

Литература

  • Breiman, L. (1996). Bagging predictors. Machine learning, 24(2), 123-140.
  • Breiman, L. (2001). Random forests. Machine learning, 45(1), 5-32.
  • Efron, B. (1979). Bootstrap methods: Another look at the jackknife. The Annals of Statistics, 7(1), 1-26.
  • Efron, B., & Tibshirani, R. J. (1994). An Introduction to the Bootstrap. Chapman and Hall/CRC.
  • Gal, Y., & Ghahramani, Z. (2016). Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In International conference on machine learning (pp. 1050-1059). PMLR.
  • Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer. (Глава 7: Model Assessment and Selection).
  • Meinshausen, N., & Bühlmann, P. (2010). Stability selection. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 72(4), 417-473.
Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%91%D1%83%D1%82%D1%81%D1%82%D1%80%D1%8D%D0%BF»
Личные инструменты