Что делает его быстрее и эффективнее
LightGBM, созданный исследователями из Microsoft, представляет собой реализацию деревьев решений с градиентным усилением (GBDT), который представляет собой метод ансамбля, который комбинирует деревья решений (как слабые обучающиеся) последовательным образом (повышение).
Деревья решений объединяются таким образом, чтобы каждый новый учащийся соответствовал остаткам из предыдущего дерева, чтобы модель улучшалась. Окончательная модель объединяет результаты каждого шага, и получается сильный ученик.
GBDT настолько точен, что его реализации доминируют на крупных соревнованиях по машинному обучению.
Мотивация LightGBM
Деревья решений строятся путем разделения наблюдений (т. Е. Экземпляров данных) на основе значений характеристик. Так «учится» дерево решений. Алгоритм ищет лучшее разбиение, которое дает наибольший выигрыш информации.
Прирост информации - это в основном разница между энтропией до и после разделения. Энтропия - это мера неопределенности или случайности. Чем больше случайности у переменной, тем выше энтропия. Таким образом, разбиение выполняется таким образом, чтобы уменьшить случайность.
Поиск наилучшего разделения оказывается самой трудоемкой частью процесса изучения деревьев решений. Двумя алгоритмами других реализаций GBDT для поиска наилучшего разделения являются:
- Предварительная сортировка: значения функций предварительно сортируются и оцениваются все возможные точки разделения.
- На основе гистограммы: непрерывные объекты разделены на дискретные ячейки, которые используются для создания гистограмм признаков.
«Sklearn GBDT» и «gbm in R» используют предварительно отсортированный алгоритм, тогда как «pGRT» использует алгоритм на основе гистограммы. «Xgboost» поддерживает оба.
Алгоритм на основе гистограммы более эффективен с точки зрения потребления памяти и скорости обучения. Однако как предварительно отсортированные, так и основанные на гистограммах работают медленнее по мере увеличения количества экземпляров или функций. LightGBM призван решить эту проблему эффективности, особенно с большими наборами данных.
Что делает LightGBM более эффективным
Отправной точкой для LightGBM был алгоритм на основе гистограммы, поскольку он работает лучше, чем предварительно отсортированный алгоритм.
Для каждой функции все экземпляры данных сканируются, чтобы найти наилучшее разделение с точки зрения получения информации. Таким образом, сложность алгоритма на основе гистограммы определяется количеством экземпляров данных и функций.
Чтобы решить эту проблему, LightGBM использует два метода:
- GOSS (градиентная односторонняя выборка)
- EFB (набор эксклюзивных функций)
Давайте подробно рассмотрим, что делают эти методы и как они делают LightGBM «легким».
GOSS (односторонняя выборка градиента)
Мы упоминали, что общие реализации GBDT сканируют все экземпляры данных, чтобы найти лучшее разделение. Это определенно не лучший способ.
Если нам удастся отобрать данные на основе получения информации, алгоритм будет более эффективным. Один из способов - это выборка данных на основе их веса. Однако его нельзя применить к GBDT, поскольку в GBDT нет веса выборки.
GOSS решает эту проблему, используя градиенты, которые дают нам ценную информацию о получении информации.
- Небольшой градиент: алгоритм был обучен на этом экземпляре, и связанная с ним ошибка мала.
- Большой градиент: ошибка, связанная с этим экземпляром, велика, поэтому он даст больше информации.
Мы можем исключить экземпляры с маленькими градиентами и сосредоточиться только на тех, которые имеют большие градиенты. Однако в этом случае распределение данных будет изменено. Мы не хотим этого, потому что это отрицательно повлияет на точность изученной модели.
GOSS предоставляет способ выборки данных на основе градиентов с учетом распределения данных.
Вот как это работает:
- Экземпляры данных сортируются по абсолютному значению их градиентов.
- Выбраны топовые экземпляры ax100%
- Из остальных экземпляров выбирается случайная выборка размером bx100%.
- Случайная выборка малых градиентов умножается на константу, равную (1-a) / b, когда вычисляется информационный выигрыш.
В конечном итоге GOSS добивается того, что акцент модели делается на экземплярах данных, которые вызывают больше потерь (т. Е. Недостаточно обучены), но не сильно влияют на распределение данных.
EFB (набор эксклюзивных функций)
Наборы данных с большим количеством функций, вероятно, будут иметь разреженные функции (т. Е. Множество нулевых значений). Эти редкие объекты обычно исключают друг друга, что означает, что они не имеют одновременно ненулевых значений. Рассмотрим случай текстовых данных с горячим кодированием. В конкретной строке только один столбец, указывающий на конкретное слово, не равен нулю, а все остальные строки равны нулю.
EFB - это метод, который использует жадный алгоритм для объединения (или объединения) этих взаимоисключающих функций в одну функцию (например, набор эксклюзивных функций) и, таким образом, уменьшения размерности. EFB сокращает время обучения GDBT без значительного влияния на точность, поскольку сложность создания гистограмм функций теперь пропорциональна количеству пакетов, а не количеству функций (#bundles намного меньше, чем #features).
Одна из задач EFB - найти оптимальные пакеты. Исследователи из Microsoft разработали алгоритм, который преобразует проблему связывания в проблему раскраски графа.
В задаче раскраски графа объекты берутся за вершины, а ребра добавляются между объектами, которые не исключают друг друга. Затем для создания пакетов используется жадный алгоритм.
Чтобы сделать еще один шаг вперед, алгоритм также позволяет объединять функции, которые редко имеют одновременно ненулевые значения (т. Е. Почти взаимоисключающие).
Еще одна проблема - объединить функции в пакете таким образом, чтобы можно было извлечь значения исходных функций. Рассмотрим набор из 3 функций. Нам нужно иметь возможность идентифицировать значения этих 3 функций, используя значение встроенной функции.
Напомним, что алгоритм на основе гистограммы создает дискретные ячейки для непрерывных значений. Чтобы преодолеть проблему слияния функций, исключительные значения функций в пакете помещаются в разные ячейки, что может быть достигнуто путем добавления смещений к исходным значениям функций.
Заключение
Мотивация за LightGBM заключается в решении проблем скорости обучения и потребления памяти, связанных с традиционными реализациями GBDT при работе с большими наборами данных.
Основная цель состоит в том, чтобы уменьшить размер (как с точки зрения экземпляров данных, так и функций), сохранив при этом информацию в максимально возможной степени. Для достижения этой цели применяются методы GOSS и EFB.
Согласно статье создателей LightGBM, LightGBM ускоряет процесс обучения обычного GBDT более чем в 20 раз при достижении почти такой же точности.
Спасибо за чтение. Пожалуйста, дайте мне знать, если у вас есть какие-либо отзывы.
