Реализация XGBoost, я думаю, в основном заключается в улучшении GBDT. Для тех, кто не знаком с GBDT, пожалуйста, прочитайте мою статью«ГБДТ». Лично я считаю, что разница между ними в основном в деталях, я думаю, что понимание GBDT почти равно пониманию XGBoost.
Я сосредоточусь на сравнении различий между двумя алгоритмами XGBoost и GBDT:
Целевая функция XGBoost отличается от GBDT тем, что есть член разложения Тейлора:
Основное отличие заключается в том, что XGBoost имеет на два расширения Тейлора больше, чем GBDT. В частности, как получается это разложение Тейлора и для чего оно нужно? Мы смотрим на:
Алгоритм XGBoost можно рассматривать как аддитивную модель, состоящую из K деревьев:
Среди них F - функциональное пространство, составленное из всех деревьев (дерево регрессии здесь также является кусочной функцией, и разные значения разных сегментов составляют дерево). В отличие от общих алгоритмов машинного обучения, модель сложения не обучается d веса размерного пространства, но непосредственно узнать набор деревьев решений.
Целевая функция приведенной выше аддитивной модели определяется как:
Где Ω представляет собой сложность дерева решений, так как же определить сложность дерева? Например, можно учитывать количество узлов в дереве, глубину дерева или норму L2 оценок, соответствующих листовым узлам и т. д.
Как изучить аддитивную модель?
Для решения этой задачи оптимизации можно использовать прямой поэтапный алгоритм. Основываясь на предыдущем GBDT, мы знаем, что ученик аддитивной модели использует функцию, чтобы соответствовать предыдущему дереву, не подбирая каждый раз полные остатки Наконец, добавление всех этих остатков даст полный остаток для целевого прогноза, который также называется повышением. В частности, мы начинаем с постоянного предсказания и каждый раз изучаем новую функцию, процесс выглядит следующим образом:
Эта формула все еще кажется довольно неудобной.Если вы хотите понять, пожалуйста, прочитайте мою предыдущую статью«ГБДТ», легко понять формулу после понимания режима работы.
Это создаст новый вопрос, как появилась недавно добавленная функция f? Принцип заключается в минимизации целевой функции. Мы можем записать нашу целевую функцию как:
Затем мы используем квадрат ошибки для измерения нашей функции потерь:
вЭто то, что мы называем остатком. Каждый раз, когда мы используем функцию квадрата, алгоритм разрабатывается с учетом этого остатка.
Некоторые друзья могут быть не очень знакомы с формулой Тейлора, поэтому я напишу здесь основное использование формулы Тейлора:
Мы все знаем, что разложение в ряд Тейлора на самом деле имеет бесконечные многочлены.В виде бесконечных многочленов оно строго равно.Здесь мы берем только первые три члена и опускаем последние, поэтому оно приблизительно равно.
На основе формулы Тейлора мы можем преобразовать предыдущий вариант целевой функции в:
Среди них g и hчастная производная первого порядка и частная производная второго порядка функции потерь, соответственно, Конкретная математическая форма выглядит следующим образом:
Мы также можем удалить постоянный член напрямую, не затрагивая его, чтобы целевая функция выглядела так:
Поскольку изучаемая функция зависит только от целевой функции, из «целевой функции, удаляющей постоянный член», видно, что для задачи обучения необходимо определить только функцию потерь, а первая производная и второй порядок функция потерь рассчитывается для каждой обучающей выборки.Производная, функция, которую необходимо изучить на каждом шаге, может быть получена путем минимизации целевой функции на наборе обучающей выборки, так что окончательная обучаемая модель может быть получена в соответствии с моделью сложения .
Просто кратко упомянув разницу между GBDT и XGBoost, очевидно, что GBDT не использует квадратичное расширение Тейлора.Это, казалось бы, простое различие на самом деле обеспечивает более быструю подгонку и значительно уменьшает размер связующего дерева.Сокращение времени выполнения.
По сравнению с GBDT, XGBoost добавляет термин регуляризации (Regularization).
Мы используем оптимизацию функции потерь, чтобы избежать недообучения, и используем термин регуляризации, чтобы избежать переобучения. Член регуляризации и функция потерь вместе образуют нашу целевую функцию. XGBoost добавляет больше условий регуляризации, состоящих из сложности дерева, чем GBDT, что является одной из причин, почему XGBoost на самом деле работает лучше.
Что такое срок регуляризации? Какова роль члена регуляризации?
Все мы знаем, что когда мы оптимизируем целевую функцию, мы всегда хотим, чтобы она была более «маленькой», то есть оптимизация вообще означает минимизацию. Теперь, если мы добавим квадрат переменной к целевой функции, то, если переменная станет большой, целевой функции не должно нравиться то, что переменная становится большой, чтобы «минимизировать», и она намеренно будет избегать этого при выборе. путь, где переменная становится больше. Вероятно, это простое объяснение регуляризации. В XGBoost мы добавляем сложность дерева как обычный член, поэтому при работе оптимизатор будет стараться не усложнять дерево, чем и будет достигнут наш эффект.
Мы предполагаем, что количество листовых узлов дерева решений XGBoost равно T, дерево решений — это вектор w, состоящий из значений, соответствующих всем листовым узлам, и функция, которая отображает вектор признаков в индекс листового узла (Index )составлено, мы можем записать дерево как:
, мы также можем определить сложность дерева решений как обычный член:
Тогда целевая функция может быть записана в виде:
Подставляя G и H вместо исходной формулы, получаем упрощенную формулу:
Предполагая, что структура дерева фиксирована, то есть функция q(x) фиксирована, а первая производная целевой функции установлена равной 0, значение, соответствующее листовому узлу j, может быть рассчитано как:
Таким образом, при этом условии значение целевой функции принимает вид:
Почему вычисляются эти два значения?
Это описание процесса генерации единого дерева решений для вас:
- перечислить все возможные древовидные структуры q
- Используйте значение целевой функции для вычисления соответствующей оценки Obj для каждого q. Чем меньше оценка, тем лучше структура.
- В соответствии с результатом предыдущего шага найдите дочерний узел с наименьшей оценкой, сгенерируйте новую ветвь и вычислите прогнозируемое значение для каждого дочернего узла.
Сравнение усиления разделения XGBoost с GBDT
Количество древовидных структур бесконечно, поэтому перечислить все возможные древовидные структуры практически невозможно. Как правило, мы используем жадную стратегию для генерации каждого узла дерева решений.
Давайте посмотрим, как работает этот жадный алгоритм:
- Начиная с дерева с глубиной 0, перечислите все доступные функции для каждого конечного узла.
- Для каждого признака обучающие выборки, принадлежащие узлу, располагаются в порядке возрастания в соответствии со значением признака, а оптимальная точка разделения признака определяется линейным сканированием, и фиксируется максимальная прибыль признака (прибыль, когда принимается оптимальная точка разделения) )
- Выберите функцию с наибольшей прибылью в качестве функции разделения, используйте лучшую точку разделения функции в качестве позиции разделения, вырастите два новых листовых узла слева и справа от узла и свяжите соответствующий набор выборок для каждого нового узла.
- Вернитесь к шагу 1 и выполняйте рекурсивно, пока не будут выполнены определенные условия.
Как рассчитать доходность каждого сплита? Если предположить, что текущий узел обозначается как C, левый дочерний узел после разделения обозначается как L, а правый дочерний узел обозначается как R, то доход, полученный в результате разделения, определяется как значение целевой функции текущего узла. минус сумма значений целевой функции левого и правого дочерних узлов: Gain=ObjC-ObjL-ObjR, а именно, согласно формуле значения целевой функции: