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

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

Допустим, f (x) - ваша модель, y - фактическое значение, гамма - это прогнозируемое значение, а L - функция потерь. Первая модель f0 (x) построена на {xi, yi}, как показано ниже:

Теперь вычислите остаток (ri = (y-gamma)) и постройте вторую модель h1 (x) на {xi, ri}. Добавьте h1 (x) к f0 (x) и получите новую улучшенную модель f1 (x)

Повторяйте описанный выше процесс снова и снова. Итак, обобщенная форма уравнения, скажем, на итерации m будет:

Вышеприведенное уравнение является общим уравнением для алгоритма повышения. Есть несколько способов решить, какую долю hm (x) добавить к fm-1 (x). Уравнение будет выглядеть так.

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

Теперь возникает вопрос, что такое повышение градиента? Термин градиент в повышении градиента происходит от включения градиентного спуска в усиление. Для определения альфа-канала или размера шага используется метод на основе градиентного спуска. Для вычисления альфа, скажем, на итерации m вычисляется первая псевдо-остаток (обод) и строится новая модель hm (x) на {xi, rim}. Псевдо-остаток рассчитывается по:

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

Теперь вставьте эти значения альфа и hm (x), чтобы получить fm (x).

В GBM алгоритм такой же, как и в повышении градиента. Модель основана на дереве решений, т.е. f (x) и h (x) - это CART-деревья. Для дерева с T листами модель hm (x) может быть записана как:

bjm - это прогнозируемое значение (среднее, медиана, максимальное количество голосов и т. д.) в области Rjm (лист j). Если hm (x) для дерева подключен к уравнению повышения градиента, будут альфа и bjm. В GBM альфа и bjm объединяются, чтобы получить частоту шагов для каждого листа. Итак, в дереве с T листами будет T альфа (частота шагов). Уравнения для GBM становятся:

Итак, мы увидели, как строится GBM. Вы, должно быть, заметили, что вычисление шаговой скорости в GBM требует двух шагов 1) Вычислить псевдо-остаток 2) Вычислить альфа. Кроме того, существуют шансы переобучения в GBM, которые можно уменьшить, добавив регуляризацию. XGBoost объединяет два шага для расчета скорости шага в один шаг и добавляет условия регуляризации в функцию потерь для противодействия переобучению. В XGBoost дерево на каждой итерации строится таким образом, чтобы при каждом разбиении выигрыш был максимальным. Чего ждать? Давайте посмотрим шаг за шагом.

Сначала поймите, что функция потерь в XGBoost имеет дополнительный термин omega. Эта функция потерь используется для вычисления максимального усиления, которое может быть напрямую использовано в процессе построения дерева при разделении каждого узла. Таким образом, двухэтапный процесс в GBM с регуляризацией сводится к одношаговому.

Давайте посмотрим, как рассчитывается Gain при построении дерева XGBoost. Начиная с функции потерь, которую необходимо минимизировать.

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

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

Термин омега регуляризации для дерева можно записать как:

Подставляя значение hm (x) как уравнение дерева и отбрасывая m (номер итерации) для аккуратности, функция потерь становится:

Далее упрощая уравнение,

Наша цель - минимизировать эту функцию потерь. Теперь, если вы заметили первый член, член суммирования, является уравнением параболы. Это можно увидеть как ax + bx². Минимальное значение параболы будет при x = -a / 2b. В нашем случае bj = -Gj / (Hj + lamba). Подставляя bj в функцию потерь, оптимальная функция потерь принимает вид:

Прирост, когда лист разделен на два листа (левый левый и правый R), становится:

Используя это усиление, XGBoost строит древовидную структуру.

Надеюсь, вам это понравится, и, пожалуйста, хлопайте, если да :)