[머신러닝] XGBoost

XGBoost란?

앞서 Gradient Boosting에 대해서 설명했다.

Gradient Boosting이란, 이전 모델에서 나온 결과값의 Gradient 값(psuedo residual)을 이용해서 다음 모델에 학습을 시키고, 이를 모두 선형 결합한 결과물이 나오는 알고리즘을 의미했다.

 

이렇듯 기본적으로 사용되고 있는 Gradient Tree Boosting 기법에서 '과적합 방지'와 '병렬 학습'이 가능하도록 만든 boosting 알고리즘이 바로 XGBoost이다.

 

XGBoost의 대표적인 장점을 나열해 보자면 다음과 같다.

 

1. 정규화, 근사치를 이용한 학습 개선 :
   • 정규화를 이용한 과적합 개선 : 학습을 위한 오차 항에서 L2(Ridge) Regularization 항을 추가해 모델(트리)의 복잡도를 제어하고, 이를 통해 과적합을 개선한다(뒤의 알고리즘 부분에서 설명)
   • 근사치를 이용한 오차 개선 : Taylor Expansion을 통한 근사치를 이용해서 오차를 보정하는 방법을 이용하고 있어서 더 효율적으로 트리를 학습시킬 수 있다(뒤의 알고리즘 부분에서 설명)
2. 병렬 처리를 통한 빠른 결과 도출 : XGBoost는 독립적으로 학습되는 다수의 결정 트리를 활용하고, 데이터를 병렬로 처리하기 위해 여러 부분으로 분할(Partitioning)하여 학습한다(뒤의 병렬 처리 부분에서 설명)

 

이렇듯 기본적인 GBM에 비해 다양한 장점을 가지고 있으며, 이를 XGBoost의 알고리즘과 결합하여 설명하고자 한다.

 

 

XGBoost 알고리즘

• 하단의 내용은 모두 XGBoost 관련 논문의 내용과 이를 정리한 블로그 글을 참조하여 적었습니다.
  • 논문 제목 : XGBoost: A Scalable Tree Boosting System
  • 논문 링크 : https://arxiv.org/pdf/1603.02754.pdf
  • 참조 블로그 : https://kicarussays.tistory.com/25

XGBoost는 기본적으로 CART(Classification And Regression Trees) 알고리즘을 따라간다고 한다.

 

기본 Tree Ensemble 모델에 대한 그림

간단하게 설명하자면 분류, 회귀 트리를 활용한 앙상블(Boosting) 모델이라고 설명할 수 있다.

CART 모델의 원리를 간단히 수식으로 정리해 보자면 다음과 같다.

이렇게 각각의 트리에 가중치를 곱해서 전부 더해, 하나의 예측 output을 내는 방식을 의미한다(이를 영어로 additive learning → '더해서, 배운다' 라고 한다)

 

XGBoost도 기본적으로 이러한 구조를 가지고 있다.

즉, 의사결정나무를 여러개 학습시켜 예측값을 반환한다는 뜻을 가지고 있으며, 이를 수식으로 표현해보면 다음과 같다.

Input으로 $n \times m$ (n개 samples, m개 features)가 주어지며 $|\mathcal{D}| = n, \mathbb{x}_i \in \mathbb{R}^m, y_i \in \mathbb{R}$ 데이터셋을 가지고 있다고 한다면, 

$$\hat{y}_i = \phi(\mathbb{x}_i) = \sum_{k=1}^{K} f_k(\mathbb{x}_i), f_k \in \mathcal{F}, \tag{1}$$

$$\text{where  } \mathcal{F} = \left\{ f(\mathbb{x}) = w_{q(\mathbb{x})} \right\}(q: \mathbb{R}^m \to T, w \in \mathbb{R}^{T}) \tag{a}$$

 

여기서 $\mathcal{F}$는 Regression Tree들을 나타내며, $f(x) = w_{q(x)}$는 input으로 들어간 $m$차원의 $x$라는 값이 해당 tree를 거쳐 $x$에 해당하는 Tree의 leaf에 위치하는 끝마디의 값(output, 출력값)인 $w_{q(x)}$를 도출해내기 때문에

 

$q: R^m \to T$ 즉, $q$는 $m$차원에서 트리의 $T$개의 끝마디 값 중 하나를 결과로 이끌어내게 된다.

($T$는 leaf node의 갯수이다.)

 

일반적인 Tree Boosting 모델이라면 손실 함수는 다음과 같을 것이다.

$$\mathcal{L}(\phi) = \sum_{i} l(\hat{y}_i, y_i)$$

이는 output $y_i$와 예측값 $\hat{y_i}$의 실제 차이를 나타내는 값이며, 이를 모두 합한 값이 손실 함수로 정의되었다.

 

그러나 XGBoost의 경우 여기에 정규화(Regularizaiton) 항을 하나 추가하여 손실 함수를 정의했다.

$$\mathcal{L}(\phi) = \sum_{i} l(\hat{y_i}, y_i) + \sum_{k} \Omega(f_k), \tag{2}$$

 

정규화 항은 $\Omega$이며, 이를 수식적으로 풀어보면 다음과 같다.

$$\Omega(f) = \gamma T + \frac{1}{2} \lambda ||w||^2$$

 

각각 항의 의미를 살펴보면

• $\gamma T$ : Regularization Parameter $\gamma$와 leaf node의 수 $T$의 곱으로, 직관적으로 생각해보자면 leaf node의 수가 적어질수록 손실 함수는 최소화된다.
• $\lambda ||w||^2$ : Regularization Parameter $\lambda$와 L2 norm $||w||^2$의 곱으로, $||w||^2 = \sum_{j=1}^{T} w_{j}^{2}$로 $w_{j}$는 j번째 트리의 끝마디에서의 출력값이다. 각 leaf의 L2 norm이 작으면(오버피팅을 방지) 손실 함수가 최소화될 것이다.

 

이처럼 Regularizaiton Term을 추가함을 통해 보다 간단하고, 오버피팅을 방지할 수 있는 모델을 이용해 트리를 학습시킨다.

 

이제 좀 더 자세히 학습 과정을 살펴보자.

XGBoost에서는 트리의 가지를 하나씩 늘려가는 형식으로 학습이 진행된다.

$$ \mathcal{L}^{(t)}=\sum_{i=1}^{n} l(y_i, \hat{y_i}^{(t-1)} + f_t(\mathbb{x}_i)) + \Omega(f_t) + \text{Constant}, \tag{3} $$

 

다음과 같이 t번째 iteration의 경우 loss function이 정의된다.

t번째 iteration의 loss 값은

 

1. 바로 이전 예측값 $\hat{y_i}^{(t-1)}$와 t번째 iteration에서의 예측값 $f_t(\mathbb{x}_i))$을 더한 결과와,
2. real output $y_i$ 사이의 loss function의 총합 및 regulation term $\Omega(f_t)$,
3. 그리고 이전까지의 regulation term을 모두 더한 값 $\text{Constant}$(이는 현재 iteration에서는 변하지 않는 값이기 때문에 constant로 나타낼 수 있다)

를 모두 더한 값이라고 할 수 있다.

 

이어서 해당 식을 taylor expansion을 통해 2차 근사치를 도출해보자.

• Taylor Expansion : 하나의 함수를 한 지점에서 계산한 도함수의 무한집합의 총합으로 나타내는 표현식$$y(x)=y(a+u)=y(a)+u\frac{\mathrm{d} y}{\mathrm{d} x}+\frac{1}{2!}u^{2}\frac{\mathrm{d}^2 y}{\mathrm{d} x^{2}}+\frac{1}{3!}u^{3}\frac{\mathrm{d}^3 y}{\mathrm{d} x^{3}}+...+\frac{1}{n!}u^{n}\frac{\mathrm{d}^n y}{\mathrm{d} x^{n}} + ...$$

 

$f(y) = l(y_i, y + f_t(\mathbb{x}_i))$, $y = \hat{y}_i^{t-1} -f_t(\mathbb{x}_i)$를 이용하여 Taylor Expansion의 2차 근사치를 도출한 결과는 다음과 같다.

$$\mathcal{L}^{(t)} \simeq \sum_{i=1}^{n}[ l(y_i, \hat{y}^{(t-1)}) + \frac{\partial}{\partial \hat{y_i}^{(t-1)}} l(y_i, \hat{y}^{(t-1)}) \cdot f_t(\mathbb{x}_i) + \frac{1}{2} \cdot \frac{\partial^2}{\partial^2 \hat{y_i}^{(t-1)}} l(y_i, \hat{y}^{(t-1)}) \cdot f_t^2 (\mathbb{x}_i) ] + \Omega(f_t), \tag{4} $$

 

계산의 편의성을 위해 loss function의 1차 미분식을 $g_i = \frac{\partial}{\partial \hat{y}_i^{t-1}} l(y_i, \hat{y}_i^{t-1})$로, 2차 미분식을 $h_i = \frac{\partial^2}{\partial^2 \hat{y}_i^{t-1}} l(y_i, \hat{y}_i^{t-1})$이라 치환한다면

$$\mathcal{L}^{(t)} \simeq \sum_{i=1}^{n}[ l(y_i, \hat{y}^{(t-1)}) + g_i  f_t(\mathbb{x}_i) + \frac{1}{2}  h_i  f_t^2 (\mathbb{x}_i) ] + \Omega(f_t), \tag{5}$$

 

이라는 식을 도출할 수 있다.

여기서 바로 이전 iteration에서 계산된 값인 $l(y_i, \hat{y}^{(t-1)})$은 상수 취급되어 사라지게 되면, 최종 식은 다음과 같이 도출된다.

$$\tilde{\mathcal{L}}^{(t)} = \sum_{i=1}^{n}[g_i  f_t(\mathbb{x}_i) + \frac{1}{2}  h_i  f_t^2 (\mathbb{x}_i) ] + \Omega(f_t), \tag{6}$$

 

트리의 학습은 해당 손실 함수를 최소화하는 방향으로 진행되게 되며, 최종 손실 함수가 오직 $g_i$와 $h_i$에 의존하여 나오게 되므로 손실 함수의 종류와 상관 없게 계산이 되게 되어 2차 근사식이 좋은 이유도 여기에서 알 수 있다.

 

모든 leaf node에 대해서 $I_j = \left\{ i | q(\mathbb{x}_i) = j\right\} $($q$는 $x_i$에 대해서 어떤 leaf node가 해당되는지 반환해주는 함수)식을 정의하면, 다음과 같은 식으로 (6)번 식을 풀어 쓸 수 있다.

$$\begin{align*} \tilde{\mathcal{L}}^{(t)} &= \sum_{i=1}^{n}[g_i  f_t(\mathbb{x}_i) + \frac{1}{2}  h_i  f_t^2 (\mathbb{x}_i) ] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T} w_{j}^{2} = \sum_{j=1}^{T} [ (\sum_{i \in I_j} g_i)w_j + \frac{1}{2} (\sum_{i \in I_j} h_i + \lambda) w_{j}^2 ] + \gamma T \end{align*} \tag{7}$$

 

글 상단의 (a)번 식에서 $\left\{f(\mathbb{x}) = w_{q(\mathbb{x})} \right\} $로 정의했기 때문에 $w_j$라는 것은 입력 변수 $x_i$가 위에서 정의한 $I_j$에 포함되었을 때 leaf node 끝마디의 값(output, 출력값)이라고 볼 수 있다.

 

위 식을 $w_j$에 대해서 미분 후 손실함수 값을 최소화할 수 있는 $w_j^{*}$ 값을 구하면 다음과 같다.

$$ w_j^* = -\frac{\sum_{i \in l_j} g_i}{\sum_{i \in l_j} h_i + \lambda}, \tag{8} $$

 

그리고 이를 (7) 식에 대입하여 풀면,

$$\tilde{\mathcal{L}}^{(t)} (q) = -\frac{1}{2} \sum_{j=1}^{T} \frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda} + \gamma T, \tag{9}$$

 

라는 손실함수 값을 구할 수 있다.

각 leaf의 $I_j, g_j, h_j$ 값들과 이를 통한 quality score을 도출하는 과정

이와 같이 2차 근사식을 바탕으로 가지를 하나씩 늘려 나가는 방식을 채택하고 있으며

(9)번 식에서 나타나는 손실 함수값이 최소화가 되는 split point를 찾아내는 것이 XGBoost의 목적이다.

 

왼쪽과 오른쪽의 splited sample들을 $I_L, I_R$이라 하면, split된 후 총 손실 함수값의 감소량 $\mathcal{L}_{split}$은 다음과 같다.

$$\mathcal{L}_{split} = \frac{1}{2} \left[ \frac{(\sum_{i \in I_L} g_i)^2}{\sum_{i \in I_L} h_i + \lambda } +  \frac{(\sum_{i \in I_R} g_i)^2}{\sum_{i \in I_R} h_i + \lambda } - \frac{(\sum_{i \in I} g_i)^2}{\sum_{i \in I} h_i + \lambda } \right] - \gamma \tag{10}$$

 

 

XGBoost의 Split 알고리즘

1. Basic Exact Greedy Algorithm

Basic Exact Greedy Algorithm이란 가능한 모든 경우를 나열해서 split point를 찾는 경우를 말한다.

Exact Greedy Algorithm 모식도

 

여기서 각 기호를 설명하자면

 

• $I$ : Split 하기 전의 대상이 되는 모든 sample의 집합
• $d$ : feature의 갯수(위 식에서 $m$이라 나타냄)
• $gain$ : split하는 후보들을 평가하고 선택할 때 사용되는 지표로, 분할 시행 시 예측 오차가 얼마나 줄어들었는지 나타냄(위 식에서 score로 나타냄)

 

각 과정을 설명하자면

 

1. gain(score)에 0을 입력한다.
2. split 이전의 gradient 값을 $G$, $H$에 입력
3. $m$개의 feature에 대해서 가능한 모든 split point로 $G_L$, $H_L$, $G_R$, $H_R$을 계산
4. (10)번 식에 의해 score에 손실함수 값의 감소량을 입력
5. score가 가장 높았던 split point를 선택

 

하지만 이러한 Greedy Algorithm에는 문제점이 여럿 발생한다.

 

모든 데이터를 통해 모든 경우의 수를 탐색해야 하기 때문에 데이터 전체가 메모리에 올라가지 않으면 수행이 불가능하고, 분산 환경에서 수행할 수 없다.

그렇기에 해당 문제점을 보완하는 여러 방법들을 언급해보고자 한다.

 

2. Approximate Algorithm

위의 Greedy 알고리즘처럼 가능한 모든 split point를 찾는 것이 아니라, split 후보군을 선정하고 그 후보군 내에서 가장 좋은 split point를 찾는 알고리즘이다.

Approximate Algorithm 모식도

 

1. Global Variant : 한 번에 모든 split point 후보군을 제시
2. Local Variant : 매 iteration마다 split point 후보군을 제시

 

당연히 Local Variant가 더 많은 계산량을 요구하게 된다.

아래는 이러한 방식의 차이에 대한 성능 비교 그래프이다.

split 알고리즘에 대한 성능 비교 그래프

eps는 Approximative Algorithm의 파라미터 값이고, eps가 작을수록 더 많은 후보군을 제시한다고 생각하면 된다.

 

물론 exact greedy algorithm이 가장 우수하지만, 낮은 eps의 global variant 방식과 0.3 eps를 가진 local variant 방식이 유사한 성능을 지님을 알 수 있다.

이렇듯 split 알고리즘의 선택이 잘 이루어진다면 높은 성능을 낼 수 있으며 XGBoost 오픈 소스 패키지에서는 이를 사용자가 자유롭게 선택이 가능하다.

 

3. Weighted Quantile Sketch(Histogram Based Algorithm)

이는 데이터를 정렬하지 않고도 히스토그램을 생성하는 방식으로, 데이터를 일정 갯수의 버킷(bucket)으로 나누고 각 버킷에 데이터 포인트의 가중치를 누적하여 저장한다.

 

간단하게 과정을 살펴보자면

 

1. 데이터 구성 : train data의 feature을 히스토그램 형식으로 구성한다. 이는 데이터의 분포를 근사적으로 표현한다.
2. 분할 후보 생성 : 분할 후보들을 생성하기 위해 데이터 히스토그램을 사용하며, 각 데이터 포인트의 가중치를 고려하여 구성되어 있다.
3. Quantile 추정 : 데이터의 분위수(quantile)를 추정하는데 사용되며 효율적으로 데이터의 분포를 파악하고 분할을 수행할 때 활용된다.

 

이는 데이터의 크기와 상관 없이 히스토그램을 생성시켜주는데, 이는 XGBoost의 분할 후보 생성 및 트리 구축 속도를 높이는 데 기여한다.

 

4. Sparsity-aware Split Finding

이는 결측치가 있는 데이터에 한해서도 학습이 가능하게 만드는 알고리즘이다.

Sparsity aware split finding의 모식도

 

알고리즘을 살펴보자면 한 번은 모두 오른쪽에, 다른 한번은 모두 왼쪽에 배치하고 split point를 찾는 것이다.

이는 분류할 Defalut 방향을 결정하기 위해서이다.

 

아래 그림을 살펴보면, 모든 결측치를 왼쪽에 배치했을 때 더 좋은 split point를 찾을 수 있으므로 해당 branch에서 결측치 데이터를 분류할 방향을 왼쪽 leaf로 설정하게 된다.

Sparsity aware Split Finding 예

 

 

System Design(분산 처리 환경)

XGBoost는 분산 처리 환경에서 학습이 가능하고,

CPU 캐시를 고려한 알고리즘으로 데이터의 크기가 커져도 빠른 학습 속도를 자랑한다.

 

<추후 정리 예정>

 

 

References

https://kicarussays.tistory.com/25

[논문리뷰/설명] XGBoost: A Scalable Tree Boosting System (1)

https://wooono.tistory.com/97

[ML] XGBoost 개념 이해

https://dining-developer.tistory.com/3

XGBoost (1) - 입문용 예제로 개념 쉽게 이해하기

https://zephyrus1111.tistory.com/232

21. XGBoost에 대해서 알아보자