Дерево решений с градиентным усилением (GBDT) — это метод, основанный на ансамбле, в котором деревья последовательно обучаются остаткам функции потерь. Основная стоимость GBDT — построение деревьев решений, а самая трудоемкая часть — поиск лучших точек разделения для каждого узла. XGBoost¹, представленный в 2016 году, был эффективной реализацией решения этих проблем, и ниже мы рассмотрим, как он решил эти проблемы.

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

От функции потерь к дереву решений

Функция потерь и оптимальное конечное значение. Рассмотрим общую древовидную структуру, в которой у нас есть T конечных узлов, и каждый узел имеет вес/значение w. Взяв аппроксимацию второго порядка функции потерь, мы можем переписать ее в следующем виде. Последние два термина являются термином регуляризации, который штрафует количество листьев и значение листа соответственно.

f(x), g,и hявляются значением дерева, градиентом и гессианом для каждой выборки iв наборе данных. Каждая из этих выборок попадет в один из T конечных узлов. Вес листа будет предсказан для этой выборки. Используя это, мы можем переписать функцию потерь в следующем виде.

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

Минимальное значение функции потерь (L*) можно использовать в качестве показателя для оценки структуры дерева и решения об обрезке дерева или выбора порогового значения для разделения. по этой мере.

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

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

Факторы, влияющие на скорость

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

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

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

Доступ с поддержкой кеша: блочная структура помогает оптимизировать сложность вычислений при разделенном поиске, но создает другую проблему. Каждый отсортированный объект теперь находится в порядке, отличном от исходного индекса данных. Доступ к статистике градиента для них осуществляется в этом прерывистом порядке, что приводит к накладным расходам во времени. Чтобы решить эту проблему в приближенном алгоритме, выбирается оптимальный размер ²¹⁶ примеров в каждом блоке. Больший размер блока приведет к промаху кеша, так как статистика градиента не поместится в кеш процессора.

Сравнение с LightGBM

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

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

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

  1. Чен Т. и Гестрин К. (2016 г., август). Xgboost: масштабируемая система повышения дерева. В Материалы 22-й международной конференции acm sigkdd по открытию знаний и интеллектуальному анализу данных (стр. 785–794).
  2. Ке, Г., Мэн, К., Финли, Т., Ван, Т., Чен, В., Ма, В., … и Лю, Т. Ю. (2017). Lightgbm: высокоэффективное дерево решений для повышения градиента. Достижения в системах обработки нейронной информации, 30, 3146–3154.

Дайте мне знать, если у вас есть вопросы или отзывы в комментариях.