[ЗАСТАВКА] В этом видео мы поговорим о том,
как применять градиентный бустинг, если базовый алгоритм — это решающие деревья.
Сначала вспомним как выглядят поверхности, которые восстанавливают решающие деревья.
Начнем с классификации.
Представьте, что у нас есть три класса,
и в этом случае решающее дерево может разделить выборку примерно вот так.
Поскольку условия в каждой вершине дерева довольно простые — они сравнивают
значение конкретного признака с порогом — то решающее дерево выделяет каждый
класс с помощью некой области, стороны которой параллельны осям координат.
В этой задаче области будут примерно вот такие.
Видно, что их три штуки, и в каждой области предсказания константные.
Например, в красной области дерево относит все объекты к красному классу.
В регрессии, функция которой восстанавливает решающее дерево,
тоже кусочно постоянная.
В данном случае у нее есть четыре участка, где она возвращает одно и то же число.
Итак, если говорить об этом более формально, то мы приходим к тому,
что решающее дерево разбивает все пространство объектов на
J областей, которые мы обозначим как R1, R2, ..., RJ,
и при этом в каждой области дерево возвращает константное предсказание.
В области R1 оно будет обозначаться как b1,
в области R2 — как b2, и так далее, в RJ — как bj-ое.
Таким образом решающее дерево b(x) можно записать
как сумму по всем областям — от 1 до j — вот таких индикаторов.
Индикаторов того, что объект x,
в котором мы хотим посчитать прогноз, попал в область RJ.
Если он не попал, то это слагаемое будет равно нулю, если попал,
то мы возвращаем bj-ое — константный прогноз в этой области.
В градиентном бустинге мы прибавляем каждый новый базовый алгоритм bN к
уже построенной композиции.
Представим, что у нас базовый алгоритм — это решающие деревья,
то есть они выглядят так, как мы только что обсудили.
В этом случае новый алгоритм...
новая композиция aN будет выглядеть как сумма уже построенной композиции aN −
1 и вот такой суммы, которая представляет собой решающее дерево.
Обратите внимание, что на это можно посмотреть и немножко с другой стороны —
по сути, мы прибавляем не одно решающее дерево, а J очень простых алгоритмов.
Каждый алгоритм возвращает константное предсказание в некоторой области Rj и ноль
во всем остальном пространстве объекта.
Здесь возникает следующая идея: что, если мы подберем прогноз в каждой области,
которая обозначается как bNj-ое, где N — это номер дерева — N-ное,
которое мы только что добавили, j — номер листа этого дерева, номер области.
Так вот — что если мы подберем этот прогноз bNj-ое так,
чтобы он был оптимален с точки зрения исходной функции потерь L,
тогда как, напомню, мы дерево строили на среднеквадратичную функцию потерь.
Получаем следующую задачу: здесь стоит сумма по всем объектам обучающей выборки,
и каждое слагаемое — это ошибка суммы уже построенной
композиции aN − 1 и ответа нашего нового решающего дерева.
Мы хотим найти такие прогнозы в листьях bNj-ое,
чтобы как можно сильнее уменьшить эту сумму потерь.
Можно показать, что данная задача распадается на J маленьких
подзадач — сколько у нас было листьев в дереве, столько и подзадач.
При этом, например, поиск оптимального прогноза в j-ом листе будет
выглядеть вот так: мы будем минимизировать сумму по всем объектам обучающей выборки,
которые попали в данный лист, то есть в Rj-ое, в область Rj-ое,
отклонений истинного ответа yi-ое от суммы уже построенной композиции N
− 1 и прогноза в этом листе, который обозначается как γ (гамма).
То есть мы ищем такой прогноз в этом листе,
который будет оптимален для данных объектов обучающей выборки.
γ — это число из...
вещественное число, и мы будем искать ее каким-нибудь простым методом.
Часто эта задача решается аналитически, или можно, например,
решать ее перебором γ-фасетки или каким-то градиентным методом.
Итак, структура базового решающего дерева в градиентном
бустинге настраивается по среднеквадратичной ошибке,
которая измеряет отклонение от веток дерева от вектора сдвигов S.
При этом мы можем переподобрать ответы в листьях, перенастроить их так,
чтобы они были оптимальны не с точки зрения среднеквадратичной ошибки,
а с точки зрения исходной функции потерь L.
Оказывается, если мы так сделаем,
то сходимость градиентного бустинга очень сильно ускорится.
Нам понадобится гораздо меньше деревьев, чтобы достичь такого же качества,
как и без переподбора.
Давайте разберем пример.
Представим, что мы решаем задачу классификации с логистической
функцией потерь.
В этом случае практически оптимальные значения для коэффициентов для прогнозов
в листьях будут выглядеть вот так: оптимальный прогноз в j-ом листе зависит
от значений сдвигов si-ых для тех объектов, которые попадают в этот лист.
Итак, мы выяснили, что решающее дерево — это кусочно постоянный алгоритм,
и в градиентном бустинге он настраивается на среднеквадратичную ошибку.
Если мы перенастроим ответы в листьях этого дерева,
так чтобы они были оптимальны с точки зрения исходного функционала,
то мы существенно ускорим сходимость градиентного бустинга.
На этом урок про градиентный бустинг оканчивается, и теперь вам предстоит
решить несколько практических заданий, где вы сами воспользуетесь случайным лесом
и градиентным бустингом, чтобы решать реальные задачи.
Evgeniy Riabenko
Evgeny Sokolov
Victor Kantor
Emeli Dral
Константин Воронцовдоктор физико-математических наук, профессор
