虽然PGM和NMF提供了很多很炫酷的模型,但是实际上很多的DM任务并不使用这些复杂的模型。相反,很多简单的模型诸如linear regression、logistic regression、RF和GBDT等模型更加常用。所以,平时也应该关注一下这些基本的模型和技巧。

Aggregation Models

为什么要aggregation

对于存在的很多hypothesis\(g_1, ..., g_T\),我们想要找一个\(G(x) = g_{t*}(x)\),使其满足\(t* = argmin_{t \in \{1,2,..,T\}}E_{val}(g^-)\)

简单可以想到的三种方法

  • \(G(x) = sign(\sum_{t}1*g_t(x))\) 平均的投票策略

  • \(G(x) = sign(\sum_{t}\alpha_t g_t(x))\) with \(a_t \geq 0\),非平均

  • 可以包括之前的两种 \(G(x) = sign(\sum_{t} q_t(x)g_t(x))\) with \(q_t(x) \geq 0\), 权值是由函数确定的

其本质是通过weak hypotheses来构造一个strong hypotheses。每一个hypotheses也可以看做feature transform.

Blending

所谓的blending就是把我们已经得到的很多 hypotheses在重新混合。从最简单的uniform blendinglinear blendingAny Blending

Uniform Blending

所谓的uniform blending就是认为所有的hypotheses都是有相同的权重,这在分类的情况下比较好理解,就是哪个投票多的就选哪个,在Regression的时候就取均值就好,那这样具体究竟是哪里好呢?

首先设最后得到的hypotheses为\(G\),那么就有 \[G(x) = \frac{1}{T}\sum^{1}_{t=1}g_t(x)\] 假设真正的函数应该是\(f\),则其差距为 \[\begin{split} avg((g_t(x) - f(x))^2) & = avg(g_t^2 - 2gf + f^2) \\ &= avg(g_t^2) - 2Gf - f^2 \\ & = avg(g_t^2) - 2G^2 + G^2 + (G - f)^2 \\ & = avg(g_t^2 -2g_tG + G^2) + (G - f)^2 \\ & = avg((g_t - G)^2) + (G - f)^2 \end{split}\]

所以,当我们考虑的是\(E_{out}\)的时候,就会有 \[\begin{split} avg(E_{out}(g_t)) & = avg(\varepsilon(g_t -G)) + E_{out}(G) \\ & \geq E_{out}(G) \end{split}\]

所以我们可以看出来,其实最终得到的\(E_{out}(G)\)一定比任意一个\(g_t\)的表现要好。

其实换一个角度看,如果每次获得\(g_t\)都是从相同的分布的不同样本生成的话,当选取的\(g_t\)的个数趋向于无穷的时候,最终的得到的\(G\)可以看做整个模型的表现的期望等价于模型本身的差距\(E_{out}(G)\)以及模型的variance\(\varepsilon(g_t -G)\)而我们取平均就是为了减少方差,也就减少了模型本身过拟合的可能性。这种方法并不少见,回忆一下,在linear regression的时候我们引入L1范数不也是为了减少variance嘛。

Linear Blending and Any Blending

Uniform Blending扩展一下,不同的\(g_t\)有不同的权重就变成了Linear Blending。考虑到regression的情况就变成

\[min_{\alpha_t \geq 0} \frac{1}{N}\sum_{n = 1}^N (y_n - \sum_{t = 1}^T \alpha_t g_t(x_n))^2\]

显然这里可以把每一个\(g_t(x)\)看做一个特征转换的方式,考虑到这里面\(\alpha \geq 0\)的约束其实是不必要的,我们完全可以采用线性回归的方法。

整个流程可以这样看: 1. 先从多个不同的H里面选出来不同的\(g_t\),它们都是最小的\(E_{in}\) 2. 这个时候,为了避免过拟合,应该从validation set里面进行学习\(\alpha\)

既然linear可以那么显然其他的非线性的模型也都可以只要把学习\(\alpha\)的时候换成学习其他的模型就可以了。

Bagging

当我们手中的数据有限的时候,我们不容易直接得到真正的很多的\(g_t\),而当我们数据本身是无偏的话,从另一方面,我们可以用采样的方法来获得更多的样本的效果。

假设我们手中有train set为\(Z = (z_1, z_2, z_3,...,z_N)\)其中\(z_i = (x_i, y_i)\),然后采用有放回的采样,采出来等同的N个数据,然后执行这个方法B次,就得到了B个Bootstrap的data set。设由第b个data set训练出来的分类器为\(g^{*b}\),则 \[\hat{Error_{boot}} = \frac{1}{B}\frac{1}{N}\sum_{b=1}^B\sum_{i=1}^NL(y_i, g^{*b}(x_i))\]

但是我们单单这样做结果还不太好,原因也很显然,没有真正意义上的交叉验证最终我们相当于用Bootstrap得到的数据集当做训练集,用完整的数据集当做测试集,当然容易过拟合了。

如果对于每一个Bootstrap的数据集都是采用leave one out的方法的话,\(Err_{boot}\)就会变成

\[Err_{boot(1)} = \dfrac{1}{N}\sum_{i=1}^N\dfrac{1}{|C^{-i}|}\sum_{b\in C^{-i}}L(y_i,f^b(x_i))\]

虽然leave one out这种方式解决了overfitting的问题,但是它确是有偏的,为了解决这个有偏的问题,Efron和Tibshirani提出了0.632 estimator

\[Err_{.632} = 0.368\overline{err} + 0.632Err_{boot(1)}\] 其中 \[\overline{err} = \dfrac{1}{N}\sum_{i=1}^N L(y_i,f(x_i))\]

为什么是0.632呢?考虑一个观察的样本属于第b个Bootstrap样本的概率应该为 \[\begin{split} Pr\{observation i &\in bootstrap sample b \} \\ & = 1 - (1 - \frac{1}{N})^N \\ & = 1 - e^{-1} \\ &= 0.632 \end{split}\]

即两个不同dataset里面应该有0.632N个不同的数据。但是问题又出来了,这种方式在拟合的很好,即\(\overline{err}\)很小的时候,就会变得不好了。 最终,有一种利用权值调解的方法

\[Err_{.632} = (1-\hat{w})\overline{err} + \hat{w}Err_{boot(1)}\] 其中 \[\hat{w} = \frac{0.632}{1 - 0.368\hat{R}}\]

\(\hat{R}\)relative overfitting rate\[\hat{R} = \frac{\hat{Err^{1}} - \overline{err}}{\sigma-\overline{err}}\] \[\sigma = \frac{1}{N} \sum_i \sum_j L(y_i - f_j(x_i))\]

Adaptive Boosting

再回去看看之前的Bagging方法,它仅仅就是从数据里面抽样而已。假设我们直接得到最后的结果,那么由于放回采样可能得到有重复数据的训练集可以写成

\[E_{in}^u(h) = \frac{1}{N} \sum_{n=1}^Nu_n^t [[y_n \neq h(x_n)]]\]

其中\(u_n^t\)就是样本t中出现第n个样本的次数,所以就可以看成每一个\(g_t\)都在极小化一个带权值的错误即minimizing bootstrap-weighted error\[E_{in}^u(h) = \frac{1}{N} \sum_{n=1}^Nu_n L(y_n ,h(x_n)))\]

意识到这一点之后,再进一步,我们为了更好的学习我们的模型,往往希望不同的\(g_t\)尽可能的不相同,即有更多的hypotheses,所以我们可以通过调整权值来获得不同的\(g_t\)。 当我们获得一个\(g_t\)的时候,然后我们调整\(u^{t+1}\),试得到的数据上\(g_t\)的表现很差,那么\(g_{t+1}\)自然就会和\(g_t\)不一样了(相关性很弱)。换而言之,就是希望 \[\frac{\sum_n^N u_n^{t+1}[[y_n \neq g_t(x_n)]]}{\sum_{n=1}^N u_n^{t+1}} = \frac{1}{2}\]

这个式子直观的解释其实就是\(g_t\)犯错的点与权值乘积的和占整个数据集的一半,这样怎么调整权值就很直观了。 最后还有一个小问题,就是最后我们怎么通过不同的\(g_t\)的到\(G\),显然直接通过投票是不合适的,所以就有了一下动态求\(\alpha\)的过程

  1. 初始化,权值\(u_1\)均为\(\frac{1}{N}\)

  2. 然后计算错误率\(\varepsilon_t = \frac{\sum_n^N u_n^{t}[[y_n \neq g_t(x_n)]]}{\sum_{n=1}^N u_n^{t}}\) ,更新系数\(\alpha_m = \log \sqrt {\frac{1 - \varepsilon_t}{\varepsilon_t}}\)

  3. 更新权值\(u_{ti} = u_{ti} * exp(\alpha_t*[[y\neq g_t(x_i)]])\)

  4. 最后输出\(G(x) = sign(\sum_{t=1}^T\alpha_t g_t(x))\)

from VC theory

AdaBoost的VC bound如下

\[E_{out}(G) \leq E_{in}(G)+O(\sqrt {O(d_{vc}(\mathcal{H})T*\log Tl\frac{\log N}{N})})\]

另外,作者还证明了,\(E_{in}\)可以在\(T = O(\log N)\)的迭代次数内减少到一个很小的值,而且对于分类器只要求比瞎猜强一点即\(\varepsilon_t \leq \varepsilon \lt 1/ 2\)就可以。 所以,由于T的增长比较缓慢,所以随着N的增大,\(E_{out}\)的值可以被明显的限制住。

###其他几点 ####为什么用指数模型 为什么系数这里突然出来个对数,可能一开始感觉比较奇怪。 我们设 \[f_*(x) = arg min_{f(x)} E_{Y|x}(e^{-Yf(x)}) = \frac{1}{2} \log \frac{Pr(Y=1|x)}{Pr(Y=0|x)}\] 改一下形式就是 \[Pr(Y=1|x) = \frac{1}{1 + e^{-2f^*(x)}}\] 也就是,这里其实就是为了求最优的二分类的解。 在换个角度,取\(p(x) = Pr(Y = 1|x)\)\(Y^{'} = (Y + 1) / 2 \in \{0,1\}\),此时采用cross-entropy作为损失函数的话就变成了 \[-l(Y, f(x)) = Y^{'}\log p(x) + (1 - Y^{'}l\log(1 - p(x)))\] 整理后为 \[-l(Y, f(x)) = log (1 + e ^{-2Yf(x)})\] 所以,也可以看做极小化交互熵。

####从贝叶斯看Bootstrap 设一个狄利克雷分布 \[w \sim Dir_L(a1)\] 其中\(a1\)是L维的向量,然后我们采样N个得到的分布可以看成 \[w \sim Dir_L(a1 + N*\hat{w})\]\(a1 = 0\)是,我们得到一个无信息先验分布noinformative prior \[w \sim Dir_L(N\hat{w})\] 由于我们是有放回的采样,所以不同分类可以看做从多项分布里面采样

\[N\hat{w}^* \sim Mult(N, \hat{w})\]

而这个分布的形式与后验分布的形式应该是一样的,理论上应该有相同的矩阵协方差矩阵等。所以,Bootstrap可以看做一种利用采样来获得非参共轭先验的方法,所以根据共轭的性质,可以通过采样得到的结果来减少后验的variance,所以能取得更好地结果。




X