Автор: Byte Mobile Technology - Сюй Яокун

Прежде всего, давайте проясним, что XGBoost — это метод обучения для обучения модели дерева решений.Если быть точным, это метод обучения модели ансамбля деревьев.Здесь модель ансамбля деревьев транслируется в модель ансамбля деревьев.

Например

Вот простой набор данных, абсцисса представляет дозу препарата, зеленый цвет указывает на то, что препарат эффективен, а красный цвет указывает на то, что препарат неэффективен.

Сначала дается модель дерева решений, полученная после обучения,

Каждый неконечный узел здесь является условием оценки, потому что набор данных относительно прост, здесь есть только одна оценка функции, и в процессе фактического использования будет несколько функций. Каждый листовой узел имеет соответствующий вес.Обратите внимание, что начальная вероятность предсказания установлена на 0,5, то есть, когда мы ничего не знаем в начале, вероятность того, что лекарство считается эффективным в дозе, равна 0,5, и тогда дерево дает То, что получается, является смещением относительно первоначального предположения.Например, когда Dosage

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

Вероятно, с этим простым примером, вот простой математический вывод.

теоретическая часть

модель ансамбля деревьев

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

Вот формальное определение оригинальной статьи.

учитывая набор данных $\mathcal{D}$ , набор данных имеет $n$ тренировочные данные, каждые данные имеют $m$ характеристика,

\mathcal{D} = \{(x_{i}, y_{i})\}(|\mathcal{D}|=n, x_{i}\in\mathbb{R}^{m}, y_{i}\in\mathbb{R})

интегрированный $K$ Модель древовидного ансамбля отдельных деревьев решений может быть выражена как

\hat{y_{i}} = \phi(x_{i})=\sum_{k=1}^{K}f_{k}(x_{i}), f_{k}\in\mathcal{F}

здесь $f_k(\cdot)$ представляет результат прогнозирования дерева решений для ввода, $\mathcal{F}$ представляет все возможные деревья решений. Здесь следует отметить, что дерево решений состоит из двух аспектов: во-первых, это форма дерева, то есть, как оно выглядит, сколько у него ветвей и насколько оно глубоко, а во-вторых, это вес дерева. дерево, соответствующее листовым узлам. Во время вывода дерево решений делит тестовые выборки на соответствующие листовые узлы, а вес этого листового узла является оценкой тестовых выборок под деревом решений, то есть здесь $f_{k}(x_{i})$ .

Как обучить модель ансамбля деревьев

Обучение модели заключается в определении параметров модели, а в контексте XGBoost — в определении формы дерева решений и весов конечных узлов дерева решений.

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

В общем, функция потерь модели ансамбля деревьев определяется следующим образом:

\mathcal{L}(\phi)=\sum_{i}l(\hat{y_{i}},y_{i})+\sum_{k}\Omega(f_{k})

\Omega(f)=\gamma T+\frac{1}{2}\lambda||\omega||^{2}

в $\mathcal{L}(\cdot)$ называется функцией потерь, видно, что функция потерь $\phi$ Функция , обратите внимание здесь $\phi$ является моделью ансамбля деревьев. первый пункт $\sum_{i}l(\hat{y_{i}},y_{i})$ Представляет разницу между прогнозируемым значением модели и истинным значением, второй член $\sum_{k}\Omega(f_{k})$ Представляет собой накопление сложности всех деревьев, в $\Omega(f)$ В расширении , $T$ представляет количество листовых узлов в дереве, $\omega$ Представляет сумму весов всех конечных узлов дерева.

Проще говоря, для заданного входа $x_{i}$ , модель будет иметь соответствующий вывод $\phi(x_{i})$ . Учитывая функцию потерь, мы получаем $\mathcal{L}(\phi(x_{i}))$ , с помощью метода нахождения минимального значения в математике можно получить соответствующее $\phi$ параметр.

Вполне возможно, что приведенное выше решение пытается решить параметры формы и веса всех деревьев решений одновременно, что трудно сделать.

Gradient Tree Boosting

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

Учитывая функцию потерь алгоритма дерева с градиентным усилением,

\mathcal{L}^{(t)} = \sum_{i=1}^{n}l(y_{i}, \hat{y_{i}}^{(t-1)}+f_{t}(x_{i}))+\Omega(f_{t})

Функция потерь здесь представляет собой рекурсивную формулу.Отличие от функции потерь, описанной в предыдущем разделе, заключается в том, что предыдущее прогнозируемое значение равно $\hat{y_{i}}$ , параметрами целевой оптимизации являются параметры всех деревьев решений, а прогнозируемое значение здесь равно $\hat{y_{i}}^{(t-1)}+f_{t}(x_{i})$ , то есть результат предсказания первого t-1 дерева плюс результат предсказания t-го дерева, а параметры целевой оптимизации являются параметрами t-го дерева.

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

XGBoost

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

$\mathcal{L}^{(t)}$ относительно $f_{t}(x_{i})$ функция , здесь для $\mathcal{L}^{(t)}$ Выполните разложение Тейлора, чтобы получить

\mathcal{L}^{(t)} \simeq{\sum_{i=1}^{n}[l(y_{i},\hat{y}^{(t-1)})+g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^{2}(x_{i})]+\Omega(f_{t})}

здесь $g_{i}=\frac{\partial l(y_{i},\hat{y}^{(t-1)})}{\partial \hat{y}^{(t-1)}}$ , $h_{i}=\frac{\partial ^{2}l(y_{i},\hat{y}^{(t-1)})}{\partial \hat{y}^{(t-1)^{2}}}$ ,Сейчас $л (у_ {я}, \ шляпа {у} ^ {(т-1)})$ правильно $\hat{y}^{(t-1)}$ Первая и вторая производные от . С помощью разложения Тейлора функция потерь преобразуется в квадратичную функцию, причем коэффициент при квадратичном члене здесь положительный, что позволяет легко найти минимальное значение функции.

объясни еще раз $f_{t}(x_{i})$ означает первый $i$ ввод в $t$ вывод на дереве, где верхняя граница знака суммирования $n$ Указывает общее количество выборок в наборе обучающих данных.

В этом месте наша цель - решить $f_t(\cdot)$ , появляется в виде переменной в приведенной выше формуле, а в квадратичной функции принимает экстремальное значение на оси симметрии. Для простоты постоянный член равен $f_t(\cdot)$ Удалите неактуальные элементы.

\mathcal{L}^{(t)} \simeq{\sum_{i=1}^{n}[g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^{2}(x_{i})]+\Omega(f_{t})}

Как было сказано выше, решение $f_t(\cdot)$ В основном есть две широты, одна - форма дерева, а другая - вес листовых узлов дерева. Математическое выражение здесь таково,

\sum_{i=1}^{n}f_t(x_i) = \sum_{j=1}^{T}\sum_{i\in{I_j}}\omega_{j}

Смысл левой части уравнения очевиден, то есть все отсчеты находятся в первой $t$ Сумма выходных данных по дереву, правая часть уравнения выражает это значение по-другому, первый символ суммирования представляет все листовые узлы, а второй символ суммирования представляет набор отсчетов, которые присвоены каждому конечному узлу, $\{i|i\in{I_j}\}$ значит быть назначенным $j$ Пример набора конечных узлов. $\omega_{j}$ представитель $j$ вес каждого листового узла. Можно понять, какой листовой узел, которому назначен образец, представляет структуру дерева.

Принимая это уточненное выражение в приближенную функцию потерь разложения Тейлора, мы получаем,

\mathcal{L}^{t} \simeq{\sum_{j=1}^{T}[(\sum_{i\in{I_{j}}}g_i)w_j+\frac{1}{2}(\sum_{i\in{I_{j}}}h_i+\lambda)w_j^{2}]}+\gamma T

Учитывая структуру дерева здесь, мы можем вывести оптимальное решение веса каждого листового узла при приближенных условиях, когда структура данного дерева неявна в $\{i|i\in{I_j}\}$ В наборе, поскольку этот набор необходимо зафиксировать во время расчета по приведенной выше формуле, можно рассчитать следующий шаг.

Оптимальное решение записывается как

w^{\ast}_{j}=-\frac{\sum_{i\in{I_{j}}}g_{i}}{\sum_{i\in{I_{j}}}h_{i}+\lambda}

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

Так как же определить структуру дерева?

One of the key problems in tree learning is to find the best split. In order to do so, a split finding algorithm enumerates over all the possible splits on all the features.

Ответ - перечисление.Если вы хотите разбить узлы в узле, какие сэмплы должны быть разделены влево, а какие узлы должны быть разделены вправо, XGBoost сортирует все сэмплы по определенному признаку, а затем делит их, чтобы определить структура дерева перебирается и минимальное значение потерь рассчитывается как оптимальная структура.

учебный пример

Рисунок в начале статьи представлен таблицей,

Drug Dosage	Effectiveness	$g_{i}$	$h_{i}$
4	0	-0.5	0.75
9	1	0.5	0.25
11	1	0.5	0.25
17	0	-0.5	0.75

Прежде всего видно, что начальное прогнозируемое значение для всех выборок равно 0,5, что соответствует приведенной выше формуле $\hat{y}^{(t-1)}$ , метка отрицательного образца равна 0, а метка положительного образца равна 1, что соответствует приведенной выше формуле $y_{i}$ , в самом начале обучения все образцы находятся на листовых узлах.

На рисунке показано состояние листовых узлов в начале обучения, все обучающие выборки находятся на листовых узлах, а листовые узлы представлены своими характеристиками (Drug Dosage):

Подставляем данные в расчет $w^{\ast}_{j}$ Вычислите вес листового узла в формуле, а затем поднесите соответствующий $\mathcal{L}^{t}$ В формуле получен убыток в это время, а регулярное направление убрано для удобства расчета, т. е. $\gamma =0$ ,получить $\mathcal{L}^{t}=0$ .

Сначала мы пытаемся разделить признаки от доз менее 15, поэтому мы получаем следующее дерево:

В это время потеря этого дерева равна потере левого поддерева плюс потеря правого поддерева.Подставьте данные, чтобы получить $\mathcal{L}^{t}=-1.33$ , потери уменьшаются, и мы решаем, что разбиение этого узла лучше, чем то, что все узлы находятся на корневом узле.

Затем перебрать по очереди, найти уменьшение потерь в случае Dosage

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

Note

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

\sum_{i=1}^{n}f_t(x_i) = \sum_{j=1}^{T}\sum_{i\in{I_j}}\omega_{j}

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

Используйте параллельную стратегию для разделения решений для каждой функции: сначала отсортируйте каждую функцию, потому что разделение функций в разных местах независимо (например, две точки разделения Dosage
Стратегия кэширования градиентных данных: в исходных данных выборки не хранятся в порядке собственных значений или для разных собственных значений хранение выборок не является непрерывным. Тогда при вычислении функции потерь при взятии соответствующей производной первого порядка и производной второго порядка обращение к памяти не является непрерывным. Когда XGBoost будет реализован, он поместит необходимые данные градиента в дополнительную память и будет использовать предварительную выборку и кэширование для повышения скорости попадания в кэш, тем самым повышая скорость ввода-вывода данных.
Стратегия децентрализованной памяти: например, для достижения децентрализованных вычислений иногда объем данных слишком велик для запуска на одной машине, данные делятся на разные блоки, а затем все блоки сохраняются на диске. В процессе вычислений используется отдельный поток для предварительной выборки данных на диске, чтобы гарантировать, что операция и выборка данных могут выполняться одновременно.

Reference

оригинальная бумага
пример источника

О команде мобильной платформы Byte

Команда мобильных платформ ByteDance (Клиентская инфраструктура) является лидером в крупной индустрии передовых базовых технологий и отвечает за создание крупномасштабной передовой инфраструктуры во всем китайском регионе ByteDance, повышение производительности, стабильности и проектирования. эффективность всей линейки продуктов компании, поддерживающих продуктов, включая, помимо прочего, Douyin, Toutiao, видео с арбузом, видео с вулканом и т. д., а также углубленное исследование мобильных терминалов, веб-, настольных и других терминалов.

Это снег!Клиент/Внешний интерфейс/Сервер/Конечный интеллектуальный алгоритм/Разработка тестовНайм по всему миру!Давайте использовать технологии, чтобы изменить мир вместе, заинтересованные могут обращаться по электронной почтеchenxuwei.cxw@bytedance.com,Тема письмаРезюме - Имя - Цель работы - Предполагаемый город - Телефон.