[ML][Ensemble]XGBoost(Extreme Gradient Boost)

XGBoost(Extreme Gradient Boost)

XGBoost는 기존 GBM 알고리즘의 성능과 속도를 향상시킨 알고리즘이다

기존 GBM은 학습 데이터에 대한 Residual을 계속 줄이는 방향으로 학습하기 때문에 Overfitting이 되기 쉽다

따라서 정규화 항을 Loss Function에 추가함으로써 Overfitting을 방지한다

또한 Split Finding 알고리즘을 통해 연산의 효율성을 높혔다

• 정규화
  • $\Omega(f) = \gamma T + \frac{1}{2}\lambda ||c||^2$ (T : Terminal Node의 수, c : 각 노드의 가중치)
  • 여기서 $\gamma,\; \lambda$는 Hyper Parameter이다
• Split Finding
  • 기존에는 모든 Feature를 Split 기준으로 탐색
  • 이에 대한 근사 알고리즘을 제안하여 속도를 향상시킴

---

알고리즘

Step 1 : 초기 모형은 상수로 설정

$$F_0(x) = \underset{c}{\arg\min} \sum \limits_{i=1}^{n}L(y_1, c)$$

Step 2 : $m=1,\cdots ,M$에 대해 반복

$$
\begin{aligned}
for\;&m=1\;to\;M:\\
&(1) Gradient\;g_i와\;Hessian\;h_i를\;구한다\\
&\qquad g_i = \big[ \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}\big]_{F(x) = F_{m-1}(x)} \\
&\qquad h_i = \big[ \frac{\partial^2 L(y_i, F(x_i))}{\partial F(x_i)^2}\big]_{F(x) = F_{m-1}(x)}\\
&(2) Decision\;Tree\;\phi을\;아래와\;같이\;Fitting\\
&\qquad \phi_m = \underset{\phi}{\arg\min} \sum \limits_{i=1}^{n}\frac{1}{2} h_i [-\frac{g_i}{h_i} - \phi(x_i)]^2 + \gamma T + \frac{1}{2}\lambda ||\phi||^2\\
&\qquad T:\phi의\;Terminal\;node\;개수 \quad w_j:j번째\; Terminal\;Node \quad ||\phi||^2:\sum \limits_{j=1}^{T} w_j^2\\
&(3) Model;Update\\
&\qquad F_m(x) = F_{m-1} - l\cdot \phi_m(x)\\
\end{aligned}
$$  

---

알고리즘 풀이

1. Gradient와 Hessian

Loss Function을 2차 근사하기 위해 Hessian이 필요하다

$$l = \sum \limits_{i=1}^{n} L(y_i, F_{m-1}(x_i) + \phi(x_i)) + \gamma T + \frac{1}{2}\lambda ||\phi||^2 $$

여기서 $  L(y_i, F_{m-1}(x_i) + \phi(x_i)) $ 부분을 직접 최소화하는게 까다롭기 때문에 2차 근사를 수행한다

 

$$\tilde{l} = \sum \limits_{i=1}^{n} \big[ L(y_i, F_{m-1}(x_i)) + g_i \phi(x_i) + \frac{1}{2}h_i \phi(x_i)^2 \big] +  \gamma T + \frac{1}{2}\lambda ||\phi||^2 $$

 

이제 $\phi$와 관계없는 항을 제외하면 아래와 같다

$$
\tilde{l} = \sum \limits_{i=1}^{n} \big[g_i \phi(x_i) + \frac{1}{2}h_i \phi(x_i)^2 \big] +  \gamma T + \frac{1}{2}\lambda ||\phi||^2
$$

여기서 $\phi(x_i)$는 각 Terminal Node $R_j$에 속한 모든 $x_i$에 대해 같은 값 $w_j$를 가지기 때문에 따라서, 이를 아래의 식과 같이 바꿀 수 있다(  $x_i \in R_j$는 j번째 Terminal Node에 포함된 입력벡터를 의미하고, $w_j$는 입력벡터가 $R_j$에 포함될 경우 $\phi$의 출력값  )

$$
\begin{aligned}
\tilde{l} &= \sum \limits_{i=1}^{n} \big[g_i \phi(x_i) + \frac{1}{2}h_i \phi(x_i)^2 \big] +  \gamma T + \frac{1}{2}\lambda \sum \limits_{j=1}^{T} w_j^2\\
&= \sum \limits_{j=1}^{T} \big[ (\sum \limits_{x_i \in R_j} g_i) w_j + \frac{1}{2} (\sum \limits_{x_i \in R_j} h_i +\lambda)w_j^2 + \gamma \big] \\
\end{aligned} 
$$

위에서 정리된 수식 $\tilde{l}$을 최소화하면 원하는 $\phi_m$을 얻을 수 있습니다
$\tilde{l}$을 최소화하는 $\phi$, 즉, $\frac{\partial \tilde{l}}{\partial w_j}=0$을 만족하는 최적점을 찾아야한다

$$ 
\begin{aligned}
&\frac{\partial \tilde{l}}{\partial w_j}  = 0 = \sum \limits_{j=1}^{T} \big[ \sum \limits_{x_i \in R_j} g_i + (\sum \limits_{x_i \in R_j} h_i + \lambda) w_j \big]\\ 
&\therefore w_j^* = - \frac{\sum \limits_{x_i \in R_j} g_i}{\sum \limits_{x_i \in R_j} h_i + \lambda}
\end{aligned}
$$

 

$w_j^*$를 $\tilde{l}$에 대입하면 아래 식과 같습니다

 

$$
\begin{aligned}
\tilde{l}^* &= \sum \limits_{j=1}^{T} \big[ (\sum \limits_{x_i \in R_j} g_i) (-\frac{\sum \limits_{x_i \in R_j} g_i}{\sum \limits_{x_i \in R_j} h_i + \lambda}) + \frac{1}{2} (\sum \limits_{x_i \in R_j} h_i + \lambda) (- \frac{\sum \limits_{x_i \in R_j} g_i}{\sum \limits_{x_i \in R_j} h_i + \lambda})^2 \big] + \gamma T \\
&= \sum \limits_{j=1}^{T} \big[ -\frac{(\sum \limits_{x_i \in R_j} g_i)^2}{\sum \limits_{x_i \in R_j} h_i + \lambda} + \frac{1}{2}\frac{(\sum \limits_{x_i \in R_j} g_i)^2}{\sum \limits_{x_i \in R_j} h_i + \lambda} \big] + \gamma T\\
&=\sum \limits_{j=1}^{T} \big[- \frac{1}{2} \frac{(\sum \limits_{x_i \in R_j} g_i)^2}{\sum \limits_{x_i \in R_j} h_i + \lambda} + \gamma \big] \\
\end{aligned}
$$

 

따라서 최종적인 $\tilde{l}$는 아래와 같습니다

$$\tilde{l}^* = \sum \limits_{j=1}^{T} \big[- \frac{1}{2} \frac{(\sum \limits_{x_i \in R_j} g_i)^2}{\sum \limits_{x_i \in R_j} h_i + \lambda} \big] + \gamma T $$

---

하지만 최적의 분할 기준점을 찾기 위해 Loss의 감소량을 계산해야 합니다

최적의 분할점을 찾기 위해 여러 후보 분할점에서 손실 감소량(아래 식)을 계산하고, 이를 최대화 하는 분할점을 선택합니

$$
\frac{1}{2} \big[ \frac{(\sum \limits_{x_i \in R_{L}} g_i)^2}{\sum \limits_{x_i \in R_L} h_i + \lambda} +  \frac{(\sum \limits_{x_i \in R_R} g_i)^2}{\sum \limits_{x_i \in R_R} h_i + \lambda} -  -\frac{(\sum \limits_{x_i \in R_P} g_i)^2}{\sum \limits_{x_i \in R_P} h_i + \lambda}\big] - \gamma
$$