提升方法 AdaBoost

机器学习

AdaBoost

Input: Training set $T = \{ (x_1, y_1), (x_2, y_2), \dots, (x_N, y_N) \}$, $x_i \in \mathcal X \subseteq \mathrm R^n$; A weak learning algorithm.

Output: Classifier $G(x)$.

1. Initialize weight distribution

   $$D_1 = (w_{11}, \dots, w_{1N}), w_{1i} = \frac{1}{N}, i = 1, 2, \dots, N$$

2. For $m = 1, 2, \dots, M$:

   1. Train classfier $G_m(x): \mathcal X \to \{ -1, +1 \}$ with weight distribution $D_m$;
   2. Define error rate:
      $$e_m = \sum_{i=1}^N w_{mi} I(G_m(x_i) \not= y_i)$$
   3. Define $G_m(x)$ factor $\alpha$ as:
      $$a_m = \frac{1}{2} \log{\frac{1-e_m}{e_m}}$$
   4. Update weight distribution of training set $D_{m+1} = (w_{m+1,1}, w_{m+1,2}, \dots, w_{m+1,N})$:
      $$w_{m+1,i} = \frac{w_{mi}}{Z_m} \exp{(-\alpha_m y_i G_m(x_i))}$$
      where $Z_m = \sum_{i=1}^N w_{mi} \exp{(-\alpha_m y_i G_m(x_i))}$.
3. Construct linear combination of basic classifiers:
   $$G(x) = \mathrm{sign}(f(x)) = \mathrm{sign} \left( \sum_{m=1}^{M} \alpha_m G_m(x) \right)$$

Forward Stagewise Additive Modeling

AdaBoost is a special case of Forward Stagewise Additive Modeling, with basic classifier as addictive model and exponential function as loss function.

Input: Training set $T = \{ (x_1, y_1), (x_2, y_2), \dots, (x_N, y_N) \}$, $x_i \in \mathcal X \subseteq \mathrm R^n$; Loss function $L(y, f(x))$; Base function set $\{ b(x; \gamma) \}$.

Output: Additive model $f(x)$.

1. Initialize $f_0(x) = 0$;
2. For $m = 1, 2, \dots, M$:
   
   1. Minimize loss function
      $$(\beta_m, \gamma_m) = \mathrm{argmax}_{\beta, \gamma} \sum_{i=1}^N L(y_i, f_{m-1}(x_i) + \beta b(x_i; \gamma))$$
   2. Update $f_m(x) = f_{m-1}(x) + \beta_mb(x; \gamma_m)$;
3. Obtain addictive model:
   $$f(x) = f_M(x) = \sum_{m=1}^M \beta_M b(x; \gamma_m)$$

Boosting Tree

Boosting Tree is one kind of boosting with regression tree or classification tree as basic classifier. Boosting tree model can be presented as additive model of decision tree

Input: Training set $T = \{ (x_1, y_1), (x_2, y_2), \dots, (x_N, y_N) \}$, $x_i \in \mathcal X \subseteq \mathbf R^n$; $y_i \in \mathcal Y \subseteq \mathbf R$.

Output: Boosting tree $f_M(x)$.

1. Initialize $f_0(x) = 0$;
2. For $m = 1, 2, \dots, M$:
   
   1. Calculate residue
      $$r_{mi} = y_i - f_{m-1}(x_i), i = 1, 2, \dots, N$$
   2. Learn a regression tree fitting residue $r_m$, obtain $T(x; \Theta_m)$;
   3. Update $f_m(x) = f_{m-1}(x) + T(x; \Theta_m);$
3. Obtain regression boosting tree:
   $$f_M(x) = \sum_{m=1}^M T(x; \Theta_m)$$