集成学习

Boosting

1. learn over a subset of data --> rule
2. combine

bagging

combine(mean)

Boosting

choose "hardest" example

weighted mean

error: $Pr_D[h(x)\neq{C(x)}]$

D: distribution H:hypothesis C:true concept

Weak learning

weak learner: learner that does better than chance always <= 1/2

$\forall_{D}Pr_D[\cdot] \le 1/2-\epsilon$

Boosting in code

• Given training $\{x_i,y_i)\}$, $y_i\in{\{-1,+1\}}$
• For t = 1 to T
• • Construct $D_t$
  • find weak classifier $h_t(x)$ with small error $\epsilon_t=Pr_{D_t}[h_t(x_i)\neq{y_i}]$
  • output $H_{final}$

$D_i(i)=\frac{1}{n}$

$D_{t+1}(i)=\frac{D_t(i)\cdot{e^{-\alpha_ty_ih_t(x_i)}}}{z_t}$

where $\alpha_t=1/2\ln{\frac{1-\epsilon_t}{\epsilon_t}}$, $z_t$ 归一化常数

$H_{final}(x)=sgn(\displaystyle\sum_t\alpha_th_t(x))$

boosting 不怎么会过拟合

pink noise: uniform noise will lead to overfit