Алгоритм, объясненный примером, математикой и кодом

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

Цель этой статьи — предоставить вам все подробности об алгоритме, в частности об алгоритме регрессии, включая его математику и код Python с нуля. Если вас больше интересует алгоритм классификации, посмотрите Часть 2.

Алгоритм с примером

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

В этом разделе мы шаг за шагом строим деревья регрессии с повышением градиента, используя приведенный ниже пример, который имеет нелинейную связь между x и y, чтобы интуитивно понять, как это работает (все изображения ниже созданы автором). ).

Первый шаг — сделать очень наивное предсказание цели y. Мы делаем первоначальный прогноз F₀ как общее среднее значение y:

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

Чтобы улучшить наш прогноз, мы сосредоточимся на остатках (то есть ошибках прогноза) с первого шага, потому что это то, что мы хотим минимизировать, чтобы получить лучший прогноз. Остатки r₁ показаны вертикальными синими линиями на рисунке ниже.

Чтобы свести к минимуму эти невязки, мы строим модель дерева регрессии с x в качестве признака и остатками r₁ = y − mean(y) в качестве цели. Причина этого в том, что если мы сможем найти некоторые закономерности между x и r₁, создав дополнительную слабую модель, мы сможем уменьшить остатки, используя ее.

Чтобы упростить демонстрацию, мы строим очень простые деревья, каждое из которых имеет только один расщепленный и два конечных узла, которые называются «пеньками». Обратите внимание, что деревья повышения градиента обычно имеют немного более глубокие деревья, например, с 8-32 конечными узлами.

Здесь мы создаем первое дерево, предсказывающее остатки с двумя разными значениями γ₁ = {6.0, −5.9} (мы используем γ(gamma) для обозначения предсказания).

Этот прогноз γ₁ добавляется к нашему исходному прогнозу F₀, чтобы уменьшить невязки. На самом деле, алгоритм повышения градиента не просто добавляет γ к F, поскольку он делает модель более подходящей для обучающих данных. Вместо этого γ уменьшается на скорость обучения ν, которая находится в диапазоне от 0 до 1, а затем прибавляется к F.

В этом примере мы используем относительно большую скорость обучения ν = 0.9, чтобы облегчить понимание процесса оптимизации, но обычно предполагается, что она будет намного меньше, например, 0,1.

После обновления наш комбинированный прогноз F₁ становится таким:

Теперь обновленные остатки r₂ выглядят так:

На следующем шаге мы снова создаем дерево регрессии, используя тот же x в качестве функции и обновленные остатки r₂ в качестве цели. Вот созданное дерево:

Затем мы обновляем наш предыдущий комбинированный прогноз F₁ новым прогнозом дерева γ₂.

Мы повторяем эти шаги до тех пор, пока предсказание модели не перестанет улучшаться. На рисунках ниже показан процесс оптимизации от 0 до 6 итераций.

Вы можете видеть, что комбинированный прогноз F𝑚 все больше приближается к нашей целиy по мере добавления новых деревьев в комбинированную модель. Вот как работает повышение градиента для прогнозирования сложных целей путем объединения нескольких слабых моделей.

Математика

В этом разделе мы углубимся в математические детали алгоритма. Вот и весь алгоритм в математических формулах.

Давайте демистифицируем это построчно.

Шаг 1

Первым шагом является создание начального прогноза постоянного значения F₀. L — это функция потерь, и в нашем случае регрессии это квадрат потерь.

argminозначает, что мы ищем значение, γкоторое минимизируетΣL(yᵢ,γ). Давайте вычислим значение γ, используя нашу фактическую функцию потерь. Чтобы найти γ, который минимизирует ΣL, мы берем производную от ΣL по отношению к γ.

И мы находим γ, что делает ∂ΣL/∂γ равным 0.

Оказалось, что значение γ, которое минимизирует ΣL, является средним значением y. Вот почему мы использовали среднее значение y для нашего первоначального прогноза F₀ в последнем разделе.

Шаг 2

Все процессы шага 2 от 2–1 до 2–4 повторяются M раз. M обозначает количество создаваемых деревьев, а маленькая цифра m представляет индекс каждого дерева.

Шаг 2–1

Мы вычисляем остатки rᵢ𝑚, беря производную функции потерь по отношению к предыдущему прогнозу F𝑚-₁ и умножая ее на −1. Как видно из индекса нижнего индекса, rᵢ𝑚 вычисляется для каждой отдельной выборки i. Некоторым из вас может быть интересно, почему мы называем это остатками rᵢ𝑚. Это значение на самом деле представляет собой отрицательный градиент, который дает нам представление о направлениях (+/−) и величине, в которой функция потерь может быть минимизирована. Вскоре вы увидите, почему мы называем это остатками. Кстати, этот метод, когда вы используете градиент для минимизации потерь в вашей модели, очень похож на метод градиентного спуска, который обычно используется для оптимизации нейронных сетей. (На самом деле они немного отличаются друг от друга. Если вам интересно, посмотрите эту статью с подробным описанием этой темы.)

Давайте посчитаем остатки здесь. F𝑚-₁ в уравнении означает прогноз из предыдущего шага. В этой первой итерации это F₀. Решаем уравнение для остатков rᵢ𝑚.

Мы можем взять 2 из него, так как это просто константа. Это оставляет нам rᵢ𝑚 = yᵢ − F𝑚-₁. Теперь вы понимаете, почему мы называем это остатками. Это также дает нам интересное понимание того, что отрицательный градиент, который дает нам направление и величину, до которой минимизируются потери, на самом деле является просто остатками.

Шаг 2–2

j представляет конечный узел (т. е. выход) в дереве, m обозначает индекс дерева, а заглавная J означает общее количество листьев.

Шаг 2–3

Мы ищем γⱼ𝑚, который минимизирует функцию потерь на каждом конечном узле j. Σxᵢ∈Rⱼ𝑚 L означает, что мы суммируем потери по всем образцам xᵢ, принадлежащим конечному узлу Rⱼ𝑚. Подключим функцию потерь к уравнению.

Затем мы находим γⱼ𝑚, при котором производная Σ(*) равна нулю.

Обратите внимание, что nⱼ означает количество выборок в терминальном узле j. Это означает, что оптимальное значение γⱼ𝑚, которое минимизирует функцию потерь, представляет собой среднее значение остатков rᵢ𝑚 в конечном узле Rⱼ𝑚. Другими словами, γⱼ𝑚 — это обычные прогнозные значения деревьев регрессии, которые являются средними целевыми значениями (в нашем случае — остатками) в каждом конечном узле.

Шаг 2–4

На последнем этапе мы обновляем прогноз комбинированной модели F𝑚. γⱼ𝑚1(x ∈ Rⱼ𝑚) означает, что мы выбираем значение γⱼm, если данное x попадает в конечный узел Rⱼ𝑚. Поскольку все конечные узлы являются исключающими, любой заданный одиночный x попадает только в один конечный узел, и соответствующий γⱼ𝑚 добавляется к предыдущему прогнозу F𝑚-₁, что делает обновленный прогноз F𝑚.

Как упоминалось в предыдущем разделе, ν — это скорость обучения в диапазоне от 0 до 1, которая определяет степень вклада дополнительного предсказания дерева γ в комбинированное предсказание F𝑚. Меньшая скорость обучения снижает эффект дополнительного предсказания дерева, но в основном также снижает вероятность переобучения модели обучающим данным.

Теперь мы прошли все этапы. Чтобы получить наилучшую производительность модели, мы хотим повторить шаг 2 M раз, что означает добавление M деревьев к комбинированной модели. В действительности вам может понадобиться добавить более 100 деревьев, чтобы получить наилучшую производительность модели.

Некоторым из вас может показаться, что вся эта математика излишне сложна, поскольку в предыдущем разделе основная идея была показана гораздо проще, без всех этих сложностей. Причина этого в том, что повышение градиента предназначено для работы с любыми функциями потерь, если они дифференцируемы, и рассмотренная нами математика представляет собой обобщенную форму алгоритма повышения градиента с такой гибкостью. Это делает формулу немного сложной, но в этом и заключается красота алгоритма, поскольку он обладает огромной гибкостью и удобством для работы с различными типами задач. Например, если ваша задача требует абсолютной потери вместо квадратичной, вы можете просто заменить функцию потерь, и весь алгоритм будет работать, как определено выше. Фактически, популярные реализации повышения градиента, такие как XGBoost или LightGBM, имеют широкий спектр функций потерь, поэтому вы можете выбрать любые функции потерь, которые подходят для вашей задачи (см. различные функции потерь, доступные в XGBoost или LightGBM). ).

Код

В этом разделе мы переводим математику, которую мы только что рассмотрели, в жизнеспособный код Python, чтобы помочь нам лучше понять алгоритм. Код в основном получен из реализации Мэтта Бауэрса, поэтому вся заслуга принадлежит его работе. Мы используем DecisionTreeRegressor из scikit-learn для построения деревьев, что помогает нам просто сосредоточиться на самом алгоритме повышения градиента, а не на алгоритме дерева. Мы имитируем реализацию в стиле scikit-learn, в которой вы обучаете модель методом fit и делаете прогнозы методом predict.

Обратите внимание, что все обученные деревья хранятся в объекте списка self.trees и извлекаются, когда мы делаем прогнозы с помощью метода predict.

Затем мы проверяем, работает ли наш CustomGradientBoostingRegressor так же, как GradientBoostingRegressor из scikit-learn, просматривая их RMSE на наших данных.

Как видно из приведенного выше вывода, обе модели имеют одинаковый RMSE.

Заключение

Алгоритм, который мы рассмотрели в этом посте, является лишь одним из вариантов алгоритма повышения градиента, характерного для задач регрессии с квадратичными потерями. Если вас также интересует алгоритм классификации, посмотрите часть 2.



Все, что вам нужно знать об алгоритме повышения градиента. Часть 2. Классификация
Алгоритм, объясненный на примере, математике и кодеtowardsdatascience.com



Есть также несколько других замечательных ресурсов, если вам нужна дополнительная информация об алгоритме:

  • StatQuest, Gradient Boost Часть 1 и Часть 2
    Это видео на YouTube, объясняющее алгоритм регрессии GB с отличными визуальными эффектами в удобной для начинающих форме.
  • Теренс Парр и Джереми Ховард, Как объяснить повышение градиента
    Эта статья также посвящена регрессии ГБ. Это объясняет, как алгоритмы различаются между квадратичными потерями и абсолютными потерями.
  • Джером Фридман, Приближение жадных функций: машина повышения градиента
    Это оригинальная статья Фридмана. Хотя это немного сложно понять, это, безусловно, показывает гибкость алгоритма, когда он показывает обобщенный алгоритм, который может решать любые типы задач с дифференцируемой функцией потерь.

Вы также можете просмотреть полный код Python по ссылке Google Colab или по ссылке Github ниже.



Google Colaboratory
Алгоритм усиления градиента — регрессия





Алгоритм повышения градиента — регрессия на tomonori-masui/gradient-boosting
github.com



Рекомендации