XGBoost, LightGBM или CatBoost - какой алгоритм бустинга следует использовать?

Алгоритмы градиентного бустинга являются наиболее популярными при обучении на табличных данных. За последние несколько лет нам посчастливилось иметь не только одну реализацию boosted trees, но и несколько алгоритмов boosting - каждый со своими уникальными характеристиками.

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

В чем их особенность?

Алгоритмы отличаются друг от друга реализацией алгоритма boosted trees, а также технической совместимостью и ограничениями. XGBoost был первым, кто попытался улучшить время обучения GBM, за ним последовали LightGBM и CatBoost, каждый со своей собственной техникой, в основном связанной с механизмом расщепления. Пакеты всех алгоритмов постоянно обновляются, добавляя новые функции и возможности. В большинстве случаев мы представляем поведение алгоритмов в R по умолчанию, хотя могут быть доступны и другие варианты. В этом разделе мы сравниваем только XGBoost, LightGBM и CatBoost. Если вы пропустили GBM, не волнуйтесь - вы найдете его в разделе результатов.

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

Сила сообщества - По нашему опыту, с XGBoost проще всего работать, когда вам нужно решить возникшие проблемы, потому что у него сильное сообщество и много соответствующих постов в сообществе. У LightGBM сообщество меньше, поэтому с ним немного сложнее работать или использовать расширенные функции. У CatBoost также небольшое сообщество, но у них есть отличный Telegram-канал, где разработчики продукта отвечают на вопросы в кратчайшие сроки.

Удобство анализа - При обучении модели, даже если вы тесно взаимодействуете с документацией, вы хотите убедиться, что обучение было проведено именно так, как вы задумали. Например, вы хотите убедиться, что нужные признаки были обработаны как категориальные и что деревья были построены правильно. При таких критериях CatBoost и LightGBM представляются мне скорее "черным ящиком", поскольку в R невозможно построить деревья и получить всю информацию о модели (например, невозможно получить список категориальных признаков модели). XGBoost более прозрачен, позволяет легко строить деревья и, поскольку в нем нет встроенной кодировки категориальных признаков, нет возможных сюрпризов, связанных с типом признаков.

Ограничения в работе модели - При выборе алгоритма для продакшена нельзя просто провести эксперименты в любимой среде (R/Python) и выбрать тот, который имеет наилучшие показатели, потому что, к сожалению, все алгоритмы имеют свои ограничения. Например, если вы используете Predictive Model Markup Language (PMML) для скоринга в продакшене, он доступен для всех алгоритмов. Однако в CatBoost вам разрешено использовать для этого только кодировку one-hot. Причина в том, что стандартное представление CatBoost для категориальных признаков не поддерживается PMML. Поэтому я рекомендую принять эти соображения во внимание, прежде чем начинать экспериментировать с собственными данными.

Теперь давайте рассмотрим их основные характеристики:

Сплиты

Перед обучением все алгоритмы создают пары признак-сплит для всех признаков. Примерами таких пар являются: (возраст, <5), (возраст, >10), (сумма, >500). Эти пары признак-сплит строятся на основе гистограммы и используются во время обучения в качестве возможных расщеплений узлов. Этот метод предварительной обработки быстрее, чем точный жадный алгоритм, который линейно перечисляет все возможные разбиения для непрерывных признаков.

lightGBM предлагает градиентную одностороннюю выборку (GOSS), которая выбирает разбиение, используя все экземпляры с большими градиентами (т.е. с большой ошибкой) и случайную выборку экземпляров с малыми градиентами. Чтобы сохранить одинаковое распределение данных при вычислении информационного выигрыша, GOSS вводит постоянный множитель для экземпляров данных с малыми градиентами. Таким образом, GOSS достигает хорошего баланса между увеличением скорости за счет уменьшения количества экземпляров данных и сохранением точности для выученных деревьев решений. Этот метод не является методом по умолчанию для LightGBM, поэтому его следует выбирать явно.

Catboost предлагает новую технику под названием Minimal Variance Sampling (MVS), которая представляет собой взвешенную выборку версии Stochastic Gradient Boosting. В этой технике взвешенная выборка происходит на уровне дерева, а не на уровне разбиения. Наблюдения для каждого дерева бустинга отбираются таким образом, чтобы максимизировать точность оценки разбиения.

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

Рост листьев

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

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

XGboost разделяет до заданного гиперпараметра max_depth, а затем начинает обрезать дерево в обратном направлении и удаляет части, за пределами которых нет положительного выигрыша. Такой подход используется, поскольку иногда за расщеплением без уменьшения потерь может следовать расщепление с уменьшением потерь. XGBoost также может выполнять рост дерева по листьям (как LightGBM).

Обработка пропущенных значений

Catboost имеет два режима обработки отсутствующих значений: "Min" и "Max". В режиме "Min" отсутствующие значения обрабатываются как минимальное значение для признака (им присваивается значение, которое меньше всех существующих значений). Таким образом, гарантируется, что при выборе разбиения будет учитываться разбиение, которое отделяет отсутствующие значения от всех остальных значений. "Max" работает точно так же, как и "Min", только с максимальными значениями.

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

Метод важности признаков

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

LightGBM и XGBoost имеют два похожих метода: Первый - "Gain", который представляет собой улучшение точности (или общий выигрыш), приносимое признаком ветвям, на которых он находится. Второй метод имеет разное название в каждом пакете: "split" (LightGBM) и "Frequency"/"Weight" (XGBoost). Этот метод вычисляет относительное количество раз, когда определенный признак встречается во всех расщеплениях деревьев модели. Этот метод может быть необъективным для категориальных признаков с большим количеством категорий.

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

Обработка категориальных признаков

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

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

XGBoost не имеет встроенного метода для категориальных признаков. Кодирование (one-hot, целевое кодирование и т.д.) должно выполняться пользователем.

Кто же победитель?

В нашем эксперименте мы использовали 4 набора данных, связанных с предотвращением мошенничества в мире электронной коммерции, с бинарной целевой переменной, указывающей, был ли заказ, сделанный клиентом, мошенническим или законным. Эти наборы учебных данных содержат около 300 признаков, относительно большую долю (~ 1/3 ) категориальных признаков и около 100 тысяч наблюдений.

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

Во всех экспериментах мы обучались на CPU, используя экземпляр AWS c4.xlarge.

Скорость обучения

Мы сравнили скорость обучения, пытаясь создать максимально похожие условия для всех алгоритмов. Для этого мы обучили модель с 4000 деревьев и глубиной 1 (только корневой узел), со скоростью обучения 0,01.

На графике ниже показаны результаты эксперимента. Каждая точка представляет собой среднее значение из 3 повторных тренировок.

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

Для наших наборов данных LightGBM, CatBoost и XGBoost были ~15x, 5x и 3x быстрее, чем GBM, соответственно.

Сравнение точности

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

В таблице ниже показаны результаты эксперимента по перекрестной валидации. Каждая ячейка представляет собой среднее значение WAUC из 5 повторных экспериментов.

В базовом наборе данных CatBoost превосходит остальные на 0,8-1%, что является значимой разницей. В других наборах данных различия не столь значительны, что говорит о том, что точность может не быть главным критерием при выборе алгоритма для этих наборов данных. Поэтому важно принимать во внимание другие критерии, такие как скорость и технические ограничения.

Примечания

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

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

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

Спасибо команде Яндекса за ценный вклад и обратную связь!

Радуйте нас своими комментариями, предложениями и мыслями!

Источник: m.vk.com

Комментарии: