Деревья решений и ансамбли

Дерево решений — модель из вопросов «признак больше порога?». Само по себе оно слабое и капризное, но сотня деревьев, собранных в Random Forest или градиентный бустинг, — до сих пор чемпион по табличным данным и обязательный пункт собеседования.

Интуиция

Дерево решений (decision tree) играет в «двадцать вопросов»: «доход выше 80 тысяч? стаж больше 2 лет?» — и после серии вопросов выносит вердикт. Каждый вопрос режет пространство признаков вертикальной или горизонтальной границей, поэтому области решений у дерева всегда «ступенчатые» — из прямоугольников.

Как дерево выбирает вопросы

Обучение жадное (greedy): в каждом узле дерево перебирает все признаки и пороги и выбирает разрез, который сильнее всего уменьшает «грязность» (impurity) получившихся половинок. Стандартная мера — индекс Джини (Gini impurity):

Gini равен нулю, когда в узле один класс, и максимален при смеси 50/50. Разрезав данные, дерево рекурсивно повторяет процедуру в каждой половинке — пока узлы не станут чистыми или не кончится глубина. Жадность означает: выбирается лучший разрез сейчас, без заглядывания вперёд, поэтому дерево не гарантирует глобально оптимального разбиения.

Глубина (max depth) — главный регулятор сложности. Дерево глубины 1 (пень, stump) проводит одну границу и почти всегда недообучено. Дерево глубины 20 выучивает каждую точку — включая шум: на трейне точность 100%, на тесте провал. Это модель с низким смещением и огромным разбросом (low bias, high variance) — про сам компромисс см. переобучение и регуляризацию.

Бэггинг и Random Forest

Бэггинг (bagging, bootstrap aggregating) лечит нестабильность усреднением: делаем B бутстреп-выборок (bootstrap — выборка с возвращением того же размера), на каждой обучаем своё дерево, ответы усредняем (или голосуем). Ошибки независимых деревьев частично взаимно гасятся, и разброс (variance) падает, а смещение почти не меняется. Random Forest добавляет второй источник разнообразия: в каждом узле дерево выбирает лучший разрез не среди всех признаков, а среди случайного подмножества — деревья получаются менее похожими, и усреднение работает ещё лучше. Поэтому в лесу деревья можно (и нужно) растить глубокими: переобученность каждого гасится ансамблем. Бонус: объекты, не попавшие в бутстреп дерева (~37%), дают бесплатную out-of-bag оценку качества.

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

Бустинг (boosting) строит деревья не параллельно, а последовательно: каждое следующее неглубокое дерево обучается исправлять ошибки текущего ансамбля — в градиентном бустинге (gradient boosting) оно приближает антиградиент функции потерь, то есть «направление исправления» (родство с градиентным спуском не случайно: это спуск в пространстве функций). Ансамбль наращивается с малым шагом — learning rate. Бустинг в первую очередь снижает смещение (bias), поэтому базовые деревья берут слабые и неглубокие. Индустриальный стандарт — реализации XGBoost, LightGBM и CatBoost: с регуляризацией, обработкой пропусков и категориальных признаков из коробки.

Запомни контраст: RF борется с variance (усредняет глубокие независимые деревья, почти не переобучается, мало настроек), бустинг борется с bias (последовательно наращивает точность, выжимает максимум качества, но чувствителен к числу итераций и learning rate). На табличных данных бустинг чаще всего обходит и лес, и нейросети: деревья нечувствительны к масштабу признаков, дружат с категориями и пропусками и не требуют гигантских выборок.