XGBoost - это высокоэффективная библиотека, предназначенная для решения задач регрессии и классификации в рамках структуры Gradient Boosting. Он был разработан Т. Ченом и К. Гестрином в 2016 году и предусматривал создание деревьев с усилением экстремального градиента.

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

Теперь давайте рассмотрим эти характеристики, чтобы понять мощь XGBoost.

Регуляризация

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

Алгоритмы разделения и распараллеливание

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

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

Затем мы могли бы поговорить о поиске разбиения с учетом разреженности, который объясняет, как XGBoost обрабатывает разреженные данные в данных, такие как наличие 1) отсутствующих данных, 2) плотных нулевых записей, 3) горячего кодирования. ценности. Чтобы алгоритм знал об этих разреженности, XGBoost определяет для них направление по умолчанию. Оптимальное направление по умолчанию можно найти, попробовав оба направления в разбиении и выбрав то, которое предлагает максимальное усиление. Для поиска оптимального направления просматриваются только не пропущенные наблюдения, что приводит к снижению сложности вычислений.

Доступ с учетом кеша и блоки для внепрограммных вычислений

Другие характеристики XGBoost также делают его быстрым, и они больше связаны с компьютерным оборудованием. Один из них - Доступ с учетом кеша. Для расчета прироста в каждом разбиении XGBoost использует кэш ЦП для хранения вычисленных градиентов и Гессианов (покрытия) для быстрого выполнения необходимых вычислений. Когда данные не помещаются в кэш и основную память, становится важным использовать дисковое пространство. В этом случае очень важны блоки для внепрограммных вычислений. Считывание / запись данных с жесткого диска - дорогостоящая операция. Чтобы преодолеть это, с помощью сжатия блоков каждый блок сжимается по столбцам и распаковывается при загрузке в основную память. Хотя распаковка требует времени, она все же быстрее, чем чтение с диска. А в сегментировании блоков, если доступно несколько дисков, данные разделяются на эти диски, что увеличивает скорость чтения с диска.

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

Надеюсь, вам понравилось!

[1]: Тианки Чен, Карлос Гестрин (10 июня 2016 г.). XGBoost: масштабируемая система повышения качества дерева