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

 

이번엔 XGBoost를 다루려고 합니다. 해당 논문을 읽고 정리한 내용이니 좀더 자세하고 이해하기 쉬운 설명은 다음 포스팅을 참고해주세요!

 

1️⃣ 서론

---

기계 학습과 데이터 기반 접근법이 많은 분야에서 중요해지고 있다.(스팸 분류, 적절한 광고 노출, 사기 감지 등등) 이러한 성공적인 응용 프로그램을 이끄는 두가지 요소는

 

1. 복잡한 데이터 종속성(상관)을 포착하는 효과적인 모델의 사용
2. 대규모 데이터셋으로부터 관심있는 모델을 학습하는 확장가능한 학습 시스템

 

2015년 Kaglle의 29개 과제중 17개의 우승 솔루션이 XGBoost일 정도로 ML 및 데이터 마이닝 경쟁에서 큰 영향력을 발휘. 무엇보다도 오픈소스!

XGBoost의 성공의 가장 중요한 요인은 모든 시나리오에서의 확장성(scalability)라고 하네요. 여기서 말하는 확장성이란 어떠한 손실 함수에 적용하여도 빠르게 계산가능하다.. 라는 정도로 알아 들었습니다.

 

논문의 주요 사항으로는

• 높은 확장성을 갖는 end to end tree boosting system 설계, 구축
• 효율적 계산을 위해 이론적으로 정립된 weighted quantile sketch 제안
• 병렬 트리 학습을 위한 현실적으로 유용한 novel sparsity-aware algorith 도입
• 메모리 외부 트리 학습 위한 효과적인 cache-aware block structure 제안

 

2️⃣ Tree Boosting in a Nutshell(트리 부스팅 요약)

---

XGboost는 gradient boosting이 기반이 되기 때문에 같이 설명해 주고 있습니다.

 

◾ Regularized Learning objective(정규화된 학습 목적 함수)

 

트리 앙상블 모형은 K개의 가법 함수(additive functions)를 사용하여 결과를 예측합니다.

 

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

 

여기서

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

 

$q$는 트리의 구조(input을 나무의 leaf에 매핑하는 함수), $T$는 트리의 leaf 수, $w$는 leaf의 가중치

회귀트리는 각 leaf에 연속적인 점수를 포함합니다.

 

주어진 데이터에 대해서, 우리는 트리의 결정 규칙 $q$를 사용해 해당하는 leaf로 분류하고, 해당 leaf에서의 점수를 합산하여 최종 예측을 계산합니다.

모델에서 사용되는 함수 집합을 학습하기 위해, 다음과 같은 정규화된 목적 함수를 최소화

 

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

$l$은 예측 $\hat{y}_i$와 실제값 $y_i$ 간의 차이를 측정하는 미분 가능한 볼록 손실 함수.

$\Omega$는 모델의 복잡성(즉, $f_k$인 회귀 트리 함수)에 대한 패널티 부여 > 과적합의 방지를 위해 모델의 복잡성을 제한.

 

 

◾ Gradient Tree Boosting

 

Eq(2)는 전통적인 최적화 방법을 사용하여 최적화할 수 없다. 대신 gradient 방법으로 이용.
t번째 반복에서 i번째 인스턴스의 예측을 $\hat{y}_i^{(t)}$이라고 할 때, 다음 목적 최소화 위해 $f_t$를 추가해야한다.

 

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

 

이는 Eq(2)에 따라 모델을 가장 향상시키는 $f_t$를 점진적으로 추가
어떠한 손실함수도 이와같이 적용가능하도록 해당 식을 태일러 급수 기반 2차 근사를 활용하여 최적화

 

$$
\mathcal{L}^{(t)} \cong \sum^n_{i =1}[l(y_i, \hat{y}_i^{(t-1)}) + g_if_t(x_i) + \frac12h_if_t^2(x_i)] + \Omega(f_t)
$$

 

$$
where. \ g_i = \partial_{\hat{y}^{(t-1)}}l(y_i,\hat{y}^{(t-1)})
\\
h_i = \partial_{\hat{y}^{(t-1)}}^2l(y_i,\hat{y}^{(t-1)})
$$

 

위 식에서 근사에 필요없는 상수항을 제거하면 단순화된 목적함수를 얻을 수 있음

 

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

 

트리 구조(q)에서 leaf node j의 인스턴스 집합을 $I_j$로 나타내면 $I_j = \{i|q(x_i)= j \}$, Eq(2)의 $\Omega$를 적용하면 다음과 같이 쓸 수 있다.

 

$$
\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}
$$

 

$q(x)$에 대해, leaf node j의 최적 가중치 $w_j^*$는 다음과 같이 계산.

$$
Eq. (5). \ w_j^* = -\frac{\sum_{i∈I_j}g_i}{\sum_{i∈I_j}h_i + \lambda}
$$

 

그리고 해당 최적값 계산 Eq.(5) -> Eq.(4)

$$
Eq. (6). \ \tilde{\mathcal{L}}^{(t)}(q) = -\frac12\sum_{j=1}^T\frac{(\sum_{i∈I_j}g_i)^2}{\sum_{i∈I_j}h_i + \lambda} + \gamma T
$$

 

Eq.(6)은 트리 구조 q의 quality를 측정하는 score 함수로 사용. 이 점수는 의사 결정 트리의 불순도 점수와 유사.

보다 다양한 목적 함수에 대해 유도됨

 

• 각 leaf node에서 1차 gradient와 2차 gradient 통계량을 합산한 다음. scoring 공식 적용하여 점수. 이 점수가 낮아야함.

 

보통 모든 가능한 트리 구조 q를 보는 것을 불가능하고, 대신 단일 leaf에서 시작하여 반복적으로 가지를 추가하는 greedy 알고리즘 사용

분할 후, 왼쪽 node와 오른쪽 node의 인스턴스 집합을 각각 $I_L, I_R$이라고 가정할 때, $I = I_L \cup I_R$로 두면, 분할 후의 loss reduction은 아래와 같다.

 

$$
Eq. (7). \ \mathcal{L}_{split} = \frac12[\frac{(\sum{i∈I_L}g_i)^2}{\sum_{i∈I_L}h_i + \lambda} + \frac{(\sum_{i∈I_R}g_i)^2}{\sum_{i∈I_R}h_i + \lambda} - \frac{(\sum_{i∈I}g_i)^2}{\sum_{i∈I}h_i + \lambda}] - \gamma
$$

이러한 공식으로 실제 split candidates 평가.

 

◾ Shrinkage and column Subsampling

 

Gradient boosting에 나오는 shrinkage. 학습률에 대한 설명을 해주고 있다. 학습률 설정으로 개별 트리의 영향력을 감소시키고 후에 향상된 모델을 위해 미래 트리에 여유 공간을 남김.

 

column subsampling은 열 부분 샘플링으로 각 트리를 구성할 때, 열에 해당하는 feature를 무작위로 선택. 또한 전체가 아닌 일부만을 선택하여 모델을 구축. 이로인해 모델 복잡성이 줄고 과적합이 저하된다.

 

3️⃣ Split Finding Algorithms

 

트리의 가지를 분할할 때 사용되는 알고리즘들에 대한 설명

◾ Basic Exact Greedy algorithm

앞서 설명한 Eq(7) 처럼 최상의 분할을 찾는 것. 모든 가능한 분할을 열거하여 찾는 방식. 해당 알고리즘은 논문을 참고해주세요! 간단한 알고리즘으로 따로 다루지는 않겠습니당

 

◾ Approximate Algorithm

위의 greedy algorithm은 모든 가능 분할 지점을 탐색하기에 용량에 따라 버거울수가 있다. 그래서 각 feature 분포의 백분위수에 따라 분할 후보 지점을 제안하고, 이러한 후보 지점으로 분할된 그룹으로 매핑.
쉽게 설명하면 데이터 하나하나 보는게 아닌 일정 범위로 묶어서 데이터를 사용한다고 보면 됩니다.

 

◾ Weighted Quantile Sketch

approximate algorithm이 좋긴 하나 결국 분할 지점을 선택하는 것은 연구자의 몫. 기존 방법은 휴리스틱(어림잡아)하는 방식이었다고 한다. 이를 해결하기 위해 가중치가 부여된 분위수를 사용하는 방법을 제시한다.

 

◾ Sparsity-aware Split Finding

변수의 결측치를 처리하는 방안. 쉽게 설명하면 기본 방향을 정해놓고 결측치 포함된 행을 모두 한 방향(left or right)으로 밀어넣은 다음에 손실 감소를 계산. 두 개의 값 중 최대로 하는 마디에 결측치를 모두 할당하는 방법이다.

 

외 내용들

---

이 다음에 System design 은 컴퓨터와 관련된 내용이라.. 다루기 어렵더라구요 ㅜ block에 관한 이야기도 나오는데 잘 모르겠네요.

후에는 이를 이용한 여러 연구에 관한 내용으로 XGboost가 좋다! 라는 것을 실험으로 보여줍니다.
내용이 좀 어렵습니다. 물론 이쪽 분야에서 공부를 하시는 분들은 좀 쉬우실 것 같아요. 그래서 좀 더 공부해서 간단한게 정리해보려고 합니다!

이상 XGboost : A Scalable Tree Boosting System 리뷰였습니다! ☠️

참조

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