Boosting

부스팅 기법(Boosting)에 대해 알아보자

Weak Learner

부스팅 기법에 대해 알아보기 전에 알아야 할 몇가지 용어들이 있다. 그 중 하나가 Weak Learner이다.
Weak Learner는 다른 말로 Simple Learner이라고도 불리우며, 간단한 학습기 정도로 보면 될 것이다.

대표적인 Weak Learner는 다음과 같다.

• Decision stumps : depth가 1인 decision tree
• Shallow decision trees
• Naïve Bayes
• Logistic regression

우리는 Weak Learner를 많이 가질 것이고, 많은 학습기들을 이용해서 예측작업을 할 것이다.
Weak Learner들의 앙상블을 통해 어떤 결과를 예측해보려는 것이다. 이렇게 다수의 Weak Learner들을 이용해서 학습하면, input space의 다른 부분들을 보완해줄 수 있다.

부스팅에 대해서 공부할 때 배깅이 자주 등장하는데 차이를 비교해보자면 다음과 같다.

Bagging

• 훈련 데이터에서 다수의 표본을 추출하고, 개별 트리의 결과를 병합하여 단일 예측 모델을 생성
• 각 bootstrap 과정이 독립적이므로 병렬 처리가 가능

Boosting

• Bagging과는 달리 순차적으로 시행되며 bootstrap 과정이 없음
• Original dataset에서 약간의 수정을 거친 데이터를 개별적으로 학습한 후, 결합되어 강력한 분류기 생성

부스팅의 아이디어는 간단하다. 약한 학습기들을 이용해서 학습된 학습기들을 결합해 strong learner를 만드는 것이다. Classifier의 경우 학습기들의 결합방법은 Majority voting방식이 될 것이고, Regressor의 경우 학습기들의 결합방법은 평균이 될 것이다.

부스팅의 알고리즘도 심플하다. 앙상블 내, $t$번째 분류기 $c_t$와 $t+1$번째 분류기 $c_{t+1}$이 연관성을 가지고 생성하는 것이다.

1. 훈련데이터 X의 샘플을 $c_t$가 옳게 분류하는 것과, 그렇지 않은 것으로 나눈다.
2. 옳게 분류하는 샘플들은 인식이 가능하므로 가중치를 낮춘다.
3. 틀리게 분류하는 샘플들은 가중치를 높인다.
4. $c_{t+1}$학습시키기 위한 정책으로 sampling과정에서 가중치가 높은 샘플이 뽑힐 확률이 높아지게 한다.

Ada Boost(Adaptive Boosting)

Yoav Freund & Robert Schapire가 제안하였고, Weak learner를 반복적으로 사용하고, 그 결과를 합하여 모델의 accuracy를 향상시킨다.

AdaBoosting은 위에서 살펴본 알고리즘이 작동하는 방식과 거의 비슷하게 동작한다.

그림과 함께 살펴보자

첫번째 그림에서 약한 학습기인, 결정 그루터기가 하나의 결정경계를 가지고 +와 -를 나누고 있다. 이렇게 나눴을 때 위쪽의 3개의 +들은 잘못 분류가 되어 가중치가 높아진다. 두번째 그림에서는 오른쪽의 - 두 개만 잘 분류가 되었고 결정경계 왼쪽의 대개의 -들은 잘못 분류가 되어버렸다. 이 역시 가중치가 높아지고 학습된 3개의 Weight를 결합해서 + -를 잘 분류해내는 하나의 강 분류기를 만들어낸다. 결국 Weak Learner들의 앙상블이다.

가중치 업데이트 규칙은 다음과 같다.
$w^{(i)} = w^{(i)}$, $\hat{y_j}{(i)}= y_{(i)}$ 일때
$w^{(i)} = w^{(i)}exp(\alpha_j)$, $\hat{y_j}{(i)}\neq y_{(i)}$ 일때
그런 다음 모든 샘플의 가중치를 정규화 한다.(즉, $\sum_{i}^{m}w^{(i)}$로 나눠준다.)

마지막으로 새 예측기가 업데이트된 가중치를 사용해 훈련되고 전체 과정이 반복된다. 새 예측기의 가중치가 계산되고 샘플의 가중치를 업데이트해서 또 다른 예측기를 훈련시키는 방식이다.

Adaboost는 지정된 예측기 수에 도달하거나 완벽한 예측기가 만들어지면 중지된다.

Adaboost의 예측은 $\hat{y}(x)=\sum_{i=1}^{N}\alpha_j$로 이루어진다.($N$은 예측기의 수)

Gradient Boosting

그래디언트 부스팅은 Ada부스팅처럼 이전까지의 오차를 보정하도록 예측기를 순차적으로 추가한다. 하지만 Ada처럼 반복마다 샘플의 가중치를 수정하는 대신 이전 예측기가 만든 잔여 오차(residual error)에 새로운 예측기를 학습시킨다. 다시말해서 약한 분류기가 이전 학습에서 발견하기 어려웠던 문제성 관측값, 즉, 예측이 틀린 관측값에 집중하게 하는 것이다.

다른 boosting 기법처럼 모델을 단계적으로 구축해 나가는 것은 같지만 임의의 미분 가능한 손실 함수를 최
적화하는 문제로 일반화한 방법이다. GB는 여러개의 간단한 모델의 ensemble을 학습한다.

Motivation of Gradient Boosting

($x_1$,$y_1$),($x_2$,$y_2$) …, ($x_n$,$y_n$) 총 n개의 데이터가 있고, 이 데이터를 이용하여 회귀모형 $F(x)$ 를 학습하는 프로젝트를 진행한다고 생각해보자. 팀원이 모델 $F$를 만들었다. 하지만 성능이 그다지 좋지 않다. $F(x_1)$ = 0.8의
예측값을 생성한다. 하지만 실제 $y_1$ = 0.9이다. $y_2$ = 1.3인데, $F(x_2)$ = 1.4의 값이 나온다. 이 모델의 성능을
향상시켜야 하는데 한가지 제약조건이 있다. 팀원이 만든 모델 $F$는 절대 건드리지 않고, 모델을 향상시켜야
한다. 어떤 방법이 있을까?

방법은 간단하다. 원래 모델은 그냥 두고, 차이만큼을 더해주는 함수 $h(x)$를 만들어주면 되는 것이다.
완벽하게 우리의 목적을 달성시키지는 못하지만, 근사적으로 달성할수는 있다.

그렇다면$h(x)$는 어떻게 구할 수 있을까?
$h(x_1) = y_1 - F(x_1)$
$h(x_2) = y_2 - F(x_2)$
$…$
$h(x_n) = y_n - F(x_n)$ 이므로,$(x1, y_1-F(x_1))$, $(x2, y_2-F(x_2))$,$…,$,$(x_n, y_n-F(x_n))$을 학습하면 된다.

학습데이터를 이용하여 75%정도의 정확도까지 모델을 학습하고, 나머지 미설명 부분은 오차항에 남겨둔다.
$Y = F(x) + E$
오차항을 이용하여 다른 모델을 학습시킨 후, 그 전 모델에서는 미설명 부분이었으나 이번 학습에서는 설명
이 되는 부분을 찾아내 원 모델에 추가한다. 단, 추가 모델은 반드시 전체 정확도를 향상시켜야만 한다.
$Gradeint(E) = G(x) + E2$

모델이 약 80%의 정확도를 갖게 되면 식은 다음과 같게 된다.
$Y + F(x) + G(x) + E2$

이런 방법을 계속해서 사용해 나가고, GB는 단순 합보다 가중 평균을 사용하여(다른 모델보다 정확도가 높은 예측 결과를 가진 모델에 더 높은 중요도 점수를 부여) 모델의 정확도를 더 개선할 수 있다
$Y=\alpha{F(x)}+\beta{G(x)}+\gamma{H(x)} + E$ $…$

Gradient Boosting의 Loss Function

손실 함수는 해결하려는 문제에 따라 다르다. 부스팅에서는 처음부터 최적화를 하는 것이 아니라, 각 단계별로 이전 단계에서 설명되지 못한 손실에 관해 최적화를 수행한다.

• 회귀 문제 : Least squares method (최소 자승법)
• 분류 문제 : Log loss function (로그 손실 함수)

손실 함수를 최소화하기 위해 약한 분류기를 추가할 가법 모델(additive model)

• 기존 트리는 변동이 없고 새로운 트리가 하나씩 추가된다.
• 기울기 하강 절차가 사용되어 트리가 추가될 때의 손실을 최소화한다.

Leaf node마다 가중치, score가 부여가 된다. Gini계수 등을 사용하지 않는다.
분류 / 회귀 : Sklearn에서는 (friedman) mse를 사용한다.