Деревья. Случайный лес. Градиентный бустинг

Введение

В данной главе рассматриваются методы анализа больших массивов данных, основанные на деревьях решений и их ансамблях. Мы изучим регрессионные деревья, проблему смещения и разброса (bias-variance), а также методы объединения моделей: бэггинг (Bagging), случайный лес (Random Forest) и бустинг (Boosting), включая градиентный бустинг.

1. Деревья решений

Регрессия

При построении деревьев для задач регрессии используется критерий качества разбиения. Обозначения из лекции:

• $G_{x_i, t_j} = L_Q H_L + R_Q H_R$
• MSE (Среднеквадратичная ошибка): $H_R = \frac{1}{N} \sum_{i}^{N} (y_m - y_i)^2$, где $y_m$ — среднее значение.
• MAE (Средняя абсолютная ошибка): $H_R = \frac{1}{N} \sum_{i}^{N} |y_m - y_i|$, где $y_m$ — медиана.

Оптимизация

Сложность алгоритмов построения деревьев оценивается следующим образом:

• Сложность подготовки: $O(N \cdot \log N \cdot d)$, где $d$ — количество признаков, $N$ — количество объектов. Необходимо отсортировать все признаки перед тем, как считать ошибку на разных разбиениях.
• Сложность ошибки: $O(N)$.
• Сложность нахождения оптимального разбиения: $O(N^2 d)$.

Существуют методы оптимизации пересчета ошибок. Например, переход от суммы квадратов отклонений для $N$ объектов к сумме для $N-1$ объектов может быть выполнен за $O(1)$ для одного пересчёта при использовании определенных формул преобразования сумм. Также применяются эвристические оптимизации, например, рассмотрение случайного набора признаков в каждой вершине.

2. Смещение и Разброс (Bias-Variance)

Decomposition of Error

Рассмотрим модель зависимости истинных значений от функции: $$y = f(x) + \varepsilon$$ где:

• $y$ — истинные значения;
• $f(x)$ — закон природы;
• $\varepsilon$ — ошибка измерения ($\varepsilon \in N(0, \sigma^2)$, математическое ожидание $M\varepsilon = 0$).

Таким образом, $y \in N(f(x), \sigma^2)$, математическое ожидание $My = f(x)$.

Рассмотрим семейство функций-регрессоров $b = b(x)$, приближенных к $f(x)$. В конкретной точке множество регрессоров даст множество значений. У $b(x)$ есть математическое ожидание и дисперсия.

Разложение среднеквадратичной ошибки (MSE): $$MSE = M(y - b)^2 = M(y^2) + M(b^2) - 2M(by)$$

Используя свойства дисперсии $Var(x) = Dx = M(x - Mx)^2 = Mx^2 - M[x]^2$:

1. $My^2 = Dy + M[y]^2 = \sigma^2 + f^2$
2. $Mb^2 = Db + M[b]^2$
3. $Mby = M(f + \varepsilon)b = Mfb + M\varepsilon b = fMb + M\varepsilon Mb = fMb$

Подставляя в формулу MSE: $$MSE = \sigma^2 + f^2 + Db + Mb^2 - 2fMb = (f - Mb)^2 + Db + \sigma^2$$

Где:

• $(f - M[b]) = \text{bias}$ (смещение);
• $Db = \text{variance}$ (разброс);
• $\sigma^2$ — неустранимая ошибка.

Итоговая формула decomposition: $$MSE = \text{bias}^2 + \text{variance} + \sigma^2$$

Влияние сложности модели

• Сложные модели склонны иметь большое значение variance из-за переобучения.
• Простые модели склонны иметь большое значение bias.

3. Ансамбли моделей

Мудрость толпы

На ярмарке проводилась лотерея: нужно было угадать вес быка по внешнему виду.

• Участвовало 800 человек.
• Реальный вес быка: 1198 фунтов.
• Ни один человек не угадал точный вес.
• Среднее арифметическое их предсказаний: 1197 фунтов.

Почему так? Каждый, основываясь на своём «независимом» опыте, ошибался в большую или меньшую сторону, но «в среднем» одинаково.

Бэггинг (Bagging)

Идея заключается в усреднении предсказаний нескольких классификаторов или регрессоров. Чтобы дать моделям разный «опыт», их обучают на разных данных. Используется метод Bootstrap: элемент из общей выборки берётся случайным образом, при этом один и тот же элемент может быть взят несколько раз.

Пусть $b_1(x), ..., b_n(x)$ — модели регрессии, $f(x)$ — функция истинных значений. Квадратичная ошибка $i$-й модели: $\varepsilon_i^2(x) = (b_i(x) - f(x))^2$. Если усреднить ошибку всех моделей, получим $\frac{1}{n} M_x [\sum \varepsilon_i^2(x)]$.

Предположим, что ошибки несмещены ($M_x \varepsilon_i(x) = 0$) и некоррелированы ($M_x \varepsilon_i(x)\varepsilon_j(x) = 0$ при $i \neq j$). Построим новую модель: $$a(x) = \frac{1}{n} \sum_{i}^{n} b_i(x)$$

Тогда среднеквадратичная ошибка новой модели: $$M_x \left( \frac{1}{n} \sum_{i}^{n} b_i(x) - f(x) \right)^2 = M_x \left( \frac{1}{n} \sum_{i}^{n} \varepsilon_i(x) \right)^2 = \frac{1}{n^2} M_x \sum_{i}^{n} \varepsilon_i^2(x)$$

Вывод: Бэггинг снижает variance в ошибке (снижает эффект переобучения) примерно в $n$ раз (при условии некоррелированности). Модели «в среднем» ошибаются одинаково, но в разные стороны. В меньшее число моделей попадают выбросы.

Случайный лес (Random Forest)

Метод развивает идею бэггинга для деревьев:

1. Обучаем деревья на разных подвыборках.
2. Чтобы повысить некоррелированность деревьев, при построении узла дерева ищем наилучшее разбиение не по всем признакам, а лишь по части.

Гиперпараметры: количество деревьев + гиперпараметры дерева.

• В регрессии выбираем среднее.
• В классификации выбираем большинство.

Преимущества:

• Высокая точность.
• Менее чувствителен к выбросам.
• Менее склонен к переобучению.
• Хорошо параллелится.
• Хорошо работает с дефолтными параметрами.

Недостатки:

• Сложно интерпретировать.
• Плохо работает с разреженными признаками.
• Не экстраполируется.
• Требует много памяти.

4. Бустинг

AdaBoost и случайные пни

В бустинге элементы, на которых модель ошиблась, будут иметь больший вес на следующих шагах. Часто используются «пни» — деревья глубиной 1.

Градиентный бустинг: Пример

Задача: Предсказать цену товара по возрасту (в днях). Допустим, есть только один признак.

Шаг 1: Начальное приближение — среднее по выборке. Цены: 700, 800, 600, 400, 300. Среднее: $(700+800+600+400+300) / 5 = 560$.

Считаем остатки (цена - приближение):

Шаг 2: Строим регрессионное дерево, которое предсказывает остатки. Разбиение по признаку Возраст >= 80:

• Ветка 1 (Age < 80): Остатки 140, 240, 40. Среднее: 140.
• Ветка 2 (Age >= 80): Остатки -160, -260. Среднее: -210.

Шаг 3: Прибавляем предсказание дерева к приближению (можно с коэффициентом, в примере без него).

Далее процесс продолжается: строим деревья дальше, изменяем приближение, считаем новые остатки.

Градиентный бустинг: Формализация

На $t$-м шаге модель представляет собой сумму функций: $$f(x) = \sum_{i=0}^{t-1} f_i(x)$$

Параметры нового шага находятся через минимизацию функции потерь $L$: $$\rho_t, \theta_t = \arg\min_{\rho, \theta} M_{x,y} [L(y, f(x) + \rho h(x, \theta))]$$ где $f_t(x) = \rho_t h(x, \theta_t)$.

Остаток на $i$-м элементе (градиент): $$r_{i,t} = - \left[ \frac{\nabla L(y_i, f(x_i))}{\nabla f(x_i)} \right]$$ Мы хотим уменьшить этот остаток новой функцией.

1. Параметры дерева: $\theta_t = \arg\min_{\theta} \sum_{i}^{n} (r_{i,t} - h(x_i, \theta))^2$
2. Параметры «линейной регрессии» (шаг): $\rho_t = \arg\min_{\rho} \sum_{i}^{n} L(y_i, f(x_i) + \rho h(x_i, \theta_t))$

Случай MSE: Для среднеквадратичной ошибки остаток равен разнице между истинным значением и предсказанием: $$r_{i,t} = - \frac{\nabla L}{\nabla f} = -2(y_i - y_i) \rightarrow \text{разница между истинным значением и предсказанием}$$

Сравнение Градиентного бустинга и Бэггинга

• Точность: Градиентный бустинг точнее, чем Bagging и Random Forest.
• Переобучение: Бустинг любит переобучаться. Нужна тестовая выборка. Если переобучить дерево в начале цепочки, остальные деревья не смогут исправить это переобучение. Поэтому гиперпараметры деревьев выбирают так, чтобы они были достаточно «глупые».
• Параллелизм: Деревья строятся последовательно. Параллелизм возможен только на уровне построения одного дерева (в отличие от Random Forest).
• Линейные модели: С логистической регрессией работает нормально.