XGBoost에 대해(원리와 공식)

 

 

저번 포스팅에 이어서 XGBoost의 원리와 왜 확장성이 높은 알고리즘인가에 대해서 포스팅 하려고 합니다!

공식의 유도와 원리에 대한 이야기이기 때문에 전 포스팅을 보고 와주세요.

XGBoost: A Scalable Tree Boosting System(Carlos & Tianqi. 2016) 리뷰

 

📌 XGBoost

---

 

우선 XGBoost란 부스팅의 한 종류로 gradient boosting의 upgrade 버전으로 보시면 되겠습니다. Gradient Boosting과 같이 잔차로부터 훈련하며 약한 learner를 강한 learner로 향상시킵니다.(앙상블 모형)

 

큰 특징이라면 빠른 속도와 성능이라고 합니다.

 

 

⚙️ 원리와 공식 유도

---

• n : data set내의 examples 수
• m : examples안의 요인 수
• D : n개의 example, 각 example은 m개의 특성을 지님 (n x m)

위와 같은 조건일 때 D는

$$
D = {(x_i, y_i)} (|D| = n, x_i ∈ \mathbb{R}^m, y_i ∈ \mathbb{R})
$$

이를 기반으로 설명해봅시다.

 

1️⃣ 앙상블 모델 기반

 

XGBoost는 앙상블 모델 기반으로, K개의 가법 함수를 이용하여 output을 예측합니다. 쉽게 설명하면 여러개의 트리를 합친 것을 이용하여 결과를 예측한다는 것입니다. 식으로 표시하면 결과 = 트리의 합들

 

$$
Eq(1) :
\hat{y}_i = \phi(x_i) = \sum^K_{k=1} f_k(x_i), f_k\in \mathcal{F}
$$

• K : 트리의 개수
• $f$ : tree($\mathcal{F}$에 속하는 함수)
• $\mathcal{F}$ : 함수공간으로 모든 가능한 트리의 집합

 

$$
\mathcal{F} = {f(x) = w_{q(x)}}(q : \mathbb{R}^m → T, w ∈ \mathbb{R}^T)
$$

• $w$ : 트리의 leaf에서의 점수 벡터
• $q$ : 데이터 포인트를 해당하는 리프에 할당하는 함수
• $T$ : leaf의 수

 

2️⃣ 최적화해야하는 정규화된 목적 함수

 

우선 목적함수를 봅시다. 목적함수는 아래와 같이 손실함수 + 정규화항으로 이루어져 있습니다.

$$
Eq(2). \ \mathcal{L}(\phi) = \sum_il(y_i,\hat{y}_i) + \sum_k\Omega(f_k)
\\ where \ \Omega(f) = \gamma T + \frac12 \lambda||w||^2
$$

 

정규화항인 $\Omega(f)$의 다양한 정의가 있지만 해당식이 가장 좋다고 하네요.

 

앞서 XGBoost는 Gradient boosting의 업그레이드 버전이라고 하였습니다. 목적함수에 Gradient Tree Boosting을 적용해봅시다.($\hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + f_t(x_i)$)

 

$t$번째 트리에서의 목적함수는 아래와 같습니다.

$$
\mathcal{L}^{(t)} = \sum^n_{i =1}l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) + \Omega(f_t) + \text{constant}
$$

 

여기서 우리에게 친숙한 평균제곱오차(MSE)를 손실함수로 사용한다면? 해당 목적함수는 아래와 같게 됩니다.

$$
\begin{split}\mathcal{L}^{(t)} & = \sum_{i=1}^n (y_i - (\hat{y}_i^{(t-1)} + f_t(x_i)))^2 + \sum_{i=1}^t\Omega(f_i) \\ & = \sum_{i=1}^n [2(\hat{y}_i^{(t-1)} - y_i)f_t(x_i) + f_t(x_i)^2] + \Omega(f_t) + \mathrm{constant}\end{split}
$$

위 식은 1차항과 2차항을 가지며 깔끔한 형식을 보입니다 문제는 다른 손실함수를 사용할 경우 이와같이 계산하기 좋은 형태를 가지기 어렵습니다.

그래서 우리는 태일러 전개의 2차수까지 취하여 기존 목적함수를 근사합니다.

 

3️⃣ 태일러 2차 근사 목적함수

 

태일러 전개의 2차수 까지 취하여 목적함수를 근사한 식은 아래와 같습니다.

 

$$
\mathcal{L}^{(t)} \cong \sum_{i=1}^n [l(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t) + \mathrm{constant}
$$

 

$$
\begin{split}g_i &= \partial_{\hat{y}_i^{(t-1)}} l(y_i, \hat{y}i^{(t-1)})
\\ h_i &= \partial_{\hat{y}_i^{(t-1)}}^2 l(y_i, \hat{y}_i^{(t-1)})\end{split}
$$

$g_i, h_i$를 보시면 아시겠지만, 이는 1차 그레디언트값, 2차 그레디언트값입니다!

 

여기서 근사에 필요없는 상수항을 제거한다면

$$
Eq.(3). \ \tilde{\mathcal{L}}^{(t)} = \sum^n_{i =1}[g_if_t(x_i) + \frac12h_if_t^2(x_i)] + \Omega(f_t)
$$

 

여기서 Eq(2)의 정규화항을 대입하고, $I = \{i|q(x_i) = j\}$(트리구조 q에서 리프 노드 j의 인스턴스 집합)로 정의하여 대입하면

 

$$
\begin{align}
Eq.(4). \ \tilde{\mathcal{L}}^{(t)} &= \sum^n_{i =1}[g_if_t(x_i) + \frac12h_if_t^2(x_i)] + \gamma T + \frac12 \lambda\sum_{j=1}^Tw_j^2
\\ &= \sum_{j=1}^T[(\sum_{i∈I_j}g_i)w_j + \frac12(\sum_{i∈I_j}h_i + \lambda)w_j^2] + \gamma T
\end{align}
$$

 

$G_j = \sum_{i \in I_j}g_i, H_j = \sum_{i \in I_j}h_i$라고 나타내고, 최적의 $w_j^*$를 $-\dfrac{G_j}{H_j + \lambda}$라고 정의 하여 대입하면 아래와 같은 최종식이 나옵니다.

 

$$
Eq. (6). \ \tilde{\mathcal{L}}^{(t)}(q) = -\frac12\sum_{j=1}^T\frac{G_j^2}{H_j + \lambda} + \gamma T
$$

 

score 함수

 

Eq(6)인 목적함수를 트리 구조 q의 quality를 측정하는 score함수로 이용합니다.

값이 작을수록 구조가 좋다는 의미입니다.

왜냐면 그레디언트 값인 $g_i$에 음의 값을 취한것은 잔차라고 graident boosting의 원리에서 알 수 있고, 이 잔차가 크다는 것은 그만큼 예측을 못했다는 것입니다.

그렇기 때문에 값이 작을수록 구조가 좋다고 결론을 낼 수 있다는 것입니다.

 

Greedy algorithm

 

그런데 문제가 있습니다. 해당 방법은 가능한 모든 트리 구조 q를 보아야합니다. 사실상 불가능한 일이죠. 그래서 단일 leaf에서 시작해서 반복적으로 가지를 추가하는 greedy algorithm을 사용합니다. 한가지에서 분할 후의 손실 감소값을 찾아 가지를 추가합니다.

 

식은 아래와 같습니다.

 

$$
L_{split} = \frac{1}{2} \left[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right] - \gamma
$$

 

위 식은 양의 값이네요. 이 값이 최대인 변수와 그에 대응하는 분리 기준을 바탕으로 가지를 추가합니다.

 

⚓ 마치며

---

이해하는 데 조금 걸렸는데, 여러가지 tutorial을 찾아보고 확실히 국내보다는 해외 연구가 많이 되어있다보니.. 해외 글들 찾아보면 금방 이해할 수 있더라구요. 이해하기 쉬우셨으면 좋겠습니다.

이상 XGBoost의 원리 였습니다! ☠️

참조

Introduction to Boosted Trees — xgboost 1.7.6 documentation