Дружелюбное, но строгое объяснение

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

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

Вступление

Gradient Tree Boosting - один из лучших алгоритмов для работы со структурированными данными. Он используется повсеместно в основном потому, что он просто превосходит другие алгоритмы для огромного количества наборов данных. Он обладает множеством преимуществ, таких как тот факт, что его можно обучать на различных размерах выборки и относительно быстро (особенно с учетом недавних реализаций на GPU). Эти преимущества подтолкнули к тому, чтобы такие алгоритмы, как SVM, использовались все реже и реже.

Это семейство алгоритмов возникло на основе метода повышения, который является одной из самых мощных идей обучения, представленных за последние 25 лет. AdaBoost, представленный Йоавом Фройндом и Робертом Шапиром в 1997 году, был первым примером этого метода. Позже в том же году Лео Брейман понял, что повышение может быть переформулировано как задача оптимизации с соответствующей функцией затрат, что породило градиентное повышение, разработанное Джеромом Фридманом в 2001 году.

Повышение

Повышение - это метод ансамбля, который означает, что он объединяет результаты многих слабых учеников для создания мощного комитета. Слабый ученик - это тот, у которого частота ошибок немного выше, чем у случайных предположений. При бустинге слабые ученики строятся последовательно. Каждая модель построена на модифицированной версии входных данных, пытаясь сосредоточиться на ошибках, допущенных ее предшественницей. Модель повышения - это аддитивная модель. Это означает, что конечный результат представляет собой взвешенную сумму базисных функций (неглубокие деревья решений в случае повышения градиентного дерева). Первая версия Boosting (Adaboost.M1) была моделью классификации, в которой мы применяли знаковую функцию к результату аддитивного расширения. Объявив H нашей моделью и используя M базисных функций f, мы имеем:

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

В конце первой итерации мы построили первый классификатор слабого дерева решений с глубиной 1 (только 1 граница решения). Примеры слева были идеально классифицированы, но справа от границы решения были допущены 4 ошибки.

Затем происходит то, что входные наблюдения для второй модели взвешиваются с учетом ошибок, сделанных деревом f1. Второе дерево, f2, затем будет уделять особое внимание ошибкам, сделанным его предшественником (которые мы выделили).

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

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

Общий алгоритм Adaboost выглядит следующим образом (в псевдокоде):

На шаге 2.b мы вычисляем общую частоту ошибок для текущего классификатора. Затем, в 2.c, мы вычисляем общий вес, который будет применен к текущему слабому классификатору в окончательной формуле. В 2.d мы обновляем индивидуальные веса каждого наблюдения. Обратите внимание на использование экспоненциальной функции, которая подчеркивает тот факт, что неправильно классифицированное наблюдение получит гораздо больший вес в следующем раунде.

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

От повышения к усилению градиента

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

Итак, мы начинаем с нулевой функции и на каждом шаге добавляем конкретную функцию (результат слабого обучаемого) с весом β. В случае Adaboost и с учетом того, что результат классификации находится в {-1,1}, функция потерь L является экспоненциальной функцией потерь:

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

w_i не зависит от β или f, поэтому его следует рассматривать как константу по отношению к нашей цели минимизации. Теперь мы собираемся переписать цель, используя тот факт, что наша цель либо 1, либо -1. Мы вводим функцию A (для простоты обозначений) как ту, которую мы хотим минимизировать. Итак, мы разделяем цель на два случая: один, когда y_i и G (x_i) согласны, и другой, когда они не согласны:

Теперь цель - выявить индикаторную функцию, которую мы видим в алгоритме Adaboost. Итак, мы пишем:

Теперь мы хотим найти значение β, которое решает нашу задачу минимизации. Мы устанавливаем частную производную A по β равной 0 и решаем уравнение:

Как видите, за исключением множителя 1/2, мы возвращаемся к выражению 2.c алгоритма Adaboost с членом ошибки, равным выражению 2.b:

Теперь мы можем продемонстрировать окончательную эквивалентность (строка 2.d) алгоритма Adaboost. Итак, мы ранее ввели определение весов:

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

Теперь, если мы включим правило обновления (строка 2.b) прямой поэтапной аддитивной модели:

У нас есть:

Теперь, поскольку целевая метка равна -1 или 1, мы можем написать:

В итоге получаем:

И мы вернулись к правилу обновления весов 2.d Adaboost ожидать для последнего члена exp (-β_m). Этот последний член - единственное различие между двумя процедурами, но на самом деле он не повлияет на результат, потому что он умножает все веса на одно и то же значение. Итак, в целом мы продемонстрировали, что эти 2 процедуры абсолютно одинаковы.

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

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

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

Итак, что делает усиление градиента:

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

Процедура выглядит так:

Используя ту же функцию потерь на шагах 2.a и 2.b, эта процедура эквивалентна градиентному спуску в функциональном пространстве.

Давайте рассмотрим простой пример, чтобы наглядно представить, что здесь происходит. Допустим, мы пытаемся подогнать регрессионную модель к следующему набору данных (только 1 предиктор X1):

В конце первой итерации мы построили следующее дерево регрессии:

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

Мы подгоняем дерево решений к отрицательным остаткам:

И объединяем результаты:

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

Прочие потери при классификации

Отличие от Adaboost заключается в том, что Gradient Boosting позволяет обобщить процедуру обучения на другую функцию стоимости L. И что действительно интересно в этом обобщении, так это то, что вы можете использовать функции стоимости, которые имеют разные свойства, чтобы дать другое общее поведение процедуры (особенно относительно выбросов).

Можно показать, что экспоненциальная потеря имеет тот же минимизатор совокупности, что и биномиальное отрицательное логарифмическое правдоподобие или биномиальное отклонение:

Вот почему в реализации scikit-learn Gradient Boosting Classifier вы можете выбрать либо экспоненциальную потерю, либо отклонение.

Имейте в виду, что биномиальное отклонение - это то же самое, что и логистические потери (также известные как двоичная кросс-энтропия), когда ответ находится в наборе {0, 1}. В этом случае мы используем следующую формулу:

Вот почему пакет XGBoost предлагает функцию двоичных: логистических потерь.

Экспоненциальная потеря - это монотонно убывающая функция запаса y f (x). В настройке классификации с ответом -1/1 правило классификации G (x) = sign [f (x)] подразумевает, что наблюдения с положительным запасом классифицируются правильно (y и f (x) совпадают), а наблюдения с отрицательная маржа неправильно классифицирована (y и f (x) не согласуются). Таким образом, цель алгоритма классификации - как можно чаще получать положительную маржу. Критерий потерь должен наказывать отрицательную маржу намного сильнее, чем положительную. Давайте посмотрим, как ведут себя обычные функции потерь двоичной классификации в отношении запаса:

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

Прочие потери за регресс

В настройке регрессии обычно используются 3 разные функции потерь:

  • Квадрат потерь ошибок используется, например, в обычной регрессии методом наименьших квадратов. Он менее устойчив к выбросам или когда в данных слишком много шума, но все же предпочтительнее, когда нет выбросов:

  • Абсолютная потеря ошибок, более устойчивая при наличии выбросов:

  • Потеря хубера - это смесь двух вышеперечисленных:

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

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

Заключение

При наличии зашумленного набора данных квадратичная потеря ошибок для регрессии и экспоненциальная потеря могут быть не лучшим выбором, хотя оба они приводят к элегантному модульному алгоритму повышения (Adaboost). Для квадрата ошибок потерь можно просто подобрать базового ученика непосредственно к остаткам из текущей модели, а для экспоненциальных потерь выполнить взвешенную подгонку с весами, равными exp (-y f (x)). Градиентное повышение - это обобщение алгоритма повышения на другие функции стоимости. Это стало возможным благодаря выражению остатков текущего слабого ученика в виде отрицательного градиента функции затрат.

Ссылка

Элементы статистического обучения, интеллектуального анализа данных, вывода и прогнозирования. Тревор Хасти, Роберт Тибширани, Джером Фридман