Всем привет!

На данный момент мы рассмотрели 9 тем, от исследовательского анализа данных до анализа временных рядов в Python. Сегодня мы рассмотрим один из самых популярных и практичных алгоритмов машинного обучения: повышение градиента. Более подробную математику вы можете найти в формате статьи nbviewer.

Краткое содержание статьи

  1. Введение и история бустинга
  2. Алгоритм Gradient Boosting Machine
  3. Функции потерь
  4. Задание №10
  5. Полезные ресурсы

1. Введение и история бустинга

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

Более того, XGBoost часто является стандартным рецептом для победы в соревнованиях по ML. Он настолько популярен, что идея объединения XGBoosts стала мемом. Более того, повышение является важным компонентом многих рекомендательных систем; иногда даже считается брендом. Давайте посмотрим на историю развития бустинга.

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

Положительный математический ответ на этот вопрос был найден, но потребовалось несколько лет, чтобы разработать полностью работающие алгоритмы на основе этого решения, например AdaBoost. Эти алгоритмы используют жадный подход: во-первых, они создают линейную комбинацию простых моделей (базовых алгоритмов) путем повторного взвешивания входных данных. Затем модель (обычно дерево решений) строится на ранее неправильно предсказанных объектах, которым теперь присвоены большие веса.

Многие курсы машинного обучения изучают AdaBoost - предок GBM (Gradient Boosting Machine). Однако с тех пор, как AdaBoost объединился с GBM, стало очевидно, что AdaBoost - это всего лишь частный вариант GBM.

Сам алгоритм имеет очень четкую визуальную интерпретацию и интуицию для определения весов. Давайте посмотрим на следующую задачу классификации игрушек, в которой мы собираемся разделить данные между деревьями глубины 1 (также известными как «пни») на каждой итерации AdaBoost. Для первых двух итераций мы имеем следующую картину:

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

Вот более подробный пример AdaBoost, где по мере выполнения итерации мы можем видеть увеличение веса, особенно на границе между классами.

AdaBoost работает хорошо, но отсутствие объяснения того, почему алгоритм работает успешно, посеял семена сомнений. Некоторые считали это супер-алгоритмом, серебряной пулей, но другие были настроены скептически и считали, что AdaBoost просто переоснащен.

Проблема переобучения действительно существовала, особенно когда данные имели сильные выбросы. Следовательно, при таких проблемах AdaBoost работал нестабильно. К счастью, несколько профессоров статистического факультета Стэнфорда, которые создали лассо, эластичную сеть и случайный лес, начали исследовать алгоритм. В 1999 году Джером Фридман придумал обобщение разработки алгоритмов повышения - Gradient Boosting (Machine), также известное как GBM. Этой работой Фридман заложил статистическую основу для многих алгоритмов, обеспечивающих общий подход повышения для оптимизации в функциональном пространстве.

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

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

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

История GBM

После внедрения GBM прошло более 10 лет, прежде чем он стал неотъемлемой частью инструментария для науки о данных. GBM был расширен для применения к различным задачам статистики: GLMboost и GAMboost для усиления уже существующих моделей GAM, CoxBoost для кривых выживаемости и RankBoost и LambdaMART для ранжирования.

Многие реализации GBM также появились под разными названиями и на разных платформах: Stochastic GBM, GBDT (деревья решений с градиентным усилением), GBRT (деревья регрессии с градиентным усилением), MART (деревья множественной аддитивной регрессии) и другие. Кроме того, сообщество машинного обучения было очень сегментированным и разобщенным, что затрудняло отслеживание того, насколько широкое распространение получил бустинг.

В то же время бустинг активно использовался в поисковом рейтинге. Эта проблема была переписана в терминах функции потерь, которая штрафует ошибки в порядке вывода, поэтому стало удобно просто вставить ее в GBM. AltaVista была одной из первых компаний, которая ввела бустинг в рейтинге. Вскоре идеи распространились на Yahoo, Яндекс, Bing и т. Д. Как только это произошло, бустинг стал одним из основных алгоритмов, который использовался не только в исследованиях, но и в основных промышленных технологиях.

Соревнования по ML, особенно Kaggle, сыграли важную роль в популяризации. Теперь у исследователей была общая платформа, на которой они могли соревноваться в различных задачах науки о данных с большим количеством участников со всего мира. С помощью Kaggle можно тестировать новые алгоритмы на реальных данных, давая возможность алгоритмам сиять, и предоставлять полную информацию при совместном использовании результатов производительности модели в наборах данных о конкуренции. Именно это произошло с бустингом, когда он использовался в Kaggle (посмотрите интервью с победителями Kaggle, начиная с 2011 года, которые в основном использовали бустинг). Библиотека XGBoost быстро завоевала популярность после своего появления. XGBoost - не новый уникальный алгоритм; это просто чрезвычайно эффективная реализация классической GBM с дополнительной эвристикой.

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

2. Алгоритм Gradient Boosting Machine.

Мы собираемся решить задачу аппроксимации функции в общей среде контролируемого обучения. У нас есть набор функций X и целевых переменных y, которые мы используем для восстановления зависимости y = f (x). Мы восстанавливаем зависимость, аппроксимируя f (x) и понимая, какое приближение лучше, когда мы используем функцию потерь L (y, f), которую мы хотим минимизировать:

В настоящий момент мы не делаем никаких предположений относительно типа зависимости f (x), модели нашего приближения или распределения целевой переменной. Мы только ожидаем, что функция L (y, f) дифференцируема. Наша формула очень общая; давайте определим его для конкретного набора данных со средним значением для генеральной совокупности. Наше выражение для минимизации потери данных следующее:

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

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

Затем остается только найти подходящий итерационный алгоритм для минимизации последнего выражения. Градиентный спуск - самый простой и часто используемый вариант. Мы определяем градиент и добавляем к нему наши итерационные оценки (поскольку мы минимизируем потери, мы добавляем знак минус). Наш последний шаг - инициализировать наше первое приближение и выбрать количество итераций M. Давайте рассмотрим шаги этого неэффективного и наивного алгоритма:

Функциональный градиентный спуск

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

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

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

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

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

Классический алгоритм GBM Фридмана

Теперь мы можем определить классический алгоритм GBM, предложенный Джеромом Фридманом в 1999 году. Это контролируемый алгоритм, который имеет следующие компоненты:

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

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

Пошаговый пример: как работает GBM

Давайте посмотрим на пример того, как работает GBM. В этом примере игрушки мы восстановим зашумленную функцию

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

  • Данные игрушек
  • Количество итераций M = 3
  • Функция потерь среднеквадратичной ошибки L (y, f) = (y - f) ²
  • Градиент L (y, f) - это просто остатки r = (y-f)
  • Деревья решений как базовые алгоритмы
  • Гиперпараметры деревьев решений: глубина деревьев равна 2

Мы запустим GBM и нарисуем два типа графиков: текущее приближение (синий график) и каждое дерево, построенное на его псевдо-остатках (зеленый график). Номер графика соответствует номеру итерации:

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

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

3. Функции потерь

Что изменится, если мы захотим решить проблему классификации вместо регрессии? Нам нужно только выбрать подходящую функцию потерь L (y, f). Это наиболее важный момент высокого уровня, который определяет, как именно мы будем оптимизировать и какие характеристики мы можем ожидать в окончательной модели.

Самым придумывать это, как правило, не нужно - исследователи уже сделали это за нас. Сегодня мы рассмотрим функции потерь для двух наиболее распространенных целей: регрессии и бинарной классификации.

Функции регрессионных потерь

Начнем с задачи регрессии для y действительного числа. Чтобы выбрать подходящую функцию потерь, нам необходимо рассмотреть, какие из свойств условного распределения (y | x) мы хотим восстановить. Самые распространенные варианты:

  • L (y, f) = (y - f) ² a.k.a. L2 потеря или гауссова потеря. Это классическое условное среднее, самый простой и распространенный случай. Если у нас нет какой-либо дополнительной информации или требований для устойчивости модели, мы можем использовать гауссовские потери.
  • L (y, f) = | y - f | иначе говоря, L1 потеря или лапласовская потеря. На первый взгляд эта функция не кажется дифференцируемой, но на самом деле она определяет условную медиану. Как известно, медиана устойчива к выбросам, поэтому в некоторых случаях эта функция потерь лучше. Штраф за большие вариации не такой большой, как в L2.
  • Lq потери или квантильные потери. Вместо медианы используются квантили. Мы можем видеть, что эта функция асимметрична и наказывает наблюдения, которые находятся справа от определенного квантиля.

Давайте воспользуемся функцией потерь L_q для наших данных. Цель состоит в том, чтобы восстановить условный 75% -ный квантиль косинуса. Соберем все для GBM:

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

Общие результаты GBM с функцией квантильных потерь такие же, как результаты со смещением квадратичной функции потерь на ~ 0,135. Но если бы мы использовали квантиль 90%, у нас не было бы достаточно данных из-за того, что классы стали бы несбалансированными. Об этом нужно помнить, когда мы имеем дело с нестандартными проблемами.

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

Мы можем проиллюстрировать это на следующем примере. Данные генерируются из функции y = sin (x) / x с добавленным шумом, смесью нормального распределения и распределения Бернулли. Мы показываем функции на графиках A-D и соответствующую GBM на F-H (график E представляет начальную функцию):

"Первоначальный размер".

В этом примере мы использовали сплайны в качестве базового алгоритма. Видите, не всегда деревья для усиления?

Мы ясно видим разницу между функциями L2, L1 и функцией потери Хубера. Если мы выберем оптимальные параметры для потерь Хубера, мы сможем получить наилучшее возможное приближение среди всех наших вариантов. Разницу также можно увидеть в квантилях 10%, 50% и 90%.

К сожалению, функция потери Хубера поддерживается только очень немногими популярными библиотеками / пакетами; h2o поддерживает это, а XGBoost - нет. Это относится к другим вещам, более экзотическим, например, к условным ожиданиям, но все же может быть интересным знанием.

Классификационные функции потерь

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

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

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

Мы будем использовать логистические потери, чтобы найти то, что мы на самом деле увеличиваем. Итак, мы снова собрали то, что мы будем использовать для GBM:

На этот раз инициализация алгоритма немного сложнее. Во-первых, наши классы несбалансированны (63% против 37%). Во-вторых, нет известной аналитической формулы для инициализации нашей функции потерь, поэтому мы должны искать ее с помощью поиска:

Наше оптимальное начальное приближение составляет около -0,273. Вы могли догадаться, что оно отрицательное, потому что выгоднее все предсказать как самый популярный класс, но формулы для точного значения не существует. Теперь давайте, наконец, запустим GBM и посмотрим, что на самом деле происходит под капотом:

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

Вес

Иногда возникает ситуация, когда нам нужна более конкретная функция потерь для нашей проблемы. Например, в финансовых временных рядах мы можем захотеть придать больший вес крупным движениям во временных рядах; для прогнозирования оттока более полезно предсказать отток клиентов с высоким LTV (или пожизненной ценностью: сколько денег клиент принесет в будущем).

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

Вместо этого был изобретен очень простой инструмент (о котором редко вспоминают на практике): взвешивание наблюдений и назначение весовых функций. Самый простой пример такого взвешивания - установка весов для баланса класса. В общем, если мы знаем, что какое-то подмножество данных как во входных переменных, так и в целевой переменной имеет большее значение для нашей модели, мы просто присваиваем им больший вес w (x, y) . Основная цель - выполнение общих требований к весам:

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

Ясно, что для произвольных весов мы не знаем статистических свойств нашей модели. Часто связывание весов со значениями y может быть слишком сложным. Например, использование весов, пропорциональных | y | в функции потерь L1, не эквивалентно потерям L2, потому что градиент не учитывается учитывать значения самих прогнозов.

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

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

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

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

Заключение

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

Практика и соревнования по машинному обучению показывают, что в стандартных задачах (за исключением изображений, звука и очень разреженных данных) GBM часто является наиболее эффективным алгоритмом (не говоря уже о наложении и высокоуровневых ансамблях, где GBM почти всегда является их частью). ). Также существует множество адаптаций GBM для обучения с подкреплением (Minecraft, ICML 2016). Кстати, алгоритм Виолы-Джонса, который до сих пор используется в компьютерном зрении, основан на AdaBoost.

В этой статье мы намеренно опустили вопросы, касающиеся регуляризации, стохастичности и гиперпараметров GBM. Не случайно мы использовали небольшое количество итераций M = 3 повсюду. Если бы мы использовали 30 деревьев вместо 3 и обучили GBM, как описано, результат не был бы таким предсказуемым:

4. Задание №10.

Полные версии заданий объявляются каждую неделю при новом запуске курса (1 октября 2018 г.). А пока вы можете потренироваться с демо-версией: Kaggle Kernel, nbviewer.

5. Полезные ресурсы

Автор: Алексей Натэкин, основатель OpenDataScience, евангелист по машинному обучению. Перевод и редакция: Ольга Дайховская, Анастасия Манохина, Егор Полусмак, Юаньюань Пао.