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

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

История

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

Неофициальное знакомство

(Этот раздел следует за изложением повышения градиента Ченг Ли. )

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

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

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

$F_{m+1}(x_{i})=F_{m}(x_{i})+h_{m}(x_{i})=y_{i}$

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

$h_{m}(x_{i})=y_{i}-F_{m}(x_{i})$.

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

$L_{\rm {MSE}}={\frac {1}{n}}\sum _{i=1}^{n}\left(y_{i}-F(x_{i})\right)^{2}$

$-{\frac {\partial L_{\rm {MSE}}}{\partial F(x_{i})}}={\frac {2}{n}}(y_{i}-F(x_{i}))={\frac {2}{n}}h_{m}(x_{i})$.

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

Алгоритм

Во многих задачах обучения с учителем имеется выходная переменная y и вектор входных переменных x , связанные друг с другом некоторым вероятностным распределением. Цель состоит в том, чтобы найти некоторую функцию ${\hat {F}}(x)$ который лучше всего аппроксимирует выходную переменную из значений входных переменных. Это формализуется введением некоторой функции потерь $L(y,F(x))$ и минимизируем его в ожидании:

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

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

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

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

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

$F_{m}(x)=F_{m-1}(x)+\left({\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]\right)(x)$,

для $m\geq 1$, где $h_{m}\in {\mathcal {H}}$ — это базовая функция обучающегося.

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

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

Основная идея наикрутейшего спуска состоит в том, чтобы найти локальный минимум функции потерь путем итерации $F_{m-1}(x)$. Фактически, локальное направление максимального спуска функции потерь представляет собой отрицательный градиент.

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

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

где $\gamma >0$. Для маленьких $\gamma$, это означает, что $L(y_{i},F_{m}(x_{i}))\leq L(y_{i},F_{m-1}(x_{i}))$.

показывать Доказательство функциональной формы производной

To prove the following, consider the objective $O=\sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}$ Doing a Taylor expansion around the fixed point $F_{m-1}(x_{i})$ up to first order $O=\sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}\approx \sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i}))+h_{m}(x_{i})\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}+\ldots$ Now differentiating w.r.t to $h_{m}(x_{i})$, only the derivative of the second term remains $\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))$. This is the direction of steepest ascent and hence we must move in the opposite (i.e., negative) direction in order to move in the direction of steepest descent.

Кроме того, мы можем оптимизировать $\gamma$ найдя $\gamma$ значение, при котором функция потерь имеет минимум:

$\gamma _{m}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L(y_{i},F_{m}(x_{i}))}}={\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)}}.$

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

$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}))}$

где $\gamma _{m}$ длина шага, определяемая как $$\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)}}.$$ Однако в дискретном случае, т. е. когда множество ${\mathcal {H}}$ конечно , мы выбираем функцию-кандидат h, ближайшую к градиенту L , для которой коэффициент γ затем можно вычислить с помощью поиска строки по приведенным выше уравнениям. Обратите внимание, что этот подход является эвристическим и поэтому не дает точного решения данной проблемы, а скорее приближения. В псевдокоде общий метод повышения градиента:

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

Алгоритм:

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

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

2. Для m = 1 до M :
   1. Вычислите так называемые псевдоостатки :

      $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. Установите базового ученика (или слабого ученика, например дерева), закрытого при масштабировании. $h_{m}(x)$ к псевдоостаткам, т.е. обучить его с помощью обучающего набора $\{(x_{i},r_{im})\}_{i=1}^{n}$.
   3. Вычислить множитель $\gamma _{m}$ решив следующую одномерную задачу оптимизации:

      $\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. Обновите модель:

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

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

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

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

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

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

где $b_{jm}$ прогнозируемое значение в регионе $R_{jm}$.

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

$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})).$

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

$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 ).$

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

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

Хасти и др. прокомментируйте, что обычно $4\leq J\leq 8$ хорошо работают для повышения, и результаты довольно нечувствительны к выбору $J$ в этом диапазоне, $J=2$ недостаточно для многих приложений, и $J>10$ вряд ли понадобится.

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

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

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

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

Усадка

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

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

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

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

Стохастическое усиление градиента

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

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

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

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

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

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

Штрафовать за сложность дерева

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

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

Повышение градиента можно использовать в области обучения ранжированию . Коммерческие поисковые системы Yahoo и Яндекс использовать варианты повышения градиента в своих механизмах ранжирования с машинным обучением. Повышение градиента также используется в физике высоких энергий при анализе данных. На Большом адронном коллайдере (БАК) варианты градиентного усиления глубоких нейронных сетей (DNN) успешно воспроизвели результаты методов анализа, не связанных с машинным обучением, на наборах данных, использованных для открытия бозона Хиггса . Дерево решений повышения градиента также применялось при геологических исследованиях и исследованиях земли – например, при оценке качества коллектора из песчаника.

Имена

Метод имеет множество названий. Фридман представил свою технику регрессии как «Машину повышения градиента» (GBM). Мейсон, Бакстер и др. описал обобщенный абстрактный класс алгоритмов как «функциональное повышение градиента». Фридман и др. описать развитие моделей с градиентным усилением как деревьев множественной аддитивной регрессии (MART); Элит и др. опишите этот подход как «Деревья усиленной регрессии» (BRT).

Популярная реализация R с открытым исходным кодом называет ее «Обобщенной моделью повышения». однако пакеты, расширяющие эту работу, используют BRT. Еще одно название — TreeNet, в честь ранней коммерческой реализации Дэна Стейнберга из Salford System, одного из исследователей, которые первыми начали использовать древовидные методы.

Рейтинг важности функций

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

Недостатки

Хотя повышение может повысить точность базового метода обучения, такого как дерево решений или линейная регрессия, оно жертвует разборчивостью и интерпретируемостью . Например, проследить путь, по которому дерево решений принимает решение, тривиально и самоочевидно, но следовать путям сотен или тысяч деревьев гораздо сложнее. Чтобы добиться как производительности, так и интерпретируемости, некоторые методы сжатия модели позволяют преобразовать XGBoost в единое «возрожденное» дерево решений, которое аппроксимирует одну и ту же функцию принятия решений. Кроме того, его реализация может быть более сложной из-за более высоких вычислительных затрат.

См. также

• АдаБуст
• Случайный лес
• Кэтбуст
• ЛайтГБМ
• XGBoost
• Обучение дереву решений

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

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

Внешние ссылки

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