A Step by Step Adaboost Example
적응형 부스팅(adaptive boosting) 또는 짧게 부스팅(boosting)은 부스팅 알고리즘을 수상했다. 이론은 기본적이다. 약한 작업자(weak worker)는 무거운 바위를 옮기지 못하지만 약한 작업자들이 모여서 무거운 바위를 옮기고 피라미드를 만든다. 알고리즘이 약한 학습기(learner)를 실행하는 것을 기대한다. 이 약한 학습기는 단일 레이어 퍼셉트론(single layer perceptron)일 수도 있다. 약한 학습기는 비선형 문제(non-linear problem)을 해결하지 못하지만 이것의 연속적인 사용은 비선형 문제 해결을 가능하게 한다. 트릭(trick)은 시퀀스(sequence)사이에서 틀린 결정에 대한 가중치를 증가시키고 올바른 결정에 대한 가중치는 감소시키는 것이다. Adaboost는 결정트리(decision tree)와는 관계가 없다. 1-레벨 기본 결정트리(decision stump)를 사용할 수 있지만 반드시 그래야 하는 것은 아니다.
tug of war
Adaboost in Python
이 글에서는 adaboost 알고리즘을 깁게 알아보고 단계적으로 문제를 해결해 본다. Adaboost 알고리즘 파이썬 구현은 여기에서 찾을 수 있다.
Data set
아래의 데이터셋을 사용한다. 각 인스턴스는 2차원 공간으로 표현되고 분류(class) 또한 갖는다.
| x1 | x2 | Decision |
|---|---|---|
| 2 | 3 | true |
| 2.1 | 2 | true |
| 4.5 | 6 | true |
| 4 | 3.5 | false |
| 3.5 | 1 | false |
| 5 | 7 | true |
| 5 | 3 | false |
| 6 | 5.5 | true |
| 8 | 6 | false |
| 8 | 2 | false |
여기서 true는 +1, false는 -1이다.
Plotting the data set
명확하게 이해하기 위해 특성(feature)과 분류(class)값을 그려본다.
import pandas as pd
import matplotlib.pyplot as plt
import numpy as np
df = pd.read_csv("dataset/adaboost.txt")
positives = df[df['Decision'] >= 0]
negatives = df[df['Decision'] < 0]
plt.scatter(positives['x1'], positives['x2'], marker='+', s=500*abs(positives['Decision']), c='blue')
plt.scatter(negatives['x1'], negatives['x2'], marker='_', s=500*abs(negatives['Decision']), c='red')
plt.show()
위 소스코드는 아래 그래프를 그린다. 보이는 것과 같이 true 분류는 더하기(+) 문자로 표시되는 반면, false 분류는 빼기(-) 문자로 표시된다.
Adaboost를 위한 데이터셋
true와 false 분류를 분할해 보자. 이것은 선형 분할 문제가 아니다. 퍼셉트론(perceptron) 또는 결정 스텀프(decision stump, 1레벨 기본 결정트리)같은 선형 분류기(linear classifier)는 이 문제를 분류하지 못한다. 여기서 adaboost는 선형분류기가 이 문제를 해결할 수 있게 한다.
Decision stumps
결정트리는 분할하여 정복(divide and conquer)하는 방법으로 문제에 접근한다. 결정트리는 많은 내포된 결정 규칙을 갖을 것이다. 이것이 결정트리를 비선형 분류기로 만든다. 반대로 결정 스텀프(dicision stump)는 1레벨 결정 트리로 (단일층) 퍼셉트론 같은 선형분류기이다. 여러분은 누군가의 키가 1.7미터(5.57피트)보다 크면 남성일 것이고 그렇지 않으면 여성일 것이다라고 생각할 수 있다. 이 결정 스텀프는 적어도 50%의 정확도로 올바르게 성별을 분류한다. 그렇기 때문에 이러한 분류기는 약한 학습기(weak learner)이다.
성별에 대한 결정 스텀프
Decision stump building
결정 스텀프를 다루기 위해 여기에서 결정트리 소스를 수정했다. 기본적으로 'buildDecisionTree' 함수는 결정에 도달할때까지 재귀호출된다. 만약 adaboost가 가능하다면 이 재귀호출을 종료한다.
Regression for adaboost
Adaboost의 주요 이론(principle)은 분류되지 않은 것에 대해 가중치를 증가시키고 분류된 것에 대한 가중치 값을 감소시키는 것이다. 하지만 우리는 분류 문제에서 작업중이다. 데이터셋에서 목표값(target value)이 범주형 값이다. 그렇기 때문에 문제를 회귀 작업(regression task)로 변환한다. 여기서는 true 분류는 1, false 분류는 -1로 한다.
처음에 균등 분포(uniform distribution)으로 가중치(weight)를 배포한다. 여기서는 모든 인스턴스에 대해 가중치를 $1/n$으로 설정한다. 여기서 $n$은 인스턴스의 총 개수이다.
| x1 | x2 | actual | weight | weighted_actual |
|---|---|---|---|---|
| 2 | 3 | 1 | 0.1 | 0.1 |
| 2 | 2 | 1 | 0.1 | 0.1 |
| 4 | 6 | 1 | 0.1 | 0.1 |
| 4 | 3 | -1 | 0.1 | -0.1 |
| 4 | 1 | -1 | 0.1 | -0.1 |
| 5 | 7 | 1 | 0.1 | 0.1 |
| 5 | 3 | -1 | 0.1 | -0.1 |
| 6 | 5 | 1 | 0.1 | 0.1 |
| 8 | 6 | -1 | 0.1 | -0.1 |
| 8 | 2 | -1 | 0.1 | -0.1 |
가중치가 적용된 실제 점수(weighted actual score)는 각 라인에서 $\text{가중치(weight)} \times \text{실제값(actual value)}$을 저장한다. 이제 목표값으로 가중치가 적용된 실제값을 사용하는 반면 'x1'과 'x2'는 결정 스텀프를 구축하기 위한 특성이다. 아래 규칙은 결정 스텀프 알고리즘을 수행할 때 만들어진다.
def findDecision(x1, x2):
if x1>2.1:
return -0.025
if x1<=2.1:
return 0.1
$\pm1$값으로 실제값이 설정된 반면 결정 스텀프는 소수값을 반환한다. 여기서 트릭은 이 문제를 해결하기 위해 'sign'함수를 적용하는 것이다.
def sign(x):
if x > 0: return 1
elif x < 0: return -1
else: return 0
요약하면 예측은 'x1'이 2.1보다 크면 $sign(-0.025) = -1$이 되고 'x1'이 2.1보다 작거나 같으면 $sign(0.1) = +1$이 된다.
예측(prediction) 컬럼을 추가한다. 또한 손실(loss) 컴럼에서 실제와 예측이 얼마나 같은지를 점검한다. 예측이 올바르면 0, 잘못된 예측이면 1이 된다.
| x1 | x2 | actual | weight | weighted_actual | prediction | loss | $weight \times loss$ |
|---|---|---|---|---|---|---|---|
| 2 | 3 | 1 | 0.1 | 0.1 | 1 | 0 | 0 |
| 2 | 2 | 1 | 0.1 | 0.1 | 1 | 0 | 0 |
| 4 | 6 | 1 | 0.1 | 0.1 | -1 | 1 | 0.1 |
| 4 | 3 | -1 | 0.1 | -0.1 | -1 | 0 | 0 |
| 4 | 1 | -1 | 0.1 | -0.1 | -1 | 0 | 0 |
| 5 | 7 | 1 | 0.1 | 0.1 | -1 | 1 | 0.1 |
| 5 | 3 | -1 | 0.1 | -0.1 | -1 | 0 | 0 |
| 6 | 5 | 1 | 0.1 | 0.1 | -1 | 1 | 0.1 |
| 8 | 6 | -1 | 0.1 | -0.1 | -1 | 0 | 0 |
| 8 | 2 | -1 | 0.1 | -0.1 | -1 | 0 | 0 |
$weight \times loss$ 컬럼의 합은 전체 오류(error)로 이 경우엔 0.3이다. 여기서 새로운 변수 알파($\alpha$)를 정의한다.
$\alpha = \ln((1 - \epsilon) \div \epsilon) \div 2 = \ln((1 - 0.3) \div 0.3) \div 2 = 0.42$
알파를 다음번에 가중치를 갱신하기 위해 사용한다.
$w_{i+1} = w_i \times e^{-\alpha \times actual \times prediction}$
- i : 인스턴스 넘버
또한 가중치의 합은 반드시 1이어야 한다. 그렇기 때문에 가중치를 정규화(normalize)해야 한다. 각각의 가중치 값을 가중치 컬럼의 합으로 나누어 정규화 할 수 있다.
| x1 | x2 | actual | weight | prediction | $w_{i+1}$ | $norm(w_{i+1})$ |
|---|---|---|---|---|---|---|
| 2 | 3 | 1 | 0.1 | 1 | 0.065 | 0.071 |
| 2 | 2 | 1 | 0.1 | 1 | 0.065 | 0.071 |
| 4 | 6 | 1 | 0.1 | -1 | 0.153 | 0.167 |
| 4 | 3 | -1 | 0.1 | -1 | 0.065 | 0.071 |
| 4 | 1 | -1 | 0.1 | -1 | 0.065 | 0.071 |
| 5 | 7 | 1 | 0.1 | -1 | 0.153 | 0.167 |
| 5 | 3 | -1 | 0.1 | -1 | 0.065 | 0.071 |
| 6 | 5 | 1 | 0.1 | -1 | 0.153 | 0.167 |
| 8 | 6 | -1 | 0.1 | -1 | 0.065 | 0.071 |
| 8 | 2 | -1 | 0.1 | -1 | 0.065 | 0.071 |
이번 라운드는 끝이다.
Round 2
이번에는 정규화된 $w_{i+1}$ 컬럼($norm(w_{i+1})$)을 가중치 컬럼으로 옮겼다. 그리고 결정 스텀프를 만든다. 여전히, 'x1'과 'x2'는 특성이지만, 가중치가 적용된 실제값은 목표값이다.
| x1 | x2 | actual | weight | weighted_actual |
|---|---|---|---|---|
| 2 | 3 | 1 | 0.071 | 0.071 |
| 2 | 2 | 1 | 0.071 | 0.071 |
| 4 | 6 | 1 | 0.167 | 0.167 |
| 4 | 3 | -1 | 0.071 | -0.071 |
| 4 | 1 | -1 | 0.071 | -0.071 |
| 5 | 7 | 1 | 0.167 | 0.167 |
| 5 | 3 | -1 | 0.071 | -0.071 |
| 6 | 5 | 1 | 0.167 | 0.167 |
| 8 | 6 | -1 | 0.071 | -0.071 |
| 8 | 2 | -1 | 0.071 | -0.071 |
이 새로운 데이터셋의 그래프는 아래와 같다. 올바르게 분류된 것의 가중치는 감소되었고 잘못 분류된 것은 증가하였다.
튜닝된 가중치를 가진 데이터셋
아래 결정 스텀프는 이 데이터셋으로 만들어진다.
def findDecision(x1, x2):
if x2<=3.5:
return -0.02380952380952381
if x2>3.5:
return 0.10714285714285714
예측에 $sign$함수를 적용하고 손실(loss)과 $가중치(weight) \times 손실(loss)$ 컬럼을 추가한다.
| x1 | x2 | actual | weight | prediction | loss | $weight \times loss$ |
|---|---|---|---|---|---|---|
| 2 | 3 | 1 | 0.071 | -1 | 1 | 0.071 |
| 2 | 2 | 1 | 0.071 | -1 | 1 | 0.071 |
| 4 | 6 | 1 | 0.167 | 1 | 0 | 0.000 |
| 4 | 3 | -1 | 0.071 | -1 | 0 | 0.000 |
| 4 | 1 | -1 | 0.071 | -1 | 0 | 0.000 |
| 5 | 7 | 1 | 0.167 | 1 | 0 | 0.000 |
| 5 | 3 | -1 | 0.071 | -1 | 0 | 0.000 |
| 6 | 5 | 1 | 0.167 | 1 | 0 | 0.000 |
| 8 | 6 | -1 | 0.071 | 1 | 1 | 0.071 |
| 8 | 2 | -1 | 0.071 | -1 | 0 | 0.000 |
이번 반복에 대한 오류(error)와 알파($\alpha$)를 계산할 수 있다.
- $\epsilon = 0.21$
- $\alpha = 0.65$
따라서 다음 라운드를 위한 가중치를 알 수 있다.
| x1 | x2 | actual | weight | prediction | $w_{i+1}$ | $norm(w_{i+1})$ |
|---|---|---|---|---|---|---|
| 2 | 3 | 1 | 0.071 | -1 | 0.137 | 0.167 |
| 2 | 2 | 1 | 0.071 | -1 | 0.137 | 0.167 |
| 4 | 6 | 1 | 0.167 | 1 | 0.087 | 0.106 |
| 4 | 3 | -1 | 0.071 | -1 | 0.037 | 0.045 |
| 4 | 1 | -1 | 0.071 | -1 | 0.037 | 0.045 |
| 5 | 7 | 1 | 0.167 | 1 | 0.087 | 0.106 |
| 5 | 3 | -1 | 0.071 | -1 | 0.037 | 0.045 |
| 6 | 5 | 1 | 0.167 | 1 | 0.087 | 0.106 |
| 8 | 6 | -1 | 0.071 | 1 | 0.137 | 0.167 |
| 8 | 2 | -1 | 0.071 | -1 | 0.037 | 0.045 |
Round 3
이번 라운드는 아래와 같다.
| x1 | x2 | actual | weight | prediction | loss | $w \times loss$ | $w_{i+1}$ | $norm(w_{i+1})$ |
|---|---|---|---|---|---|---|---|---|
| 2 | 3 | 1 | 0.167 | 1 | 0 | 0.000 | 0.114 | 0.122 |
| 2 | 2 | 1 | 0.167 | 1 | 0 | 0.000 | 0.114 | 0.122 |
| 4 | 6 | 1 | 0.106 | -1 | 1 | 0.106 | 0.155 | 0.167 |
| 4 | 3 | -1 | 0.045 | -1 | 0 | 0.000 | 0.031 | 0.033 |
| 4 | 1 | -1 | 0.045 | -1 | 0 | 0.000 | 0.031 | 0.033 |
| 5 | 7 | 1 | 0.106 | -1 | 1 | 0.106 | 0.155 | 0.167 |
| 5 | 3 | -1 | 0.045 | -1 | 0 | 0.000 | 0.031 | 0.033 |
| 6 | 5 | 1 | 0.106 | -1 | 1 | 0.106 | 0.155 | 0.167 |
| 8 | 6 | -1 | 0.167 | -1 | 0 | 0.000 | 0.114 | 0.122 |
| 8 | 2 | -1 | 0.045 | -1 | 0 | 0.000 | 0.031 | 0.033 |
- $\epsilon = 0.31$
- $\alpha = 0.38$
Weights in round 3
def findDecision(x1, x2):
if x1>2.1:
return -0.003787878787878794
if x1<=2.1:
return 0.16666666666666666
Round 4
| x1 | x2 | actual | weight | prediction | loss | $w \times loss$ | $w_{i+1}$ | $norm(w_{i+1})$ |
|---|---|---|---|---|---|---|---|---|
| 2 | 3 | 1 | 0.122 | 1 | 0 | 0.000 | 0.041 | 0.068 |
| 2 | 2 | 1 | 0.122 | 1 | 0 | 0.000 | 0.041 | 0.068 |
| 4 | 6 | 1 | 0.167 | 1 | 0 | 0.000 | 0.056 | 0.093 |
| 4 | 3 | -1 | 0.033 | 1 | 1 | 0.033 | 0.100 | 0.167 |
| 4 | 1 | -1 | 0.033 | 1 | 1 | 0.033 | 0.100 | 0.167 |
| 5 | 7 | 1 | 0.167 | 1 | 0 | 0.000 | 0.056 | 0.093 |
| 5 | 3 | -1 | 0.033 | 1 | 1 | 0.033 | 0.100 | 0.167 |
| 6 | 5 | 1 | 0.167 | 1 | 0 | 0.000 | 0.056 | 0.093 |
| 8 | 6 | -1 | 0.122 | -1 | 0 | 0.000 | 0.041 | 0.068 |
| 8 | 2 | -1 | 0.033 | -1 | 0 | 0.000 | 0.011 | 0.019 |
- $\epsilon = 0.10$
- $\alpha = 1.10$
def findDecision(x1,x2):
if x1<=6.0:
return 0.08055555555555555
if x1>6.0:
return -0.07777777777777778
Prediction
각 라운드의 $\alpha \times prediction$의 누적되는 합은 최종 예측이 된다.
| round1 $\alpha$ | round2 $\alpha$ | round3 $\alpha$ | round4 $\alpha$ |
|---|---|---|---|
| 0.42 | 0.65 | 0.38 | 1.1 |
| prediction | prediction | prediction | prediction |
|---|---|---|---|
| 1 | -1 | 1 | 1 |
| 1 | -1 | 1 | 1 |
| -1 | 1 | -1 | 1 |
| -1 | -1 | -1 | 1 |
| -1 | -1 | -1 | 1 |
| -1 | 1 | -1 | 1 |
| -1 | -1 | -1 | 1 |
| -1 | 1 | -1 | 1 |
| -1 | 1 | -1 | -1 |
| -1 | -1 | -1 | -1 |
예를 들어, 첫번째 인스턴스의 예측은
$0.42 \times 1 + 0.65 \times (-1) + 0.38 \times 1 + 1.1 \times 1 = 1.25$
여기에 $sign$함수를 적용하면
$sign(1.25) = +1$ 즉 true, 올바르게 분류된 것이다. (여기서 $sign$ 함수는 이 글 위에서 정의한 함수이다.)
아래 그림처럼 adaboost 계산을 정리할 수 있다. 4가지 다른(약한) 분류기와 알파 곱셈기(multiplier)가 있다. 파란색 부분의 인스턴스는 true로 분류되지만 붉은색 부분은 false로 분류된다.
모든 인스턴스에 대해 이 계산을 적용하면 모든 인스턴스가 올바르게 분류된다. 이런 방법으로 훈련셋에 나타나지 않은 새로운 인스턴스에 대한 결정을 알 수 있다.
최종 결정
가지치기(Pruning)
아마도 round 1과 round 3의 결과가 같다는 것을 눈치챘을 것이다. Adaboost에서 가지치기는 성능항상을 위해 유사한 약한 분류기를 제거하는 것이 목적이다. 게다가 남은 하나의 알파($\alpha$)값 곱셈기를 증가시켜야 한다. 이런 경우, Round 3을 제거하고 이것의 계수(coefficient)를 round 1에 추가한다.
비록 선형의 약한 분류기를 사용했지만, 모든 인스턴스가 올바르게 분류된다.
실생활에서의 Adaboost
얼굴 인식(face recognition)은 딥러닝에서 뜨거운 주제이다. Face detection과 face alignment는 얼굴 인식 파이프라인의 필수적인 초기 단계이다. 가장 얼굴인식의 일반적인 방법은 haar cascade로 주로 adaboost 알고리즘에 기초한다.
Haar cascade schema map
다음 비디오에서 haar cascade 알고리즘의 성능을 볼 수 있다. 비록 현재적인 알고리즘이 존재하고 있다고 해도 haar cascade는 여전히 유망한 한가지이다.
고대 이집트의 adaboost