Как с нуля построить регрессионное дерево

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

Ключевыми механизмами, выбиравшими там каждое разбиение, были примесь Джини и прирост информации. Для регрессии мы заменяем примесь Джини дисперсией. Вместо вопроса о том, насколько перемешаны метки, мы спрашиваем, насколько разбросаны значения цели. Хорошее разбиение — то, которое уменьшает этот разброс, измеряемый здесь как уменьшение суммарной квадратичной ошибки.

Критерий разбиения и значение, хранимое в каждом листе, — две стороны одного решения. Примесь узла есть ошибка обучения того ответа, который даст его лист. Джини измеряет цену предсказания долей классов для группы меток; дисперсия измеряет цену предсказания среднего для группы зарплат. Меняется предсказание листа — меняется вместе с ним и подходящая мера ошибки.

Генерация кандидатов, рекурсивное разбиение и правило остановки остаются прежними. Изменить нужно только вычисление примеси и предсказание листа.

Мы также разберём ограничение, которое становится заметно только для числовой цели. Любое предсказание регрессионного дерева — это среднее зарплат из обучающих данных. Поэтому сколько бы сезонов или попаданий вы ему ни показали, оно не предскажет зарплату выше максимальной в обучающей выборке. В классификации такой проблемы нет: возможные ответы ограничены самими метками классов. Числовые значения, напротив, могут выходить за наблюдаемый диапазон, но дерево не умеет за ними следовать.

Тот же механизм

Алгоритм по-прежнему CART, по-прежнему выращивающий бинарное дерево, в котором каждый узел задаёт один вопрос «да или нет» и имеет ровно двоих потомков. Разложенный по шагам, он почти весь работает без изменений. Строя дерево, мы генерируем вопросы-кандидаты, задаём каждый кандидат всем строкам, чтобы разделить их на две группы — ответившую True и ответившую False, — оцениваем кандидата по тому, сколько примеси убирает это разбиение, оставляем лучшего и рекурсивно повторяем с каждой стороны, пока ни один вопрос больше ничего не убирает.

Кандидаты генерируются ровно как раньше — каждый признак в паре с каждым значением, которое он принимает в имеющихся строках, по одной паре на вопрос, причём числовой столбец спрашивает >=, а категориальный ==. Изменился только тип целевого столбца, а предикторы по-прежнему могут быть любого вида. Генератор ничего не знает и знать не хочет о содержимом целевого столбца: пять строк с двумя столбцами по четыре различных значения дают восемь кандидатов независимо от того, предсказываете вы болезнь или зарплату.

Изменить нужно способ оценки группы — то, насколько её строки отличаются друг от друга. В классификаторе функция gini измеряла, насколько перемешаны метки. Для числовой цели используется variance: она показывает, насколько зарплаты отклоняются от своего среднего.

Интересно, что формула прироста информации, которой мы оценивали вопросы, меняться вместе с ней не обязана. Вот так мы оценивали разбиение в классификаторе:

def info_gain(left, right, current_uncertainty):
    p = float(len(left)) / (len(left) + len(right))
    return current_uncertainty - p * gini(left) - (1 - p) * gini(right)

А вот так — в регрессоре, та же функция с одним изменённым именем:

def info_gain(left, right, current_uncertainty):
    p = float(len(left)) / (len(left) + len(right))
    return current_uncertainty - p * variance(left) - (1 - p) * variance(right)

Это то самое вычитание, которое статья о классификаторе разобрала полностью: группа, с которой мы начали, минус каждый потомок, взвешенный долей попавших в него строк. Здесь важно, что оно никогда не спрашивает, что лежит в целевом столбце; оно спрашивает лишь, насколько различаются строки в каждой группе. Подайте ему gini — и разность будет приростом информации; подайте variance — и та же разность станет падением квадратичной ошибки, в квадратных долларах, а не в примеси.

У того, что этот критерий означает, когда цель — число, есть формулировка проще этой формулы, и мы дойдём до неё, построив примесь.

Пять игроков

Набор данных — пять игроков из исследования Hitters: два числовых предиктора и одна числовая цель.

years — число сезонов, отыгранных в высшей лиге, hits — число попаданий в прошлом сезоне, salary — зарплата за сезон 1987 года, в тысячах долларов. Это настоящие строки из настоящего исследования, сверенные с полным файлом.

Измерение разброса набора данных

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

И, как и раньше, мы оцениваем вопрос по тому, сколько этого разброса он убирает, так чтобы после разбиения две группы оказались менее разбросанными, чем та, из которой они вышли. Эта оценка — уменьшение суммарной квадратичной ошибки, аналог прироста информации, и побеждает вопрос, у которого её больше всего.

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

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

Команда B взята из нашего настоящего набора данных — это зарплаты пяти игроков выше; команда A — гипотетический клуб, где все получают примерно поровну.

Один способ — нанести обе на график:

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

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

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

Значит, нам нужны величины без знаков. Сделать это можно двумя способами: взять модули или возвести в квадрат. Сначала сосредоточимся на возведении в квадрат — общепринятом выборе — по двум причинам: оно гладко и дифференцируемо везде, тогда как у модуля в нуле излом, и оно наказывает один большой промах намного сильнее, чем несколько маленьких. Модули, впрочем, — настоящая альтернатива, и позже мы увидим, как их выбор меняет модель.

Возведите отклонения в квадрат и сложите — получится SSE; поделите это на их количество — получится дисперсия:

SSE — это суммарный разброс группы, а дисперсия — средний, та же сумма, делённая на число строк, из которых она получена; обе величины в квадратных единицах, поэтому числа такие большие. Добавьте игроков — и SSE продолжит расти, тогда как дисперсия останется на месте. Обе говорят об этих двух командах одно и то же — 200.00 для команды A и 86,207.50 для команды B, — и более широкая ведомость получает число больше в 431 раз.

Записанная формулой, дисперсия выглядит так:

где $n$ — сколько строк содержит группа, $y_i$ — зарплата одной из них, а $\bar{y}$ — их среднее, так что $y_i - \bar{y}$ есть отклонение одной строки, тот самый столбец, который мы свели в таблицу выше.

Уберите $\frac{1}{n}$, и то, что останется, $\sum_{i=1}^{n}(y_i - \bar{y})^2$, — это SSE.

Только что построенная формула известна как дисперсия генеральной совокупности, и, посмотрев её, вы найдёте рядом вторую версию, выборочную дисперсию, отличающуюся только знаменателем:

Где бы дерево ни делило, оно делит на $n$ — форма для генеральной совокупности, $\sigma^2$, где $n$ есть число строк в группе. (Часто оно не делит вовсе, работая в суммах, — об этом дальше.) Выборочная дисперсия использует $n - 1$, потому что оценивает разброс большей совокупности по горстке вытянутых из неё строк. Лист будет отвечать средним ровно этих строк, поэтому примесь обязана быть ценой ровно этого ответа. Поправка Бесселя, то самое $n - 1$, нужна, чтобы убрать смещение такой оценки, а узлу оценивать нечего.

Почему это правильная примесь

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

Допустим, дерево вообще не разбилось: один лист, содержащий целую команду и предсказывающий среднюю зарплату 420.0 каждому игроку в ней.

Для команды A это хороший ответ: никто там не зарабатывает дальше 20 от него, так что худшее, чем может ошибиться лист, — это 20. Для команды B ответ плохой: Робиду зарабатывает 67.5, а Мозби 787.5, и обоим говорят 420.0, промахиваясь на 352.5 и 367.5. Возведите эти промахи в квадрат, усредните — и вы вернётесь к двум числам из таблицы, 200.00 и 86,207.50: те же дисперсии, прочитанные теперь как ошибка, которую сделал бы каждый лист. Итак, разброс внутри узла — это ошибка, которую сделал бы ответ этого узла, и именно это число дерево сравнивает, решая, какой вопрос задать, предпочитая тот, чьи две группы оставляют её меньше всего.

Всё это уже есть в формуле $\frac{1}{n}\sum_{i=1}^{n}(y_i - \bar{y})^2$. Здесь $\bar{y}$ — те 420.0, которые лист предсказывает каждому, кто в него попал. Каждое $(y_i - \bar{y})$ — ошибка для одного игрока: $-352.5$ для Робиду, $+367.5$ для Мозби и не хуже $\pm 20$ для любого в команде A. Возведение этих ошибок в квадрат и усреднение даёт нам 86,207.50 и 200.00. Дисперсия, таким образом, есть средняя квадратичная ошибка обучения листа, предсказывающего среднее — ошибка, которую всё равно сделал бы лучший возможный постоянный лист.

Классификация и регрессия используют одну и ту же структуру. Лист хранит лучшее постоянное предсказание, а примесь измеряет ошибку этого предсказания. Для классификации это доли классов и примесь Джини; для регрессии — среднее и дисперсия. Примесь вычисляется для каждого кандидата в каждом узле, поэтому её замена может сдвинуть каждое разбиение в дереве. Статистика листа при выборе разбиений не используется: она определяет, что предсказывает готовое дерево, а не какой оно формы.

Среднее или медиана: выбор критерия

Квадратичную ошибку мы выбрали несколькими абзацами выше, когда у отклонений нужно было убрать знаки и мы возвели их в квадрат, а не взяли модули. Это то, что библиотеки ставят по умолчанию: например, scikit-learn использует criterion="squared_error", если не сказать иного. Но это не единственный вариант, и выбор заходит дальше, чем кажется: функция потерь, которой мы оцениваем разбиения при построении, задаёт и то, что лист обязан хранить для предсказания, потому что и то и другое — ответы на один вопрос: какая единственная константа минимизирует эту потерю.

• Минимизируем квадратичную ошибку → лист хранит среднее.
• Минимизируем абсолютную ошибку → лист хранит медиану.

Возьмём лист со значениями [10, 12, 14, 16, 200], где 200 — выброс или ошибка ввода данных:

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

Итак, выбранная нами примесь решает, какую константу хранит лист, и поэтому две функции ниже написаны парой.

def mean(rows):
    return sum(row[-1] for row in rows) / float(len(rows))

def variance(rows):
    targets = [row[-1] for row in rows]
    m = sum(targets) / len(targets)
    return sum((t - m) ** 2 for t in targets) / len(targets)

variance — то, что мы вычисляем, чтобы оценить узел; mean — то, что будет хранить лист. Именно эту пару требует квадратичная ошибка. Абсолютная потребовала бы другую: сумму абсолютных отклонений и медиану в листе. Сейчас у нас есть число для одного узла, регрессионный аналог Джини. Превратить его в оценку разбиения — следующий шаг и аналог прироста информации.

Оценка разбиения

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

Они упорядочивают вопросы-кандидаты одинаково, так что от выбора ничего не зависит. Арифметика в суммах проще, с неё и начнём; усреднённая форма — то, что вычисляет код, и мы вернёмся к ней, когда критерий будет на месте.

Вопрос делит узел на две группы, и каждая отвечает своим средним — $\bar{y}_L$ с одной стороны, $\bar{y}_R$ с другой. Значит, формулу SSE можно применить к каждой группе отдельно, относительно её собственного среднего. Сложив эти две SSE, мы получим остаточную сумму квадратов (RSS) — ошибку, которую разбиение оставляет после себя:

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

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

Оценка по тому, что разбиение убирает

Есть другой способ использовать SSE для оценки вопроса. Примените ту же формулу к родительской группе — строкам до разбиения, индекс $P$ — относительно её собственного среднего $\bar{y}_P$, и вы получите $\text{SSE}_P = \sum_{i=1}^{n_P}(y_i - \bar{y}_P)^2$ — ошибку, которую эта группа делает как есть, отвечая каждой строке одним числом. Так что вместо вопроса, сколько ошибки разбиение оставляет, можно спросить, сколько оно убрало: родительская ошибка минус то, что два потомка всё ещё несут:

Это форма прироста информации, записанная в суммах, а не во взвешенных средних.

И это тот же самый выбор, что и раньше, потому что $\text{SSE}_P$ фиксирована, пока мы сравниваем кандидатов в одном узле: вычитание одной и той же константы из каждой оценки сдвигает их все одинаково и ничего не переставляет. Пусть ошибка родителя равна 100, а два кандидата оставляют 60 и 25:

Кандидат, который оставляет меньше всех, убрал больше всех. Минимизация RSS и максимизация прироста делают одну работу с двух концов.

Прирост никогда не может быть отрицательным. Каждый потомок мог бы сохранить среднее родителя, но вместо этого использует своё — а оно по определению есть константа, минимизирующая его собственную квадратичную ошибку. Поэтому на обучающих строках разбиение всегда не хуже, и поэтому gain == 0 означает «ни один вопрос не помогает», а не «некоторые вопросы вредят». По той же причине ошибка обучения никогда не сможет подсказать дереву, когда остановиться: предоставленная себе рекурсия работает, пока почти у каждой строки не появится собственный лист, так что правило остановки обязано прийти извне критерия — ограничение глубины, минимальное число строк в листе или отсечение постфактум.

Тот же критерий в записи через дисперсию

Прирост записан в суммах, тогда как info_gain — функция из статьи о классификаторе, с variance там, где она звала gini, — записана в средних, взвешивая каждого потомка его долей строк:

def info_gain(left, right, current_uncertainty):
    p = float(len(left)) / (len(left) + len(right))
    return current_uncertainty - p * variance(left) - (1 - p) * variance(right)

p — это доля строк родителя, оказавшихся в левой группе: три строки из пяти дают p = 0.6, оставляя 1 - p = 0.4 правой группе, — и она нужна потому, что мы работаем в средних. Дисперсия ничего не говорит о том, сколько строк её породило, так что потомок из одной строки и потомок из сотни считались бы наравне; а если мы хотим и дальше пользоваться дисперсиями, размеры приходится возвращать руками, чем p и 1 - p ровно и занимаются.

В записи через суммы никакие веса не нужны вовсе:

def gain_sse(rows, left, right):
    return sse(rows) - (sse(left) + sse(right))

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

Подставьте это для всех трёх групп, и прирост станет

а деление на $n_P$ — снова константу в этом узле, снова безвредно — даёт форму, которой пользовалась статья о классификации, и ту, что вычисляет info_gain:

Веса, которые в усреднённой форме выглядят как проектное решение, — это просто числа строк, уже сидевшие внутри сумм. Так что берите любую из трёх форм: числа они сообщают разные, но кандидатов упорядочивают одинаково, и побеждает один и тот же вопрос. Форма с приростом оставляет код классификатора неизменным; форму с RSS вы обычно встретите в учебниках и библиотеках — именно поэтому scikit-learn называет критерий squared_error. Эта статья пользуется приростом, когда цитирует код, и RSS, когда объясняет, что происходит.

Оценка кандидатов в корне

Прогоним теперь этот критерий на первом узле настоящего дерева — на корне, который держит всех пятерых игроков, до того как задан хоть один вопрос. Его среднее равно $2100/5 = 420.0$, а дисперсия — 86,207.50, так что по $\text{SSE} = n \cdot \text{Var}$ квадратичная ошибка, которую мы пытаемся уменьшить, есть $\text{SSE}_P = 5 \times 86{,}207.50 = 431{,}037.5$. Каждый кандидат ниже оценивается относительно этого числа в усреднённой форме — это gain, который печатает наш код, $\text{Var}_P$ минус две взвешенные по размеру дисперсии потомков, — а победителя мы потом прочитаем как RSS.

Вопросы-кандидаты генерируются ровно как раньше — каждый признак в паре с каждым значением, которое он принимает. Два столбца по четыре различных значения дают восемь кандидатов, двое из которых вообще не делят строки. Здесь они выложены от лучшего, хотя код их никогда не сортирует; он просто держит текущего победителя:

Два пропущенных кандидата — наименьшее значение в каждом столбце: years пробегает 2, 2, 3, 6, 7, а hits — 41, 41, 77, 130, 149, — так что каждая строка отвечает на них «да». Всё уходит на сторону True и ничего на сторону False, отсюда 5 / 0: разбиения, которое можно оценить, нет, и они отбрасываются.

Столбец gain — то, что сообщает код, поскольку оценку делает функция info_gain. Прочитайте победителя как суммарную квадратичную ошибку — и критерий станет виднее. Is hits >= 77? отправляет Дэвиса, Маршалла и Мозби в одну сторону, а двух совпавших игроков — в другую:

против $431{,}037.50$ в корне. Один вопрос убирает 89% квадратичной ошибки набора данных, и ни один другой предложенный вопрос не оставляет меньше. (Столбец прироста — тот же факт в пересчёте на наблюдение: убрано $76{,}501.0417 \times 5 = 382{,}505.21$, и $431{,}037.5 - 382{,}505.21 = 48{,}532.29$.)

Два кандидата дают ровную ничью на вершине — Is years >= 3? и Is hits >= 77?, оба 76501.0416666667, потому что режут пятерых игроков на те же две группы. >= в find_best_split отдаёт победу тому столбцу, который просматривается последним, ровно как и в статье о классификации.

Готовое дерево и то, что хранят его листья

Доведите рекурсию до конца — и она остановится, когда ни одну группу больше нельзя разделить:

Три листа держат ровно по одному игроку и воспроизводят их зарплату в точности. Четвёртый держит совпавшую пару и отвечает 81.25, среднее 67.5 и 95.0.

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

BillyJo Robidoux     факт     67.5   прогноз    81.25
Jack Howell          факт     95.0   прогноз    81.25
Alvin Davis          факт    480.0   прогноз   480.00
Mike Marshall        факт    670.0   прогноз   670.00
Lloyd Moseby         факт    787.5   прогноз   787.50

Это учебниковое запоминание — дерево делило, пока почти у каждой строки не появился собственный лист, ровно как делал классификатор и по той же причине: gain == 0 — единственное, что его останавливает.

Эти 81.25 наглядно показывают, почему в листе мы держим среднее, а не что-нибудь другое — скажем, меньшую из двух зарплат или большую. Лист обязан выдать одно число, назовём его $c$, а минимизируемая нами потеря — квадратичная ошибка, так что вопрос в том, какое $c$ делает $\sum_i (y_i - c)^2$ как можно меньше. Это гладкая функция от $c$, поэтому минимум там, где её производная обращается в ноль:

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

На этом листе дерево и перестаёт улучшаться. У Робиду и Хауэлла одинаковые years и hits, так что никакой вопрос никогда их не разделит: они делят лист на любой глубине, и каким бы числом этот лист ни отвечал, оно неверно хотя бы для одного из них. Ответ 81.25 оставляет $(67.5 - 81.25)^2 + (95 - 81.25)^2 = 378.125$ квадратичной ошибки, и никакое дерево, читающее только эти два столбца, не опустит её ниже — это пол под ошибкой обучения, который не пробить ростом вглубь.

И это не артефакт пяти удобных строк: среди 263 игроков встречается девять таких пар, худшая из которых расходится на $310,000, — так что на этих двух столбцах даже идеальная модель ошибалась бы на этой паре в среднем на $155,000. В полном файле есть ещё семнадцать предикторов, которые их растащили бы; смысл в том, что при любом фиксированном наборе признаков существует пол, и среднее в листе — то, как дерево его находит.

Внутри данных: лестница

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

Чтобы показать это попроще, ниже мы рисуем синтетический набор данных, а не Hitters: 40 строк с одним признаком $x$, равномерно расположенным от 0 до 10, и целью, идущей по гладкой волне с небольшим шумом.

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

На глубине 1 площадок две и подгонка ужасна. К глубине 6 их 27, а квадратичная ошибка упала с 5,816 до 89 — это ошибка всей подгонки: каждая из 40 точек прошла вниз по дереву и была оценена относительно среднего, хранимого листом, в который она попала, ровно та сумма, которую мы называли RSS, теперь по 27 листьям, а не по двум. Дерево сходится к кривой, но никогда не изгибается — оно приближает гладкую функцию, рубя её на всё более узкие постоянные куски.

Это структурное отличие от линейной модели, и оно режет в обе стороны. Дереву не нужно предположение, что зависимость линейна, монотонна или гладка, а взаимодействия между столбцами оно подхватывает даром. Отдаёт оно за это способность компактно выразить даже простейший непрерывный тренд: представление $y = 2x$ стоит одного коэффициента в линейной модели и неограниченного числа ступеней в дереве.

С двумя признаками лестница становится рельефом

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

Две панели ниже — одна и та же модель. Слева разбиение, увиденное сверху, где предсказание проявляется в закраске и числе внутри каждого прямоугольника, — картинка, которую рисовала статья о классификации для решающих регионов. Справа те же коробки подняты до этого числа, так что высота несёт то, что несла ось $y$ на лестнице:

Каждая крыша плоская, а каждая стена вертикальная — вот как выглядит кусочная постоянность, когда её видно. Поднимайте глубину, и рельеф набирает блоки так же, как лестница набирала ступени: 2 региона, потом 4, 8, 16 — приближаясь к форме данных плоскими гранями, никогда наклонами.

За пределами данных: потолок

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

Механизм за этим не уникален для регрессии. Регионы классификатора точно так же плоски, и он тоже отвечает на всё за пределами обучающих данных тем, что держит его крайний лист. Для регрессии ограничение особенно заметно, потому что у целевых значений есть порядок. Если зарплата продолжает расти за пределами обучающего диапазона, дерево не может за ней последовать; оно продолжает возвращать значение, сохранённое в крайнем листе. У меток нет аналогичного направления — нет категории выше «болезни», — поэтому в классификации то же поведение менее очевидно.

Это поведение прямо следует из того, как работает предсказание: строка, приходящая с $x = 10^6$, отвечает «да» на каждый пороговый вопрос по пути вниз, попадает в самый правый лист и получает среднее обучающих строк, которые попали туда же. Нет механизма, которым значение листа могло бы зависеть от того, насколько далеко за порогом находится строка.

Вот максимально острая демонстрация — идеально линейная зависимость вообще без шума, $y = 2.5x + 3$, отобранная на $x \in [0, 10]$, приближённая деревом глубины 3 и обычной линейной регрессией:

X = np.linspace(0, 10, 60).reshape(-1, 1)
y = 2.5 * X.ravel() + 3

tree = DecisionTreeRegressor(max_depth=3).fit(X, y)
linear = LinearRegression().fit(X, y)

Обе модели обучены на одних и тех же 60 строках, все они внутри $x \in [0, 10]$. Спросим теперь каждую о значениях внутри этого диапазона, а затем далеко за ним:

Прорисовано до $x = 20$, при том что обучающий диапазон кончается на 10:

Линейная модель восстанавливает правило в точности и верна при $x = 1000$. Дерево возвращает 26.52 при $x = 12$, при $x = 50$ и при $x = 1000$ — одно число на любой вход за пределами его опыта, на данных без шума и с зависимостью, которую прямая ловит двумя параметрами.

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

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

На прямой выше наибольшее значение, которое дерево может выдать, — 26.5169 против обучающего максимума 28.0: оно не дотягивается даже до самого большого числа, которое видело. Впрочем, это не универсально, и Hitters показывает почему. Подгоните дерево к зарплатам, и его потолок окажется 2127.3, что и есть обучающий максимум в точности, на любой глубине вплоть до 2:

глубина 2         наибольшее возможное предсказание  2127.3   достигается 1 игроком
глубина 3         наибольшее возможное предсказание  2127.3   достигается 1 игроком
глубина 5         наибольшее возможное предсказание  2127.3   достигается 1 игроком
полная глубина    наибольшее возможное предсказание  2127.3   достигается 1 игроком

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

В любом случае потолок оказывается на уровне наибольшей обучающей цели или ниже — никогда выше, что дереву ни скорми. Спросите то же дерево глубины 3, во сколько оценить игрока с вдвое лучшими карьерными показателями, чем у кого-либо в наборе:

дерево глубины 3      предсказывает   1169.8
линейная регрессия    предсказывает   5836.3

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

Больше всего это важно, когда экстраполяция входит в задачу:

• Тренды и временные ряды. Как только временной признак проходит все выученные пороги, дерево продолжает предсказывать одну и ту же площадку. Если важен сам тренд, сначала уберите его и моделируйте деревом остатки — или возьмите модель, способную выразить наклон.
• Цены и рост. Дерево не может продолжить растущую закономерность за пределы значений признаков, представленных его выученными порогами.
• Ансамбли. Случайные леса наследуют то же ограничение. Бустинговые деревья могут выдавать значения вне исходного диапазона цели, но их предсказания всё равно становятся постоянными, как только каждый признак уходит за выученные пороги разбиения.

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

От одного дерева к ансамблю

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

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

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

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