Повышение градиента - Gradient boosting

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

Идея повышения градиента возникла в результате наблюдения Лео Брейман это повышение можно интерпретировать как алгоритм оптимизации подходящей функции стоимости.^[1] Алгоритмы повышения градиента явной регрессии были впоследствии разработаны Джером Х. Фридман,^[2][3] одновременно с более общей перспективой повышения функционального градиента Лью Мэйсона, Джонатана Бакстера, Питера Бартлетта и Маркуса Фрина.^[4][5]В последних двух статьях был представлен взгляд на алгоритмы повышения как на итерационные функциональный градиентный спуск алгоритмы. То есть алгоритмы, которые оптимизируют функцию стоимости в функциональном пространстве путем итеративного выбора функции (слабая гипотеза), которая указывает в направлении отрицательного градиента. Этот функциональный градиентный взгляд на повышение привел к разработке алгоритмов повышения во многих областях машинного обучения и статистики, помимо регрессии и классификации.

Неформальное введение

(Этот раздел следует за описанием повышения градиента, сделанным Ли.^[6])

Как и другие методы повышения, градиентное повышение объединяет слабых «учащихся» в одного сильного учащегося итеративным способом. Проще всего объяснить методом наименьших квадратов регресс сеттинг, цель которого - "научить" модель ${\displaystyle F}$ прогнозировать значения формы ${\displaystyle {\hat {y}}=F(x)}$ минимизируя среднеквадратичная ошибка ${\displaystyle {\tfrac {1}{n}}\sum _{i}({\hat {y}}_{i}-y_{i})^{2}}$, куда ${\displaystyle i}$ индексы по некоторому обучающему набору размера ${\displaystyle n}$ фактических значений выходной переменной ${\displaystyle y}$:

• ${\displaystyle {\hat {y}}_{i}=}$ прогнозируемое значение ${\displaystyle F(x)}$
• ${\displaystyle y_{i}=}$ наблюдаемое значение
• ${\displaystyle n}$ количество образцов в ${\displaystyle y}$

Теперь давайте рассмотрим алгоритм повышения градиента с ${\displaystyle M}$ этапы. На каждом этапе ${\displaystyle m}$ (${\displaystyle 1\leq m\leq M}$) повышения градиента, предположим некоторую несовершенную модель ${\displaystyle F_{m}}$ (для низкого ${\displaystyle m}$, эта модель может просто вернуть ${\displaystyle {\hat {y}}_{i}={\bar {y}}}$, где RHS среднее значение ${\displaystyle y}$). Чтобы улучшить ${\displaystyle F_{m}}$, наш алгоритм должен добавить новую оценку, ${\displaystyle h_{m}(x)}$. Таким образом,

${\displaystyle F_{m+1}(x)=F_{m}(x)+h_{m}(x)=y}$

или, что то же самое,

${\displaystyle h_{m}(x)=y-F_{m}(x)}$.

Следовательно, повышение градиента подойдет час к остаточный ${\displaystyle y-F_{m}(x)}$. Как и в других вариантах повышения, каждый ${\displaystyle F_{m+1}}$ пытается исправить ошибки своего предшественника ${\displaystyle F_{m}}$. Обобщение этой идеи на функции потерь кроме квадратичной ошибки, и задачи классификации и ранжирования, следует из наблюдения, что невязки ${\displaystyle h_{m}(x)}$ для данной модели отрицательные градиенты среднеквадратичная ошибка (MSE) функция потерь (по ${\displaystyle F(x)}$):

${\displaystyle L_{\rm {MSE}}={\frac {1}{2}}\left(y-F(x)\right)^{2}}$

${\displaystyle h_{m}(x)=-{\frac {\partial L_{\rm {MSE}}}{\partial F}}=y-F(x)}$.

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

Алгоритм

Во многих контролируемое обучение проблемы есть выходная переменная y и вектор входных переменных Икс описано через совместное распределение вероятностей ${\displaystyle P(x,y)}$. Использование обучающего набора ${\displaystyle \{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}}$ известных значений Икс и соответствующие значения y, цель - найти приближение ${\displaystyle {\hat {F}}(x)}$ к функции ${\displaystyle F(x)}$ что минимизирует ожидаемое значение некоторых указанных функция потерь ${\displaystyle L(y,F(x))}$:

${\displaystyle {\hat {F}}={\underset {F}{\arg \min }}\,\mathbb {E} _{x,y}[L(y,F(x))]}$.

Метод повышения градиента предполагает наличие действительного значения y и ищет приближения ${\displaystyle {\hat {F}}(x)}$ в виде взвешенной суммы функций ${\displaystyle h_{i}(x)}$ из какого-то класса ${\displaystyle {\mathcal {H}}}$, называется базой (или слабый ) учащиеся:

${\displaystyle {\hat {F}}(x)=\sum _{i=1}^{M}\gamma _{i}h_{i}(x)+{\mbox{const}}}$.

В соответствии с минимизация эмпирического риска принцип, метод пытается найти приближение ${\displaystyle {\hat {F}}(x)}$ который минимизирует среднее значение функции потерь на обучающей выборке, т.е. минимизирует эмпирический риск. Он делает это, начиная с модели, состоящей из постоянной функции ${\displaystyle F_{0}(x)}$, и постепенно расширяет его в жадный мода:

${\displaystyle F_{0}(x)={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L(y_{i},\gamma )}}}$,

${\displaystyle F_{m}(x)=F_{m-1}(x)+{\underset {h_{m}\in {\mathcal {H}}}{\operatorname {arg\,min} }}\left[{\sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}}\right]}$,

куда ${\displaystyle h_{m}\in {\mathcal {H}}}$ является базовой функцией обучаемого.

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

Идея состоит в том, чтобы применить крутой спуск шаг к этой задаче минимизации (функциональный градиентный спуск). Если рассматривать непрерывный случай, т.е. когда ${\displaystyle {\mathcal {H}}}$ - множество произвольных дифференцируемых функций на ${\displaystyle \mathbb {R} }$, мы бы обновили модель в соответствии со следующими уравнениями

$${\displaystyle F_{m}(x)=F_{m-1}(x)-\gamma _{m}\sum _{i=1}^{n}{\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))},}$$

$${\displaystyle \gamma _{m}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L\left(y_{i},F_{m-1}(x_{i})-\gamma \nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))\right)}},}$$

где производные берутся по функциям ${\displaystyle F_{i}}$ за ${\displaystyle i\in \{1,..,m\}}$, и ${\displaystyle \gamma _{m}}$ - длина шага. Однако в дискретном случае, т.е. когда множество ${\displaystyle {\mathcal {H}}}$ конечно, выбираем функцию-кандидат час ближе всего к градиенту L для которого коэффициент γ затем можно рассчитать с помощью линейный поиск по приведенным выше уравнениям. Обратите внимание, что этот подход является эвристическим и поэтому дает не точное решение данной проблемы, а скорее приближение. В псевдокоде общий метод повышения градиента:^[2][7]

Вход: обучающий набор ${\displaystyle \{(x_{i},y_{i})\}_{i=1}^{n},}$ дифференцируемая функция потерь ${\displaystyle L(y,F(x)),}$ количество итераций M.

Алгоритм:

1. Инициализировать модель с постоянным значением:

   ${\displaystyle F_{0}(x)={\underset {\gamma }{\arg \min }}\sum _{i=1}^{n}L(y_{i},\gamma ).}$

2. За м = От 1 до M:
   1. Вычислить так называемые псевдо-остатки:

      ${\displaystyle r_{im}=-\left[{\frac {\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}}\right]_{F(x)=F_{m-1}(x)}\quad {\mbox{for }}i=1,\ldots ,n.}$

   2. Подобрать базового ученика (или слабого ученика, например, дерево) ${\displaystyle h_{m}(x)}$ к псевдо-остаткам, т.е. обучить его с помощью обучающей выборки ${\displaystyle \{(x_{i},r_{im})\}_{i=1}^{n}}$.
   3. Вычислить множитель ${\displaystyle \gamma _{m}}$ решив следующие одномерная оптимизация проблема:

      ${\displaystyle \gamma _{m}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{i=1}^{n}L\left(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i})\right).}$

   4. Обновите модель:

      ${\displaystyle F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x).}$

3. Выход ${\displaystyle F_{M}(x).}$

Повышение градиента дерева

Повышение градиента обычно используется с деревья решений (особенно КОРЗИНА деревья) фиксированного размера в качестве базовых учащихся. Для этого особого случая Фридман предлагает модификацию метода повышения градиента, которая улучшает качество соответствия каждого базового ученика.

Общее повышение градиента на м-й шаг соответствует дереву решений ${\displaystyle h_{m}(x)}$ к псевдоостаточным остаткам. Позволять ${\displaystyle J_{m}}$ быть числом его листьев. Дерево разбивает входное пространство на ${\displaystyle J_{m}}$ непересекающиеся области ${\displaystyle R_{1m},\ldots ,R_{J_{m}m}}$ и прогнозирует постоянное значение в каждом регионе. С использованием обозначение индикатора, выход ${\displaystyle h_{m}(x)}$ для ввода Икс можно записать как сумму:

${\displaystyle h_{m}(x)=\sum _{j=1}^{J_{m}}b_{jm}\mathbf {1} _{R_{jm}}(x),}$

куда ${\displaystyle b_{jm}}$ это значение, прогнозируемое в регионе ${\displaystyle R_{jm}}$.^[8]

Тогда коэффициенты ${\displaystyle b_{jm}}$ умножаются на некоторое значение ${\displaystyle \gamma _{m}}$, выбирается с помощью линейного поиска, чтобы минимизировать функцию потерь, и модель обновляется следующим образом:

${\displaystyle F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x),\quad \gamma _{m}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{i=1}^{n}L(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i})).}$

Фридман предлагает модифицировать этот алгоритм, чтобы он выбирал отдельное оптимальное значение ${\displaystyle \gamma _{jm}}$ для каждой области дерева вместо одного ${\displaystyle \gamma _{m}}$ для всего дерева. Он называет модифицированный алгоритм «TreeBoost». Коэффициенты ${\displaystyle b_{jm}}$ из процедуры аппроксимации дерева можно просто отбросить, и правило обновления модели станет:

${\displaystyle F_{m}(x)=F_{m-1}(x)+\sum _{j=1}^{J_{m}}\gamma _{jm}\mathbf {1} _{R_{jm}}(x),\quad \gamma _{jm}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{x_{i}\in R_{jm}}L(y_{i},F_{m-1}(x_{i})+\gamma ).}$

Размер деревьев

${\displaystyle J}$количество конечных узлов в деревьях - это параметр метода, который можно настроить для имеющегося набора данных. Он контролирует максимально допустимый уровень взаимодействие между переменными в модели. С ${\displaystyle J=2}$ (пни решения ), взаимодействие между переменными не допускается. С ${\displaystyle J=3}$ модель может включать эффекты взаимодействия между двумя переменными и так далее.

Hastie et al.^[7] комментарий, который обычно ${\displaystyle 4\leq J\leq 8}$ хорошо работают для повышения, и результаты довольно нечувствительны к выбору ${\displaystyle J}$ в этом диапазоне, ${\displaystyle J=2}$ недостаточно для многих приложений, и ${\displaystyle J>10}$ вряд ли потребуется.

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

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

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

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

Усадка

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

${\displaystyle F_{m}(x)=F_{m-1}(x)+\nu \cdot \gamma _{m}h_{m}(x),\quad 0<\nu \leq 1,}$

куда параметр ${\displaystyle \nu }$ называется «скорость обучения».

Опытным путем было установлено, что использование малых скорость обучения (Такие как ${\displaystyle \nu <0.1}$) приводит к значительным улучшениям в способности обобщения моделей по сравнению с усилением градиента без сжатия (${\displaystyle \nu =1}$).^[7] Однако это происходит за счет увеличения вычислительное время как во время тренировки, так и запрос: более низкая скорость обучения требует большего количества итераций.

Стохастическое повышение градиента

Вскоре после введения повышения градиента Фридман предложил небольшую модификацию алгоритма, мотивируя это тем, что Брейман с начальная агрегация («мешковина») метод.^[3] В частности, он предположил, что на каждой итерации алгоритма базовый обучающийся должен соответствовать подвыборке обучающей выборки, выбранной случайным образом без замены.^[9] Фридман заметил существенное улучшение точности повышения градиента с помощью этой модификации.

Размер подвыборки - некоторая постоянная доля ${\displaystyle f}$ размера обучающей выборки. Когда ${\displaystyle f=1}$, алгоритм детерминирован и идентичен описанному выше. Меньшие значения ${\displaystyle f}$ ввести случайность в алгоритм и помочь предотвратить переоснащение, выступая в качестве своего рода регуляризация. Алгоритм также становится быстрее, потому что деревья регрессии должны соответствовать меньшим наборам данных на каждой итерации. Фридман^[3] получил, что ${\displaystyle 0.5\leq f\leq 0.8}$ приводит к хорошим результатам для тренировочных наборов небольшого и среднего размера. Следовательно, ${\displaystyle f}$ обычно устанавливается равным 0,5, что означает, что половина обучающего набора используется для построения каждого базового ученика.

Кроме того, как и в случае с мешками, субдискретизация позволяет определить ошибка вне сумки повышения производительности прогнозирования путем оценки прогнозов по тем наблюдениям, которые не использовались при построении следующего базового обучаемого. Оценки вне пакета помогают избежать необходимости в независимом наборе данных для проверки, но часто недооценивают фактическое улучшение производительности и оптимальное количество итераций.^[10][11]

Количество наблюдений в листах

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

Введение этого ограничения помогает уменьшить разброс прогнозов на листьях.

Наказывать сложность дерева

Еще один полезный метод регуляризации для повышения градиента деревья состоит в том, чтобы снизить сложность модели изученной модели.^[12] Сложность модели можно определить как пропорциональное количество листьев в изученных деревьях. Совместная оптимизация потерь и сложности модели соответствует алгоритму пост-отсечения для удаления ветвей, которые не могут снизить потери на пороговое значение. Другие виды регуляризации, такие как ${\displaystyle \ell _{2}}$ также может быть добавлен штраф за конечные значения, чтобы избежать переоснащение.

использование

Повышение градиента может использоваться в области учиться ранжировать. Коммерческие поисковые системы Yahoo^[13] и Яндекс^[14] используют варианты повышения градиента в своих машинах ранжирования с машинным обучением.

Имена

У этого метода множество названий. Фридман представил свою технику регрессии как «машину повышения градиента» (GBM).^[2] Мейсон, Бакстер и др. описал обобщенный абстрактный класс алгоритмов как «повышение функционального градиента».^[4][5] Friedman et al. описать развитие моделей с градиентным усилением как деревья множественной аддитивной регрессии (MART);^[15] Elith et al. описать этот подход как «деревья регрессии с ускорением» (BRT).^[16]

Популярная реализация с открытым исходным кодом для р называет это «Обобщенной моделью ускорения»,^[10] однако пакеты, расширяющие эту работу, используют BRT.^[17] Коммерческие реализации от Salford Systems используют названия «Деревья множественной аддитивной регрессии» (MART) и TreeNet, оба зарегистрированные товарными знаками.^{[нужна цитата ]}

Смотрите также

• AdaBoost
• Случайный лес
• LightGBM
• XGBoost
• Изучение дерева решений

Рекомендации

1. Брейман, Л. (июнь 1997 г.). "Дуга по краю" (PDF). Технический отчет 486. Статистический факультет Калифорнийского университета в Беркли.
2. Фридман, Дж. Х. (февраль 1999 г.). «Аппроксимация жадной функции: машина для повышения градиента» (PDF).
3. Фридман, Дж. Х. (март 1999 г.). «Стохастическое повышение градиента» (PDF).
4. Mason, L .; Baxter, J .; Bartlett, P.L .; Фриан, Маркус (1999). «Алгоритмы повышения как градиентный спуск» (PDF). В С.А.Солле и Т.К. Лин и К. Мюллер (ред.). Достижения в системах обработки нейронной информации 12. MIT Press. С. 512–518.
5. Mason, L .; Baxter, J .; Bartlett, P.L .; Фриан, Маркус (май 1999). «Алгоритмы повышения качества как градиентный спуск в функциональном пространстве» (PDF). Архивировано из оригинал (PDF) на 2018-12-22.
6. Ченг Ли. «Нежное введение в повышение градиента» (PDF).
7. Hastie, T .; Tibshirani, R .; Фридман, Дж. Х. (2009). «10. Развивающие и аддитивные деревья». Элементы статистического обучения (2-е изд.). Нью-Йорк: Спрингер. С. 337–384. ISBN  978-0-387-84857-0. Архивировано из оригинал на 2009-11-10.
8. Примечание: в случае обычных CART-деревьев, деревья аппроксимируются методом наименьших квадратов потерь, поэтому коэффициент ${\displaystyle b_{jm}}$ для региона ${\displaystyle R_{jm}}$ равно просто значению выходной переменной, усредненному по всем обучающим экземплярам в ${\displaystyle R_{jm}}$.
9. Обратите внимание, что это отличается от бэггинга, когда выборки с заменой, потому что он использует выборки того же размера, что и обучающий набор.
10. Риджуэй, Грег (2007). Обобщенные модели с ускорением: руководство по пакету gbm.
11. Изучите алгоритм повышения градиента для лучшего предсказания (с кодами в R)
12. Тяньци Чен. Введение в усиленные деревья
13. Коссок, Дэвид и Чжан, Тонг (2008). Статистический анализ байесовского оптимального ранжирования подмножеств В архиве 2010-08-07 на Wayback Machine, стр.14.
14. Запись в корпоративном блоге Яндекса о новой модели рейтинга «Снежинск» (на русском)
15. Фридман, Джером (2003). «Деревья множественной аддитивной регрессии с применением в эпидемиологии». Статистика в медицине. 22 (9): 1365–1381. Дои:10.1002 / sim.1501. PMID  12704603.
16. Элит, Джейн (2008). «Рабочее руководство по усиленным деревьям регрессии». Журнал экологии животных. 77 (4): 802–813. Дои:10.1111 / j.1365-2656.2008.01390.x. PMID  18397250.
17. Элит, Джейн. «Деревья ускоренной регрессии для экологического моделирования» (PDF). КРАН. КРАН. Получено 31 августа 2018.

дальнейшее чтение

• Бёмке, Брэдли; Гринвелл, Брэндон (2019). «Повышение градиента». Практическое машинное обучение с R. Чепмен и Холл. С. 221–245. ISBN  978-1-138-49568-5.

внешняя ссылка

• Как объяснить повышение градиента
• Деревья регрессии с градиентным усилением
• LightGBM