Улучшения градиентного бустинга

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

Сжатие

В традиционном градиентном бустинге обновление ансамбля происходит добавлением новой базовой модели с коэффициентом (если модель - решающее дерево, то без коэффициента):

$$G_{m}(\mathbf{x}):=G_{m-1}(\mathbf{x})+\varepsilon_m f_m(\mathbf{x})$$

Идея сжатия (shrinkage) основана на том, чтобы добавлять $\varepsilon_m f_m(\mathbf{x})$ не полностью, а с некоторым малым коэффициентом $\alpha\in (0,1]$:

$$G_{m}(\mathbf{x}):=G_{m-1}(\mathbf{x})+{\color{red}\alpha} \varepsilon_m f_m(\mathbf{x})$$

Константный шаг

В случае обновления ансамбля с фиксированным шагом

$$G_{m}(\mathbf{x}):=G_{m-1}(\mathbf{x})+\varepsilon f_m(\mathbf{x})$$

отдельно на $\alpha$ не домножают, а просто берут фиксированный множитель $\varepsilon\in(0,1]$.

Чем базовых моделей в ансамбле больше, тем весь ансамбль в среднем получается точнее, поскольку модели отчасти компенсируют ошибки друг друга. Сжатие позволяет искусственно увеличить число базовых моделей в ансамбле, снижая вклад каждой базовой модели в отдельности. Чем гиперпараметр $\alpha$ меньше, тем больше шагов $\hat{M}$ потребуется произвести, чтобы дойти до оптимального решения, поскольку двигаться мы будем более малыми шагами. Вместе они связаны следующим соотношением:

$$\alpha \hat{M} \approx const$$

Например, если двигаться с уменьшенным шагом в десять раз, то потребуется в 10 раз больше итераций. Такая модификация позволяет искусственно завысить число шагов (и базовых моделей ансамбля), увеличивая его качество за счёт того, что мы точнее сойдёмся к оптимуму. Обычно выбирают $\alpha \sim 0.01-0.1$. В результате, приближаясь к оптимальному решению более малыми шагами, мы сможем сойтись к нему более точно.

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

Рассмотрим задачу классификации. Пример зависимости точности градиентного бустинга от числа базовых моделей для различных значений $\alpha$ приведён ниже:

Как видим, уменьшение $\alpha$ приводит к более высокому числу базовых моделей в оптимальной конфигурации. Зато точность ансамбля повышается.

Ускоренный поиск лучшей конфигурации

Чтобы найти наилучшую конфигурацию бустинга быстрее, поступают следующим образом:

1. С большим $\alpha$ по сетке значений настраивают параметры градиентного бустинга. Это включает оптимальное число базовых моделей $\hat{M}$, глубину решающих деревьев, критерий неопределённости при их настройке и прочие гиперпараметры.

2. Уменьшают $\alpha$ в $K$ раз:

   $$\alpha:=\alpha/K$$

3. Увеличивают оптимальное число базовых моделей в $K$ раз:

   $$\hat{M}:=\hat{M}*K$$

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

Сэмплирование

В обычной реализации бустинга каждая базовая модель $f_m(\mathbf{x})$ настраивается, используя все объекты и признаки обучающей выборки.

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

• настройка бустинга производится быстрее;

• базовые модели становятся более разнообразными, что повышает итоговую точность ансамбля (см. разложение неоднозначности).

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

Настройка базовых моделей бустинга по подмножеству объектов также позволяет использовать out-of-bag оценку для оценки качества ансамбля, не прибегая к дополнительной валидационной выборке.

Гиперпараметры сэмплирования

При использовании сэмплирования возникают гиперпараметры:

• доля сэмплируемых объектов,

• доля сэмплируемых признаков.

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

Рассмотрим задачу регрессии. Пример зависимости средней ошибки MAE на тестовой выборке от доли использованных объектов приведён ниже:

Далее приведён пример зависимости от числа сэмплируемых признаков:

В приведённых примерах настройка базовых моделей не на всех, а на случайной части объектов и признаков привела к улучшению точности ансамбля.

Выбор гиперпараметров

В отличие от $\alpha$, которое чем меньше, тем лучше при достаточном числе базовых моделей, зависимость от доли используемых объектов и признаков сложна и неоднозначна и требует тщательного подбора по кросс-валидации.

Поиск разбиений по сетке

При использовании решающих деревьев в качестве базовых моделей бустинга, вместо того, чтобы перебирать все допустимые пороги, можно перебирать пороги только по грубой сетке значений. Для этого рекомендуется использовать 10,20,30, ... 90% квантильные значения признака для объектов, попадающих в соответствующий узел дерева. Можно использовать и другую сетку квантизации. Это ускоряет выбор правил при настройке решающих деревьев, снижая точность подгонки под данные. Но высокая точность в бустинге нам и не нужна, поскольку неточности в настройке текущей базовой модели исправят последующие модели ансамбля.