В этом видео мы разберемся, как работает градиентный бустинг — один из лучших способов направленного построения композиции на сегодняшний день. Итак, будем строить композиции вот такого вида. Саму композицию из N алгоритмов будем обозначать как a с индексом N (x) и она будет представлять собой сумму N базовых алгоритмов bn (x). Обратите внимание, что мы не усредняем, а просто складываем базовые алгоритмы. Поскольку каждый следующий корректирует ошибки предыдущих. И будем считать, что у нас есть некая функция потерь, которую мы хотим минимизировать. Функция потерь — это некая функция L, которая измеряет ошибку на одном объекте. Ее аргументами являются y, истинный ответ на этом объекте, и z, прогноз нашего алгоритма на этом объекте. Примерами функции потерь в задаче регрессии может служить, например, среднеквадратичная ошибка — это (y – z) в квадрате. В случае с классификацией это может быть логистическая функция потерь, которая устроена вот так. Мы с ней уже сталкивались, когда обсуждали логистическую регрессию. Начнем с того, что инициализируем нашу композицию. Построим самый первый базовый алгоритм b0 (x). Он не должен быть очень сложным, не стоит тратить много усилий на его построение. Например, это может быть константный алгоритм, который всегда возвращает ноль, если задача регрессии. Или чуть сложнее — средний ответ по всей обучающей выборке. Если же это классификация, он может возвращать самый популярный класс на обучающей выборке. Ничего сложного. Будем действовать по индукции. Будем считать, что мы уже построили N – 1 алгоритмов, например, для N = 1 — это будет означать, что мы построили только самый первый алгоритм b0. И попробуем понять, как именно нужно выбрать следующий базовый алгоритм b с индексом N. Задача будет выглядеть вот так. Мы суммируем потери на всей обучающей выборке суммы уже построенной композиции a(N – 1) и нового алгоритма b (x). И будем пытаться выбрать алгоритм b (x) так, чтобы как можно сильнее уменьшить ошибку композиции на обучающей выборке, то есть, чтобы как можно сильнее уменьшить вот этот функционал. Давайте для начала упростим себе задачу и попробуем ответить на более простой вопрос, а именно: какие значения наш новый базовый алгоритм должен принимать на объектах обучающей выборки, чтобы как можно сильнее уменьшить ошибку на обучающей выборке? Задача будет выглядеть вот так. Мы суммируем функцию потерь по всем объектам из обучения и подставляем в нее следующий прогноз. Прогноз уже построенной композиции N – 1, и некоторый сдвиг этого прогноза на i-ом объекте, который мы будет обозначать, как si, и нужно найти такие значения si, чтобы они как можно сильнее уменьшили значение ошибки. Итак, мы получаем следующую задачу оптимизации. Нам нужно найти такой вектор сдвигов s, который будет минимизировать данную функцию F (s), и на самом деле мы уже знаем, как решать такую задачу. Вектор, который как можно сильнее уменьшает функцию — это антиградиент, поскольку он направлен в сторону наискорейшего убывания функции. Значит, вектор s должен быть просто равен антиградиенту функции F, а именно он будет выглядеть вот так. У него будет компонент столько, сколько объектов у нас на обучающей выборке и, например, первая компонента, это будет частная производная функции потерь L по второму аргументу, по прогнозу, и вычислять мы ее будем в точке, которая равна прогнозу уже построенной композиции на объекте x1, и все это берется с минусом. Последняя компонента, для примера, этого вектора, это снова частная производная функции потерь с минусом и при этом она вычисляется уже в точке равная прогнозу построенной композиции на объекте xl. Итак, мы с вами поняли, как именно нужно сдвинуть прогнозы уже построенной композиции, чтобы достаточно хорошо уменьшить значение функции потерь на обучающей выборке. Иными словами, мы знаем какие значения новый алгоритм должен принимать на объектах обучающей выборки, и по этим значениям, в конечном числе точек, мы должны построить функцию b (x), которая будет выдавать прогноз на любой точке из нашего пространства объектов. На самом деле это задача, с которой мы уже много раз сталкивались и обсуждаем ее не первую неделю. Это задача обучение на размеченных данных. У нас есть обучающая выборка и есть ответы на ней, которые в нашем случае равны сдвигам si, и нужно по этим данным построить алгоритм b (x). Мы это умеем решать. Давайте настраивать алгоритм bn (x), следующий алгоритм, так, чтобы он был как можно ближе к сдвигам si, и при этом близость будем измерять с помощью среднеквадратичного отклонения. Функционал нашей задачи будет выглядеть вот так. Это будет сумма квадратов отклонений, ответов нашего алгоритма b (x) от сдвигов si. Обратите внимание, что вся информации об исходной функции потерь L, которая может быть не квадратичная, это может быть, например, логистическая функция потерь или абсолютная ошибка, вся эта информация уже содержится в градиенте, содержится в сдвигах si-тых. И потому нам не нужно использовать эту же функцию потерь на данном шаге. Достаточно приближать ответы к сдвигам по квадрату отклонения. Этого достаточно в большинстве задач. Именно этот функционал используется в градиентном спуске. Итак, давайте еще раз поговорим, как устроен градиентный спуск. В первую очередь мы находим инициализацию — самый первый базовый алгоритм b0, каким-то простым способом, например, усреднением, или это алгоритм, который возвращает самый популярный класс. Далее мы по итерациям повторяем следующие шаги. На каждой итерации мы строим новый базовый алгоритм bn. В первую очередь мы вычисляем вектор сдвига s, который показывает, как нужно скорректировать прогнозы уже построенной композиции, чтобы довольно сильно уменьшить ошибку на обучающей выборке. Вектор s устроен вот так, это вектор частных производных функции потерь в точках обучающей выборки. Далее мы строим базовый алгоритм bn путем подгонки его ответов на обучающей выборке к данным сдвига si-тое. После того, как алгоритм найден, это должно быть довольно просто из-за простого функционала, мы добавляем его в композицию. Повторяем эти шаги до тех пор по ка не наступит сходимость или не будет выполнен некоторый критерий останова, о которых мы поговорим в следующих видео. Итак, мы с вами разобрались, что такое градиентный бустинг и выяснили, что он строит композицию последовательно, и каждый следующий алгоритм приближает вектор антиградиента на обучающей выборке. За счет чего он довольно сильно уменьшает ошибку уже построенной композиции на объектах обучения. По сути градиентный бустинг представляет собой градиентный спуск в пространстве всех возможных алгоритмов, всех возможных функций, и каждый шаг этого градиентного спуска делается по базовому алгоритму bn (x). К сожалению, градиентный бустинг в отличие от случайного леса может переобучаться. И в следующем видео мы поговорим о том, как с этим можно бороться.
