≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记(十四)

开春,复课。

一句无关的话...今天打开Google Reader看到7月份要关的提示,无限悲伤。看着落园若干RSS源里面累计800+的读者,只能说句bless...2008年开始使用,到现在,伴我度过了多少读书时光呀。不过确实也衰落了,高峰的时候一个RSS源就有600+读者,现在也只剩一半了。写博客,越来越像一件出力不讨好的事情了。

--------正文开始---------

提升与梯度树

1. Boost(AdaBoost)

这里讲的AdaBoost是仅针对二类分类器的提升。大致的思想就是,给我一个弱分类器,还你一个强分类器。听起来蛮神奇的对不对?

先说算法实现。

第一步:初始化。f_{0}(x)=0,权重初始值 w_{i}=\frac{1}{N},\,\forall i\in\{1,...,n\}

第二步:迭代。

for m = 1 to M

  • 根据已有算法(即弱分类器)和{w_{i}}得到一个分类器G_{m}(x).
  • 计算误差:err_{m}=\frac{\sum_{1}^{N}I(y_{i}\neq G_{m}(x_{i}))\cdot w_{i}}{\sum_{i=1}^{N}w_{i}},这里我们把权重进行归一化。
  • 计算G_{m}权重:\alpha_{m}=\log\frac{1-err_{m}}{err_{m}}
  • 修改样本权重w_{i}w_{i}=w_{i}\cdot\exp(\alpha_{m}\cdot I(y_{i}\neq G_{m}(x_{i}))

也就是说,我们不断的生成新的权重,当分类器分错的时候更改权重。

第三步:输出。最终的分类器为前面的加权。

G(x)=sign(\sum_{m=1}^{M}\alpha_{m}G_{m}(x))

这样就实现了从一个弱分类器改善到一个强分类器。这里弱分类器是指误差比随机猜的1/2少一点。

另注:在修改权重那一步的时候,也可以定义\beta_{m}=\frac{\alpha_{m}}{2},然后w_{i}=w_{i}\cdot\begin{cases} e^{\beta_{m}} & if\, right\\e^{-\beta_{m}} & if\, wrong \end{cases},这样在最后的时候也可以改成G(x)=sign(\sum_{m=1}^{M}\beta_{m}G_{m}(x))。总之这里的直觉是,如果分对了,那么权重下降;反之,分错的时候这些样本的权重上升。最后take average就可以了。

2. 自适应基函数模型、前向分布算法

之所以上面又引入\beta_{m},便是为了更好地理解这一类模型:自适应基函数模型。

1. 我们称 f(x)=\sum_{m=1}^{M}\beta_{m}b(x,\gamma_{m})为基函数模型,其中\{b(x,\gamma),\gamma\in\Gamma\}成为基函数基。注意这里和GLM有很大的不同,广义线性模型后面的\gamma_{m}为确定的。

2. 前向分步算法。

数据集记作\{(x_{i},y_{i}),1\leq i\leq N\}。定义一个损失函数,比如常见的\mathcal{L}_{2}均方误差,

(y-f(x))^{2},或者0-1准则。

然后步骤为:

  • 初始化:f_{0}(x)=0
  • 迭代:For m=1 to M,(\beta_{m},\gamma_{m})=\arg\min\sum_{i=1}^{N}L(y_{i},f_{m-1}(x_{i})+\beta b(x_{i},\gamma))
  • f_{m}(x)=f_{m-1}(x)+\beta_{m}b(x_{i},\gamma)
  • 输出f_{m}(x)

这样我们就把这个最优化问题转变成了M步,每步只做一个参数的最优化(近似方法)。

3. 指数损失函数与AdaBoost

有了这么一个一般性的框架,我们就可以套用具体的形式。

1. 定义指数损失函数: L(y,f(x))=\exp(-yf(x))

2. 两类分类、指数损失函数的自适应基函数模型。

前向分布算法:

(i)

\begin{eqnarray*} & & \sum_{i=1}^{N}L(y_{i},f_{m-1}(x_{i})+\beta b(x_{i},\gamma))\\ & = & \sum_{i=1}^{N}\exp\left[-y_{i}(f_{m-1}(x_{i})+\beta b(x_{i},\gamma))\right]\\ & = & \sum_{i=1}^{N}w_{i}^{(m)}\cdot\exp(-\beta y_{i}b(x_{i},\gamma)),\, w_{i}^{(m)}=\exp(-y_{i}f_{m-1}(x_{i}))\\ & = & e^{\beta}(\sum_{y\neq b(x_{i},\gamma)}w_{i}^{(m)})+e^{-\beta}(\sum_{y=b(x_{i},\gamma)}w_{i}^{(m)})\\ & = & \sum_{i=1}^{N}w_{i}^{(m)}\left[e^{\beta}\frac{\sum_{y\neq b(x_{i},\gamma)}w_{i}^{(m)}}{\sum_{i=1}^{N}w_{i}^{(m)}}+e^{-\beta}\frac{\sum_{y=b(x_{i},\gamma)}w_{i}^{(m)}}{\sum_{i=1}^{N}w_{i}^{(m)}}\right]\end{eqnarray*}

定义

err_{m}^{(\gamma)}=\frac{\sum_{y\neq b(x_{i},\gamma)}w_{i}^{(m)}}{\sum_{i=1}^{N}w_{i}^{(m)}}

这样上式就可以化作

\begin{eqnarray*} & = & \sum_{i=1}^{N}w_{i}^{(m)}\left[e^{\beta}err_{m}^{(\gamma)}+e^{-\beta}(1-err_{m}^{(\gamma)})\right]\\ & = & \sum_{i=1}^{N}w_{i}^{(m)}\left[(e^{\beta}-e^{-\beta})err_{m}^{(\gamma)})+e^{-\beta}\right]\end{eqnarray*}

(ii) 固定\beta>0,优化\gamma.

\sum_{y\neq b(x_{i},\gamma)}w_{i}^{(m)}=\sum_{i=1}^{N}w_{i}^{(m)}I(y\neq b(x_{i},\gamma))

然后最小化,则\gamma=\arg\min\sum_{i=1}^{N}w_{i}^{(m)}I(y\neq b(x_{i},\gamma))。假定\gamma已被优化,然后继续。

(iii)优化\beta\beta_{m}=\arg\min\sum_{i=1}^{N}w_{i}^{(m)}\left[(e^{\beta}-e^{-\beta})err_{m}^{(\gamma)})+e^{-\beta}\right]

取一阶条件FOC,则有

(e^{\beta}-e^{-\beta})err_{m}^{(\gamma)})-e^{-\beta}=0

这样最后

\beta=\left[\log\frac{1-err_{m}}{err_{m}}\right]/2

这样就看出来上面那个AdaBoost里面的\beta是怎么来的了吧?

(iv) 回到AdaBoost

\begin{eqnarray*}f_{m}(x) & = & f_{m-1}(x)+\beta_{m}b(x_{i},\gamma)\\w_{i}^{(m)} & = & \exp(-y_{i}f_{m-1}(x))\\ & = & \exp(-y_{i}[f_{m-1}(x_{i})+\beta_{m}b(x_{i},\gamma)])\\ & = & w_{i}^{(m)}\exp(-y_{i}\beta_{m}b(x_{i},\gamma))\\ & = & w_{i}^{(m)}\exp\beta_{m}\left[-y_{i}b(x_{i},\gamma)\right]\end{eqnarray*}

看出来最后的AdaBoost雏形了吧?


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *