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

Мы вывели алгоритм градиентного бустинга из линейного приближения функции потерь. Но можно было бы применить ту же самую идею, используя более точное квадратичное приближение!

Рассмотрим для объекта $(\mathbf{x},y)$ функцию потерь $\mathcal{L}(\mathbf{x},y)$ и введём обозначения для её первой и второй производной по значению прогноза:

$$\begin{aligned} g(\mathbf{x}) &= \frac{\partial\mathcal{L}(G(\mathbf{x}),y)}{\partial G} \\ h(\mathbf{x}) &= \frac{\partial^{2}\mathcal{L}(G(\mathbf{x}),y)}{\partial G^{2}} \end{aligned}$$

Тогда из разложения Тейлора второго порядка [1] получим следующую квадратичную аппроксимацию для функции потерь:

$$\begin{gathered}\mathcal{L}(G(\mathbf{x})+f(\mathbf{x}),\,y)\approx\mathcal{L}(G(\mathbf{x}),y)+g(\mathbf{x})f(\mathbf{x})+\frac{1}{2}h(\mathbf{x})\left(f(\mathbf{x})\right)^{2}=\\ \frac{1}{2}h(\mathbf{x})\left(f(\mathbf{x})+\frac{g(\mathbf{x})}{h(\mathbf{x})}\right)^{2}+\text{const}(f(\mathbf{x})), \end{gathered}$$

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

Отсюда следует, что для минимизации функции потерь для объекта $\mathbf{x}$ базовая модель $f(\mathbf{x})$ должна приближать $-g(\mathbf{x})/h(\mathbf{x})$ с весом $h(\mathbf{x})$. То есть должна настраиваться на следующей обучающей выборке:

$$\{ \mathbf{x}_n, -g(\mathbf{x}_{n})/h(\mathbf{x}_{n}) \}_{n=1}^N$$

с соответствующими весами $\{h(\mathbf{x}_{n})\}_{n=1}^N$, которые будут неотрицательны в окрестности локального минимума.

На приближении второго порядка основан алгоритм LogitBoost, подробно описанный в [2], а также алгоритм xgBoost [3].

Литература

1. Викиконспекты ИТМО: формула Тейлора для произвольной функции.

2. Мерков А. Б. Распознавание образов: введение в методы статистического обучения. // Москва: Едиториал УРСС. – 2019.

3. Chen T., Guestrin C. Xgboost: A scalable tree boosting system //Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. – 2016. – С. 785-794.