Бустеры градиента

XGBoost

GBM, потрясшая мир

А теперь давайте уберем слона - XGBoost. Это самый популярный родственник в семействе Gradient Boosting. XGBoost с его молниеносно быстрой реализацией ворвался на сцену и почти единогласно изменил ситуацию в свою пользу. Вскоре Gradient Boosting через XGBoost стал правящим королем в соревнованиях Kaggle Competitions, и довольно скоро он просочился в мир бизнеса.

Было несколько ключевых нововведений, которые сделали XGBoost настолько эффективным:

Явная регуляризация

Подобно Regularized Greedy Forest, XGBoost также имеет явный член регуляризации в целевой функции.

γ - это член регуляризации, который штрафует T, количество листьев в дереве, а λ - член регуляризации, который штрафует w, веса различных листьев.

Это гораздо более простой термин регуляризации, чем некоторые из способов, которые мы видели в Regularized Greedy Forest.

Реализация, не зависящая от целевой функции

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

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

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

Позволять,

Приблизительная функция потерь:

Первый член, убыток, является постоянным на этапе построения дерева, t, и поэтому не добавляет ценности цели оптимизации. Итак, удалив его и упростив, мы получаем,

Подставляя Ω на член регуляризации, получаем:

Функция f (x), о которой мы говорим, по сути является деревом с весами листьев w. Итак, если мы определим Iⱼ как набор экземпляров в листе j, мы можем подставить древовидную структуру непосредственно в уравнение и упростить его следующим образом:

Обнуляя это уравнение, мы можем найти оптимальное значение для wⱼ как:

Возвращая это в функцию потерь и упрощая, мы получаем:

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

См. Здесь для получения списка всех целевых функций, которые предварительно встроены в XGBoost.

Стратегия построения дерева

Стратегия построения дерева находится где-то посередине между классическим усилением градиента и регуляризованными жадными лесами. В то время как классическое усиление градиента рассматривает дерево на каждом этапе как черный ящик, Regularized Greedy Forest работает на уровне листа, обновляя любую часть леса на каждом этапе. XGBoost занимает золотую середину и считает дерево, созданное в предыдущей итерации, священным, но при создании дерева для любой итерации он не использует стандартные меры примесей, а использует функцию потерь на основе градиента, которую мы вывели в последнем разделе в процесс построения дерева. В то время как в классическом Gradient Boosting оптимизация функции потерь происходит после построения дерева, XGBoost также получает эту оптимизацию во время процесса построения дерева.

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

Алгоритм нахождения расщеплений

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

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

  1. Предложите возможные точки разделения для всех функций, используя процентили функций.
  2. Сопоставьте непрерывные объекты с сегментами, разделенными точками разделения кандидатов
  3. Агрегируйте статистику градиента для всех функций на основе возможных точек разделения.
  4. Находит лучшее решение среди предложений на основе совокупной статистики

Взвешенный квантильный набросок

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

Обнаружение разделения с учетом разреженности

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

  1. Наличие пропущенных значений в данных
  2. Частые нулевые значения
  3. Артефакты разработки функций, такие как One-Hot Encoding

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

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

Это нововведение имеет двоякое преимущество:

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

Улучшения производительности

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

Блок столбцов для параллельного обучения

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

Доступ с учетом кеша

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

Блоки для внепрограммных вычислений

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

  • Сжатие блоков, при котором каждый блок сжимается перед сохранением и распаковывается на лету во время чтения.
  • Разделение блоков, при котором блок разбивается на несколько частей и сохраняется на нескольких дисках (если есть). И программа предварительной выборки считывает блок, поочередно переключаясь между двумя дисками, тем самым увеличивая пропускную способность чтения с диска.

Гиперпараметры

У XGBoost так много статей и блогов о гиперпараметрах и их настройке, что я даже не буду пытаться это сделать.

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

Основные из них:

eta [по умолчанию = 0,3, псевдоним: learning_rate]

  • Уменьшение размера шага, используемое в обновлении, чтобы предотвратить переоснащение. После каждого шага повышения мы можем напрямую получить веса новых функций, а eta уменьшает веса функций, чтобы сделать процесс повышения более консервативным.
  • диапазон: [0,1]

гамма [по умолчанию = 0, псевдоним: min_split_loss]

  • Минимальное снижение потерь, необходимое для дальнейшего разбиения на листовом узле дерева. Чем больше гамма, тем более консервативным будет алгоритм.
  • диапазон: [0, ∞]

max_depth [по умолчанию = 6]

  • Максимальная глубина дерева. Увеличение этого значения сделает модель более сложной и с большей вероятностью переобучится. 0 принимается только в политике роста с учетом потерь, когда tree_method установлен как hist и указывает на отсутствие ограничения по глубине. Помните, что XGBoost агрессивно расходует память при обучении глубокого дерева.
  • диапазон: [0, ∞] (0 принимается только в политике роста с учетом потерь, когда tree_method установлен как hist)

min_child_weight [default = 1]

  • Минимальная сумма веса экземпляра (гессиан), необходимая для ребенка. Если на этапе разбиения дерева получается листовой узел с суммой весов экземпляров меньше min_child_weight, то процесс построения откажется от дальнейшего разбиения. В задаче линейной регрессии это просто соответствует минимальному количеству экземпляров, которое должно быть в каждом узле. Чем больше min_child_weight, тем более консервативным будет алгоритм.
  • диапазон: [0, ∞]

подвыборка [по умолчанию = 1]

  • Соотношение подвыборки обучающих примеров. Установка его на 0,5 означает, что XGBoost будет случайным образом выбирать половину обучающих данных перед выращиванием деревьев. и это предотвратит переоснащение. Субдискретизация будет выполняться один раз на каждой итерации повышения.
  • диапазон: (0,1]

colsample_bytree, colsample_bylevel, colsample_bynode [default = 1]

  • Это семейство параметров для подвыборки столбцов.
  • Все параметры colsample_by * имеют диапазон (0, 1], значение по умолчанию 1, и определяют долю столбцов, подлежащих подвыборке.
  • colsample_bytree - это соотношение столбцов подвыборки при построении каждого дерева. Подвыборка выполняется один раз для каждого построенного дерева.
  • colsample_bylevel - отношение подвыборки столбцов для каждого уровня. Субдискретизация выполняется один раз для каждого нового уровня глубины, достигнутого в дереве. Столбцы выбираются из набора столбцов, выбранных для текущего дерева.
  • colsample_bynode - это отношение подвыборки столбцов для каждого узла (разбиение). Субдискретизация происходит каждый раз, когда оценивается новое разбиение. Столбцы выбираются из набора столбцов, выбранных для текущего уровня.
  • colsample_by * параметры работают кумулятивно. Например, комбинация {‘colsample_bytree’: 0.5, ‘colsample_bylevel ’: 0.5, ‘colsample_bynode’: 0.5} с 64 функциями оставит 8 функций на выбор для каждого разделения.

лямбда [по умолчанию = 1, псевдоним: reg_lambda]

  • Член L2 регуляризации весов. Увеличение этого значения сделает модель более консервативной.

альфа [по умолчанию = 0, псевдоним: reg_alpha]

  • Член регуляризации L1 на весах. Увеличение этого значения сделает модель более консервативной.

ОБНОВЛЕНИЕ - 13–02–2020

Лиственный рост деревьев

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

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

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

Вы можете включить построение деревьев по листам в XGBoost, установив для параметра tree_method значение «hist», а для параметра grow_policy значение «lossguide».

Другие статьи в Бустеры градиента

использованная литература

  1. Фридман, Джером Х. Аппроксимация функции жадности: машина повышения градиента. Анна. Статист. 29 (2001), нет. 5, 1189–1232.
  2. Чен, Тяньци и Гестрин, Карлос. (2016). XGBoost: масштабируемая система повышения качества дерева. 785–794. 10.1145 / 2939672.2939785.

Первоначально опубликовано на http://deep-and-shallow.com 12 февраля 2020 г.