Наконец-то кто-то прояснил - алгоритм XGBoost

1. Что такое XGBoost

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

Говоря о XGBoost, я должен упомянуть GBDT (Gradient Boosting Decision Tree). Поскольку XGBoost по сути является GBDT, но стремится к максимальной скорости и эффективности, он называется X (Extreme) GBoosted. Включая вышеупомянутое, оба являются методами повышения.

О GBDT я не буду упоминать здесь, вы можете ознакомиться с введением в моей предыдущей статье,Нажмите здесь, чтобы прыгнуть.

1.1 Определение дерева XGBoost

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

Таким образом обучаются два дерева дерево 1 и дерево 2. Подобно предыдущему принципу gbdt, выводы двух деревьев накапливаются, чтобы стать окончательным выводом, поэтому прогнозируемая оценка ребенка - это узел, в который ребенок попадает в Два дерева Сложите баллы: 2 + 0,9 = 2,9. То же самое верно и для прогнозируемой оценки дедушки: -1 + (-0,9) = -1,9. В частности, как показано на рисунке ниже:

Что ж, возможно, вам придется хлопнуть по столу и воскликнуть, разве это не то же самое, что и GBDT, представленный выше?

На самом деле, если не учитывать некоторые различия в инженерной реализации и решении проблем, большая разница между XGBoost и GBDT заключается в определении целевой функции. Целевая функция XGBoost показана на следующем рисунке:

в:

L, на которую указывает красная стрелка, — это функция потерь (например, квадратичная функция потерь:)
В красной рамке обозначен обычный термин (включая обычный термин L1, обычный L2).
Красный кружок - постоянный член
Для f(x) XGBoost использует Тейлора для расширения трех членов, чтобы сделать приближение.f(x) представляет одно из деревьев регрессии.

У некоторых читателей может закружиться голова, увидев такое количество формул,Я даю здесь только краткое объяснение.Чтобы узнать о конкретных деталях алгоритма и формулах, пожалуйста, ознакомьтесь с этим сообщением в блоге, которое очень подробно.:Популярное понимание kaggle game killer xgboost

XGBoostОсновная идея алгоритмаЭто не сложно, это в основном:

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

Очевидно, наша цель состоит в том, чтобы сделать прогнозируемое значение древовидной группы $y_i^{'}$ максимально близкое к истинному значению y_i , и имеет наибольшую возможную способность к обобщению. Подобно предыдущей процедуре GBDT, XGBoost также необходимо накапливать оценки нескольких деревьев, чтобы получить окончательную оценку прогноза (каждая итерация на основе существующего дерева добавляет дерево, соответствующее результату прогнозирования предыдущего дерева и реальному). остаточная стоимость).

Тогда как мы выбираем, к какому f присоединиться в каждом раунде? Ответ прост: выберите f, которое минимизирует нашу целевую функцию. Здесь f можно аппроксимировать с помощью формулы разложения Тейлора.

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

1.2 Регулярные термины: сложность дерева

Сложность дерева XGBoost состоит из двух частей:

Один - это количество T листовых узлов в дереве.
Один из них - квадрат L2 по модулю оценки w листовых узлов на дереве (регуляризация L2 w эквивалентна добавлению сглаживания L2 к оценке каждого листового узла, чтобы избежать переобучения)

Давайте еще раз взглянем на целевую функцию XGBoost (функция потерь показывает ошибку обучения + сложность определения регуляризации):

L(\phi)=\sum_{i}l(y_i^{'}-y_i)+\sum_k\Omega(f_t)

Формула регуляризации представляет собой вторую половину целевой функции.Для приведенной выше формулы $y_i^{'}$ является выходом всей модели накопления, а член регуляризации ∑kΩ(ft) представляет собой функцию, представляющую сложность дерева Чем меньше значение, тем ниже сложность и тем сильнее способность к обобщению.

1.3 Как должно расти дерево

Одна из интересных вещей заключается в том, что мы понимаем, как xgboost оптимизирует и рассчитывает от начала до конца, но мы никогда не видели, как выглядит дерево. Очевидно, что генерация дерева делится на две части узлом, а затем непрерывно разделяется, чтобы сформировать целое дерево. Таким образом, то, как дерево разбивается, становится ключом к тому, что мы обсудим далее. Чтобы узнать, как разделить листовой узел, автор XGBoost дал метод разделения узлов в своей оригинальной статье:Жадный метод для перечисления всех различных древовидных структур

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

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

1.4 Как остановить циклическую генерацию деревьев

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

Когда выигрыш, принесенный введенным разделением, меньше заданного порога, мы можем игнорировать разделение, поэтому не всякая функция потерь разделения будет увеличиваться в целом, что означает предварительную обрезку. Параметр порога равен (то есть обычному члену Коэффициент числа листовых узлов T);
Когда дерево достигает максимальной глубины, прекратите построение дерева решений и установите гиперпараметр max_depth, чтобы дерево не было слишком глубоким для изучения локальных выборок и переобучения;
Когда сумма весов выборок меньше установленного порога, построение дерева прекращается. Что это значит, что включает в себя гиперпараметр - минимальный вес выборки и min_child_weight, которые аналогичны параметру min_child_leaf GBM, но не совсем такие же. Общая идея состоит в том, что существует слишком мало выборок конечного узла, и завершение также должно предотвратить переоснащение;

2. В чем разница между XGBoost и GBDT

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

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

3. Почему XGBoost использует расширение Тейлора и каковы его преимущества?

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

4. Реализация кода

Гитхаб:нажмите, чтобы войти

【Машинное обучение легко понять серия статей】

5. Ссылки

автор:@mantchs

Гитхаб:GitHub.com/NLP-love/ml…

Приглашаются все желающие присоединиться к обсуждению! Улучшайте этот проект вместе! Номер группы: [541954936]