[Xiaobai изучает ИИ] Подробное объяснение вывода XGBoost и метод Ньютона

Статья взята из публичного аккаунта WeChat: [Machine Learning Alchemy]

[TOC]

1 Предисловие автора

В 2020 году еще разбирается алгоритм XGB, который на самом деле немного устарел. Однако это в основном для расширения знаний и прохождения собеседований. В текущем конкурсе больших данных XGB практически полностью заменен моделью LGB, основная цель здесь — изучить алгоритм Boost. Алгоритм Adaboost и алгоритм Gradient-boost уже были представлены ранее в других сообщениях блога.Эта статья объясняет XGBoost.

2 Обзор древовидной модели

XGB — это модель экстремального повышения градиента Extreme Gradient Boosting. XGB — это просто комбинация набора деревьев классификации и регрессии (CART). Аналогично GBDT и Adaboost. 【CART=деревья классификации и регрессии】

Здесь для дерева решений, как разделить и как выбрать оптимальную точку разделения, на самом деле является процессом поиска. Как разделить поиск, чтобы минимизировать целевую функцию. Целевая функция выглядит следующим образом: $Obj = Loss + \Omega$ $Obj$ функция оптимизации, которую мы хотим минимизировать, $Loss$ Это результат прогнозирования этой модели CART и истинное значение потерь. $\Omega$ Это сложность этой модели CART, аналогичная обычному термину в нейронной сети.[Приведенная выше формула является абстрактным понятием. Что нам нужно знать, так это то, что древовидная модель CART не только требует, чтобы предсказание было максимально точным, но также требует, чтобы древовидная модель не была слишком сложной. 】

Для задач регрессии мы можем использовать среднеквадратичную ошибку как Loss: $Loss=\sum_i{(y_i-\hat{y_i})^2}$

Для задач классификации очень часто используется кросс-энтропия Вот пример бинарной кросс-энтропии: $Loss = \sum_i{(y_ilog(\hat{y_i})+(1-y_i)log(\hat{y_i}))}$

Короче говоря, эта потеря является мерой потери точности предсказания модели.

Давайте посмотрим, как рассчитать сложность этой модели. $\Omega$ Бар. $\Omega = \gamma T+\frac{1}{2} \lambda \sum^T_j{w_j}^2$

$T$ представляет количество листовых узлов, $w_j$ Представляет вес каждого конечного узла (пропорционально количеству выборок конечного узла).

[Проблема в том, что, $w_j$ пропорциональна количеству выборок на листовой узел, но не количеству выборок. это $w_j$ Вычисление , зависит от производной всей целевой функции, а затем находит значение веса каждого листового узла $w_j$ . 】

3 XGB vs GBDT

На самом деле, сказав так много, кажется, что между XGB и GDBT нет большой разницы? Это потому, что после стольких разговоров я так и не начал говорить о XGB! Общая концепция модели дерева уже обсуждалась ранее. Давайте объясним XGB~ Я разберу некоторые высказывания в Интернете, а также свое собственное понимание. Если есть ошибки, пожалуйста, укажите в комментариях, спасибо!

3.1 Отличие 1: Поставляется с обычными предметами

В GDBT для соответствия отрицательному градиенту используется только новый слабый классификатор Сколько деревьев подходит для рассмотрения? понятия не имею. Среди функций оптимизации XGB есть $\Omega$ сложность. Эта сложность представляет собой не сложность определенного класса CART, а общую сложность всех CART в XGB. Можно предположить, что с каждой дополнительной ТЕЛЕГОЙ сложность будет увеличивать его наказание.Когда потери уменьшаются меньше, чем увеличивается сложность, XGB останавливается.

3.2 Отличие 2: имеется производная информация второго порядка

Новый CART в GBDT соответствует отрицательному градиенту, который является первой производной. В XGB учитывается информация второй производной.

Вот простой вывод того, как XGB использует информацию о второй производной:

Ранее мы получили оптимизированную функцию для XGB:

$Obj = Loss + \Omega$

Затем мы пишем Loss и Omega, чтобы быть более конкретными:

$Obj = \sum_i^n{Loss(y_i,\hat{y}_i^t)}+\sum_j^t{\Omega(cart_j)}$ - $\hat{y_i^t}$ Это означает, что всего существует t слабых классификаторов CART, и тогда t слабых классификаторов дают оценочное значение выборки i. - $y_i$ Истинное значение i-й выборки; - $\Omega(cart_j)$ Сложность j-й модели CART.

Теперь мы просим взять функцию оптимизации t-й модели CART, поэтому в настоящее время мы знаем только предыдущую модель t-1. Итак, мы получаем:

$\hat{y}_i^t = \hat{y}_i^{t-1}+f_t(x_i)$ Предсказания моделей t-CART равны предсказаниям предыдущих моделей t-1 CART плюс предсказания t-й модели.

Итак, вы можете получить:

$\sum_i^n{Loss(y_i,\hat{y}_i^t)}=\sum_i^n{Loss(y_i,\hat{y}_i^{t-1}+f_t(x_i))}$ Рассмотрим расширение Теллера здесь: $f(x+\Delta x)\approx f(x)+f'(x)\Delta x + \frac{1}{2} f''(x)\Delta x^2$

Как привнести в него формулу Тейлора?

${Loss(y_i,\hat{y}_i^t)}$ середина $y_i$ Это константа, а не переменная Так что на самом деле это можно рассматривать как $Loss(\hat{y}_i^t)$ , это: $Loss(\hat{y}_i^{t-1}+f_t(x_i))$

Вводя формулу Тейлора, $f_t(x_i)$ рассматривается как $\Delta x$ :

$Loss(\hat{y}_i^{t-1}+f_t(x_i))=Loss(\hat{y}_i^{t-1})+Loss'(\hat{y}_i^{t-1})f_t(x_i)+\frac{1}{2}Loss''(\hat{y}_i^{t-1})(f_t(x_i))^2$ - Во многих статьях будет использоваться $g_i=Loss'(\hat{y}_i^{t-1})$ ,а также $h_i=Loss''(\hat{y}_i^{t-1})$ для представления первой и второй производной функции.

Верните разложение Тейлора к исходной функции оптимизации и удалите постоянный член $Loss(\hat{y}_i^{t-1})$ (это никак не связано с t-й моделью ТЕЛЕГИ) и сложностью предыдущих t-1 моделей можно получить функцию оптимизации t-й ТЕЛЕГИ:

$Obj^t \approx \sum_i^n{[g_i f_t(x_i)+\frac{1}{2}h_i(f_t(x_i))^2}]+{\Omega(cart_t)}$

[Таким образом, XGB использует производную информацию второго порядка, в то время как GBDT использует только градиент первого порядка]

3.3 Отличие 3: выборка столбца

XGB опирается на практику случайного леса, поддерживает не только выборочную выборку, но и выборку признаков (выборку по столбцам), которая может не только уменьшить переобучение, но и сократить объем вычислений. (Но я лично сомневаюсь в этом. Я чувствую, что это всего лишь функция, заданная кодом, и это не преимущество собственного алгоритма XGB по сравнению с GBDT. Потому что XGB и GBDT, очевидно, могут использовать выборку столбцов.Короче говоря, наиболее важным отличием является вторая производная и введение регулярного члена)

4 Почему XGB использует вторую производную?

Это расширенный вопрос интервью о XGB. Когда я впервые увидел этот вопрос, я был ошеломлен.

[Давайте сначала поговорим о моем собственном ответе]

Информация о второй производной используется для ускорения сходимости.
Количество вычислений уменьшается.

4.1 Почему объем вычислений уменьшается

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

$loss(y,\hat{y}^t)$ Как и прежде, выпишите все ранее обученные слабые классификаторы и классификаторы, которые обучаются $loss(y,\hat{y}^{t-1}+f_t(x))$ Если мы посчитаем эту потерю, нам нужно посчитать 500 раз $loss(y,\hat{y}^{t-1}+f_t(x))$ Но предположим, что мы используем разложение Тейлора, чтобы получить: $loss(\hat{y}^{t-1})+g*f_t(x)+\frac{1}{2}h(f_t(x))^2$ один из них $loss(\hat{y}^{t-1})$ , $g$ , $h$ Они связаны только с ранее обученным деревом решений, поэтому являются константами, поэтому их можно разделить на 500 расчетов, и одного расчета достаточно.

4.2 Зачем ускорять конвергенцию

Здесь мы возвращаемся к разложению Тейлора: $f(x+\Delta x) = f(x) + g(x) * \Delta x + \frac{1}{2} h(x) (\Delta x)^2$ Фактически эту формулу можно рассматривать как $F(\Delta x)$ ,так как $x$ можно рассматривать как константу. мы надеемся $F(\Delta x)$ минимум (то есть потери минимальны), поэтому имеем $\Delta x$ Найдите производную: $F'(\Delta x)=g(x)+h(x)\Delta x=0$ Если производная равна 0, это минимальное значение (по умолчанию используется выпуклая функция). $\Delta x=-\frac{g(x)}{h(x)}$ , то есть размер шага обновления на самом делеПервая производная, деленная на вторую производную.

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

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

[Почему метод Ньютона быстро сходится] На самом деле, я не могу внятно объяснить эту часть, потому что я не очень хорошо разбираюсь в алгоритме оптимизации (кажется, я вдруг нашел причину, по которой я не могу найти работу 2333). Можно дать более простое объяснение:По сути, метод Ньютона — это сходимость второго порядка, а градиентный спуск — сходимость первого порядка, поэтому метод Ньютона быстрее. Если чаще говорят, например, что вы хотите найти кратчайший путь ко дну бассейна, метод градиентного спуска выбирает только направление с наибольшим уклоном каждый раз из вашего текущего положения, а метод Ньютона выбирает направлении., он не только рассмотрит, достаточно ли велик уклон, но также рассмотрит, станет ли уклон больше после того, как вы сделаете шаг.

5 метод Ньютона

Вот краткое введение в то, что такое метод Ньютона. В конце концов, некоторые друзья, возможно, не знали этого или забыли, как я.

[Цель метода Ньютона] Найдите корень функции, который является пересечением функции с осью x.

Вот кубическая кривая, мы сначала указываем на позицию A, а затем делаем касательную в позиции A, вы можете обнаружить, что эта касательная пересекает ось x.Затем этот фокус образует линию, параллельную оси у, пересекающуюся в точке В, затем касательную в точке В, затем пересекающую ось х, затем...

Затем итерации к точке C

Медленно приближается пересечение кубической функции и оси x, то есть корень кубической функции, равный 0.

【Математическая формула】 $x_n$ Касательное уравнение для точки: $f(x_n)+f'(x_n)(x-x_n)=0$ Так легко получить: $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$ [Почему здесь используется только информация первого порядка? 】 Потому что цель здесь — найти корень функции, то есть корень функции, равный 0. В задаче оптимизации мы решаем минимальное значение функции, для чего необходимо найти корень производной этой функции, равный 0, поэтому в задаче оптимизации это метод оптимизации производной второго порядка.

Я написал 4000 слов, так устал. Добро пожаловать, чтобы добавить друзей для общения.