[ЗАСТАВКА] Бустинг
— это ещё один способ построения композиций в машинном обучении.
И он отличается от бэггинга сразу по нескольким направлениям, обобщая его.
Во-первых, мы будем рассматривать такой вариант бустинга,
который одинаково применим и к задачам регрессии, и к задачам классификации,
то есть он будет допускать произвольные функции потерь,
и мы будем делать оптимизацию функционала аппроксимированного
эмпирического риска с произвольной функцией потерь.
Далее он использует не простое голосование, как бэггинг, а взвешенное
голосование, где каждый базовый алгоритм получает свой весовой коэффициент.
Ещё важное отличие бустинга от бэггинга заключается в том, что, как правило,
в бустинге базовые алгоритмы строятся один за другим,
это такой жадный способ, где каждый следующий базовый алгоритм строится так,
чтобы исправить ошибки предыдущих базовых алгоритмов.
Но однако, оба метода объединяет то, что они являются методами-обёртками,
то есть они эксплуатируют уже готовый метод обучения базовых алгоритмов.
Давайте рассмотрим формальную постановку задачи.
Как обычно у нас имеется обучающая выборка, это пара объект-ответ,
и мы договариваемся строить линейную композицию базовых алгоритмов,
базовых алгоритмов T штук, вот в таком виде, в виде суперпозиции.
Это линейная комбинация базовых алгоритмов bt с весами αt,
и при этом ещё с применением решающего правила.
Решающее правило нам нужно для общности постановки задачи, в частности,
если мы будем решать задачи восстановления регрессии,
то решающие правила нам не нужны и мы будем считать,
что Cb это просто b, тождественная функция.
А вот в случае классификации, в частности на два класса,
под решающим правилом обычно будет пониматься функция sign — знак,
которая превращает ответ вещественнозначной функции
b(x) в классификацию −1 или +1.
Итак, градиентный бустинг.
Мы строим линейную композицию базовых алгоритмов.
Будем оптимизировать функционал качества с произвольной функцией потерь L(b, y).
В этой функции два аргумента: первый аргумент — это оценка,
которую даёт композиция, второй аргумент — это правильный ответ.
Совершенно необязательно, чтобы это были элементы одного и того же множества,
например, правильным ответом может быть +−1, а оценка b может быть
вещественным числом, оценка степени принадлежности объекта классу.
Функционал устроен привычным нам образом.
Это сумма по всем объектам выборки,
функция потерь от нашей линейной композиции.
Мы договоримся в этой композиции строить только последний базовый
алгоритм и определять коэффициент при нём, считая, что все предыдущие
базовые алгоритмы уже построены, их коэффициенты известны и фиксированы.
Таким образом задача заключается в том,
чтобы найти базовый алгоритм bt,
который будет определять нам новый вектор u.
Вектор u состоит из ответов всей композиции на всех объектах
обучающей выборки.
Мы имели вектор uT−1, который состоял из ответов предыдущей композиции,
это как бы наше текущее приближение вектора u,
а мы хотим построить следующее приближение вектора u, uT,
который будет в качестве каждого элемента i-того содержать
ответ композиции на i-том объекте,
при этом в эту композицию надо добавить ещё один базовый алгоритм.
Мы можем рассматривать эту задачу, как задачу минимизации функционала q,
который теперь у нас зависит не от базового алгоритма, а зависит вот от
этого вектора ответов базового алгоритма на всех объектах обучающей выборки u.
Если бы u мог быть каким угодно, произвольным,
то мы бы для оптимизации функционала q(u) могли бы использовать градиентный метод,
который, как обычно, заключается в том, что мы сначала фиксируем
начальную точку u0 и затем делаем градиентные шаги,
gi — это компонента вектора градиента, g — это вектор,
который имеет размерность, равную объёму обучающей выборки,
ну а α — это параметр, величина градиентного шага.
Естественно, мы делаем шаг в направлении антиградиента,
то есть в формуле стоит минус, потому что мы минимизируем функционал.
Но вот эта вот формула градиентного шага, она очень сильно напоминает
формулу добавления ещё одного базового алгоритма в композицию.
Ведь, добавляя базовый алгоритм в композицию,
мы фактически должны сделать очень похожую вещь, мы к uT−1 добавляем α,
умноженное на bt, bt — это наш новый базовый алгоритм,
значит нас интересует ответ на i-том объекте для него,
и домноженный на коэффициент α, нам нужно определить и α и bt.
И если бы у нас bt от xi
равнялось gi, то добавление
базового алгоритма в точности бы совпадало с шагом градиентного метода.
Но в общем случае они, конечно, не равны.
И мы можем сделать так: мы будем двигаться не точно в направлении антиградиента,
а мы будем приближать его с помощью базового алгоритма.
То есть мы будем строить базовый алгоритм bt так,
чтобы он как можно точнее описывал вектор −g.
Ну для этого можно пользоваться разными оптимизационными постановками задачи.
Самое простое, что первое приходит в голову,
это использовать метод наименьших квадратов, мы выпишем функционал суммы
по всем объектам выборки, b(xi) плюс gi, это означает,
что b мы хотим построить так, чтобы он хорошо приближал вектор −g.
И получается вот такой алгоритм,
который получил название градиентного бустинга.
Бустинг потому, что он строит базовые алгоритмы один за другим, каждый следующий
базовый алгоритм пытается компенсировать ошибки предыдущих, а градиентный потому,
что вот есть такая прямая аналогия с методом градиентного спуска.
И ещё важно отметить, что этот метод появился после того,
как были предложены многие разные разновидности
бустингов, очень много разных эвристик.
А метод градиентного бустинга, он их всех объединил,
и стало понятно что можно использовать разные функции потерь,
можно использовать разные способы приближения градиента
и получать разновидности тех бустингов, которые были известны до этого.
То есть градиентный бустинг — это такое суперобобщение многих других
известных алгоритмов.
Итак, в чём он заключается?
Мы строим последовательно базовые алгоритмы,
сначала мы находим T-ый базовый алгоритм так,
чтобы он приближал вектор градиента, то есть это производные
нашей функции потерь, как только мы нашли базовые алгоритмы,
мы уже можем определить коэффициент α при этом базовом алгоритме.
Для этого решается ещё одна оптимизационная задача,
но на этот раз это задача одномерной оптимизации.
Это задача оптимизации по одному скалярному параметру α,
поэтому решается она несложно,
численных методов для одномерной оптимизации известно очень много.
Ну и третий шаг — мы обновляем значение композиции на объектах выборки.
То есть фактически добавляем ещё один базовый алгоритм bt с только
что определённым для него коэффициентом αt в композицию и вычисляем
значение этой композиции на всех объектах обучающей выборки.
Ну для этого к вектору ui достаточно добавить
выражение αt*bt(xi).
[ЗАСТАВКА]
