1. Boosting : AdaBoost
오늘은 부스팅 중에 Adaboost에 대해서 알아볼까 합나디.
📌 Adaboost 특징
- 각 단계에서 새로운 모델을 학습하여 이전 단계의 모델의 단점을 보완
- 학습 오차(Training error)가 큰 관측치의 선택 확률(Weight, 가중치)을 높이고, 학습오차가 작은 관측치의 선택 확률을 낮춤. 즉, 오분류한 관측치에 보다 집중
- 앞 단계에서 조정된 확률(Weight, 가중치)를 기반으로 다음 단계에서 사용될 학습 데이터(training dataset)를 구성
- 다시 첫 단계로 돌아감
- 최종 결과물은 각 모델의 성능지표를 가중치로하여 결합(ensemble)
💻 Algorithm
이번엔 Adaboost의 알고리즘을 알아봅시다.
1. set $W_i = \frac1n, i =1,2,..., n$ (impose equal weight initially)
처음엔 모든 가중치를 동일하게 부여합니다.
2. for $j$ = 1 to $m$ ($m$ : number of classifiers[분류기 개수])
Step 1. Find $h_j(x)$ that minimizes $L_j$ (weighted loss function)
아래의 식으로 손실함수 $L_j$를 최소화하는 $h_j(x)$를 찾습니다.
$$L_j = \frac{\sum_{i=1}^nW_iI(y_i \neq h_j(x))}{\sum_{i=1}^nW_i}$$
Step 2. Define the weight of a classifier : $\alpha_j = \log(\frac{1-L_j}{L_j})$
가중치를 위 식과 같이 정의하고
Step 3. Update weight : $W_j \leftarrow W_j e^{\alpha_jI(y_i \neq h_j(x))}, \ i=1,2,...,n$
가중치를 업데이트 해줍니다.
end for
3. Final boosted model : $h(x) = sign[\sum_{i=1}^m \alpha_jh_j(x)]$
최종 모델의 식입니다.
➕ 이해를 위해 도움되는 내용
우선 위 식에서 $h$가 모델 즉 Classifier(분류기)입니다. $L_j$(손실 함수)를 최소화하는 $h$를 찾는 것입니다.
$I$는 indicator function으로 이진 함수입니다.
출력값으로 0 or 1을 내밷는거죠.
즉 알고리즘 2-step1의 $(y_i \neq h_j(x))$이 True면 1, False면 0을 가집니다. 즉 실제값과 모델이 예측한 값이 같다면 1, 다르다면 0을 출력한다는 뜻입니다.
알고리즘 2-step2는 모델의 가중치인 $\alpha_j$를 정의한다는 내용인데 $\alpha_j$와 $L_j$의 관계를 그래프로 나타내면
위 사진과 비슷한 느낌이겠군요. $\alpha_j = \log(\frac{1-L_j}{L_j})$의 식에서 $L_j$가 0.5라면 $\alpha_j$는 $\log1$이 되어서 0이 될 것입니다.
즉! 예측을 반반 성공했다면? 가중치는 0이 되는 거겠군요.
$L_j$가 0에 가깝다면? $\alpha_j$는 $\log$가 무한대로 커지기 때문에 같이 커지게 됩니다. 즉! 예측이 실패할수록 가중치가 커진다는 것입니다.
그 후, 이 $\alpha$값을 다음 가중치 값에 집어 넣는 것입니다.(업데이트)
🧮 예시를 통한 공식 적용(주의!)
주의! 인 이유는 숫자가 많이 나오기 때문입니다 하하..
1️⃣ 첫 단계
n = 10이라고 할 때, 관측치에 대한 시작 가중치는 $w_j = \frac1{10}$(= 0.1)이 됩니다. 만약 모델 $h_1(x)$가 총 10개 중 3개를 오분류 했다면?
위 그림 처럼 동그라미 세개를 네모로 잘못 오분류 했을 경우를 예시로 든겁니다!
알고리즘을 적용해보면
$L_1 = \frac{\sum_{i=1}^nW_iI(y_i \neq h_1(x))}{\sum_{i=1}^nW_i} = \frac{0.1 \times3}{0.1 \times 10} = 0.3$
$\alpha_1 = \log(\frac{1-L_1}{L_1})=\log(\frac{1-0.3}{0.3}) \approx 0.37$
$W_e = W_ie^{\alpha_1I(y_i = h_1(x))} = 0.1e^{0.37\times0} = 0.1$: 정분류 관측치
$W_{ne} = W_ie^{\alpha_1I(y_i \neq h_1(x))} = 0.1e^{0.37\times1} = 0.14$: 오분류 관측치
즉! 정분류 관측치 가중치는 처음 설정한 그대로 0.1이 되지만 오분류한 관측치는 0.14로 증가하게 됩니다! 이로인해 다음 단계의 학습 데이터셋에 선택될 확률이 증가하게 되는 것이죠!
아래 그림과 같이말이죠!
2️⃣ 두 번째 모델
만약 다음 모델일 $h_2(x)$가 아래 그림과 같이 10개 중 3개를 오분류 했다면?
알고리즘에 따라
$L_2 = \frac{\sum_{i=1}^nW_iI(y_i \neq h_2(x))}{\sum_{i=1}^nW_i} = \frac{0.1 \times 3}{0.1 \times 7 +0.14\times3} = 0.27$
$\alpha_2 = \log(\frac{1-L_2}{L_2})=\log(\frac{1-0.27}{0.27}) \approx 0.43$
$W_e = W_ie^{\alpha_2I(y_i = h_2(x))} = {0.1 \ or \ 0.14}e^{0.43\times0} = 0.1 \ or \ 0.14$ : 정분류 관측치
$W_{ne} = W_ie^{\alpha_2I(y_i \neq h_2(x))} = 0.1e^{0.43\times1} = 0.15$ : 오분류 관측치
첫 단계와 마찬가지로 가중치를 업데이트 해줍니다.
3️⃣ 세 번째 모델
세 번째 모델인 $h_3(x)$도 마찬가지로 10개 중 3개를 오분류 한다면...
같은 방식으로 아래 그림처럼 진행될 것이고
식은 이렇게 되겠군요.
$L_3 = \frac{\sum_{i=1}^nW_iI(y_i \neq h_3(x))}{\sum_{i=1}^nW_i} = \frac{0.1 \times 3}{0.1 \times 4 +0.14\times3 + 0.15 \times 3} = 0.24$
$\alpha_3 = \log(\frac{1-L_3}{L_3})=\log(\frac{1-0.24}{0.24}) \approx 0.5$
$W_e = W_ie^{\alpha_3I(y_i = h_3(x))} = {0.1 \ or \ 0.14 \ or \ 0.15}e^{0.5\times0} = 0.1 \ or \ 0.14 \ or \ 0.15$ : 정분류 관측치
$W_{ne} = W_ie^{\alpha_3I(y_i \neq h_3(x))} = 0.1e^{0.5\times1} = 0.16$ : 오분류 관측치
도식화 하면 아래와 같이 모델들을 합친 하나의 앙상블 기법 모델을 만드는 것입니다.
식으로 표현하면
$$h(x) = sign[\sum_{i=1}^{m=3} \alpha_jh_j(x)] \ = sign[0.37h_1(x) + 0.43h_2(x) + 0.5h_3(x)]$$
이렇게요!
이해가 되셨을 까요? 저는 Adaboost보다 XGboost에 관심이 많아서 Adaboost의 경우 간단하게 어떤 기제로 이루어져있는지를 알아보았습니다.
이상 Adaboost 간단하게 알아보기 였습니다! ☠️