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

Вступление

Повышение - это метод коллективного обучения. Концептуально эти методы включают: 1. учебная база учащихся; 2. Использование всех моделей для окончательного прогноза. Методы ансамблевого обучения бывают разных типов, и все они отличаются друг от друга с точки зрения того, как они реализуют процесс обучения для базовых учащихся, а затем используют их результаты для выдачи окончательного результата. При ансамблевом обучении используются следующие методы: Bootstrap Aggregation (a.k.a. Bagging), Boosting, Cascading models и Stacked Ensemble Models. В этой статье мы кратко обсудим Bagging, а затем перейдем к Gradient Boosting, которому посвящена данная статья. Есть много источников, которые объясняют шаги алгоритма Gradient Boosting. Но если вы попытаетесь найти источник, объясняющий, что на самом деле делает каждый шаг, заставляющий работать весь алгоритм, вы, вероятно, найдете статьи, в которых в качестве примера используется квадрат ошибки. Эти объяснения очень хороши, но проблема в том, что они настолько сосредоточены на квадрате ошибки, что почти не могут передать обобщенную идею. Повышение градиента - это общая модель, которая работает с любой функцией потерь, которая является дифференцируемой, однако ее работа только с моделью квадратичных потерь не полностью объясняет, что она делает в процессе обучения. В этой статье я намерен объяснить алгоритм, используя более общий подход.

Примечание. Базовые модели в литературе также называются базовыми обучающимися. Они одно и то же. Однако я использовал термин «Базовые учащиеся» для базовых моделей и «Модель» для функции, создаваемой базовыми учащимися.

Упаковка

Упаковка - это комбинация двух последующих шагов:

я. Начальная выборка набора данных в M подмножества. Затем каждое из этих M подмножеств используется для изучения модели. Эти модели называются базовыми учащимися / моделями.

II. Проведение большинством голосов для объявления окончательного значения прогноза.

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

Boosting сильно отличается от Bagging своим подходом к обучению базовых учеников и их использованию для получения окончательных результатов. Баггинг обучает базовых учащихся на основе независимо загружаемых подмножеств данных, и, следовательно, мы можем обучать всех базовых учащихся одновременно в параллельной среде. Повышение, с другой стороны, обучает базовых учеников последовательно - модели обучаются одна за другой. Поэтому обучение базовых учеников параллельно невозможно. Более того, в алгоритме повышения мы начинаем с модели с большим смещением. Фактическая модель сначала инициализируется постоянным значением. Затем он постепенно становится менее предвзятым, добавляя к нему базовых учеников. Мы увидим, как Gradient Boosting изучает окончательную модель, которая имеет гораздо меньшее смещение при соответствующем количестве базовых учащихся.

Повышение градиента

Идея аддитивного моделирования:

Аддитивное моделирование лежит в основе алгоритмов повышения. Идея проста - сформировать сложную функцию, сложив кучу более простых терминов. В Gradient Boosting несколько более простых моделей складываются вместе, чтобы получить сложную окончательную модель. Как мы увидим, повышение градиента изучает модель, взяв взвешенную сумму подходящего количества базовых учащихся.

Алгоритм повышения градиента

Псевдоостаточные остатки

В алгоритме на этапе 2 (1) упоминается о вычислении «псевдо-остатков». Хотя вряд ли существует какое-либо конкретное концептуальное определение того, что такое псевдо-остаток, но математически упоминается то, как вы его определяете. Однако мне кажется, что это название заимствовано из разницы (y_actual - y_predicted), которую часто называют остаточной ошибкой, которую мы получаем, взяв производную квадратичной потери. функция L wrt прогнозируемое значение F (x_i) для ith примера.

В задачах оптимизации константы, прикрепленные к целевым функциям, не влияют на оптимальные точки, поэтому коэффициент '2', как показано на рисунке 2, на самом деле не имеет значения, и его можно безопасно отбросить (только когда мы решаем для оптимизации). Вероятно, никакая функция потерь не дифференцируется для получения невязки, но в случае квадрата потерь ее дифференциация дает функцию, наиболее близкую к остаточной ошибке «визуально». Может быть, название было заимствовано от этого. Тем не менее, повышение градиента не имеет ничего общего с производной функции потерь по w.r.t. гипотеза равна остаточной ошибке.

Как работает алгоритм

Возможно, мы получили представление об одной из вещей, которые мы делаем при повышении градиента - взятии производных от функции потерь по. функция гипотезы. Излишне говорить, что функция потерь должна быть дифференцируемой относительно. функция гипотезы. Как говорит алгоритм, повышение градиента принимает в качестве входных данных обучающий набор и функцию потерь. Обозначим окончательную модель, которую мы получим в конце алгоритма, F_M (x).

Обозначения

Некоторые обозначения, используемые в алгоритме, взятые из Википедии (опубликованы выше), несколько несовместимы. Итак, я буду использовать свои собственные обозначения для этих переменных.

F_M (x): окончательная модель, которая будет изучена путем взятия взвешенной суммы M базовых учащихся (аддитивное моделирование).

F_m (x): модель, полученная путем добавления m (= 1, 2,…, m) базовых учащихся и начального постоянного значения F_M (x) .

Шаг 1. Инициализируйте модель с постоянным значением.

Мы находим постоянную модель F_0 = γ, которая соответствует фактическим значениям y. Почему постоянная модель? Именно здесь начинает проявляться идея повышения - при переходе от модели с высоким смещением к модели с низким смещением. Мы начинаем с постоянной функции (никакая другая функция не может иметь большего смещения, чем постоянная функция, если только набор данных не настолько утомителен, что ему подходит даже постоянная модель), а затем проходим через несколько шагов, чтобы найти функцию с достаточно низким смещением. . В некоторых текстах вы можете найти инициализацию модели с 0 (ноль). Это тоже постоянная функция, но вполне возможно, что мы можем начать с немного лучшего варианта. Допустим, исходная модель - это постоянная функция γ. Тогда функция потерь для постоянной функции выглядит следующим образом:

Следовательно, γ_optimal определяется решением следующей задачи оптимизации:

Это наверняка лучше, чем модель, инициализированная нулем. В частности, для квадратичной ошибки потерь F_0 (x) равно среднему значению фактических y-значений, т. Е. F_0 (x) = y_mean когда используется квадрат потерь .

Часто в текстах эта модель не считается одним из базовых учащихся, хотя окончательная модель будет аддитивной моделью, полученной от базовых учащихся, и эта модель также будет одним из дополнений. Однако есть одно отличие - все модели, которые в литературе называются базовыми обучающимися, подбираются на псевдо-остатки, а не на значения y фактического набора данных (мы увидим, как это выполняется на шаге 2). Поскольку F_0 (x) соответствует y-значениям, вероятно, именно поэтому он не считается одним из основных учащихся в литературе.

В этот момент F_M (x) = F_0 (x). F_M (x),, однако, может обновляться до тех пор, пока все базовые учащиеся M не будут добавлены к нему с подходящими весами.

Шаг 2: Этот шаг необходимо выполнить для каждого базового учащегося от m = 1 до m = M. Обратите внимание, что усиление градиента добавляет одну модель за раз, одну за другой.

Алгоритм повышения градиента должен быть настроен с подходящим значением гиперпараметра M (количество базовых учащихся) перед выполнением.

Шаг 2.1. Вычислить псевдо-остатки:

Псевдо-остатки вычисляются для каждого ого примера обучения:

Обратите внимание, что F_m-1 (x) - это модель, полученная путем добавления m-1 взвешенных базовых учащихся и начальной постоянной функции. m_th (m надстрочный th) базовый обучающийся еще не добавлен. Каждый расчет остатка r_im для ith обучающего примера, соответствующего текущему базовому обучающемуся m (который будет обученный и добавленный на шаге 2.2) выполняется на взвешенной сумме базовых учащихся от 1 до m-1 и исходной постоянной функции (шаг 1). Напомним, что после шага 1 F_0 (x) = γ не включает термин, соответствующий какому-либо базовому учащемуся (напомним, что F_0 (x) чаще всего не называется базовый обучающийся в литературе (рассматривается только как начальное значение модели).

На этом этапе мы вычислили псевдоостаточные значения для каждого обучающего примера.

Шаг 2.2. Подбирайте базовых учащихся по псевдо-остаткам

Для этого шага на основе данного набора данных создается новый набор данных. Набор данных D_modified определен, как показано на рисунке 3.

Базовый ученик h_m (x) обучен и соответствует этому набору данных.

На данный момент у нас есть все необходимое для определения F_m (x). Делаем это следующим образом:

Почему в этом есть смысл?

Легко понять, почему это уравнение имеет смысл, если мы сравним его с изменениями веса, выполненными в Gradient Descent (рисунок 4) . Веса при градиентном спуске перемещаются в направлении уменьшения L потерь. Насколько необходимо переместить гири, зависит от α (скорости обучения). Аналогично этому, функция h_m (x) приспособлена к скорости изменения потерь L w.r.t. F_m-1 (x). Функция h_m (x) (которая, как ожидается, аппроксимирует поведение производной потери по F_m-1 (x) подходящим образом) представляет направление, в котором функция потерь уменьшается по F_m-1 (x). γ соответствует гиперпараметру α с точки зрения полезности (оба определяют, на какой объем следует произвести обновление). Это похоже на уравнение обновления веса в Gradient Descent, за исключением того, что γ можно обучить, а α - гиперпараметр. Мы увидим, как определяется оптимальное значение γ на шаге 2.3.

Обратите внимание, что γ - единственный параметр относительно который F_m (x) необходимо оптимизировать в исходном наборе данных. Однако базовые учащиеся изучают больше параметров в наборе данных D_modified, поскольку они являются фактическими функциями, которые складываются вместе, чтобы получить окончательную модель.

На данный момент у нас есть модель F_m (x), которая будет использоваться на следующем шаге для вычисления значений y_pred.

Шаг 2.3. Найдите оптимальное значение γ

Мы возьмем исходный набор данных D (рисунок 5) .

Мы берем модель F_m (x) в исходном наборе данных D, затем вычисляем потери L. Обратите внимание, что эта потеря является функцией γ.

Мы должны найти γ_optimum. Это можно сделать, решив следующую задачу оптимизации, которая сводит к минимуму:

На данный момент у нас есть оптимальное значение γ.

Шаг 2.4. Обновление модели

Таким образом, модель F_m (x) получается как:

В конце каждой итерации с номером m, F_M (x) обновляется до значения F_m (x).

Шаг 3. Шаг 2 выполняется для каждой базовой модели от m = 1 до M. После M итераций шага 2 мы получаем окончательную модель F_M (x).

Почему такое название «Повышение градиента»?

Мы только что увидели, какую роль в этом алгоритме играет «градиент» - мы всегда подгоняем базового ученика к градиенту функции потерь относительно. модель F_m-1 (x). Термин «повышение» относится к тому факту, что модель с высоким смещением, которая действительно плохо работает в наборе данных, повышается, чтобы наконец стать разумным классификатором и, возможно, сильным классификатором. В общем, Boosting - это семейство алгоритмов, в которых число «слабый классификатор» (тот, у которого коэффициент ошибок чуть меньше 0,5) объединяются, чтобы получить сильный классификатор (тот, который имеет частота ошибок близка к 0). При повышении градиента мы начинаем с постоянной модели (которая может быть чрезвычайно слабым классификатором в зависимости от набора данных). В конце m_th итерации обучения базового учащегося мы получаем слабого учащегося, но относительно лучший классификатор F_m (x), который постепенно становится сильным. классификатор.

Сноски

Надеюсь, эта статья имеет смысл. Моя цель - не просто написать алгоритм, я намерен демистифицировать математику (как гласит название) и выявить то, что лежит за пределами математических уравнений. Так что, если бы мне не удалось где-либо передать концептуальные идеи, лежащие в основе математики, пожалуйста, оставьте комментарий, это будет действительно заметно.

Спасибо за чтение!