Полное объяснение LightGBM - самой быстрой модели повышения градиента
LightGBM - это модель дерева решений Gradient Boosting (GBDT), разработанная Microsoft в 2016 году. По сравнению с другими моделями GBDT, LightGBM отличается более быстрой эффективностью обучения и высокой точностью.
Нет принципиальной разницы в структуре между LightGBM и общей моделью дерева решений Gradient Boosting Decision Tree, но с помощью следующих специальных методов LightGBM ускоряется в обучении.
- Односторонняя выборка на основе градиента (GOSS)
- Поиск наилучшего значения на основе гистограммы при расщеплении узлов дерева
- Оптимальное разделение по категориальным признакам
- Эксклюзивный набор функций
- Листовая стратегия роста деревьев
- Параллельная оптимизация
1. Односторонняя выборка на основе градиента (GOSS)
Обучение с помощью классического повышения градиента на основе дерева (GBDT) - это повторяющийся процесс обучения нового дерева для соответствия ошибкам прогнозирования предыдущего набора деревьев для всех экземпляров обучающего набора. (Ошибки прогнозирования - это градиенты функции потерь на всех экземплярах обучающего набора)
Итак, по умолчанию GBDT использует экземпляры всего обучающего набора для обучения каждого дерева в его ансамбле.
Для этого LightGBM представляет GOSS, в котором нам просто нужно использовать часть обучающего набора для обучения каждого дерева ансамбля. Интуиция GOSS
- Обучающий экземпляр с большим градиентом означает, что этот экземпляр имеет большую текущую ошибку прогнозирования и должен быть основной целью для размещения в следующем дереве ансамбля.
- Обучающий экземпляр с малым градиентом означает, что этот экземпляр имеет относительно небольшую текущую ошибку предсказания и не нуждается в следующем дереве ансамбля, чтобы слишком беспокоиться, поэтому мы можем отбросить его с некоторой вероятностью.
Вообще говоря, основная идея GOSS состоит в том, что перед обучением следующего дерева ансамбля мы сохраняем обучающие экземпляры с относительно большим градиентом и отбрасываем некоторые обучающие экземпляры с небольшим градиентом.
На рисунках ниже показан алгоритм GOSS.
Все обучающие экземпляры отсортированы по градиентам, a представляет процент выборки для больших экземпляров градиента, b представляет процент выборки для небольшие экземпляры градиента.
Используя GOSS, мы фактически уменьшаем размер обучающей выборки для обучения следующего дерева ансамбля, и это ускоряет обучение нового дерева.
2. Разделение узлов дерева на основе гистограммы
При поиске наилучшего значения функции для разделения узла дерева LightGBM использует гистограмму значений функций и пробует все значения бункеров гистограммы вместо того, чтобы пробовать все возможные значения функций, так что это может сократить время и вычисления, чтобы найти лучшее значение разделения функций. Между прочим, критерии разделения LightGBM должны уменьшить отклонение градиента от родительского к дочернему.
Например, учитывая возрастную характеристику, указанную ниже, значения дискретных функций гистограммы разбиваются на разные интервалы, поэтому мы можем использовать такие критерии плевания, как Age≤30, Age≤40``, Age≤100 вместо того, чтобы пробовать все возможные значения возраста, такие как Age ⩽31, возраст ⩽32 и т. Д.
Использование бункера для замены исходных данных эквивалентно увеличению регуляризации, количество бункеров определяет степень регуляризации. Чем меньше размер бункера, тем серьезнее штраф и выше риск недостаточного оснащения.
Также в сценарии разделения дерева для данной функции гистограмма является аддитивной.
Гистограмма родительского узла = Левая дочерняя гистограмма + Правая дочерняя гистограмма
Поэтому при вычислении дочерних гистограмм нам просто нужно вычислить одну дочернюю гистограмму (выбрать дочернюю гистограмму меньшего размера), а другая дочерняя гистограмма - это родительская гистограмма за вычетом рассчитанной.
3. Оптимальное разделение по категориальным признакам
Обычно, имея дело с категориальными функциями при разделении узлов дерева, мы всегда используем Один против остальных в качестве правила разделения узлов, например, условием разделения является «Погода = Солнечно» по сравнению с «Все остальные погодные условия (Дождь, Облачно, Снежно). так далее)". Как правило, проблема стратегии One Vs Rest заключается в следующем:
- Он имеет тенденцию генерировать несбалансированное распределение точек данных в дочерних узлах (например, левому дочернему элементу назначено гораздо больше точек данных, чем правому дочернему элементу), и он должен расти очень глубоко, чтобы достичь хорошей точности
- Поскольку необходимо вырастить очень глубокое дерево, нам нужно много разбиений узлов, поэтому эффективность построения дерева очень низкая.
Из-за этих проблем LightGBM использует следующую стратегию Многие ко многим.
По заданному категориальному признаку
- Для каждой категории функции рассчитайте среднее значение Sum (y) / Count (y)
- Отсортируйте все категории по их среднему значению (показано на рисунке ниже).
- Перечислите значение разделения от наименьшего среднего значения до наибольшего среднего значения, чтобы найти наилучшее значение разделения. Значение разделения группирует все категории на две части (среднее значение категории меньше или больше значения разделения), и это является условием разделения узла.
4. Набор эксклюзивных функций
EFB стремится сократить количество функций за счет объединения функций, в частности, объединения взаимоисключающих функций, которые редко принимают одновременно ненулевые значения.
LightGBM предоставляет следующие два алгоритма для реализации
- Выявление взаимоисключающих наборов функций из обучающего набора
- Объединить набор функций и присвоить ему значение
Ниже приведен пример EFB, показывающий результаты слияния функций.
В этом примере максимальное количество конфликтов K = 2, и он показывает, что исходные 5 функций могут быть сокращены до 3 функций в соответствии с алгоритмами EFB.
5. Стратегия роста деревьев по листвам.
LightGBM отказался от стратегии роста дерева решений по уровням, используемой большинством инструментов GBDT, и использовал поэтапный алгоритм с ограничениями по глубине.
В стратегии «по листу» каждый раз из всех листьев найдите лист с наибольшим усилением разделения, затем разделите и выполните цикл.
В приведенном выше процессе роста дерева узел с зеленым листом - это узел, который имеет наибольшее усиление разделения, поэтому сделайте разделение на нем, а затем переоцените, чтобы найти следующий узел с зеленым листом.
Преимущество листового разделения состоит в том, что для каждого разделения узла мы всегда можем принести максимальную выгоду дереву, поэтому дерево роста более эффективно, чем по уровням. Но нам нужно добавить глубину дерева и некоторые другие ограничения, чтобы избежать переобучения.
6. Параллельная оптимизация
Для работы с сверхбольшими наборами данных LightGBM вводит распределенные процессы для параллельного вычисления гистограммы признаков и лучшего разделения значений признаков.
LightGBM поддерживает две параллельные стратегии - параллелизм функций и параллелизм данных.
Параллельный алгоритм функций
Обучающие данные разделяются по вертикали (столбец или элемент) и распределяются между разными рабочими компьютерами для расчета локальной гистограммы и локального наилучшего разделения для выделенных функций, а затем глобального выбора наилучшего разделения из всех выходных данных рабочих.
Алгоритм параллельных данных
Обучающие данные разделяются по горизонтали (строкам) и распределяются по разным рабочим компьютерам для расчета локальных гистограмм для всех функций на основе выделенного обучающего подмножества, а затем слияния гистограмм всех функций из локальных гистограмм всех рабочих.
LightGBM также имеет дополнительную оптимизацию для алгоритма параллельных данных, идея состоит в том, что каждый рабочий выбирает K лучших функций разделения локально, а затем голосует за лучшие функции в глобальном масштабе.
После получения основных функций нам понадобится только объединить гистограмму основных функций из локальной гистограммы всех рабочих процессов.
Резюме
Все вышеперечисленные инновационные методы LightGBM нацелены на то, чтобы ускорить обучение, и они делают LightGBM отличным средством:
- Эффективность быстрого обучения
- Низкое использование памяти
- Отличная точность
- Параллельное обучение
- Возможность обрабатывать большие данные
