Bagging, Boosting and Stacking

본 포스트에서는 Bagging, Boosting 그리고 Stacking 기법이 무엇인지, 그리고 각 기법을 사용하는 대표적인 알고리즘들 Random Forest, AdaBoost, Gradient Boost 그리고 요즘 Kaggle Ranker 들이 묻지도 따지지도 않고 사용하는 XgBoost 등에 대해서 설명하고자 한다.

1. Bias & Variance

Bagging 및 Boosting 을 설명하기 위해서는 사전에 머신러닝에서 이야기 하는 Error 가 Bias 와 Variance로 구성되어 있으며, 각 Bias 와 Variance 가 어떤 특성을 가지고 있는지를 먼저 이야기 할 필요가 있다.

인터넷에서 간단하게 한장으로 Error 와 Bias, Variance 를 잘 설명한 자료가 있어서 첨부 하였다. 위에서 보는 바와 같이 Error 는 Bias 와 Variance의 합으로 구성되어 있으며, Bias 는 예측 값과 참 값의 차이의 제곱을 나타내고, Variance 는 전체 예측값의 평균과 각 예측값의 차이의 제곱으로 설명된다. 이를 시각화여 보면 아래와 같이 설명 될 수 있을 것이다.

Bias 와 Variance 는 Trade Off 관계에 있는데, 왜 그럴까? Bias 는 보통 우리가 ML 모델이 Under Fitting 된 상황에서 커지게 된다. 즉, 모델이 Train 데이터에 충분히 훈련되지 못했을 때 커지게 된다. Variance 는 어떨까? 보통 Train Data 에 너무 Over Fitting 되었을 때 커지게 된다. 즉 Bias 와 Variance 가 둘다 낮은 모델을 만들기는 참 어렵다는 이야기이다. 물론 가장 좋은 해결방법은 아주 많은 양의 데이터를 확보하는 것으로 많은 데이터가 확보 된다면 Bias, Variance 를 둘다 낮출 수 있다.

2. Bagging vs Boosting vs stacking

단순히 학습 데이터를 더 많이 확보 할 수 있다면 좋겠지만, 그렇지 못한 경우 사용할 수 있는 기법을 크게 3가지로 정리할 수 있는데, 각각 그 목적이 위에서 설명한 Bias와 Variance 가 되겠다. Random Forest로 대표되는 Bagging 은 Variance 를 줄이는 것에 그 목적이 있으며, AdaBoost 등 각종 Boosting 알고리즘으로 대표되는 Boosting 알고리즘은 Bagging 을 통해서도 맞추기 어려운 데이터를 잘 맞출수 있도록 하여 Bias 를 더 줄이는 것에 목적을 두고 있다. 마지막으로 Stacking 을 그 두가지를 동시에 달성하고자 하는 목적으로 사용된다.

3. Bagging & Random Forest

충분히 데이터를 확보 할 수 없는 상황에서 Variance 를 줄이기 위해서 Bagging 을 사용하는데, 그 프로세스는 너무나도 간단하다.

(1) 만들고자 하는 모델의 수 만큼 Random 하게 Train Data 에서 Subset 을 추출한다.
(2) 각각의 데이터를 기반으로 모델을 개발한다
(3) 각각의 모델을 Ensemble 하여 결과를 도출한다.
※ Ensemble 방법에는 Soft Ensemble, Majority Vote, Super Learner등 여러가지 방법 有

Random Forest 는 Tree 모델을 기반으로 Bagging 을 그대로 실행하는 방법이라고 생각하면 된다.

위에 시각화 한것 과 같이 Tree 모델 여러개를 Ensemble 하는 것이 바로 Random Forest 이다. 데이터를 분류하는 관점에서 보면 아래와 같은 효과가 있게 된다.

왜 Bagging 이 Variance 의 감소에 도움이 되는지 시각적으로 설명이 잘 될 수 있을 것 같다. 이러한 Bagging 의 경우 잘 맞추지 못하는 데이터는 여전히 잘 못 맞출 수 밖에 없는 구조를 가지고 있다.

4. Boosting Concept

Boosting 은 Bagging 에서 해결하지 못한, 못맞추는 문제는 여전히 못맞추는 문제 ( Bias 가 높은 문제) 를 해결하기 위한 방법으로 그 개념 매우 간단한데, Bagging 이 여러개의 모델이 서로 관련성이 없이 생성이 되었다면 (병렬로 훈련이 되어도 된다면) Boosting 은 순차적으로 모델이 생성이 되어야 하는데, 다음 모델을 만들때 마다 앞에 모델에서 잘 분류하지 못했던 데이터를 잘 분류 할 수 있도록 데이터 혹은 가중치를 그 다음 모델에 반영하면서 계속 모델을 추가해 가는 방식으로 이해하면 된다. 간단히 설명하자면 아래와 같다.

(1) Bagging 과 마찬가지로 일부 데이터를 Bagging 하여 첫번째 모델을 만든다
(2) 첫 번째 모델을 Train Data 를 기준으로 테스트하여 잘 맞추지 못한 데이터를 찾는다
(3) 두 번째 모델을 만들때에는 앞서 만든 모델에서 잘 맞추지 못하는 데이터를 맞출 수 있게 훈련
(4) 위 과정을 계속 반복한다.

4-1 AdaBoost

Boosting 의 Concept 은 알겠는데, 어떻게 두번째 모델을 만들때, 첫번째 모델에서 잘 맞추지 못하던 데이터를 맞출 수 있도록 훈련하지? 라는 질문이 들 것 같다. 실질적인 구현방법에는 여러가지가 있는데 그중에 Adaptive Boosting 이라는 알고리즘을 먼저 설명하고자 한다.

Ada Boost 를 설명하기 전에 Stump (Weak Learner ) 의 개념을 먼저 설명할 필요가 있다. 아래는 주어진 데이터를 설명하는 일반적인 Tree 모델이다.

이번에는 Boosting 모델에서 말하는 Weak Learner (Stamp) 의 예제가 되겠다. Boosting 알고리즘은 아래와 같은 복수의 Stumps 들을 모아서 더 좋은 성능의 모델을 만드는 형태이다.

Boosting 에서는 한번에 모든 모델을 병렬로 생성하는 것이 아닌 순차적인 생성 프로세스를 갖게 되는데, 아래는 Ada Boost 의 Step 별 모델 생성과정이라고 보면 된다.

간단하게 풀어서 설명하면 아래와 같다.
(1) 모든 데이터에 대한 가중치를 동일하게 세팅한다
(2) 각각의 모델에 대해서 Error 를 산출한다 (처음에는 모든 데이터의 가중치가 같다)
(3) 모든 모델에 대해서 Error 를 구하고 가장 성능이 좋은 모델을 선택한다.
(4) 해당 모델의 가중치를 Error 를 기반으로 정한다
(5) 더 모델을 추가할 지 여부를 선택한다.
(6) 종료하지 않는다면, Error 를 기반으로 데이터 자체의 가중치를 조정한다
(7) 계속 반복한다 .

뭔가 설명이 부족할 수 도 있다는 생각이 들어서, 예제를 하나 준비하였다.

위의 가정은 아래와 같다.
(1) 가지고 있는 데이터는 5개로 가정하자 (A,B,C,D,E)
(2) 구분해야 하는 Label 은 (흑, 백)이라고 가정하자
(3) 우리가 가지고 있는 Weak Learner 는 (x<2, x<4, x<6, x>2, x>4, x>6) 6개라고 가정하자

이제 순서대로 계산을 시작하여 보도록 하자 .

(1) 우리가 가지고 있는 H(x) 6개로 5개의 데이터에 대한 Error 를 구해 보자
(2) 첫번째 Step 에서는 5개 데이터 모두에 대한 중요도(가중치가) 1/5 로 동일하다
(3) 6개 모델로 테스트를 해보니, x>6 이 데이터 C 하나 틀리고 다 맞춰서 Error 가 1/5 로 가장 좋다
(4) 그럼 첫번째 모델은 x>6 으로 선택하고, 가중치를 결정해야 한다.

e = 1/5 이니까 위에 식에 넣어서 계산을 해보면, 1/2ln4 가 된다 그래서 첫 번째 모델을 아래와 같이 추가하여 준다.
그러면 현재까지의 Boosting 모델은 아래와 같다.

  H(x) = 1/2ln4(x<6)

(5) 첫 번째 모델을 선택하였으니, 이제 첫 번째 모델이 잘 맞추지 못하는 데이터를 잘 맞출 수 있는 모델을 다음 모델로 선정을 해야 한다. 현재는 모든 데이터에 대한 중요도(가중치)가 1/5로 동일하다. 지금 상태로 모든 모델을 다시 테스트하면 첫 번째 Step 과 동일한 X>6 이 선택 될 수 밖에 없다 그렇기 때문에 첫번째 모델이 잘 맞추지 못하는 데이터의 가중치는 올려주고, 잘 맞추는 데이터의 가중치는 내려주는 작업을 해야 한다. 위의 예제에서는 C 데이터를 뺀 나머지 A,B,D,E 데이터는 X>6 모델이 잘 맞추고 있다. 그럼 C 와 나머지 데이터의 가중치가 어떻게 변하는지 계산하여 보자 .
– C 의 경우 : (1/5) * (1/2)(1/(1/5)) = 1/2
– 나머지 : (1/5) * (1/2)(1/(4/5)) = 1/8
첫 번째 Step 에서 모두 1/5 이였던 데이터의 가중치가 못 맞춘 C 는 1/2 로 상승하고 나머지 맞춘 데이터는 1/8로 떨어졌다.

(6) 이 상태에서 다시 각 6개의 모델에 대한 테스트를 해보면, X<2 모델이 가장 성능이 좋은 것으로 평가가 된다. 그리고 해당 모델에 대한 가중치는 1/2ln((1-2/8)/(2/8)) = 1/2(ln3) 이 되고 지금까지 Boosting 모델은 아래와 같다.

H(x) = 1/2ln4(x<6) + 1/2(ln3)(x>2)

위와 같은 방식으로 기준치를 만족할 때 까지 계속 반복하는 것이 AdaBoosting 의 핵심이다.

4-2 Gradient Boost

아래는 Gradient Boost 는 앞에서 설명한 AdaBoost 아래와 같이 몇 가지 핵심적인 차이가 존재한다.
(1) 처음 시작시 Stump 를 가지고 시작하는 것이 아닌 Initial Value 로 시작한다
(2) Stump 처럼 1 Depth 의 Tree 가 아닌 Leaf 가 8개~32개 정도되는 더 큰 Tree 를 사용한다
(3) Tree 가 예측하는 것은 그 값 자체가 아니라 Residual 이다.

아래는 Gradient Boost 가 모델을 생성하는 과정인데, 한 Step 씩 살펴 보도록 하자.

다시한번 한글로 정리하면 아래와 같이 되겠다.
(1) X,Y 데이터 쌍을 준비하고, 미분이 가능한 Loss Function 을 설계
(2) 준비한 데이터 Set 을 최대한 잘 설명할 수 임의의 Y^ 상수를 정의 (이게 평균이다)
(3) 이제 M 개의 모델을 순차적으로 생성한다
(3-1) 첫 번째 Step 은 전체 데이터에 대해서 예측값과의 Loss Function 에 대한 Gradient 를 구하는 것
※ m 이 1이라면 Predicted Value 는 Step 1 의 초기 값이 될 것
(3-2) 각 데이터에 대해서 Gradient 를 구했으면, 이를 설명하는 Tree (사이는 Hyper Parameter) 를 그린다.
이때, 각각의 leaf 는 복수의 데이터 (j) 를 포함한다
(3-3) 각 R 에 대해서 Loss 를 최소화하는 대표값을 구한다. (이게 그냥 평균이다)
(3-4) 최종 모델 F(X) 에 방금 구한 모델을 가중치(Learning Rate)를 가지고 Update 한다
(4) M 번 모델(Hyper Parameter) 까지 다 만들고 나면 F(X) 가 정의되고 프로세스는 종료

데이터는 X, Y 쌍으로 존재해야 하며, 미분가능한 Loss Function 이 준비 되어야 함. 여기서 부터 설명을 해보도록 하겠다. Loss Function 은 Regression 문제의 경우 가장 일반적인 형태의 함수를 사용한다. 미분하면 아래와 같이 Residual 이 되는 형태의 Loss Function 이다.

이제 AdaBoost 와는 달리 Sigma(L(Y,Y^)) 를 최소화하는 Y^ 을 찾아야 하는데, 아래와 같은 3개의 데이터가 예라고 해보자.

찾고 싶은 Y^ 은 3개의 데이터를 예로 했을때, 1/2(88-y^) + 1/2(76-y^) + 1/2(56-y^) 이 최소가 되는 값이고, 이는 전체 Loss 를 Y^ 으로 비분 했을 때, 0 이 되는 지점을 찾는 문제가 된다. 이를 표현하면 아래와 같이며, 결국 수식을 풀어 보면, Y^ = (88+76+56)/3 이 되어, Y Set 의 평균이 결국 최적의 y^ 이라는 이야기가 된다.

그 다음으로는 M 개(사용자가 지정) 한 모델을 순차적으로 만든는 과정인데, 그 과정의 첫 번째는 주어진 훈련 데이터 Y 에 대해서 Y^ 과의 Loss 의 Gradient 를 구하는 것이다. 그래서 이 알고리즘 이름이 Gradient Boost 라고 한다.

그런데, 이 부분은 위의 Loss Function 정의에서 이미 계산했던 내용으로, 앞에 마이너스 까지 곱하기 때문에, 결론적으로 그냥 Residual 이다. 갑자기 앞에서 설명하는 데이터와 다른 데이터로 바뀌었다는 점은 매우 죄송하지만, 여하튼 아래와 같은 데이터에 대해서 Step2 에 A 과정을 수행이 된다고 볼 수 있다.

자 이제 다음 과정은, 계산한 Residual 을 예측하는 Tree 모형을 만드는 일이다. 여기에서 초록색 부분이 B Step 에서 이야기하는 Region R 이 되는데 여기에는 j 개의 데이터가 포함될 수 있다고 정의하고 있다.

C Step 은 각 R (Tree 의Leaf) 에 하나의 대표 값을 정의하는 과정인데, 그 방법을 아래와 같이 정의하고 있다. 이것 또한 풀어서 해석하면, m-1 번째 모델의 예측값 (여기서는 m이 1이니까 , Initial Value) 에 우리가 예측하고자하는 Residual 값을 더한것이 결국 예측하고자 하는 값과의 오차가 최소가 되게 하는 Residual 을 구해서 해당 Leaf 의 대표 값으로 사용하라는 이야기 인데, 제일 처음에 Initial Value 를 구했던 것과 동일하게 Gradient 방식으로 접근해 보면 다시 “해당 Leaf 에 소속된 데이터의 평균이 ArgMin 을 만족한다” 라고 결론 내릴 수 있다.

2번 Step 의 마지막으로 새로운 F1(x) 정의하는 과정이 남아 있는데, 하나씩 해석해 보면 매우 간단하다. Fm-1 은 현재 m이 1이기 때문에 처음에 정의한 Initial Value (평균)이라고 볼 수 있고, 감마는 Learning Rate 로써, 우리가 위에서 구한 Tree 의 Residual 예측 값에 가중치를 부여하여 조금 천천히 답에 다가갈 수 있도록 조정하는 역할을 한다. 그 뒤의 Sigma 는 만일의 경우 복수의 Leaf 가 해당 될 경우 사용되는 것이며, I 는 우리가 위에서 만든 Tree 모델이 되겠다.

이렇게 1번 모델이 만들어진 결과를 시각적으로 표현해 보면 아래와 같을 것이다.

그리고 1번,2번,3번 계속 만들어서 우리가 지정한 M 번째 모델까지 만들게 되면 아래와 같은 모양이 될 것이다.

4-3 XgBoost (eXtreme Gradient Boosting)

Gradient Boost 는 굉장히 잘 만들어진 알고리즘이지만, 그 속도가 느리고 비효율적이라는 단점이 있어, 이를 개선하기 위해서 Microsoft 에서 만든 알고리즘으로 완전한 패키지 형태로 제공되어 사용자들이 손쉽게 사용할 수 있다. 대표적인 차이는 Regularization 을 사용한다는 점과 각종 분산처리 지원을 통한 속도 향상 및 Package 화를 통해 자동으로 Hyper Parameter Search 를 지원하는 등 손쉽게 알고리즘을 사용할 수 있는 편의성 정도가 될 것 같다.

실제 해당 모델 사용시 사용자 입장에서 중요한 것은 데이터의 구성과 하이퍼 파라메터의 세팅이다. 하이퍼 파라메터는 Weak Learner 로 사용할 모델 종류, 최대 생성 모델 수, Learning Rate , Tree 의 예라면 최대 깊이 등 다양한 하이퍼 파리메터가 존재하며 손쉽게 패키지를 통해 지정 가능하다.

또, XgBoost 패키지에서는 importance 라는 기능을 통해 모델에 사용된 데이터를 해석할 수 있도록 도와주고 있는데 크게 3가지 중요한 요소가 존재한다.

Gain contribution of each feature to the model. For boosted tree model, each gain of each feature of each tree is taken into account, then average per feature to give a vision of the entire model. Highest percentage means important feature to predict the label used for the training (only available for tree models);

Cover metric of the number of observation related to this feature (only available for tree models);

Weight percentage representing the relative number of times a feature have been taken into trees.

5. Stacking

Stacking 은 여러개의 다른 종류의 모델 (전혀 다른 종류의 모델)의 결과를 다시 Level 2 모델의 Input 데이터로 활용하여 모델을 훈련하고 Final Prediction 을 하겠다라는 Concept 이다.

Stacking 에 Feature 를 뽑기 위한 모델에는 심지어 단일 모델로도 수일 이상 훈련이 필요한 DNN 계열도 사용이 될 수 있으며, 아래의 예제와 같이 2단 이상의 더 깊은 Stacking 도 가능하다.

이제 머신러닝은 누가 더 많은 H/W 자원과 데이터를 가지고, 효율적으로 빠르게 실험을 할 수 있는 프로그래밍 체계를 구축하는 것만 남았다는 어떤 교수님의 말이 떠오른다.