XGBOOST는 "Extreme Gradient Boosting" 으로 기존 Gradient Boosting 알고리즘에 CART 모델을 사용하고 병렬 처리를 가능하게 함으로써 다양한 데이터 경진대회, kaggle 대회에서 거의 항상 사용되는 모델입니다. 저 또한 XGBOOST 를 많이 사용했지만 그 내부가 어떻게 돌아가는지 정확하가 파악하지는 못했었는데요., 이번 포스트에서는 XGBOOST 공식 홈페이지에 나와있는 알고리즘 소개를 간단히 살펴보려 합니다.
Decision tree ensembles
Ensemble 이란 여러 개의 약한 모델들을 결합하여 최종적인 좋은 모델을 만드는 머신러닝 모델 학습 알고리즘 중 하나입니다. 여러 개의 모델을 병렬적으로 결합한 bagging 방식과 순차적으로 이전 모델이 잘 예측하지 못했던 부분에 가중치를 두어 학습하는 boosting 방식이 있는데요, XGBOOST 는 대표적인 boosting 방식의 학습 모델입니다. XGBOOST는 의사결정나무 (decision tree)로 구성된 다른 tree-based ensemble 모델과 달리 CART (Classification and regression trees) 라는 모델로 구성되어 있습니다.
CART는 Figure 1과 같이 의사결정나무와 달리 노드 (leaf)가 각 데이터를 나타내는 것이 아닌 하나의 값을 나타냅니다. Figure 1은 5개의 데이터에 대해 나이라는 특성을 기준으로 노드를 나누는데, 각 노드에는 어떠한 값이 할당된 것을 볼 수 있습니다.
하나의 나무는 예측 모델로 적합하지 않기 때문에 ensemble 모델에서는 여러 개의 나무를 사용하여 각 나무의 결과값의 합을 예측값으로 사용합니다. Figure 2에서 남자는 2, 0.9의 값을 가진 노드에 각각 할당되 2.9의 예측값을 가지고 할아버지는 -1, -0.9의 값을 가진 노드에 각각 할당되 -1.9의 예측값을 가진 것을 볼 수 있습니다. Ensemble 모델에서 여러 개의 나무는 각각 서로를 보완하도록 훈련되겠죠.
Figure 2의 결과를 수식으로 일반화하면 Equation 1과 같습니다. $\hat{y}_i$는 데이터 $x_i$의 예측값, $K$는 사용된 CART의 개수, $f$는 CART 모델들입니다.
각 CART 모델을 훈련시키기 위한 목적함수 (objective function)은 Equation 2와 같습니다. $l(y_i, \hat{y}_i)$는 정답 $y_i$, 예측값 $\hat{y}_i$에서 계산된 목적함수이고 $\Omega$는 과적합을 방지하기 위한 모델의 정규화 함수입니다.
Tree boosting
Equation 2에서 각각의 $f_i$는 해당 나무의 구조와 노드의 예측값을 담고 있습니다. 이 모든 나무들을 한 번에 훈련시키기는 불가능하기에 XGBOOST 에서는 additive 훈련 방법을 사용합니다. 즉, 첫 단계의 예측값을 $\hat{y}_i=0$으로 설정하고 $t$ 단계의 예측값을 $\hat{y}_i^{(t)}$라 했을 때 boosting 원리에 따라 매 단계의 예측값을 Equation 3과 같이 구성할 수 있습니다. 즉, boosting 원리처럼 매 단계마다 전 단계에서 예측하지 못했던 부분을 예측하는 모델을 additive 하게 만들어가는 것이죠.
그렇다면 $t$ 단계에서 훈련시킬 목적 함수는 Equation 4와 같이 정의할 수 있습니다.
만약 회귀분석을 위해 $l$을 MSE (Mean Squared Error)를 사용한다면 Equation 5와 같이 목적함수를 풀어쓸 수 있습니다. Equation 5에서 첫 번째 항은 전 단계의 예측값과 라벨의 차이인 residual 임을 알 수 있습니다. (이 값 자체가 MSE의 gradient 가 됩니다.)
하지만 모든 유형의 목적함수를 깔끔하게 풀어쓸 수 없기 때문에 Taylor expansion을 사용하여 $l$을 Equation 6과 같이 분해합니다. 이때, Equation 4의 $f_t (x_i)$ 부분이 매우 작다고 가능해야 잘 근사게 되겠죠. Tayler expansion의 정의에 따라 $g_i, h_i$는 Equation 7과 같이 $l$의 $\hat{y}_i^{(t-1)}$에 대한 1차, 2차 편미분값이 됩니다.
최종적으로는 상수항과 $l(y_i, \hat{y}_i^{(t-1)})$항을 제거하여 (전 단계에서 이미 계산되었으므로) Equation 8이 $t$ 단계에서의 최종 목적함수가 됩니다. 따라서 XGBOOST의 목적함수의 최적화는 $g_i, h_i$에 의존하므로 우리가 새로 설계한 목적함수에 대해 1차, 2차 미분형태를 구해 입력하면 원하는 목적함수에 맞게 XGBOOST를 최적화시킬 수 있습니다.
Model complexity
과적합을 방지하기 위해 정규화 항 $\Omega(f)$ 또한 목적함수에 넣어줍니다. 정규화란 모델을 구성하는 파라미터의 크기를 줄이는 과정이므로 먼저 모델 $f(x)$를 Equation 9와 같이 정의합니다. $w$는 각 노드의 예측값, $q$는 각 데이터가 속한 노드 인덱스, $T$는 노드의 개수입니다.
이후 모델 $f$에 대한 정규화 항 $\Omega(f)$을 Equation 10과 같이 정의합니다. 정규화 항의 정의는 여러가지로 가능하지만 실험에서는 Equation 10이 제일 잘 동작한다고 합니다. 다른 tree-based 모델이 정규화의 필요성을 간과하는 것과 달리 XGBOOST는 목적함수에 직접적으로 정규화 항을 정의함으로써 모델이 다양한 상황에서 학습이 잘 되도록 합니다.
The structure score
Equation 9에서 정의한 $f$ 로 Equation 8을 Equation 11과 같이 정리할 수 있습니다. $I_j = \{i|q(x_i)=j\}$는 $j$번째 노드에 속한 데이터 인덱스를 가리키는 indicator 로 같은 노드에 속한 데이터들은 CART에 의해 하나의 같은 값으로 표현된다는 사실을 이용한 것입니다.
$G_j=\sum_{i\in I_j}g_i$, $H_j=\sum_{i\in I_j}h_i$로 정의하면 Equation 11을 다음과 같이 정의할 수 있습니다.
Equation 12는 $w_j$에 대한 2차 함수이므로 목적함수를 최소화하는 $w_j^*$와 이에 따른 $obj^*$를 Equation 13으로 정의할 수 있습니다.
Figure 3을 보면 이 과정을 쉽게 알 수 있습니다. 각 데이터별로 $g_i, h_i$를 계산하고 이를통해 해당 단계에 맞는 최소 목적함수 값을 얻을 수 있습니다. 당연하게도 목적함수 값이 낮을수록 좋은 CART 모델이겠죠. 특히 각 노드의 $G, H$는 노드에 속하는 데이터들의 $g, h$의 합으로 결정되는 것을 볼 수 있습니다.
Learn the tree structure
가능한 모든 경우의 나무를 나열하고 가장 좋은 목적함수 값을 가지는 것을 선택하면 좋겠지만 실질적으로 불가능합니다. 따라서 나무의 매 depth (level) 마다 최적화를 수행하게 되는데요, 의사결정나무의 impurity 를 통한 분기와 마찬가지로 해당 노드에서 2개의 노드로 분기하기 위한 gain 은 Equation 14와 같이 정의됩니다.
Equation 14는 나누어진 2개의 노드에서의 $G_L, H_L, G_R, H_R$로부터 얻은 최적값에서 부모 노드의 최적값을 빼준 것으로 노드가 1개에서 2개가 되었으니 마지막에 $-\gamma$항이 추가됩니다. 따라서 gain 값이 $\gamma$보다 작을 경우 노드를 분기하지 않는 것이 낫겠죠. (이를 일반 tree-based 모델에서의 pruning 이라 합니다. 분기를 더 이상 진행하지 않고 멈춥니다.)
또한 해당 단계에서의 $g_i, h_i$를 계산한 이후 이를 크기대로 정렬하면 다음 그림과 같이 모든 분기 경우에서 최적의 분기 값을 효율적으로 찾아낼 수 있습니다.
참조
'Machine Learning Models > Classic' 카테고리의 다른 글
| LightGBM feature importance (0) | 2022.10.04 |
|---|---|
| Dimension Reduction - t-SNE (2) (0) | 2021.05.18 |
| Dimension Reduction - t-SNE (1) (0) | 2021.04.20 |
| Dimension Reduction - PCA (0) | 2021.04.20 |
| Classification - Metrics (2) (1) | 2021.04.19 |
