Градиентный бустинг остаётся главным инструментом для табличных данных, поэтому деревья и ансамбли спрашивают на каждом собесе DS: от «посчитай Джини» до «как XGBoost использует вторые производные».
Дерево решений
Дерево рекурсивно делит данные условиями вида «признак ≤ порог». В каждом узле оно жадно перебирает признаки и пороги и выбирает разбиение, сильнее всего уменьшающее взвешенную нечистоту детей.
Критерии для классификации:
Gini = 1 - Σ pₖ²
Entropy = -Σ pₖ log₂ pₖ
Узел с 6 объектами класса A и 2 класса B: Gini = 1 - 0.75² - 0.25² = 0.375. Прирост информации это энтропия родителя минус взвешенная энтропия детей. Для регрессии критерий обычно MSE.
Свойства деревьев:
- не нужно масштабировать признаки: порог инвариантен к монотонным преобразованиям;
- ловят нелинейности и взаимодействия;
- глубокое дерево легко переобучается (высокий variance).
Регуляризация: максимальная глубина, минимум объектов в листе, минимальный прирост, прунинг.
Бэггинг и случайный лес
Бэггинг: обучить много моделей на бутстреп-выборках и усреднить. Снижает variance, bias почти не меняется. Поэтому базовые модели берут глубокими.
Случайный лес добавляет случайное подмножество признаков на каждом разбиении (часто √d для классификации). Деревья становятся менее коррелированными, и усреднение работает лучше: дисперсия среднего упирается в корреляцию моделей.
Плюсы: мало гиперпараметров, параллелится, не переобучается от добавления деревьев, есть OOB-оценка: около 37% объектов не попадают в бутстреп каждого дерева, на них и проверяют.
Градиентный бустинг
Деревья строятся последовательно. Каждое новое аппроксимирует антиградиент функции потерь по текущим предсказаниям ансамбля и добавляется с маленьким шагом:
F_m(x) = F_{m-1}(x) + η · h_m(x)
Для MSE антиградиент это остатки y - F(x), для log loss y - p. Бустинг снижает bias, поэтому деревья неглубокие (глубина 4-8).
XGBoost использует разложение второго порядка: для листа суммирует градиенты G и вторые производные H, оптимальное значение листа -G/(H + λ), а прирост разбиения считается по G²/(H + λ). Это похоже на шаг Ньютона.
Главные гиперпараметры: learning rate и число деревьев (меньше lr требует больше деревьев, число подбирают early stopping), глубина или число листьев, min_child_samples, subsample строк и колонок, L2 на листья.
Библиотеки
- XGBoost: регуляризация, вторые производные, точный и гистограммный режимы.
- LightGBM: гистограммы, рост по листьям (leaf-wise), GOSS, очень быстрый.
- CatBoost: симметричные (oblivious) деревья, кодирование категорий упорядоченными target-статистиками без утечки, хорош из коробки.
Все три умеют GPU, пропуски и категориальные признаки (в разной степени).
Важности признаков
Встроенная важность по нечистоте (MDI) считается на трейне и завышает признаки с большим числом уникальных значений, вплоть до id. Надёжнее permutation importance на валидации или SHAP.
Лес или бустинг
| Случайный лес | Градиентный бустинг | |
|---|---|---|
| Деревья | глубокие, параллельно | неглубокие, последовательно |
| Снижает | variance | bias |
| Настройка | простая | чувствительная, нужен early stopping |
| Качество на таблицах | хорошее | обычно лучшее |
Частые ошибки
- Масштабировать признаки для деревьев «на всякий случай» и думать, что это помогает.
- Уменьшить learning rate и не увеличить число деревьев.
- Верить встроенной важности как доказательству.
- Путать, что снижает бэггинг, а что бустинг.
Что спросят на собесе
- Как дерево выбирает разбиение, посчитать Джини или прирост информации.
- Бэггинг против бустинга, зачем случайность признаков в лесу.
- Почему бустинг градиентный, как связаны lr и число деревьев.
- Чем отличаются CatBoost, LightGBM и XGBoost.