в чем разница между моделями xgboost lightgbm и catboost или какие их основные особенности
В этом блоге мы попытаемся определить, существует ли один настоящий алгоритм-убийца, который превосходит их всех. Мы сравним XGBoost, LightGBM и CatBoost со старым GBM, измерим точность и скорость на четырех наборах данных, связанных с мошенничеством. Мы также представим краткое сравнение всех новых алгоритмов, что позволит вам быстро понять основные различия между каждым из них. Полезно иметь предварительное представление о деревьях с градиентным бустом.
В чем их особенность?
Прежде чем мы погрузимся в детали, необходимо знать несколько важных вещей:
Теперь давайте рассмотрим их основные характеристики:
Перед обучением все алгоритмы создают пары признак-сплит для всех признаков. Примерами таких пар являются: (возраст, 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 недостающие значения будут распределяться в ту сторону, которая уменьшает потери в каждом разбиении.
Метод важности признаков
У XGBoost есть еще один метод, «Охват», который представляет собой относительное количество наблюдений, связанных с признаком. Для каждого признака мы подсчитываем количество наблюдений, используемых для выбора узла листа.
Обработка категориальных признаков
LightGBM разделяет категориальные признаки, разбивая их категории на 2 подмножества. Основная идея заключается в том, чтобы сортировать категории в соответствии с целью обучения при каждом разбиении. По нашему опыту, этот метод не обязательно улучшает модель LightGBM. Он имеет сравнимую (а иногда и худшую) производительность, чем другие методы (например, кодирование цели или метки).
XGBoost не имеет встроенного метода для категориальных признаков. Кодирование (one-hot, целевое кодирование и т.д.) должно выполняться пользователем.
В нашем эксперименте мы использовали 4 набора данных, связанных с предотвращением мошенничества в мире электронной коммерции, с бинарной целевой переменной, указывающей, был ли заказ, сделанный клиентом, мошенническим или законным. Эти наборы учебных данных содержат около 300 признаков, относительно большую долю (
1/3 ) категориальных признаков и около 100 тысяч наблюдений.
Во всех экспериментах мы обучались на 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 для данного конкретного набора данных.
Помимо работы, которую мы представили здесь, есть и другие шаги, которые можно предпринять для повышения точности и скорости. Для повышения скорости очень полезным может быть обучение на графических процессорах. Еще одним важным шагом является настройка большого количества гиперпараметров. Существует множество гиперпараметров, которые могут быть настроены в каждом пакете, некоторые из них являются эксклюзивными для определенного алгоритма. В одном из наших будущих блогов мы представим и сравним методы настройки, которые можно использовать с алгоритмами бустинга, такими как трехфазный поиск и байесовская оптимизация. Следите за новостями.
Все пакеты постоянно обновляются и улучшаются, поэтому мы рекомендуем следить за их релизами, которые иногда включают новые удивительные возможности.
Спасибо команде Яндекса за ценный вклад и обратную связь!
Радуйте нас своими комментариями, предложениями и мыслями!
XGBoost, LightGBM or CatBoost — which boosting algorithm should I use?
Gradient boosted trees have become the go-to algorithms when it comes to training on tabular data. Over the past couple of years, we’ve been fortunate to have not only one implementation of boosted trees, but several boosting algorithms– each with their own unique characteristics.
In this blog, we will try to determine whether there is one true killer algorithm that beats them all. We’ll compare XGBoost, LightGBM and CatBoost to the older GBM, measuring accuracy and speed on four fraud related datasets. We’ll also present a concise comparison among all new algorithms, allowing you to quickly understand the main differences between each. A prior understanding of gradient boosted trees is useful.
What’s their special thing?
The algorithms differ from one another in the implementation of the boosted trees algorithm and their technical compatibilities and limitations. XGBoost was the first to try improving GBM’s training time, followed by LightGBM and CatBoost, each with their own techniques, mostly related to the splitting mechanism. The packages of all algorithms are constantly being updated with more features and capabilities. In most cases, we present the default behavior of the algorithms in R, although other options may be available. In this section, we compare only XGBoost, LightGBM and CatBoost. If you miss GBM, don’t worry–you’ll find it in the results section.
A few important things to know before we dive into details:
Community strength — From our experience, XGBoost is the easiest to work with when you need to solve problems you encounter, because it has a strong community and many relevant community posts. LightGBM has a smaller community which makes it a bit harder to work with or use advanced features. CatBoost also has a small community, but they have a great Telegram channel where questions are answered by the package developers in a short time.
Analysis ease — When training a model, even if you work closely with the documentation, you want to make sure the training was performed exactly like you meant it to. For example, you want to make sure the right features were treated as categorical and that the trees were built correctly. With this criteria, I find CatBoost and LightGBM to be more of a blackbox, because it is not possible in R to plot the trees and to get all of the model’s information (it is not possible to get the model’s categorical features list, for example). XGBoost is more transparent, allowing easy plotting of trees and since it has no built-in categorical features encoding, there are no possible surprises related to features type.
Model serving limitations — When choosing your production algorithm, you can’t just conduct experiments in your favorite environment (R/Python) and choose the one with the best performance, because unfortunately, all algorithms have their limitations. For example, if you use a Predictive Model Markup Language (PMML) for scoring in production, it is available for all algorithms. However, in CatBoost you are only allowed to use one-hot encoding for that. The reason is that default CatBoost representation for categorical features is not supported by PMML. Hence, I recommend taking these considerations into account before starting to experiment with your own data.
Now let’s go over their main characteristics:
Splits
Before learning, all algorithms create feature-split pairs for all features. Example for such pairs are: (age, 10), (amount, >500). These feature-split pairs are histogram-based built, and are used during learning as possible node splits. This preprocessing method is faster than the exact greedy algorithm, which linearly enumerates all the possible splits for continuous features.
lightGBM offers gradient-based one-side sampling (GOSS) that selects the split using all the instances with large gradients (i.e., large error) and a random sample of instances with small gradients. In order to keep the same data distribution when computing the information gain, GOSS introduces a constant multiplier for the data instances with small gradients. Thus, GOSS achieves a good balance between increasing speed by reducing the number of data instances and keeping the accuracy for learned decision trees. This method is not the default method for LightGBM, so it should be selected explicitly.
Catboost offers a new technique called Minimal Variance Sampling (MVS), which is a weighted sampling version of Stochastic Gradient Boosting. In this technique, the weighted sampling happens in the tree-level and not in the split-level. The observations for each boosting tree are sampled in a way that maximizes the accuracy of split scoring.
XGboost is not using any weighted sampling techniques, which makes its splitting process slower compared to GOSS and MVS.
Leaf growth
Catboost grows a balanced tree. In each level of such a tree, the feature-split pair that brings to the lowest loss (according to a penalty function) is selected and is used for all the level’s nodes. It is possible to change its policy using the grow-policy parameter.
LightGBM uses leaf-wise (best-first) tree growth. It chooses to grow the leaf that minimizes the loss, allowing a growth of an imbalanced tree. Because it doesn’t grow level-wise, but leaf-wise, overfitting can happen when data is small. In these cases, it is important to control the tree depth.
XGboost splits up to the specified max_depth hyperparameter and then starts pruning the tree backwards and removes splits beyond which there is no positive gain. It uses this approach since sometimes a split of no loss reduction may be followed by a split with loss reduction. XGBoost can also perform leaf-wise tree growth (as LightGBM).
Missing values handling
Catboost has two modes for processing missing values, “Min” and “Max”. In “Min”, missing values are processed as the minimum value for a feature (they are given a value that is less than all existing values). This way, it is guaranteed that a split that separates missing values from all other values is considered when selecting splits. “Max” works exactly the same as “Min”, only with maximum values.
In LightGBM and XGBoost missing values will be allocated to the side that reduces the loss in each split.
Feature importance methods
Catboost has two methods: The first is “PredictionValuesChange”. For each feature, PredictionValuesChange shows how much, on average, the prediction changes if the feature value changes. A feature would have a greater importance when a change in the feature value causes a big change in the predicted value. This is the default feature importance calculation method for non-ranking metrics. The second method is “LossFunctionChange”. This type of feature importance can be used for any model, but is particularly useful for ranking models. For each feature the value represents the difference between the loss value of the model with this feature and without it. Since it is computationally expensive to retrain the model without one of the features, this model is built approximately using the original model with this feature removed from all the trees in the ensemble. The calculation of this feature importance requires a dataset.
LightGBM and XGBoost have two similar methods: The first is “Gain” which is the improvement in accuracy (or total gain) brought by a feature to the branches it is on. The second method has a different name in each package: “split” (LightGBM) and “Frequency”/”Weight” (XGBoost). This method calculates the relative number of times a particular feature occurs in all splits of the model’s trees. This method can be biased by categorical features with a large number of categories.
XGBoost has one more method, “Coverage”, which is the relative number of observations related to a feature. For each feature, we count the number of observations used to decide the leaf node for.
Categorical features handling
Catboost uses a combination of one-hot encoding and an advanced mean encoding. For features with low number of categories, it uses one-hot encoding. The maximum number of categories for one-hot encoding can be controlled by the one_hot_max_size parameter. For the remaining categorical columns, CatBoost uses an efficient method of encoding, which is similar to mean encoding but with an additional mechanism aimed at reducing overfitting. Using CatBoost’s categorical encoding comes with a downside of a slower model. We won’t go into how exactly their encoding works, so for more details see CatBoost’s documentation.
LightGBM splits categorical features by partitioning their categories into 2 subsets. The basic idea is to sort the categories according to the training objective at each split. From our experience, this method does not necessarily improve the LightGBM model. It has comparable (and sometimes worse) performance than other methods (for example, target or label encoding).
XGBoost doesn’t have an inbuilt method for categorical features. Encoding (one-hot, target encoding, etc.) should be performed by the user.
Who is the winner?
We used 4 datasets in our experiment related to fraud prevention in the e-commerce world, with a binary target variable indicating whether an order made by a customer was fraudulent or legitimate. These example training datasets have around 300 features, a relatively high portion (
⅓) of categorical features and roughly 100K observations.
The metric we use is weighted AUC (WAUC), which is similar to AUC but allows the use of different weights to different classes. In our real world data, we have orders that were declined and we can only partially tag them. Therefore, we gave these orders a lower weight in the AUC calculation. Our adjusted metric will be further presented in a future blog.
In all experiments we trained on CPU, using an AWS c4.xlarge instance.
Training speed
We compared the training speed, attempting to create as similar as possible conditions to all algorithms. To do this, we trained a model with 4000 trees and a depth of 1 (root node only), with a learning rate of 0.01.
The plot below shows the results of the experiment. Each point represents the average of 3 repeated trainings.
It is clear that LightGBM is the fastest out of all the other algorithms. CatBoost and XGBoost also present a meaningful improvement in comparison to GBM, but they are still behind LightGBM.
For our datasets, LightGBM, CatBoost and XGBoost were
15x, 5x and 3x faster than GBM, respectively.
Accuracy comparison
We compared the algorithms’ WAUC on a test set after performing cross-validation hyperparameter tuning across the relevant algorithm’s parameters. We won’t get into the details regarding the chosen hyperparameters, but one thing worth mentioning is that the hyperparameters that were chosen for CatBoost resulted in a more complex model compared to the other algorithms, meaning that the final model almost always had a larger number of trees and a higher depth.
The table below shows the test results of the cross-validation experiment. Each cell represents the average WAUC of 5 repeated experiments.
In the baseline dataset, CatBoost outperforms the rest by 0.8–1%, which is a meaningful difference. In the other datasets, the differences are not as significant, suggesting that accuracy might not be the main criterion when we choose an algorithm for these datasets. So, it’s important to take into account other criteria such as speed and technical limitations.
Endnotes
After working with all algorithms, we found that unfortunately there is no one winner across all criteria. Therefore, at Riskified, we chose to implement all of them in our systems and select the right one considering the relevant use-case. For example, if training speed is our pain point, we use LightGBM. In tasks where we need top accuracy, we may train all of the algorithms to find the one with the highest WAUC for that specific dataset.
On top of the work we presented here, there are other steps that can be taken for improving accuracy and speed. For improving speed, training on GPUs can be very meaningful. Another important step would be to tune a large number of hyperparameters. There are many hyperparameters that can be tuned in each package, some being exclusive to a specific algorithm. In one of our future blogs, we’ll present and compare tuning methods that can be used with boosting algorithms, such as three-phase search and Bayesian optimization. Stay tuned.
All packages are constantly being updated and improved, so we recommend following their releases, which sometimes include amazing new features.
Thanks to the Yandex team for their valuable inputs and feedback!
Boost us with your comments, suggestions and thoughts!
Черновое сравнение XGBoost, LightGBM и CatBoost на классификации MNIST
Снижение размерности
Датасет представляет из себя набор из нескольких десятков черно-белых картинок размером 28*28 пикселей с 256 градациями. Развернув картинку в вектор, получаем 784 признака на сэмпл. Многовато. XBGoost на таких сэмплах учится более часа на моем железе, и это сильно снижает возможности пройтись по пространству гиперпараметров и получить оптимальный набор настроек. То есть эксперименты затруднены.
Поэтому я решил сжать каждое изображение с помощью Variational AutoEncoder до 64 параметров. Реализацию VAE я взял прямо из репозитория Keras https://github.com/fchollet/keras/blob/master/examples/variational_autoencoder.py.
Такая трансформация немного ухудшает достигаемую точность. С другой стороны, более быстрый обсчет одного варианта гиперпараметров позволяет лучше настроить модель.
Исходный текст моделей
Результаты
Модели оценивались по значению logloss для тестовой выборки, и по значению точности на этой выборки.
Оптимум для XGBoost: loss=0.07388 accuracy=0.9771
Сложность модели nb_trees=2110
Оптимум для CatBoost: loss=0.06604 acc=0.9795
Сложность модели nb_trees=5000
Оптимум для LightGBM: loss=0.07778 acc=0.9746
Сложность модели nb_trees=1524
Предварительные выводы
1) В целом, CatBoost вполне может соперничать с XGBoost, по крайней мере на некоторых задачах. Например, на задаче https://www.kaggle.com/c/msk-redefining-cancer-treatment у меня XGBoost рвет CatBoost как тузик грелку.
2) Подбор правильных гиперпараметров очень важен.
3) Скорость обучения для CatBoost надо задавать больше, чем аналогичный параметр для XGBoost и LightGBM.
Что внутри XGBoost, и при чем здесь Go
В мире машинного обучения одними из самых популярных типов моделей являются решающее дерево и ансамбли на их основе. Преимуществами деревьев являются: простота интерпретации, нет ограничений на вид исходной зависимости, мягкие требования к размеру выборки. Деревья имеют и крупный недостаток — склонность к переобучению. Поэтому почти всегда деревья объединяют в ансамбли: случайный лес, градиентный бустинг и др. Сложными теоретическими и практическим задачами являются составление деревьев и объединение их в ансамбли.
Откуда растут деревья?
Рассмотрим сначала общие положения. Обычно работают с деревьями, где:
В данном дереве имеем 2 узла, 2 решающих правил и 3 листа. Под кружочками указаны значения — результат применения дерева к какому-то объекту. Обычно, к результату вычисления дерева или ансамбля деревьев применяют функцию трансформации. Например, сигмоиду для задачи бинарной классификации.
Для получения предсказаний от ансамбля деревьев, полученного методом градиентного бустинга, нужно сложить результаты предсказаний всех деревьев:
Деревья XGBoost
В XGBoost есть несколько классов (в смысле ООП) деревьев. Будем говорить об RegTree (см. include/xgboost/tree_model.h ), которая со слов документации является основной. Если оставить только детали, важные для предсказаний, то члены класса выглядят максимально просто:
Отсюда следуют две вещи:
Можно выделить следующие особенности:
В функции GetLeafIndex мы в цикле спускаемся по узлам дерева, пока не попадем в лист.
Деревья LightGBM
В LightGBM нет структуры данных для узла. Вместо этого в структуре данных дерева Tree (файл include/LightGBM/tree.h ) содержатся массивы значений, где в качестве индекса выступает номер узла. Значения в листьях также хранятся в отдельных массивах.
LightGBM поддерживает категориальные признаки. Поддержка осуществляется с помощью битового поля, которое хранится в cat_threshold_ для всех узлов. В cat_boundaries_ хранит, к какому узлу какая часть битового поля соответствует. Поле threshold_ для категориального случая переводится в int и соответсвует индексу в cat_boundaries_ для поиска начала битового поля.
Рассмотрим решающее правило для категориального признака:
Видно, что в зависимости от missing_type значение NaN автоматически спускает решение по правой ветви дерева. Иначе NaN заменяется на 0. Поиск значения в битовом поле осуществляется достаточно просто:
т.е., например, для категориального признака int_fval=42 проверяется, выставлен ли 41-ый (нумерация с 0) бит в массиве.
Этот подход имеет один существенный недостаток: если категориальный признак может принимать большие значения, например 100500, то для каждого решающего правила для этого признака будет создано битовое поле размером до 12564 байт!
Поэтому желательно перенумеровать значения категориальных признаков, чтобы они шли непрерывно от 0 до максимального значения.
Со своей стороны я внес поясняющие правки в LightGBM и их приняли.
leaves — библиотека для предсказаний в Go
XGBoost и LightGBM очень мощные библиотеки для построения моделей градиентного бустинга на решающих деревьях. Для их использования в backend сервисе, где необходимы алгоритмы машинного обучения, необходимо решить следующие задачи:
Основные возможности библиотеки:
Несмотря на то, что язык Go работает медленней C++ (в основном из-за более тяжелого runtime и проверок времени выполнения), благодаря ряду оптимизаций удалось достичь скорости предсказаний, сопоставимой с вызовом C API оригинальных библиотек.
Более подробно о результатах и способе сравнений есть в репозитории на github.
Зри в корень
Для тех же, кому интересна тема применения моделей градиентного бустинга в их сервисах на языке Go, рекомендую ознакомиться с библиотекой leaves. С помощью leaves можно довольно просто использовать leading edge решения в машинном обучении в вашей production среде, практически не проигрывая по скорости в сравнении с оригинальными реализациям на C++.