> For the complete documentation index, see [llms.txt](https://windmising.gitbook.io/lihang-tongjixuexifangfa/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://windmising.gitbook.io/lihang-tongjixuexifangfa/adaboost/2.md).

# 训练误差分析

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）：【？】泰勒公式