머신 러닝 스터디 - Boosting

Boosting은 일반적인 기법이지만 Decision tree와 결합되어 자주 사용된다. 앞서 설명한 Bagging과 다른 점은 Boosting은 순차적(Sequential)이라는 점이다. Bagging에서 각 데이터셋을 독립적으로 부트스트랩(Bootstrap)한 후 트리를 적합하고 이들을 결합하였다. 여기에서 이번에 만든 트리가 다음 트리를 만드는데 영향을 미치지 않는다.

Boosting은 이와 다르게 작은 트리(일반적으로 1개의 분할만 있는 그루터기, Stump)를 순차적으로 계속 생성한다. 이번에 생성한 트리가 제대로 예측하지 못한 데이터에 대해 좀 더 집중하는 방식으로 다음 트리를 생성한다. 또한 샘플에 대한 Bootstrap도 수행하지 않는다.

 

분류트리 생성 절차(Adaboost 방식)

1. 훈련셋에 대하여 가장 잘 적합하는 작은 트리(Stump)를 생성한다. 이 때 적합이 잘 되었는지는 Gini index 또는 Entropy등을 활용할 수 있으며 각 샘플에 대해 동일한 Weight를 적용한다.

2. 제대로 분류되지 않은 샘플에 대하여 Weight를 증가시켜준다. 

  - Total error: 전체 중 제대로 분류되지 않은 샘플의 비율

  - Amount of say: 해당 Tree의 Weight. 분류를 잘 수행할수록 높은 값을 갖는다. 아래의 공식에 의해 계산 $$ AmountOfSay = \frac{1}{2} log(\frac{1 - Total Error}{Total Error}) $$

  - 제대로 분류되지 않은 샘플에 대해 Weight를 업데이트 한다.  $$ NewWeight = Weight \times e^{AmountOfSay} $$

  - 제대로 분류된 샘플에 대해 Weight를 업데이트한다. $$ NewWeight = Weight \times e^{-AmountOfSay} $$

  - Weight의 합이 1이 되도록 Normalize한다.

3. 1,2를 반복하여 작은 트리들을 계속 생성한다.

4. 실제 분류시에는 작은 트리들의 Voting을 통해 결과를 도출한다. 이 때 각 트리는 Amount Of Say만큼의 Voting Right을 갖는다.

다음 유튜브 비디오에 잘 설명되어 있다: https://youtu.be/LsK-xG1cLYA

 

회귀트리 생성 절차(Gradient boost 방식)

1. f(x)=0 이라고 놓고 훈련셋의 모든 i에 대해 r_i = y_i로 설정한다.

2. b = 1, 2, ... B 에 대하여 다음을 반복한다.

  a. 데이터에 대해 작은 트리(Maybe bigger than stump, usually 8-32 leaf tree)를 생성한다.

  b. 새로운 트리의 수축 버전에 대하여 f를 업데이트한다. 여기에서 Lambda값에 의해 학습 속도가 결정된다. Lambda가 작을수록 학습이 천천히 일어나고 B를 크게 만들어주어야 한다. $$ f(x) \leftarrow  f(x)  + \lambda f^b(x) $$

  c. 잔차들을 업데이트한다. $$ r_i \leftarrow r_i - \lambda f^b(x) $$

3. 아래와 같이 부스팅 모델을 출력한다.(사실 2의 업데이트 과정에서 이미 완성되어있다.) $$ f(x) = \Sigma_{b=1}^{B} \lambda f^b(x) $$

다음 유튜브 비디오에 잘 설명되어 있다: https://youtu.be/LsK-xG1cLYA

 

특징

• 트리 생성이 순차적으로 이루어지며 천천히 학습된다.
• 작은 트리들을 여러 개 사용하게 되며, 이는 해석하기 용이하게 해준다.

단점

• 학습이 오래 걸리며 Overfitting될 우려가 있다.

 

XGBoost(Extreme Gradient Boosting)

Gradient boosting에서 발전된 방법론이다. 큰 그림에서는 비슷하지만 성능 향상 및 최적화를 위한 요소들이 가미되어 있다. 아래 특징 정도로 요약해 볼 수 있을 것이다.

1. Gradient Boost
2. Regularization
3. An unique regression tree
4. Approximate Greedy Algorithm
5. Parallel learning
6. Weighted Quantile Sketch
7. Sparsity-Aware Split Finiding
8. Cache-Aware Access
9. Blocks for Out-of-Core Computation

다음 유튜브 비디오에 잘 설명되어 있다: https://youtu.be/OtD8wVaFm6E

 

 

Unique regression tree 생성

• Similarity score: 각 영역들의 샘플들이 얼마나 비슷한지를 측정

$$SimilarityScore = \frac{(\sum Residuals)^2}{CountResiduals + \lambda} $$

• Similarity gain: 분기에 의해 생성된 각 영역의 Similarity score가 얼마나 증가했는지를 측정. 이를 바탕으로 분기하게 될 기준점을 정하며, Pruning을 할 때도 Similarity gain이 Threshold에 미치지 못하면 Pruning 대상이 된다.

$$Gain = Similarity_{left} + Similarity_{right} - Similarity_{root}$$

 

 

장점

• 병렬 처리가 가능하여 속도가 빠르다. - Hadoop 사용
• Overfitting 방지를 위한 regularization term이 있음
• 분류, 회귀 모두 가능하다. (CART(Classification and regression tree) 앙상블 모델 사용)
• Early stopping 기능 있음
• iteration마다 Cross-validation 기능 수행한다.

단점

• 여전히 Overfitting의 문제가 있으며 Tree based 의 태생적 한계가 있다. Entropy 문제로 인하여 Training data set에 좌지우지된다.
• hyperparameter가 많다.
• 중요 Para 추출이 어렵다.