Бэггинг и Random Forest

Мотивация

Решающие деревья неустойчивы: два дерева, обученных на слегка разных подвыборках, дают сильно отличающиеся результаты. Идея: обучить несколько моделей и усреднить их прогнозы.

Бутстрап (Bootstrap)

Генерация подвыборки из \(\mathbb{X}\) путём выбора \(\ell\) объектов с возвращением:

\[\mathbb{X} \to \bar{\mathbb{X}}_1, \dots, \bar{\mathbb{X}}_N\]

Каждая подвыборка содержит примерно 63% уникальных объектов исходной выборки.

Бэггинг (Bootstrap Aggregating)

Обучаем \(N\) базовых моделей на бутстрап-подвыборках:

\[b_n(x) = \mu(\bar{\mathbb{X}}_n), \quad n = 1, \dots, N\]

Итоговая композиция:

\[a_N(x) = \frac{1}{N} \sum_{n=1}^N b_n(x)\]

Влияние на bias и variance

\[\text{bias}(a_N) = \text{bias}(b_n)\]

\[\text{var}(a_N) = \frac{1}{N}\text{var}(b_n) + \frac{N(N-1)}{N^2}\text{cov}(b_n(x), b_m(x))\]

Бэггинг не меняет bias. Если базовые модели слабые — композиция тоже будет слабой. Variance снижается тем сильнее, чем менее скоррелированы базовые модели.

Теоретическая оценка

При допущении об отсутствии корреляции ошибок базовых моделей (\(\mathbb{E}\varepsilon_i(x)\varepsilon_j(x) = 0,\ i \neq j\)) и несмещённости (\(\mathbb{E}\varepsilon_j(x) = 0\)):

\[\mathbb{E}\left(\frac{1}{N}\sum_{n=1}^N b_n(x) - y\right)^2 = \frac{E_1}{N}\]

Усреднение \(N\) моделей снижает ошибку в \(N\) раз. На практике это не достигается из-за корреляции между моделями, но эффект всё равно существенный.

Random Forest

Ключевая идея: чтобы снизить корреляцию деревьев, при построении каждого сплита признак выбирается не из всего пространства, а из случайного подмножества размера \(k\).

Алгоритм

  • Деревья обучаются с большой глубиной (например, \(\text{min\_sample\_leaf} = 3\)).
  • Каждое дерево обучается на бутстрап-подвыборке.
  • В каждой вершине признак выбирается из подвыборки размера \(k\).

Рекомендации по выбору \(k\)

Задача Рекомендуемый \(k\)
Классификация \(k = \sqrt{d}\)
Регрессия \(k = d / 3\)

Итоговый прогноз

  • Классификация: \(\mathop{\text{argmax}}_{y \in \mathbb{Y}} \sum_{n=1}^N b_n(x)\) — голосование большинством.
  • Регрессия: \(\frac{1}{N} \sum_{n=1}^N b_n(x)\) — среднее.

Гиперпараметры

  • Число деревьев \(N\) — можно брать большим, качество монотонно растёт и стабилизируется.
  • Размер подвыборки признаков \(k\).
  • Максимальная глубина дерева.

Ограничения

  • Медленно обучается на больших данных.
  • Если \(\text{bias}(b_n) \gg 0\), RF будет плох — нужны достаточно глубокие деревья.

Out-of-Bag (OOB) оценка

Поскольку каждое дерево обучалось не на всех объектах, на объектах, не вошедших в подвыборку, можно считать ошибку без отдельной валидационной выборки:

\[\text{OOB} = \frac{1}{\ell} \sum_{i=1}^\ell L\left(y_i,\ \frac{\sum_{n=1}^N [x_i \notin \bar{\mathbb{X}}_n]\ b_n(x_i)}{\sum_{n=1}^N [x_i \notin \bar{\mathbb{X}}_n]}\right)\]

OOB-оценка близка к LOO-кросс-валидации и не требует дополнительных вычислений.

Важность признаков (permutation importance)

Важность \(j\)-го признака оценивается как прирост ошибки при случайном перемешивании значений этого признака в тестовой выборке:

\[q_j = Q^\text{test}_j - Q^\text{test}\]

  • \(q_j \approx 0\) — признак не важен.
  • \(q_j > 0\) — признак важен.
  • \(q_j < 0\) — ошибка в данных или в коде.
Permutation importance можно применять не только к Random Forest, но и к любой другой модели.

Стекинг (Stacking)

Более сложный вариант ансамблирования. Выборка делится на \(K\) фолдов. Базовые модели \(b_n\) обучаются на \(\mathbb{X} \setminus \mathbb{X}_k\), а мета-модель \(a\) обучается на их предсказаниях:

\[\sum_{k=1}^K \sum_{(x_i, y_i) \in \mathbb{X}_k} L\left(y_i, a(b_1^{-k}, \dots, b_n^{-k})\right) \to \min_a\]

← Назад к списку тем