The Beautiful Future

Adaboost 본문

알고리즘

Adaboost

Small Octopus 2016. 4. 26. 22:16

1. Exponential Loss
Exponential 함수를 이용하여 Loss를 정의한다.
나중에 Loss를 최소화하는데 Exponential이 미분하기 좋기 때문이다.

함수는 x = -1일때 2.7 ,   x = 0 일때 1,   x = 1 일때 0.37 이며 

x가 커질 수록 작아진다.  예측결과와 GT가 같으면 적은 Loss을 틀리면 큰 Loss을 할당한다.


2. boosted classifier

아래와 같은 수식으로 표현된다.

어떤 샘플하나의 중요도가 처음 이었다면 중요도는 Loss 가 곱해지면서 아래와 같이 쓸 수 있다.

Exp Loss를 다시 쓰면 





  • Samples x_1 \dots x_n
  • Desired outputs y_1 \dots y_n, y \in \{-1, 1\}
  • Initial weights w_{1,1} \dots w_{n,1} set to \frac{1}{n}
  • Error function 
  • Weak learners h\colon x \rightarrow [-1, 1]


For t in 1 \dots T:

    Choose h_t(x):
    • Find weak learner h_t(x) that minimizes \epsilon_t, the weighted sum error for misclassified points \epsilon_t = \sum_i w_{i,t}E(h_t(x), y, i)
    • Choose \alpha_t = \frac{1}{2} \ln \left(\frac{1-\epsilon_t}{\epsilon_t}\right)
    • ln(x)

  • Add to ensemble:
    • F_t(x) = F_{t-1}(x) + \alpha_t h_t(x)
  • Update weights:
    • w_{i,t+1} = w_{i,t} e^{-y_i \alpha_t h_t(x_i)} for all i



    • Renormalize w_{i,t+1} such that \sum_i w_{i,t+1} = 1
    • (Note: It can be shown that \frac{\sum_{h_{t+1}(x_i) = y_i} w_{i,t+1}}{\sum_{h_{t+1}(x_i) \neq y_i} w_{i,t+1}} = \frac{\sum_{h_t(x_i) = y_i} w_{i,t}}{\sum_{h_t(x_i) \neq y_i} w_{i,t}} at every step, which can simplify the calculation of the new weights.)


'알고리즘' 카테고리의 다른 글

Linear Classification2  (0) 2016.05.02
Linear Classification1  (0) 2016.04.28
Levenberg-Marquardt algorithm  (0) 2016.04.18
Expectation Maximization Algorithm  (0) 2015.07.16
Gaussian Mixture Model( GMM )  (0) 2015.07.14
'알고리즘' Related Articles more
Comments