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

Чему вы научитесь в этом модуле

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

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

Зачем нужен этот модуль¶

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

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

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

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

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

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

Для задач регрессии мерой неоднородности служит дисперсия. Качество конкретного разбиения оценивается так:

\[\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 мы знаем, что делать с большим разбросом. Усреднить несколько независимых оценок.

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

Ключевое слово здесь — «если». Деревья, обученные на пересекающихся бутстрэп-выборках (а они существенно пересекаются), оказываются скоррелированными между собой, и реальный выигрыш от усреднения оказывается меньше теоретически обещанного.

Случайный лес (Random Forest) борется с этой корреляцией дополнительным приёмом: на каждом разбиении дерево рассматривает не все имеющиеся признаки, а лишь случайно выбранное подмножество. Благодаря этому деревья вынуждены «смотреть» на разные аспекты данных, их ошибки становятся более разнообразными (менее коррелированными), и усреднение работает эффективнее.

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

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

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

При малом числе признаков (скажем, пять), из которых три несут практически весь полезный сигнал, дерево, которому доступны лишь два случайных признака на каждом узле, регулярно не видит ни одного информативного. В таком случае случайный лес проигрывает обычному бэггингу, и в ноутбуке это измерено: ошибка 0.545 против 0.513.

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

Бустинг: последовательное исправление ошибок¶

Бэггинг борется с разбросом (дисперсией) предсказаний. Бустинг борется с другой проблемой — со смещением, и делает это принципиально иным способом: не параллельно (обучая модели одновременно и независимо), а последовательно.

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

Начать с самого простого предсказания — константы, равной среднему значению целевой переменной.
Вычислить остатки: разность между правильными ответами и текущими предсказаниями (то, чего не хватает до правильного ответа).
Обучить неглубокое дерево предсказывать эти остатки.
Добавить предсказание нового дерева к общему предсказанию, умножив его на маленький коэффициент (скорость обучения).
Вернуться к шагу 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.

Что содержится внутри:

Решающее дерево с нуля — примерно шестьдесят строк кода. Наглядно видно, что предсказание дерева является ступенчатой (кусочно-постоянной) функцией.
Глубина дерева и переобучение: строим те же два графика ошибок (на обучении и на тесте), что и в модуле 2.
Бэггинг: измеряем, как уменьшается разброс предсказаний с ростом числа деревьев, и сверяем с теоретической зависимостью \(1/M\).
Градиентный бустинг с нуля на простых «пеньках» (деревьях глубины 1).
Скорость обучения и число деревьев: визуализация обратной связи между ними.
Бустинг против линейной модели на табличных данных с пороговыми зависимостями и взаимодействиями между признаками.
Важности признаков при коллинеарности: демонстрация того, как одна копия перехватывает практически всю важность, а не делит её поровну.

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

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

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

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

Задание¶

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

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

Проверка усвоения¶

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

Что дальше¶

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

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