В качестве примера возьмем целевую функцию модели XGBoost на -й итерации:$t$

$$\mathcal{L}^{(t)}=\sum_{i=1}^n\ell(y_i,\hat{y}_i^{(t-1)}+f_t(\mathbf{x}_i))+\Omega(f_t)$$

где - функция потерь, - выходной файл ', а - регуляризация. Одним из (многих) ключевых шагов для быстрого расчета является приближение:$\ell$$f_t$$t$$\Omega$

$$\mathcal{L}^{(t)}\approx \sum_{i=1}^n\ell(y_i,\hat{y}_i^{(t-1)})+g_tf_t(\mathbf{x}_i)+\frac{1}{2}h_if_t^2(\mathbf{x}_i)+\Omega(f_t),$$

где и - первая и вторая производные функции потерь.$g_i$$h_i$

То, что я прошу, это убедительные аргументы, чтобы объяснить, почему вышеприведенное приближение работает:

1) Как XGBoost с вышеуказанным приближением сравнивается с XGBoost с полной целевой функцией? Какое потенциально интересное поведение высшего порядка теряется в приближении?

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

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

Традиционное повышение градиента

Рассмотрим традиционный алгоритм повышения градиента (Википедия) :

• Вычислить базовую модель$H_0$
• Для$m \leftarrow 1:M$
  • Вычислить псевдо-остатки$r_{im} = -\frac{\partial \ell(y_i, H_{m-1}(x_i))}{\partial H_{m-1}(x_i)}$
  • базового ученика для псевдо-остатков$h_m(x)$
  • Вычислить множитель который минимизирует стоимость, , (используя поиск строки)$\gamma$$\gamma = \arg \min_\gamma \sum_{i=1}^N \ell(y_i, H_{m-1}(x_i) + \gamma h_m(x_i))$
  • Обновите модель .$H_m(x) = H_{m-1}(x) + \gamma h_m(x)$
• Вы получите свою усиленную модель .$H_M(x)$

Приближение функции важно для следующей части,

базового ученика для псевдо-остатков.$h_m(x)$

Представьте себе, где наивно построить алгоритм повышения градиента. Вы могли бы построить алгоритм выше, используя существующие деревья регрессии как слабые ученики. Предположим, вам не разрешено изменять существующую реализацию слабых учеников. В Matlab критерием разделения по умолчанию является ошибка среднего квадрата. То же самое можно сказать о scikit .

Вы пытаетесь найти лучшую модель которая минимизирует стоимость . Но для этого вы подгоняете простую регрессионную модель к остаткам, используя MSE в качестве целевой функции. Обратите внимание, что вы не минимизируете напрямую то, что хотите, а используете остаточные значения и MSE в качестве прокси-сервера для этого. Плохая часть в том, что это не обязательно дает оптимальное решение. Хорошая часть в том, что это работает.$h_m(x)$$\ell(y_i, H_{m-1}(x_i) + h_m(x_i))$

Традиционный градиентный спуск

Это аналогично традиционному градиентному спуску (Википедия) , где вы пытаетесь минимизировать функцию стоимости , следуя (отрицательному значению) градиенту функции, на каждом шаге.$f(x)$$-\nabla f(x)$

$$x^{(i+1)} = x^{(i)} - \nabla f(x^{(i)})$$

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

интерлюдия

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

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

Другие способы выбрать лучшую модель$h_m(x)$

Если мы посмотрим на AdaBoost как на особый случай повышения градиента, он выбирает не регрессоров, а классификаторов как слабых учеников. Если мы установим , AdaBoost выберет лучшую модель, найдя$h_m(x) \in \{-1,1\}$

$$h_m = \arg \max_{h_m} \sum_{i=1}^N w_i h_m(x_i)$$

где - остатки ( источник, начинается на слайде 20 ). Основанием для использования этой целевой функции является то, что если и в одном направлении / имеют одинаковый знак, точка движется в правильном направлении, и вы пытаетесь максимизировать максимальное количество движения в правильное направление.$w_i$ш я х в м ( х я )$w_i$$h_m(x_i)$

Но опять же, это не является прямым измерением того, какой минимизирует . Он измеряет, насколько хорош ход , с учетом общего направления, в котором вы должны идти, и измеряется с помощью невязок , которые также являются приблизительными. Остатки сообщают вам, в каком направлении вы должны двигаться, по их знаку и примерно по величине, но они не сообщают вам, где именно вам следует остановиться.$h_m$$\ell(y_i, H_{m-1}(x_i) + h_m(x_i))$$h_m$$w_i$

Лучший градиентный спуск

Следующие три примера не являются необходимыми для объяснения и предназначены только для того, чтобы представить некоторые способы добиться большего успеха, чем ванильный градиентный спуск, чтобы поддержать идею о том, что то, что делает XGBoost, является просто еще одним способом улучшения градиентного спуска. В традиционной установке градиентного спуска при попытке минимизировать можно добиться большего успеха, чем просто следование градиенту. Было предложено много расширений (Википедия) . Вот некоторые из них, чтобы показать, что это можно сделать лучше, учитывая больше времени вычисления или больше свойств функции .$f(x)$f$f$

• Поиск линии / обратное отслеживание: в градиентном спуске после вычисления градиента следующая точка должна быть$-\nabla f(x^{(i)})$

  $$x^{(i+1)} = x^{(i)} - \nabla f(x^{(i)})$$

  Но градиент дает только направление, в котором нужно двигаться, а не «сколько», поэтому можно использовать другую процедуру, чтобы найти наилучшее такое, что$c > 0$

  $$x_c^{(i+1)} = x^{(i)} - c \nabla f(x^{(i)})$$

  минимизирует функцию стоимости. Это делается оценки для некоторого , и, поскольку функция должна быть выпуклой, это относительно легко сделать с помощью поиска строки (Wikipedia) или поиска линии возврата (Wikipedia) . Здесь основной стоимостью является оценка . Так что это расширение работает лучше всего, если легко вычислить. Обратите внимание, что общий алгоритм повышения градиента использует поиск строк, как показано в начале моего ответа.$f(x_c^{(i+1)})$$c$$f$f ( x ) f$f(x)$$f$

• Метод быстрого проксимального градиента: если функция минимизации сильно выпуклая, а ее градиент гладкий ( Липшиц (Википедия) ), то есть некоторый прием, использующий эти свойства, который ускоряет сходимость.

• Стохастический градиентный спуск и метод Momentum: В Stochastic Gradient Descent вы не оцениваете градиент по всем точкам, а только по подмножеству этих точек. Вы делаете шаг, затем вычисляете градиент в другой партии и продолжаете. Стохастический градиентный спуск может использоваться, потому что вычисления по всем точкам очень дороги, или, может быть, все эти точки даже не помещаются в память. Это позволяет вам делать больше шагов, быстрее, но менее точно.

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

Наиболее актуальным расширением градиентного спуска в нашем обсуждении XGBoost является метод Ньютона (Википедия) . Вместо того, чтобы просто вычислять градиент и следовать ему, он использует производную второго порядка, чтобы собрать больше информации о направлении, в котором он должен идти. Если мы используем градиентный спуск, мы имеем это на каждой итерации, мы обновляем нашу точку следующим образом:$x^{(i)}$

$$x^{(i+1)} = x^{(i)} - \nabla f(x^{(i)})$$

А поскольку градиент указывает на направление наибольшего увеличения , его отрицательные точки направлены в сторону наибольшего уменьшения, и мы надеемся, что . Это может не сработать, так как мы можем зайти слишком далеко в направлении градиента (отсюда расширение поиска строки), но это хорошее приближение. В методе Ньютона мы обновляем следующим образом:$\nabla f(x^{(i)})$$f$$f(x^{(i+1)}) < f(x^{(i)})$$x^{(i)}$

$$x^{(i+1)} = x^{(i)} - \frac{\nabla f(x^{(i)})}{\text{Hess} f(x^{(i)})}$$

Где - это гессиан функции в . Это обновление учитывает информацию второго порядка, поэтому направление больше не является направлением наибольшего уменьшения, а должно более точно указывать на , так что (или точка, где минимально, если нет нуля). Если - многочлен второго порядка, то метод Ньютона в сочетании с поиском строки должен быть в состоянии найти минимум за один шаг.$\text{Hess} f(x)$$f$$x$$x^{(i+1)}$$f(x^{(i+1)}) = 0$$f$$f$

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

Теперь причина, по которой работает метод Ньютона, та же, что и для приближения XGBoost, и оно основано на разложении Тейлора (Википедия) и теореме Тейлора (Википедия) . Разложение Тейлора (или ряд Тейлора) функции в точке имеет вид$f(x + a)$

$$f(x) + \frac{\partial f(x)}{\partial x}a + \frac{1}{2}\frac{\partial^2 f(x)}{\partial x^2}a^2 + \cdots = \sum_{n=0} ^\infty \frac{1}{n!} \frac{\partial^n f(x)}{\partial x^n}a^n.$$

Обратите внимание на сходство между этим выражением и приближением, которое использует XGBoost. Теорема Тейлора гласит, что если вы остановите разложение в порядке , то ошибка или разница между и , не превосходит , где является функцией со свойством хорошей , что она стремится к нулю , как стремится к нулю.$k$$f(x+a)$$\sum_{n=0}^k \frac{1}{n!}\frac{\partial^n f(x)}{\partial x^n}a^n$$h_k(x) a^k$$h_k$$a$

Если вам нужна некоторая визуализация того, насколько хорошо она аппроксимирует некоторые функции, взгляните на страницы википедии, у них есть некоторые графики для аппроксимации неполиномиальной функции, такой как , .$e^x$$\log(x)$

Стоит отметить, что аппроксимация работает очень хорошо, если вы хотите вычислить значение в окрестности , то есть для очень небольших изменений . Это то, что мы хотим сделать в Boosting. Конечно, мы хотели бы найти дерево, которое делает самые большие изменения. Если слабые ученики, которых мы создаем, очень хороши и хотят внести очень большие изменения, то мы можем произвольно помешать этому, применяя только или$f$$x$$a$$0.1$$0.01$его эффекта. Это размер шага или скорость обучения градиентного спуска. Это приемлемо, потому что, если наши слабые ученики получают очень хорошие решения, это означает, что либо проблема проста, и в этом случае мы все равно получим хорошее решение, либо мы переоснащаемся, так что немного или очень многое в этом плохом направлении не меняет основной проблемы.

Так что же делает XGBoost и почему он работает?

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

Почему они построили это так

Ваш вопрос о том, почему использование этого приближения приводит к компромиссу цена / производительность. Эта функция стоимости используется для сравнения потенциальных расщеплений для деревьев регрессии, поэтому, если наши точки имеют, скажем, 50 объектов со средним значением 10 различных значений, каждый узел имеет 500 потенциальных расщеплений, то есть 500 оценок функции. Если вы отбрасываете непрерывную функцию, количество разбиений увеличивается, и оценка разделения вызывается все больше и больше (у XGBoost есть еще одна хитрость для работы с непрерывными функциями, но это выходит за рамки). Поскольку алгоритм тратит большую часть своего времени на оценку разбиений, способ ускорить алгоритм - ускорить оценку дерева.

Если вы оценили дерево с помощью функции полной стоимости, , это новое вычисление для каждого нового разбиения. Чтобы выполнить оптимизацию при вычислении функции стоимости, вам потребуется информация о функции стоимости, которая является главной целью повышения градиента: она должна работать для каждой функции стоимости.$\ell$

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

$$\mathcal{L}^{(t)}\approx \sum_{i=1}^n \underbrace{\ell(y_i,\hat{y}_i^{(t-1)})}_{\text{constant}}+\underbrace{g_i}_{\text{constant}}f_t(\mathbf{x}_i)+\frac{1}{2}\underbrace{h_i}_{\text{constant}}f_t^2(\mathbf{x}_i)+\Omega(f_t),$$

Таким образом, единственное, что вам нужно вычислить, это и , а затем остается в основном сложение и некоторые умножения. Более того, если вы посмотрите на статью XGBoost (arxiv) , вы увидите, что они используют тот факт, что они строят дерево, чтобы еще больше упростить выражение до группы суммирования индексов, что очень, очень быстро.$f_t(x_i)$$\Omega(f_t)$

Резюме

Вы можете увидеть XGBoost (с аппроксимацией) как регрессию от точного решения, аппроксимацию «истинного XGBoost», с точной оценкой. Но поскольку точная оценка является настолько дорогостоящей, другой способ увидеть это состоит в том, что на огромных наборах данных аппроксимация - это все, что мы можем реально сделать, и эта аппроксимация является более точной, чем аппроксимация первого порядка, которую сделал бы «наивный» алгоритм повышения градиента. ,

Используемое приближение аналогично методу Ньютона и обосновано рядом Тейлора (Википедия) и теоремой Тейлора (Википедия) .

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

Для визуализации проверьте страницу Википедии ряда Тейлора / Теорема Тейлора , или Академию Хана о приближении ряда Тейлора , или страницу MathDemo о приближении полиномов неполиномов