Модуль 6. Деревья и ансамбли

После этого модуля вы сможете

• Написать решающее дерево с нуля и объяснить, что именно оно оптимизирует на каждом разбиении.
• Показать, почему усреднение независимых моделей уменьшает ошибку — формулой из модуля 2.
• Отличить бэггинг от бустинга по тому, что каждый из них лечит.
• Обучить градиентный бустинг руками и побить им линейную модель на табличных данных.
• Объяснить, почему важности признаков нельзя верить при коллинеарности.

Время: около двух недель. Пререквизиты: модуль 5. Ноутбук: notebooks/06-trees-and-ensembles.ipynb

Зачем это

Табличные данные — большая часть задач, которые решают за деньги. Отток, скоринг, спрос, брак, риск. И на них с 2016 года выигрывает градиентный бустинг, а не нейросети.

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

Отсюда практическое следствие для всего оставшегося курса. Прежде чем обучать сеть на таблице, обучите бустинг. Если сеть его не обыграла, значит вы построили сложную модель ради сложности.

Решающее дерево

Дерево задаёт вопросы по одному признаку за раз: «возраст меньше 35?», «сумма больше 10 000?». Ответ ведёт в левую или правую ветку, и так до листа, где лежит предсказание.

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

Для регрессии мера разнобоя — дисперсия. Качество разбиения:

\[\text{выигрыш} = \mathrm{Var}(\text{узел}) - \frac{n_L}{n}\mathrm{Var}(L) - \frac{n_R}{n}\mathrm{Var}(R)\]

Для классификации то же самое с критерием Джини \(\sum_k p_k(1 - p_k)\) или с энтропией. Разница между ними на практике почти не видна.

Три свойства делают дерево удобным именно на таблицах.

Масштаб не важен. Дерево сравнивает признак с порогом. Умножьте признак на тысячу — порог умножится на тысячу, дерево не изменится. Всё, что в модуле 4 говорилось про нормализацию и число обусловленности, здесь просто не возникает.

Монотонные преобразования не важны. Логарифм признака даёт то же дерево. Линейной модели логарифм меняет всё.

Взаимодействия ловятся сами. Путь от корня до листа — это конъюнкция условий. Линейная модель требует, чтобы произведение признаков ей подсунули руками.

Плата — дерево переобучается охотно. Глубина \(d\) даёт до \(2^d\) листьев, и при достаточной глубине в каждом листе окажется по одному объекту. Это ровно многочлен четырнадцатой степени из модуля 2, только в другой одежде.

Бэггинг: усреднение

Одно глубокое дерево имеет маленькое смещение и огромный разброс: поменяйте несколько объектов в обучении — получите другое дерево.

Из модуля 2 известно, что делать с разбросом. Усреднить.

Бэггинг: обучить \(M\) деревьев на разных бутстрэп-выборках (тот же приём, что в модуле 1) и усреднить предсказания. Если ошибки деревьев независимы, дисперсия среднего падает в \(M\) раз. Это та же формула \(\sigma/\sqrt{n}\), применённая к моделям вместо наблюдений.

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

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

Обратите внимание на логику: качество ансамбля улучшают, ухудшив каждое отдельное дерево. Это не парадокс, а прямое следствие формулы для дисперсии среднего.

Условие, о котором обычно молчат

У раскорреляции есть цена: каждое дерево видит меньше признаков и потому хуже. Выигрыш перекрывает плату, только когда признаков много и сигнал по ним размазан.

На пяти признаках, три из которых несут почти весь сигнал, дерево с двумя случайными признаками на узле регулярно не видит ни одного информативного. Лес там проигрывает обычному бэггингу, и в ноутбуке это измерено: 0.545 против 0.513.

Это та же история, что с моментом в модуле 4. Приём лечит конкретную болезнь, и на здоровом организме он вредит.

Бустинг: исправление остатков

Бэггинг борется с разбросом. Бустинг борется со смещением, и делает это иначе — не параллельно, а последовательно.

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

1. Начать с константы — среднего значения цели.
2. Посчитать остатки: чего не хватает до правильного ответа.
3. Обучить неглубокое дерево предсказывать эти остатки.
4. Добавить его предсказание к общему с маленьким коэффициентом.
5. Вернуться к шагу 2.

Почему это называется градиентным бустингом: для квадратичной потери остаток \(y - \hat{y}\) и есть антиградиент потери по предсказанию. Каждое дерево делает шаг против градиента — та же строка, что в модуле 4, только шаг делается в пространстве функций, а не весов.

Отсюда и параметры, которые придётся настраивать:

Параметр	Что делает	Куда крутить
Число деревьев	сколько шагов спуска	больше — точнее и дольше, до переобучения
Скорость обучения	длина шага	меньше — надёжнее, нужно больше деревьев
Глубина дерева	сложность одного шага	3–8 обычно; глубже редко помогает
Доля выборки на дерево	шум, как в SGD	0.5–1.0

Скорость обучения и число деревьев связаны обратно, ровно как \(\eta\) и число шагов в модуле 4. Уменьшили скорость вдвое — увеличивайте число деревьев вдвое.

Почему бустинг выигрывает на таблицах

Четыре структурные причины, и ни одна не про «он лучше».

Признаки таблицы неоднородны. Возраст, сумма, категория, флаг — разные единицы, разные распределения. Дерево берёт каждый по отдельности, сети приходится их согласовывать.

Целевая функция кусочно-постоянна. Реальные табличные зависимости часто имеют пороги: скидка после суммы, риск после возраста. Дерево строит пороги напрямую, сеть аппроксимирует их гладкими функциями и тратит на это ёмкость.

Данных мало. Табличная задача — это тысячи или десятки тысяч строк, а не миллионы картинок. Сети нужен объём, которого здесь нет.

Нет структуры, из которой сеть извлекает пользу. Свёртки выигрывают на изображениях, потому что соседние пиксели связаны. Внимание выигрывает на тексте по той же причине. Столбцы таблицы можно переставить местами, и ничего не изменится — извлекать нечего.

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

Важность признаков

Деревья дают важности почти бесплатно: сумма выигрышей по всем разбиениям на этом признаке. Число выглядит убедительно и обманывает регулярно.

Коллинеарность отбирает важность. Добавьте копию информативного признака, и дерево на первом же узле выберет одного из двух близнецов, а второй окажется почти не нужен. В ноутбуке это измерено: важность падает с 60 % до 3 %, копия забирает 57 %. Не «делится пополам» — перехватывается почти целиком, и как именно, зависит от случайности. То же явление, что разъезжающиеся веса в модуле 3, в другой одежде.

Признаки с большим числом уровней получают фору. У непрерывного признака больше возможных порогов, значит больше шансов случайно дать хорошее разбиение.

Важность не означает причину. Признак может быть важен, потому что он следствие цели, а не её причина. Это утечка, и в модуле 7 она разбирается отдельно.

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

Практика

Часть 1. Ноутбук

Откройте notebooks/06-trees-and-ensembles.ipynb.

Что внутри:

1. Решающее дерево с нуля, около шестидесяти строк. Видно, что оно ступенчатое.
2. Глубина против переобучения: те же две кривые, что в модуле 2.
3. Бэггинг: измеряем, как падает разброс предсказаний с ростом числа деревьев, и сверяем с \(1/M\).
4. Градиентный бустинг с нуля на пеньках.
5. Скорость обучения против числа деревьев: обратная связь на графике.
6. Бустинг против линейной модели на табличных данных с порогами и взаимодействием.
7. Важности при коллинеарных признаках: как они делятся пополам.

Часть 2. Бустинг как базовая линия

Возьмите любую свою табличную задачу.

1. Обучите линейную модель из модуля 5. Запишите метрику.
2. Обучите бустинг. Запишите метрику.
3. Настройте оба одинаковым бюджетом попыток. Из модуля 1: асимметрия настройки — самый частый способ получить улучшение, которого нет.
4. Сравните с доверительными интервалами по нескольким разбиениям, а не по одному числу.
5. Запишите вывод одной фразой в формате модуля 1: величина, условия, база.

Этот результат понадобится в частях III и IV. Когда там появится сеть, сравнивать её будет с чем.

Задание

1. Допишите в своё дерево критерий Джини и решите им задачу классификации.
2. Постройте зависимость ошибки бэггинга от числа деревьев. Совпадает ли падение с \(1/M\)? Если нет — объясните через корреляцию деревьев.
3. Реализуйте случайные подмножества признаков и покажите, что лес лучше бэггинга на тех же данных.
4. Возьмите бустинг и постройте кривые ошибки на обучении и на валидации по числу деревьев. Найдите момент, где начинается переобучение.
5. Постройте задачу, на которой линейная модель выигрывает у бустинга. Объясните, чем эти данные отличаются.

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

Проверка себя

1. Что оптимизирует дерево на каждом разбиении?
2. Почему дереву не нужна нормализация признаков, а линейной модели нужна?
3. Почему случайный лес специально ухудшает каждое отдельное дерево?
4. Чем бэггинг отличается от бустинга по тому, что они лечат?
5. Почему бустинг называется градиентным?
6. Как связаны скорость обучения и число деревьев?
7. Назовите две структурные причины, по которым бустинг выигрывает на таблицах.
8. Почему важности признаков нельзя верить при коллинеарности?

Дальше

Модели есть, метрики есть. В модуле 7 — как их честно сравнивать: разбиения, кросс-валидация, утечки и подглядывание в тест. Это последний модуль части II и самый короткий, но именно он решает, значат ли что-нибудь все числа, полученные раньше.

Перед сетью на таблице обучите бустинг. Если сеть его не обыграла, вы построили сложность ради сложности.