AdaBoost?

AdaBoost란???      
"간단한", "약한"분류기들의 선형 조합으로 부터 "강한"분류기를 설계하기 위한 알고리즘이라고 정의 할 수 있다.


            T
f(x) =  sigma α_th_t(x)           //공식 넣기가 애매하네...일일이 사진 잘라오기가...ㅠ
            t=1

h_t(x) : X → {−1,+1}. h_t(x)는 "약한"분류기 혹은 "feature"라고 정의.
H(x) = sign(f(x))는 "강한"분류기 혹은 최종 분류기라고 정의.  (궁극적으로는 둘 다 같음)

Given: (x_1, y_1), . . . , (x_m, y_m); x_i는 X에 속함, y_i는  {−1, +1}에 속함
Initialise weights D_1(i) = 1/m

위에서 (x_1,y_1)....(x_m,y_m)은 주어진 데이터들의 셋으로써 데이터의 위치와 타겟 벨류와 표현한다. 
그리고 각 데이터의 초기 가중치는 1/m으로 설정한다.

For t = 1,...,T    데이터 셋과 초기설정이 끝나면 1~T까지 반복하게 된다. 이 때 반복하는 작업들을 설명하면 다음과 같다.

1. h_t의 값을 찾는게 가장 처음에 해야 할 작업이다.

여기서 에러율을 나타내는 엡실론(e)값이 가장 작게 되는 h_j라는 직선을 찾는다.
h_j직선은 H라는 모든 직선이 들어있는 큰 가설공간에서 뽑은 하나의 직선을 나타낸다.
뒤쪽에 시그마 D_t....부분은 잘못인식된 에러들에대해서 D_t라는 가중치를 곱해서 전체 에러 값을 계산하게 된다.

만약 에러 값이 0.5보다 크면 터무니 없는 에러 값이라 판단하고 작업을 중지한다.

2. 에러 값이 0.5보다 작으면 계속해서 작업을 수행하는데

이때, a_t라는 가중치를 위에 있는 공식에 의해서 셋팅하게 된다. 이 식은 Z_t를 최소화하기 위해서 설정된 공식으로

식을 유도해나가면 알 수 있다. 여기서는 간략하게만 말하고 넘어가도록 한다.

Upper bound theorem에서 만약 데이터가 잘못 분류된 경우라면 y_if(x_i) <= 0 이다.

즉 exp(-y_if(x_i) > 1는 것을 함축하고 있으므로 이 식을 이용할 수 있다.

정리하면 m개중 잘못된 에러를 측정한 결과가 Z_t라는 값의 1~t까지의 곱보다 작아야 한다.

따라서 Z_t라는 값이 작아지면 당연히 에러는 그 값보다 작아야하므로 작아지게 된다. 결국 전체적인 에러를 최소하하려면

Z_t라는 값을 최소화하면 된다는 것이다.

짧게 말하려고 했는데 너무 길어진 것같다. 어쨋든 이러한 Z_t값을 최소화하기 위해서는 a_t라는 가중치를 잘 선택해야되는데

가장 이상적인 식이 위에 나온 a_t의 식이라고 보면된다.

3.  a_t 가중치 값을 셋팅하고나면 D_t+1의 값을 업데이트하게된다. (모든 데이터 셋에 대하여)
   즉, 잘못(wrong) 매치된 부분에 대하여 가중치를 더 높게주고 잘(correct) 매치된 데이터들은 가중치를 낮게 해준다.
    (D_t(i)의 합이 1이되야 하므로)
 
4. 다시 1번부터 반복하면 된다. 

5. 사용자가 지정한 t번 만큼 반복하고 끝나던가 에러가 0.5보다 커져서 끝나던가 둘 중 하나인데,
  어쨋든 작업이 완료되면 각각의 반복에서 계산했던 weak classifier 값을 선형결합하여
  우리가 원하는 strong classifier값을 얻게된다. 
 

Pros and Cons of AdaBoost

Advantages
 - 구현이 매우 간단
 - 일반적인 학습 스키마 (다양한 학습 업무에 사용 가능)
 - feature들의 매우 큰 셋에 대해서 feature의 선택
 - good generalisation
 
Disadvantages
 - Suboptimal solution(greedy learning) 완벽한 최적화는 아니다