提升方法

AdaBoost 算法

Data Information： 二分类训练数据集 $T$

$$\begin{align} T& = \{(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)\} \\ x_i \in \mathcal{X}& = \mathbb{R}^n, \quad y_i \in \mathcal{Y} = \{+1, -1\}, \quad i = 1, 2, \ldots, N \end{align}$$

Algorithm Process

1. 初始化训练数据的权值分布：

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

2. 用权值分布 $D_i$
   (a) 计算不正确率：

   $$e_m = \sum_{i=1}^{N} P(G_m(x_i) \neq y_i) = \sum_{i=1}^{N} w_{mi} I(G_m(x_i) \neq y_i)$$

   (b) 计算 $\alpha_m$:

   $$\alpha_m = \frac{1}{2} \ln \frac{1 - e_m}{e_m}$$

   (c) 更新权值分布:

   $$D_{m+1} = (w_{m+1,1}, \dots, w_{m+1, N})$$ $$w_{m+1,i} = \frac{w_{mi}}{Z_m} \exp(-\alpha_m y_i G_m(x_i))$$

   $Z_m$ 是归一化因子。

   $$Z_m = \sum_{i=1}^{N} w_{mi} \exp(-\alpha_m y_i G_m(x_i))$$
3. 构造基本分类器的线性组合 $$f(x) = \sum_{m=1}^{M} \alpha_m G_m(x)$$
4. 得到最终分类器 $$G(x) = \operatorname{sign}\left( \sum_{m=1}^{M} \alpha_m G_m(x) \right)$$

提升树算法

Algorithm Process
输入：训练数据集 $T = \{(x_1, y_1),(x_2, y_2), \cdots, (x_N, y_N)\}$；
输出：提升树 $f_M(x)$。
（1）初始化 $f_0(x) = 0$。
（2）对 $m = 1, 2, \cdots, M$。