1. Алгоритм прямого распределения

аддитивная модель

Формула аддитивной модели:

f(x)=\sum _{ m=1 }^{ M }{ { \beta }_{ m } } b(x;{ \gamma }_{ m }

в,базисная функция, $\gamma$ - параметр базовой функции, $\beta$ - коэффициент базисной функции, указывающий на важность этой функции в аддитивной модели.

Алгоритм прямого шага

Учитывая обучающие данные и функцию потерь L(y,f(x)), изучение аддитивной модели становится задачей минимизации эмпирического риска (т. е. задачей минимизации функции потерь).

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

Таким образом, алгоритм прямого распределения упрощает задачу оптимизации, заключающуюся в одновременном решении всех параметров от m=1 до M, до последовательного решения задачи с параметрами, соответствующими каждому базовому классификатору.

Подгонка отрицательного градиента

Дэниел Фрейдман предложил использовать отрицательный градиент функции потерь, чтобы приблизиться к потерям в этом раунде, а затем подобрать дерево регрессии CART. Отрицательный градиент функции потерь для i-го образца в t-м раунде выражается как:

использовать $(x_i,r_{ti})(i=1,2,..m)$ Мы можем подогнать дерево регрессии CART и получить t-е дерево регрессии, соответствующую ему область листового узла $R_{tj},j=1,2,...,J$ , Где J - количество листовых узлов. Для образцов в каждом листовом узле мы находим выходное значение, которое минимизирует функцию потерь, то есть наилучшее выходное значение для подбора конечного узла. $c_{tj}$ следующее:

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

h_t(x)=\sum\limits_{j=1}^{J}c_{tj}I(x \in R_{tj})

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

f_{t}(x)=f_{t-1}(x)+\sum\limits_{j=1}^{J}c_{tj}I(x\in R_{tj})

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

функция потерь

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

возвращение

двухклассный, многоклассовый

Алгоритм бинарной классификации GBDT

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

в $y \in{-1, +1}$ . Тогда ошибка отрицательного градиента в это время равна

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

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

c_{tj}=\sum\limits_{x_i \in R_{tj}}r_{ti}\bigg / \sum\limits_{x_i \in R_{tj}}|r_{ti}|(1-|r_{ti}|)

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

Алгоритм многомерной классификации GBDT

Многомерный GBDT сложнее, чем бинарный GBDT, что соответствует разнице в сложности между множественной логистической регрессией и бинарной логистической регрессией. Если предположить, что количество категорий равно K, то наша функция потерь логарифмического правдоподобия:

L(y, f(x)) = - \sum\limits_{k=1}^{K}y_klogp_k(x)

где, если выходной класс выборки равен k, то y_k=1 . Вероятность класса k p_k(x) Выражение:

p_k(x) = exp(f_k(x)) \bigg / \sum\limits_{l=1}^{K}exp(f_l(x))

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

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

соответствующая категория

Истинная вероятность и t-1

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

Приведенную выше формулу сложнее оптимизировать, вместо нее мы можем использовать приблизительные значения

c_{tj} = \frac{K-1}{K} \quad \frac{\sum\limits_{x_i \in R_{tjl}}r_{til}}{\sum\limits_{x_i \in R_{til}}|r_{til}|(1-|r_{til}|)}

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

Регуляризация

Как и в случае с Adaboost, нам также необходимо упорядочить GBDT, чтобы предотвратить переоснащение. Есть три основных способа упорядочить GBDT.

• Первый — это термин регуляризации, аналогичный Adaboost, скорости обучения. определяется как $\nu$ , для предыдущей итерации слабого ученика

Если мы добавим член регуляризации, мы получим

$\nu$ Диапазон значений $0\le \nu \le 1$ . Для того же эффекта обучения тренировочного набора, чем меньше $\nu$ Значит, нам нужно больше итераций слабого ученика. Обычно мы используем размер шага и максимальное количество итераций вместе, чтобы определить подгоночный эффект алгоритма.

• Второй способ регуляризации — по подвыборке. Значение равно (0,1]. Обратите внимание, что подвыборка здесь отличается от случайного леса. Случайный лес использует замещающую выборку, но здесь нет замещающей выборки. Если значение равно 1, используются все выборки, что равнозначно Без подвыборки Если значение меньше 1, только часть выборок будет использоваться для подбора дерева решений GBDT. Выбор отношения меньше 1 может уменьшить дисперсию, то есть предотвратить переобучение, но увеличит систематическую ошибку подбора выборки , поэтому значение не может быть слишком низким.0.5, 0.8между. GBDT, в которых используется подвыборка, иногда называют стохастическими деревьями повышения градиента (SGBT). Благодаря использованию подвыборки программа может распределять выборку по разным задачам, чтобы выполнять итеративный процесс повышения и, наконец, формировать новое дерево, тем самым уменьшая слабость слабых учеников, которых трудно обучать параллельно.

• Третье — регулярное отсечение для слабых учащихся, деревья регрессии CART.

Преимущества и недостатки

преимущество

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

недостаток

Трудно распараллелить обучающие данные из-за зависимостей между слабыми учениками. Однако частичный параллелизм может быть достигнут за счет самовыборки SGBT.

sklearn параметры

class sklearn.ensemble.GradientBoostingClassifier(loss='deviance', learning_rate=0.1, n_estimators=100, subsample=1.0, criterion='friedman_mse', min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_depth=3, min_impurity_decrease=0.0, min_impurity_split=None, init=None, random_state=None, max_features=None, verbose=0, max_leaf_nodes=None, warm_start=False, presort='auto', validation_fraction=0.1, n_iter_no_change=None, tol=0.0001)[source]¶

Несколько основных параметров:

loss: {'отклонение', 'экспоненциальный'}, необязательно (по умолчанию = 'отклонение') Функция потерь должна быть оптимизирована. «Отклонение» относится к отклонению (= логистическая регрессия) для классификации с вероятностными выходными данными. Для «экспоненциального» повышения градиента потерь восстанавливает алгоритм AdaBoost. функция потерь
learning_rate: скорость обучения
n_estimators: int (по умолчанию = 100) количество слабых учеников

Сценарии применения

Из-за отсутствия опыта в этой области эта часть повторяться не будет. Нашел статью:Принципы, решенные проблемы и сценарии применения вводных руководств по GBDT

Ссылаться на

[Машинное обучение] Интегрированное обучение (3) ---- Алгоритм прямого шага, повышающее дерево и GBDT
Подробное объяснение алгоритма GBDT