EMA-FS ускоряет обучение GBDT в 2,6 раза за счет отбора признаков по приросту
Градиентный бустинг (GBDT) в реализации LightGBM тратит 65–70% времени обучения на построение гистограмм по каждому признаку. Существующие методы случайного отбора признаков не учитывают их прогностическую ценность. Новая работа на arXiv предлагает алгоритм EMA-FS, который использует информацию о приросте (gain) для фильтрации признаков.
EMA-FS поддерживает экспоненциально взвешенное скользящее среднее приростов каждого признака на всех итерациях бустинга. После короткой фазы прогрева (warmup) алгоритм строит гистограммы только для top-K признаков с наибольшим историческим приростом. Операция выполняется на уровне каждого дерева и полностью совместима с трюком вычитания гистограмм LightGBM, не требуя изменений в ядре.
Метод протестирован на наборах данных для обнаружения финансового мошенничества, прогнозирования кликов в рекламе, контроля качества и синтетических бенчмарках с размерностью от 29 до 968 признаков. На плотных данных средней и высокой размерности достигнуто ускорение 2,61x на синтетическом наборе с 500 признаками и 1,45x на датасете IEEE-CIS Fraud (432 признака) при удержании 30% признаков. При удержании 70% признаков AUC улучшился на 0,11 пункта при ускорении 1,34x.
На экстремально разреженных данных (Bosch, более 90% пропусков) ускорения не наблюдалось, поскольку LightGBM уже оптимизирует разреженные бины и пропускает пустые значения. Для таких случаев предлагается стохастическая версия S-EMA-FS, заменяющая детерминированный отбор top-K на взвешенную случайную выборку с параметром концентрации beta. Эта версия объединяет детерминированный EMA-FS (beta ? ?) и случайную подвыборку (beta = 0) в едином фреймворке.
Оба алгоритма реализованы примерно в 120 строках C++ для всех шести древовидных learners LightGBM и полностью обратно совместимы. Исходный код и детали доступны в препринте на arXiv.
