Як побудувати регресор дерева рішень з нуля

У попередня стаття ми створили класифікатор, використовуючи дерево рішень, щоб передбачити, чи є у пацієнта захворювання серця. Дерево рішень також можна використовувати для завдань регресії, щоб передбачити число замість категорії — зарплату, температуру, ціну будинку. У цій статті ми візьмемо набір даних Нападаючі і побудуємо дерево рішень, щоб передбачити зарплату гравця на основі зіграних сезонів і хітів у попередньому сезоні.

Класифікатор оцінював розділення за допомогою Зменшення домішок Джіні. Для регресії з квадратичною помилкою замість цього ми використовуємо зменшення дисперсії та прогнозуємо середнє значення для кожного аркуша. Множення зменшення дисперсії на кількість рядків у батьківському елементі дає зменшення загальної квадратичної помилки.

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

Генерація кандидатів, рекурсивне розщеплення та правило зупинки залишаються незмінними. Необхідно змінити лише розрахунок домішок і прогноз листя.

Завантажте повний приклад Python і запустіть python3 hitters_tree.py.

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

Та сама техніка

Ми зберігаємо спрощену процедуру CART класифікатора. Кожен внутрішній вузол вибирає бінарне запитання, оцінює дві отримані групи та виконує рекурсію. Лист завершує рекурсію, якщо жоден кандидат не дає позитивного покращення за межі числового допуску.

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

Що нам потрібно змінити, так це міру купи — наскільки рядки в ній відрізняються один від одного. У класифікаторі 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)

Функція віднімає дочірні дисперсії, зважені за розміром, від батьківської дисперсії. Його результатом є зменшення середнього квадрата помилки в цьому вузлі. Тут зарплати виражені в тисячах доларів, тому і дисперсія, і SSE мають одиниці тисяч доларів у квадраті.

П’ять гравців

Набір даних складається з п’яти гравців із дослідження Нападаючі — два числові предиктори, одна числова ціль:

years — сезони, проведені у вищій лізі, hits — це хіти в попередньому сезоні, salary — його зарплата за сезон 1987 року в тисячах доларів. Це реальні рядки з реального дослідження, перевірені за повним файлом.

Вимірювання поширення набору даних

Щоб оцінити розподіл кандидатів, нам потрібен показник розкиду зарплат. Почніть із суми квадратів помилок (SSE), потім розділіть на кількість рядків, щоб отримати дисперсію.

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

Склад B складається з нашого реального набору даних — зарплати п’яти гравців вище; команда А — це гіпотетичний клуб, де всі заробляють приблизно однаково.

Один із способів зробити це — помістити обидва на графік:

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

Це говорить нам, що середнє значення не може виміряти, наскільки розкидана купа — воно повідомляє 420 у будь-якому випадку. Натомість ми можемо виміряти, наскільки кожна зарплата знаходиться від середнього:

Ми не можемо використовувати відхилення в тому вигляді, в якому вони є, тому що сума обох наборів дорівнює нулю — властивість середнього: це точка балансу набору, тому все, що знаходиться над ним, точно скасовує все, що знаходиться нижче.

Зведення у квадрат запобігає скасуванню позитивних і негативних відхилень і надає більшої ваги великим промахам. Іншим варіантом є абсолютна похибка, але вона поєднується з медіанним прогнозом, а не із середнім. Диференційованість не потрібна для пошуку розділеного дерева.

Зведіть відхилення в квадрат і додайте їх, і ви отримаєте SSE; розділіть це на кількість, і ви отримаєте дисперсію:

SSE – це загальна сума; дисперсія становить SSE на рядок. Дублювання кожного рядка подвоює SSE без зміни дисперсії. Додавання довільних нових рядків може змінити обидва. Тут дисперсія команди B приблизно в 431 разів перевищує дисперсію команди A: 86 207,50 проти 200,00.

Коли ми запишемо цю арифметику у вигляді формули, дисперсія буде:

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

Відкиньте $\frac{1}{n}$ і залишиться $\sum_{i=1}^{n}(y_i - \bar{y})^2$, це SSE.

Формула, яку ми щойно створили, відома як дисперсія генеральної сукупності, і, переглянувши її, ви побачите її поруч із другою версією, дисперсією вибірки, яка відрізняється лише знаменником:

Використовуйте тут знаменник $n$, оскільки ми вимірюємо середню квадратичну помилку рядків у цьому вузлі. Поправка $n-1$ служить іншій меті: оцінці дисперсії сукупності за випадковою вибіркою. Це непотрібно для цього розрахунку втрат від навчання.

Чому це правильна домішка

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

Припустімо, що дерево взагалі ніколи не розколюється — один листок тримає цілу команду, прогнозуючи середню зарплату, 420,0, для кожного гравця в ній.

Для загону А це хороша відповідь: там ніхто не заробляє більше 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 є викидом або помилкою при введенні даних:

Середнє значення мінімізує квадратичну помилку, тоді як медіана мінімізує абсолютну помилку. Підвищення найбільшого значення понад 200 призведе до подальшого переміщення середнього значення, але залишить цю медіану рівною 14. Ця стійкість до екстремальних значень є причиною того, чому листи абсолютної помилки можуть бути корисними для викидів.

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

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$ — помилку, яку ця купа робить у поточному стані, відповідаючи на кожен рядок цим одним числом. Таким чином, замість того, щоб запитувати, скільки помилок залишає розбиття, ми можемо запитати, скільки воно видалило — ця батьківська помилка мінус те, що ще несуть два дочірні елементи:

Це форма надходження інформації, записана в загальних показниках, а не в середньозважених.

Батьківський SSE фіксується під час порівняння кандидатів на одному вузлі. Віднімання залишкової похибки кожного кандидата з цього фіксованого значення змінює рейтинг: найменший залишок дає найбільший приріст.

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

У точній арифметиці приріст квадратичної помилки не може бути від’ємним: власне середнє значення кожного дочірнього елемента є принаймні таким же хорошим для його рядків, як середнє значення батьків. Нульовий негайний прибуток не означає, що глибші поділи ніколи не допоможуть. Наша жадібна реалізація зупиняється на незначному прибутку; обмеження глибини, мінімальний розмір листя та обрізка є додатковими способами контролювати складність.

Той самий критерій у нотації дисперсії

Приріст зазначено у загальних значеннях, тоді як 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 sse(rows):
    m = mean(rows)
    return sum((row[-1] - m) ** 2 for row in rows)

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

Обидва оцінюють тих самих кандидатів у тому самому порядку, а усереднена форма – це просто те, що класифікатор уже мав, Джіні також є середнім. Обидва перетворюються один в одного за допомогою однієї ідентичності, оскільки дисперсія становить SSE на рядок:

Підставте це для всіх трьох куп, і виграш стане

і ділення на $n_P$ — знову константа в цьому вузлі, тому знову нешкідлива — дає форму, використану в класифікаційній статті, і ту, яку обчислює info_gain:

Мінімізація дочірнього SSE, максимізація зменшення SSE та максимізація зменшення дисперсії вибирають той самий розподіл у межах фіксованого батьківського вузла. Значення відрізняються постійним зміщенням або кількістю батьківських рядків. Наш код використовує зменшення дисперсії, щоб зберегти структуру балів класифікатора.

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

Давайте тепер виконаємо цей критерій на першому вузлі справжнього дерева — корені, який містить усіх п’ятьох гравців, перш ніж було поставлено будь-яке запитання. Його середнє значення дорівнює $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 — тому кожен рядок відповідає на них «так». Усе переходить до правдивої сторони, і нічого до хибної сторони, отже, 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     actual    67.5   predicted   81.25
Jack Howell          actual    95.0   predicted   81.25
Alvin Davis          actual   480.0   predicted  480.00
Mike Marshall        actual   670.0   predicted  670.00
Lloyd Moseby         actual   787.5   predicted  787.50

Три тренувальні зарплати відтворюються точно, тоді як два гравці з ідентичними прогнозами отримують спільне середнє значення. Це описує тренувальну форму; ми не вимірювали продуктивність нових гравців.

Це 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 гравців із зареєстрованими зарплатами дев’ять пар мають однакові значення (Years, Hits). Найбільша різниця в зарплаті в такій парі становить 310 000 доларів, що дає мінімальну середню абсолютну похибку в 155 000 доларів для цієї пари для будь-якого спільного прогнозу. Їх можуть розрізняти додаткові предиктори. Це обмеження зареєстрованих функцій, а не доказ того, що зарплата за своєю суттю є непередбачуваною.

Всередині даних: сходи

Давайте тепер подивимося на форму, яку малює готове дерево, а потім на те, що відбувається за краєм навчальних даних. Це допоможе нам побачити, що дерево регресії може виражати, а що ні. Дерево регресії є кусково-постійним: його питання поділяють вхідний простір на області, і кожна точка в області отримує однаковий прогноз. Як функція функцій, його результатом є набір плоских плато з вертикальними стрибками на порогах — жодних схилів ніде, на будь-якій глибині. Нижче ми називатимемо цю властивість площинністю.

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

Віджет адаптує дерево регресії до цих рядків. Пунктирні лінії позначають вивчені порогові значення, і кожен інтервал приймає середнє значення цілей навчання. Збільште межу глибини, щоб побачити більше інтервалів:

На глибині 1 є два плато і посадка жахлива. На глибині 6 є 27, а квадрат помилки впав з 5816 до 89 — ця цифра є повною помилкою підгонки, кожна з 40 точок пройшла по дереву та оцінила середнє значення, яке утримував листок, у який він потрапляє, саме ту суму, яку ми називали RSS, тепер більше 27 листків, а не двох. Дерево сходиться на кривій, але ніколи не згинається — воно наближає гладку функцію, рубаючи її на дедалі вужчі постійні частини.

Дерево може апроксимувати нелінійні зв’язки та взаємодію ознак, не вказуючи їх заздалегідь. Але скінченне дерево з постійними листками не може точно представляти непостійну пряму на безперервному інтервалі; потрібно більше кроків для більш точного наближення.

Завдяки двом функціям сходи стають рельєфом

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

Дві панелі нижче є однаковою моделлю. Ліворуч, вид зверху, де передбачення відображається як затінення та число всередині кожного прямокутника — зображення, яке стаття класифікації намалювала для регіонів прийняття рішень. Праворуч ідентичні коробки піднято до цього числа, тому висота відповідає тому, що вісь $y$ перенесла на сходах:

Кожна покрівля плоска, а кожна стіна вертикальна, ось як виглядає кусково-постійна, якщо її побачити. Збільште глибину та рельєф місцевості блокує шлях сходів до сходів — 2 регіони, потім 4, 8, 16 — наближаючись до форми даних у плоских гранях, ніколи у схилах.

Поза даними: стеля

У сходах з однією функцією кожен вхід вище найбільшого вивченого порогу досягає тієї самої зовнішньої стулки. З кількома функціями збільшення однієї функції понад усі її порогові значення зупиняє зміну рішень щодо цієї функції, але інші функції все одно можуть направляти рядки на інші листи.

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

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

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

import numpy as np
from sklearn.linear_model import LinearRegression
from sklearn.tree import DecisionTreeRegressor

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

tree = DecisionTreeRegressor(max_depth=3, random_state=0).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$ — одне число для кожного введення за межами його досвіду, на даних без шуму та зв’язку, який фіксує пряма лінія з двома параметрами.

Усередині навчального діапазону дерево також допускає помилки наближення: при $x=2$ воно повертає 7,45 замість 8,00. Деякі входи можна передбачити точно, але вісім постійних плато не можуть відтворити цю лінію всюди.

Гірше, ніж площина, - зв’язка. Лист містить середнє значення навчальних цілей, які його досягли, і середнє не може лежати за межами середніх значень. Тож кожне передбачення, яке може зробити регресійне дерево, обмежується діапазоном навчальних цілей. Воно не може спрогнозувати рекордно високі чи рекордно низькі значення на будь-якій глибині, на основі будь-яких даних.

Найбільше листове значення прикладу рядка становить 26,5169, що нижче його найбільшої цілі навчання 28,0. Дерево може досягти цільового максимуму, якщо лист містить лише цей максимум. Для порівняння, підберіть усі 19 предикторів Hitters, використовуючи 184 навчальні рядки з розподілу 70/30 з random_state=0:

depth 2      highest possible prediction  2127.3   reached by 1 player
depth 3      highest possible prediction  2127.3   reached by 1 player
depth 5      highest possible prediction  2127.3   reached by 1 player
depth full   highest possible prediction  2127.3   reached by 1 player

У цьому підході дерево глибини 2 уже ізолює найбільшого прибутку. Чи станеться це залежить від предикторів та інших рядків, а не лише від того, наскільки екстремальною є мета. Межа незмінна: аркуш середнього значення не може перевищувати найбільшу ціль, яку він містить.

Це найбільш важливо, коли екстраполяція є частиною завдання:

• Тенденції. З виправленими іншими функціями дерево припиняє змінювати свій прогноз, коли функція часу зростання досягає всіх порогів. Окреме моделювання тренду може допомогти.
• Випадкові ліси. Середнє значення дерев із середнім прогнозуванням залишається в межах цільового діапазону навчання.
• Посилені дерева. Їхні суми можуть перевищувати цей діапазон, але скінченний ансамбль дерев із постійними листками все ще залишається кусково-постійним. Уздовж фіксованого напрямку його передбачення врешті-решт припиняє змінюватися, коли більше не перетинаються межі розділення.

Обмеження походить від того, що знаходиться в аркуші, а не від розщеплення. Деякі варіанти дерев підходять для лінійної моделі в кожному аркуші замість константи. Це дозволяє екстраполювати, хоча прогнози, що виходять за межі даних, сильно залежать від підігнаного нахилу.

Від одного дерева до ансамблю

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

Регресійні дерева часто використовуються в ансамблях. Випадковий ліс навчає дерева на початкових зразках і розглядає випадкові підмножини ознак при розбиттях, а потім усереднює їхні прогнози. Це зменшує чутливість до будь-якого встановленого дерева.

Натомість підберіть їх відповідно до помилок одна одної, і ви отримаєте посилення градієнта, де мінімізована квадратична помилка є помилкою всього ансамблю. Кожен раунд вимірює те, що ансамбль все ще помиляється, і підбирає наступне дерево до цих залишків, тому кожне дерево запускає точно розділений пошук із цієї статті, тільки проти цілі, створеної з поточних помилок, а не з чистими зарплатами. Це також те, чому ці дерева виконують роботу навіть тоді, коли проблема полягає в класифікації: те, до чого вони підігнані, – це стовпець градієнтів з реальним значенням, а не мітки.

Ні глибші дерева, ні додаткові раунди посилення не гарантують нульової помилки навчання: ідентичні предиктори з конфліктними цілями вже запобігають цьому. Вибирайте глибину, розмір аркуша та розмір ансамблю, використовуючи результати перевірки, а не тренувальну посадку.