Ускорение 3 больших алгоритмов

две предыдущие статьипринцип адаптивностииПринцип повышенияПосле написания я все еще не чувствую, что понимаю буст, поэтому у меня есть эта статья.

интегрированное обучение

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

Во всем процессе есть две трудности:

Как получить несколько индивидуальных учеников
Как выбрать стратегию связывания

Давайте сначала рассмотрим первый вопрос, как получить индивидуального ученика. Есть два варианта:

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

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

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

Эта статья посвящена алгоритму повышения.

Основные принципы прокачки

Что касается алгоритма повышения, нам нужно знать 3 самых известных алгоритма:

Adaboost(Adaptive Boosting)
GBM(Gradient Boosting Machine)
XGBoost

GBM

Давайте сначала посмотрим на GBM, идея заключается в постепенном улучшении, как это понять?

Давайте сначала рассмотрим алгоритм повышения градиента: сначала задайте функцию потерьL(y,F(x)), входом которой является обучающая пара: (x1, y1), (x2, y2),..., (xn, yn), цель состоит в том, чтобы найти оптимальное F(x), чтобы функция потерь L была наименьший, согласно традиционному методу градиентного спуска, мы введем обучающие данные (xi, yi), затем найдем частную производную L по параметрам, а затем используем отрицательный градиент для обновления параметров:

Предпосылкой для этого является то, что нам нужно убедиться, что функция потерь Loss дифференцируема с F, а F с параметром $\theta$ Дифференцируемая, вторая дифференцируемая, можно сказать, более сложная, поэтому мы напрямую решаем F в функциональном пространстве F, мы предполагаем, что f представляет собой ряд наложенных друг на друга значений:

каждый из них $\theta$ и $\phi$ Получается путем нахождения минимального значения следующим образом:

для вышеперечисленного $\theta$ и $\phi$ Есть два зрелых метода получения:

Gradient Descent
Метод Ньютона

Это соответствует GBM и XGBoost соответственно, сначала поговорим о GBM.

Мы $\theta$ и $\phi$ Для вычисления минимального значения берется разложение Тейлора первого порядка по fm, и в это время получается обратное значение:

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

Мы преобразовали известные входные данные из (xi,yi) в (xi,-gm(xi)), теперь мы используем функцию $\phi_m$ чтобы соответствовать (xi,-gm(xi)), и критерии следующие:

когда мы учимся $\phi_m$ , давайте посмотрим, каким должен быть оптимальный размер шага:

Подытожим весь процесс:

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

Давайте сначала узнаем о структуре дерева.

Предположим, что дерево можно разбить на T узлов, и каждый узел имеет вес wj, тогда:

где n_jm — количество точек данных в j-м листе.Для приведенной выше формулы мы определяем G_jm как сумму градиентов всех данных в j-м листовом узле и удаляем постоянный член gm, мы получаем:

Итак, если структура дерева фиксирована, мы можем получить все веса листьев как:

Возвращаем это обратно в функцию потерь и получаем:

Давайте решим, должен ли листовой узел продолжать разделяться Мы можем рассчитать изменение потерь после разделения:

Разделить, если усиление>0, в противном случае это конечный узел.

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

wjm - вес j-го листового узла Теперь весь алгоритм выглядит следующим образом:

Adaboost

Мы приводим алгоритм алгоритма в основной статье Adaboost:

Мы можем понять алгоритм Adaboost, ответив на следующие 4 вопроса:

1) Как рассчитать коэффициент ошибок обучения e?
2) Как получить весовой коэффициент слабого ученика α?
3) Как обновить вес образца D?
4) Какая стратегия связывания используется?

Первая проблема: вычисление частоты ошибок обучения e, частота ошибок m-го слабого классификатора — это взвешенная частота ошибок на обучающем наборе:

Знаменатель здесь фактически равен 1 и может быть опущен. Вторая проблема: слабые веса классификатора.

Почему весовой коэффициент слабого ученика рассчитывается именно так? Из приведенной выше формулы видно, что чем больше частота ошибок классификации ek, тем меньше соответствующий весовой коэффициент слабого классификатора αm. То есть более слабый классификатор с меньшей частотой ошибок имеет больший весовой коэффициент. Третий вопрос: как обновить веса

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

Метод подъема

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

Потеря в Adaboost является экспоненциальной потерей:

На этом этапе m-й итерации нам требуется:

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

Итак, мы находим лучший G_m как:

Тогда у нас есть $\alpha_m$ Вывод, получаем:

XGBOOST

XGBOOST надеется напрямую решить следующую формулу, чтобы получить оптимальное fm

Мы можем выполнить разложение Тейлора второго порядка на fm-1 и получить:

Дальнейшее решение для получения:

Мы позволяем G_jm и H_jm обозначать сумму в регионе j соответственно, поэтому мы имеем:

На этом этапе мы берем производную от wjm, чтобы получить лучший wjm:

Подставить обратно в проигрыш:

На данный момент по потерям мы можем узнать структуру дерева:

Весь алгоритм описывается следующим образом:

В xgboost также добавляется обычный термин для предотвращения переобучения:

где γ — штраф за листовые узлы, α и λ — закономерности L1 и L2 соответственно, а оптимальный wjm равен:

На данный момент формула расчета выигрыша выглядит следующим образом:

Суммировать

В этой статье представлены 3 самых известных алгоритма повышения квалификации.

Adaboost(Adaptive Boosting)
GBM(Gradient Boosting Machine)
XGBoost

И представил, что Adaboost является частным случаем функции потерь GMB, является экспоненциальной потерей, в последующем будут две статьи, одна представляет вариант алгоритма adaboost, а другая представляет три алгоритма в сочетании с кодом.

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

Ссылаться на

Увеличение дерева с помощью XGBoost: почему XGBoost выигрывает «все» соревнования по машинному обучению?

Gradient Boosting from scratch

Boosting algorithm: XGBoost

Подробное объяснение GBDT в машинном обучении (23)

Gradient Boosting from scratch