Reference

• 1
• 2
• 3
  
  

1. Boosting

• boosting은 weak learners를 조합하여 strong learners로 만들어 나가는 알고리즘이다.
  • weak learners : 상대적으로 성능이 떨어지는 learners
  • strong learners : 상대적으로 좋은 성능을 발휘하는 learners

2. AdaBoost

Binary Classifier

• Input : \((x_1, y_1),\ \cdots\ ,(x_N, y_N)\)
  • \(y_i \in \{-1, +1\}\)
    
  • \(N\) : sample 수
    
    
• 모든 데이터의 가중치 초기화
  • \(i\)번째 데이터의 가중치 \(w_i^{(1)}\) 초기화
  • \(w_i^{(1)} = \begin{cases} \frac{1}{M}, & \mbox{if }\ y_i=+1\mbox{(positive)} \\ \frac{1}{L}, & \mbox{if }\ y_i=-1\mbox{(negative)} \end{cases}\)
    
  • \(M\) : positive sample의 수
  • \(L\) : negative sample의 수
    
    
• 학습(모델 생성) \(\cdots(1)\)
  • \(t\)번째 모델 \(\hat{f_t}(x)\)
    
    
• 모델의 오류 계산 \(\cdots(2)\)
  • \(t\)번째 모델의 오류 \(\boldsymbol{\varepsilon}_t\) 계산
  • \(\boldsymbol{\varepsilon}_t = \cfrac{\sum\limits_{\underset{\hat{f_t}(x_k)\ne y_k}{k=1}}^{N} w_k} {\sum\limits_{k=1}^{N} w_k} = \cfrac{\text{오류인 데이터의 가중치 합}}{\text{전체 학습 데이터의 가중치 합}}\)
    
    
    
• 모델의 가중치 계산 \(\cdots(3)\)
  • \(t\)번째 모델의 가중치 \(\alpha_t\) 계산
  • \(\alpha_t = \cfrac{1}{2} \ln \cfrac{1-\boldsymbol{\varepsilon}_t}{\boldsymbol{\varepsilon}_t}\)
    
    
    
• 데이터의 가중치 계산 및 업데이트 \(\cdots(4)\)
  • \(i\)번째 데이터의 가중치 \(w_i^{(t)}\) 업데이트
  • \(w_i^{(t+1)} \leftarrow \begin{cases} \cfrac{w_i^{(t)} e^{-\alpha_t}}{W}, & \mbox{if }\ \hat{f_t}(x_k)=y_k\ (\text{예측이 맞은 경우}) \\ \cfrac{w_i^{(t)} e^{\alpha_t}}{W}, & \mbox{if }\ \hat{f_t}(x_k)\ne y_k\ (\text{예측이 틀린 경우}) \end{cases}\)
    
  • \(W = \sum\limits_{k=1}^{N} w_k^{(t)}\)
    
    
    

• \((1)-(4)\) 과정 \(T\)번 반복
  
  

• Output : \(G(x) = \begin{cases} 1, & \mbox{if }\ \sum\limits_{t=1}^{T} \alpha_t \hat{f_t}(x) \ge \sum\limits_{t=1}^{T} \alpha_t\\ 0, & \mbox{if }\ otherwise \end{cases}\)
  
  

3. Gradient Boosting (GBM)

4. XGBoost

5. LightGBM