训练误差分析

adaboost的训练误差为：

$$ERR = \frac{\text{分类错误的样本数}}{\text{总样本数}} = \frac{\sum_{i=1}^NI(G(x_i) \neq y_i)}{N}$$

adaboost算法最终分类器的误差界为：

$$\begin{aligned} ERR = \frac{1}{N}\sum_{i=1}^NI(G(x_i) \neq y_i) &&{1} \le \frac{1}{N}\sum_{i=1}^N\exp(-y_if(x_i)) &&{2} = \prod_mZ_m &&{3} = \prod_{m=1}^M(2\sqrt {e_m(1-e_m)}) &&{4} = \prod_{m=1}^M(2\sqrt {1-4\gamma_m^2}) &&{5} \le \exp(-2\sum_{m=1}^M\gamma_m^2) &&{6} \end{aligned}$$

说明： （1）：ERR的定义 （2）:

$$I(G(x_i) \neq y_i) = I(G(x_i) \neq y_i) + 0$$

当$G(x_i) \neq y_i$时，

$$y_if(x_i)\lt 0 \Rightarrow \exp(-y_if(x_i))\gt 1 = I(G(x_i) \neq y_i)$$

当$G(x_i) = y_i$时，

$$y_if(x_i)\gt 0 \Rightarrow \exp(-y_if(x_i))\gt 1 = I(G(x_i) \neq y_i) \gt 0$$

等式得证 （3）：

$$\begin{aligned} \frac{1}{N}\sum_{i}^N\exp(-y_if(x_i)) \\ = \frac{1}{N}\sum_{i}^N\exp(-\sum_{m}^Ma_my_iG_m(x_i)), \text {公式6} \\ = \sum_i w_{1i}\sum_{i}^N\exp(-\sum_{m}^Ma_my_iG_m(x_i)), \text {公式1} \\ = Z_1\sum_i w_{2i}\sum_{2}^N\exp(-\sum_{m}^Ma_my_iG_m(x_i)), \text {公式8.4} \\ = \prod_{m=1}^MZ_m \end{aligned}$$

（4）：

$$\begin{aligned} Z_m = \sum_{i=1}^Nw_{mi}\exp (-a_my_iG_m(x_i)) \\ = \sum_{y_i=G_m(x_i)}w_{mi}e^{-a_m} + \sum_{y_i\neq G_m(x_i)}w_{mi}e^{a_m}, y_iG_m(x_i)\text{代表对样本i是否分类正确} \\ = (1-e_m)\exp(-a_m) + e_m\exp(a_m), \text{公式3} \\ = (1-e_m)\sqrt{\frac{e_m}{1-e_m}} + (e_m)\sqrt{\frac{1-e_m}{e_m}}, t\text{公式4} \\ = 2\sqrt{(1-e_m)e_m} \end{aligned}$$

（5）：令$\gamma = \frac{1}{2}-e_m$ （6）：【？】泰勒公式