Введение
На
сегодняшний день существует множество инструментов для работы с временными
рядами. Дерево решений с градиентным усилением (GBDT) является популярным
алгоритмом машинного обучения и имеет довольно много эффективных реализаций,
таких как XGBoost и pGBRT.
Обзор решений
Хотя
в этих реализациях было принято много технических оптимизаций, эффективность и
масштабируемость по-прежнему неудовлетворительны, когда свойств объекта много,
а размер данных велик. Основная причина заключается в том, что для каждой функции необходимо сканировать все экземпляры данных, чтобы оценить прирост информации
по всем возможным точкам разделения, что занимает очень много времени. Чтобы
решить эту проблему, учёными из Пекинского университета было предложено два новых метода: односторонняя выборка на основе градиента (Gradient-based One-Side Sampling, GOSS) и
пакетирование эксклюзивных функций (Exclusive Feature Bundling, EFB). С помощью GOSS исключается значительная доля экземпляров
данных с небольшими градиентами и используется только остальные для оценки
прироста информации.
В ходе исследований по созданию нового алгоритма, китайскими учёными были получены доказательства того, что GOSS может получить довольно
точную оценку прироста информации с гораздо меньшим размером данных, поскольку
экземпляры данных с большими градиентами играют более важную роль в вычислении
прироста информации. С помощью EFB учёные объединили взаимоисключающие функции
(т. е. они редко принимают ненулевые значения одновременно), чтобы уменьшить
количество функций. Также было установлено, что найти оптимальное объединение исключительных функций NP-сложно, но жадный
алгоритм может достичь довольно хорошего коэффициента аппроксимации. Таким
образом, он может эффективно уменьшить количество
функций, не сильно снижая точность определения точки разделения. Новая
реализация получила имя GBDT с помощью GOSS и EFB LightGBM. Проведённые
эксперименты с несколькими общедоступными наборами данных показывают, что
LightGBM ускоряет процесс обучения обычного GBDT более чем в 20 раз, достигая почти
такой же точности.
Данные для оценки работы
Для оценки качества работы LightGBM необходимо сравнить его с другими алгоритмами. В качестве базиса рассматриваются XGBoost и LightGBM без GOSS и EFB (называемые
lgb_baselline). Для XGBoost были использованы две версии, xgb_exa (алгоритм предварительной сортировки) и xgb_his
(алгоритм на основе гистограммы). Для xgb_his, lgb_baseline и LightGBM была использована стратегия роста деревьев по
листьям. Для xgb_exa, поскольку он поддерживает только послойную стратегию
роста, были настроены параметры для xgb_exa, чтобы он мог выращивать такие же
деревья, как и другие.
Рис. 1. Наборы данных и их описание
В качестве тестовых данных в указанной статье были использованы 5 наборов данных, которые находятся в открытом доступе. Среди них набор данных Microsoft Learning to Rank (LETOR) содержит 30 тыс. поисковых запросов в Интернете. The Allstate Insurance Claim (данные страхового возмещения) и Flight Delay (задержки рейса) содержат множество функций однократного кодирования. И последние два набора данных относятся к KDD CUP 2010 2010 и KDD CUP 2012. Таблица с пояснением представлена на Рис. 1.
Результаты
На Рис. 2. представлена таблица с временем выполнения одной итерации каждым алгоритмом на выбранных наборах данных. Наглядно видно, что алгоритм LightGBM существенно быстрее других алгоритмов. Что касается точности предсказания, то и здесь LightGBM с GOSS и EFB дал более точную оценку. Данные представлены на Рис. 3.
Рис. 3. Точность предсказания алгоритмов
Вывод
Исследовав вышеописанные результаты, можно сделать вывод, что созданный китайскими учёными алгоритм является прорывным решением в машинном обучении. Удалось получить алгоритм, который не только быстрее и эффективнее по памяти своих предшественников, но и более точный в предсказании.