입문

이번에는 XGBoost 등 머신러닝에서 기반을 이루는 이론인 Gradient Tree Boosting에 대해 알아봤다.
XGBoost는 Kaggle 등 경기에서 인기 있는 기법이지만 그 이론을 모르고 의존하면 징그럽다. 과학이 아니다.그리고 이론을 알아야 활용할 수 있다고 믿어서 여기서 정리하고 싶어요.빨리 하려고 하면 이루지 못한다.
하지만 이것은 도대체 내가 이해하는 범위를 기술한 필기라는 것을 주의하세요.
또한 다음 내용은 XGBoost의 논문 Section2를 참조하십시오.

Gradient Tree Boosting

Gradient Tree Boosting은 협동 학습 중의 하나입니다.
원래 기계 학습의 목표는 데이터에서 범용 능력이 높은 학습기를 구축하는 것이다. 그 범용 능력을 향상시키기 위해 다음과 같은 두 가지 방침을 고려할 수 있다.

단일 학습기의 정밀도를 높이고 강한 학습기 구축

여러 개의 약한 학습기를 준비하고 이러한 예측 결과를 종합하여 강한 학습기를 구축한다

협동 학습은 바로 후자의 방침을 채택한 기계 학습이다.
또한 공모학습에는 다음과 같은 두 가지 방법이 있습니다.

Bagging: 다양한 약한 학습기를 독립적(parallel)으로 제작하고 이러한 예측 결과를 종합하는 방법

Boosting: 각종 약한 학습기를 차례(sequential) 제작하여 그들의 예측 결과를 종합하는 방법

전자는 Random Forest 등, 후자는 Ada Boost와Gradient Boosting 등입니다.
Bagging 및 Boosting 이미지는 다음 그림입니다.

(인용 소스): https://quantdare.com/what-is-the-difference-between-bagging-and-boosting/
이번에 고려하는 Gradient Tree Boosting은 상기 Random Forest와 Gradient Boosting의 조합이다.

Tree Ensemble Model

이제 트리 에너지 모델을 설명할 것입니다.
현재 $n$개의 견본, $m$개의 특징량(열 등)이 있는 데이터 집합
$
\mathcal{D} =\{(\boldsymbol{x}_i, y_i)\}\quad (|\mathcal{D}| = n,\boldsymbol{x}_i\in\mathbb{R}^m, y_i\in\mathbb{R})$
컴백을 진행하다.단, $\boldsymbol{x}_i$는 설명 변수입니다. $y_i$는 의도 변수를 나타냅니다.또 공식의 굵은 체는 벡터를 나타낸다.
현재 $K$개의 트리로 구성된 모델을 고려할 때 예측치는 $\hat{y}_i$예

\hat{y}_i = \phi(\boldsymbol{x}_i) = \sum_{k=1}^{K} f_k(\boldsymbol{x}_k)\quad  ( f_k\in\mathcal{F})\\
where　\mathcal{F} = \{f(\boldsymbol{x}) = w_{q(\boldsymbol{x})}\}\quad (q:\mathbb{R}^m\rightarrow T, w\in\mathbb{R}^T)

에 설명된 해당 매개변수의 값입니다.
여기서 $\mathcal {F}$는 회귀 트리 공간(CART)이라고 불리며, 잎의 무게 $w$와 잎의 수량 $T$를 정의합니다.단, 잎의 수량 $T$는 $K$개의 나무마다 규정된 값이 아니라 각각 공통된 값을 가지고 있으며, XGBoost에서 max_depth라는 매개 변수로 제시해야 합니다.
또한 $q (\boldsymbol {x}) $는 트리 구조를 나타내며, 대충 말하면 입력 값이 모델에 의해 어느 잎으로 나뉘었는지 색인으로 되돌려주는 함수로 해석할 수 있다.

즉, 위의 의미는 "$q$에 의해 결정되는 트리 구조에 따라 입력 값은 각 잎으로 나뉩니다. 그리고 $K$개의 트리로 이 잎의 권한을 더하여 이 값을 예측값으로 $\hat {y}_i$로 출력합니다."

Regularized Learning Objective

모델을 최적화할 때 모델 평가를 하는 함수가 필요하다.신경 네트워크에서 손실 함수는 가치가 있다.여기서 다음 표현식으로 표현된 함수를 최소화하여 모델을 최적화합니다.

L(\phi)=\sum_i l(\hat{y}_i, y_i)+\sum_k\Omega(f_k)\\
where　\Omega(f) = \gamma T + \frac{\lambda}{2}||w||^2

상단 오른쪽 첫 번째 항목의 $l(\hat{y}_i, y_i)$는 예측값입니다. $\hat{y}_i$및 정확한 값 $y_i$의 차분을 계산하는 볼록 손실 함수입니다.
상단 오른쪽 두 번째 항목의 $\Omega(f)$는 정규화 항목이고, $｜w｜$는 L2 범수이다.정규화 항목에 대한 공헌은 척추 회귀 보도를 참조하십시오.여기에 $\gamma T$를 추가하여 잎사귀 증가, 즉 복잡화 모델에 대해 처벌을 내렸습니다.
$\gamma,\lambda$는 하이퍼매개 변수입니다.

Gradient Tree Boosting

여기서부터 이 트리를 Boost해야 하지만, 이전 절의 식에서 함수 $f$를 매개 변수로 가장 최적화된 설명을 해야 합니다.그러나 이른바 유클리드 공간에서의 최적화(계단식 하강법 등)를 통해 최적화하는 것은 불가능하다.
따라서 모든iteration에 함수를 추가하는 형식으로 최적화됩니다.
이제 $\hat{y}_i$를 표시하면 $t$의iteration의 목표 함수 $L^ (t)}$

L^{(t)} = \sum_{i=1}^n l\left(y_i, \hat{y}_i^{(t-1)} + f_t(\boldsymbol{x}_i)\right) + \Omega(f_t)

기술할 수 있다.이 공식의 의미는 "$t-1$의 iteration에 있는 모델에 $f_t$를 추가해서 목표 함수를 줄이려는 시도"입니다.
여기서 오른쪽 첫 번째 항목을 두 번으로 확장하면

\begin{eqnarray}
L^{(t)} &\simeq& \sum_{i=1}^n\left[l\left(y_i, \hat{y}_i^{(t-1)}\right) + \frac{\partial l}{\partial\hat{y}_i^{(t-1)}}f_t(\boldsymbol{x}_i) + \frac{1}{2}\frac{\partial^2 l}{\partial{\hat{y}_i^{(t-1)}}^2}f_t^2(\boldsymbol{x}_i)\right] + \Omega(f_t) \\
&=& \sum_{i=1}^n\left[l\left(y_i, \hat{y}_i^{(t-1)}\right) + g_i f_t(\boldsymbol{x}_i) + \frac{1}{2}h_i f_t^2(\boldsymbol{x}_i)\right] + \Omega(f_t)
\end{eqnarray} 

되다하지만

\begin{eqnarray}
g_i &\equiv& \frac{\partial l}{\partial\hat{y}_i^{(t-1)}}\\
h_i &\equiv& \frac{\partial^2 l}{\partial{\hat{y}_i^{(t-1)}}^2}
\end{eqnarray}

에서 설명한 대로 해당 매개변수의 값을 수정합니다.상수항을 빼면

\tilde{L}^{(t)} = \sum_{n=1}^n\left[g_i f_t(\boldsymbol{x}_i) + \frac{1}{2}h_i f_t^2(\boldsymbol{x}_i)\right] + \Omega(f_t)

되다
여기, $I_j=\{i_q(\boldsymbol{x}_i)=j\}$.이것은 모델에서 $j$개의 잎으로 나누어진 $i$개의 데이터의 인덱스 집합을 나타낸다I_하면, 만약, 만약...

\begin{eqnarray}
\tilde{L}^{(t)} &=& \sum_{n=1}^n\left[g_i f_t(\boldsymbol{x}_i) + \frac{1}{2}h_i f_t^2(\boldsymbol{x}_i)\right] + \gamma T + \frac{\lambda}{2}\sum_{j=1}^Tw_j^2 \\
&=& \sum_{j=1}^T\left[\left(\sum_{i\in I_j}g_i\right)w_j + \frac{1}{2}\left(\sum_{i\in I_j}h_i + \lambda\right)w_j^2\right] + \gamma T
\end{eqnarray}

변형 가능.각 잎의 득점의 총체로 쓸 수 있다는 얘기다.
단, 위에서 $\mathcal {F}$의 정의를 사용했습니다.
그럼, $w_j$를 매개 변수로 하는 함수에 대해 최소값을 충족시킬 때의 조건은

\frac{\partial\tilde{L}^{(t)}}{\partial w_j} = 0

이때 $w_j$는 $w_와 같다하면, 만약, 만약...

\left(\sum_{i\in I_j}g_i + \frac{1}{2}\sum_{i \in I_j}(h_iw_j^* + \lambda)\right) + \frac{1}{2}\sum_{i \in I_j}(h_iw_j^* + \lambda) = 0 \\
\Leftrightarrow w_j^* = -\frac{\sum_{i\in I_j}g_i}{\sum_{i \in I_j}h_iw_j^* + \lambda}

및 $w_j$의 최적 값을 구할 수 있습니다.이 $w_목표 함수의 표현식에 j^*$를 대입하면 트리 구조 $q$의 가장 좋은 목표 함수 $\tilde {L}^(t)}(q)$

\tilde{L}^{(t)}(q) = -\frac{1}{2}\sum_{j=1}^T\frac{\left(\sum_{i\in I_j}g_i\right)^2}{\sum_{i \in I_j}h_iw_j^* + \lambda} + \gamma T

요구를 받다.
일반적으로 모델의 최적화에서 단일 트리leaf부터 모든 iteration은tree에 나뭇가지를 추가하는 방법을 취한다.
여기서 나뭇가지 뒤에 있는 instance sets를 각각 $I_로 설정합니다L, I_R$로 정의, 분할 전 instance sets$I$, $I=I_L\cup I_R$가 생성된다고 가정합니다.따라서 분기, 목적 함수의 감점 $L_{split}$

\begin{eqnarray}
L_{split} &=& L_{before} - L_{after} \\
&=& \left\{-\frac{1}{2}\frac{\left(\sum_{i\in I}g_i\right)^2}{\sum_{i \in I}h_iw_j^* + \lambda} + \gamma\right\} - \left\{\left(-\frac{1}{2}\frac{\left(\sum_{i\in I_L}g_i\right)^2}{\sum_{i \in I_L}h_iw_j^* + \lambda} + \gamma\right) + \left(-\frac{1}{2}\frac{\left(\sum_{i\in I_R}g_i\right)^2}{\sum_{i \in I_R}h_iw_j^* + \lambda} + \gamma\right)\right\} \\
&=& \frac{1}{2}\left[\frac{\left(\sum_{i\in I_L}g_i\right)^2}{\sum_{i \in I_L}h_iw_j^* + \lambda} + \frac{\left(\sum_{i\in I_R}g_i\right)^2}{\sum_{i \in I_R}h_iw_j^* + \lambda} - \frac{\left(\sum_{i\in I}g_i\right)^2}{\sum_{i \in I}h_iw_j^* + \lambda}\right] - \gamma
\end{eqnarray}

계산할 수 있다.즉, 이 함수를 계산함으로써 대상의 지점을 판단할 수 있다.
모든 iteration에 대한 이상의 과정을 통해 Boosting 기반 모델의 최적화를 진행할 수 있다.
실제로 모든 실례의 $g$와 $h$값을 유지하면 됩니다.

끝날 때

XGBoost의 이론인 Gradient Tree Boosting을 공식으로 해석해 보는 게 어때요?
여러분도 정밀도를 높이고 메스꺼워지기 전에 스타일대로 메스꺼워지세요()
만약 해석이 틀렸다면 반드시 지적해 주십시오.

참고 자료

XGBoost 원본 논문https://arxiv.org/abs/1603.02754

https://www.st-hakky-blog.com/entry/2017/07/28/214518

https://quantdare.com/what-is-the-difference-between-bagging-and-boosting/

참고하도록 허락해 주세요.감사합니다.