集成学习顾名思义,就是把一堆垃圾方法集成起来变成一个牛逼的方法。集成学习主要分为两种思路:Bagging 和 Boosting。Bagging 的话就是一堆独立的垃圾方法,比如随机森林,就是通过不同的采样和不同的特征抽取方法产生一堆独立的决策树,然后把他们的决策进行投票。而 Boosting 则是通过一个垃圾方法来产生下一个垃圾方法,最知名的方法就是 AdaBoost 了。

看上去傻傻的 AdaBoost

对于普通的集成学习来说,其实最后的结果就是不同方法的线性组合,以二分类问题(1,-1)为例,最后的结果在数学上可以表示为:
\[G=sign(\sum_{t=1}^T\alpha_tg_t(x_n))\]上面的 \(g_t\) 就代表不同的学习方法,而 \(\alpha_t\) 代表着每个学习方法的权重。

在 AdaBoost 中,最关键的一点就是对于错误函数的修改。AdaBoost 使用的是带权重的错误函数,\(u_n\) 代表着每个样本点犯错误的权重:
\[E_{in}^u(h)=\frac1N\sum_{n=1}^Nu_n\cdot err(y_n,h(x_n))\]

我们就是要使用不同的 \(u_n\) 来的得到不同的方法 \(g_t\)。显然,全都差不多的 \(g_t\) 最后集成学习出来的效果肯定很垃圾。从参数上面思考可以看出,模型 \(g_t\) 是通过参数 \(u_n^t\) 生成的,而模型 \(g_{t+1}\) 则是通过参数 \(u_n^{t+1}\) 来生成的。我们想让 \(g_t\) 和 \(g_{t+1}\) 产生足够大的差距,其实就是让 \(u_n^{t+1}\) 对应的 error 在 \(g_t\) 上表现很差就好了。

什么叫表现的差呢?对于分类预测来说,最差的结果其实就是扔硬币,也就是说达到百分之 \(50\) 的错误率,这个结果已经是最差的了。我们就是要通过构造 \(u_n^{t+1}\) 使得 \(g_t\) 在这个 error 上的错误率接近 \(0.5\)。

AdaBoost 的做法很简单,如果 \(g_t\) 的错误率为 \(\epsilon_t\) 的话,那么构造一个尺度因子:
\[\diamond t=\sqrt{\frac{1-\epsilon_t}{\epsilon_t}}\]对于正确的 \(u_n^t\) 可以乘上 \(\diamond t\),对于错误的 \(u_n^t\),可以除上 \(\diamond t\)。这样就会使得正确的和错误的参数 \(u_{n+1}^t\) 达到平衡,从而达到放大错误、缩小正确的目的,使得 \(g_t\) 在新 error 上面的错误率等于 \(0.5\)。

现在有了生成每个 \(g_t\) 的方法,那每个方法的参数 \(\alpha_t\) 应该是什么呢?一个直观的想法是:生成完方法之后,再对这些方法进行线性组合的优化,然后来求出 \(\alpha_t\)。这样固然是可以的,但是其实我们可以通过数学推导,来直接算出这个 \(\alpha_t\)。这里先下结论,一会儿再进行数学推导:
\[\alpha_t=ln(\diamond t)\]

最简单的一种 AdaBoost 方法叫做 AdaBoost-Stump。在 AdaBoost-Stump 中,每个小方法都只能在某个维度上面画直线来对训练集进行分类。但就是这样简单的方法,可以通过 Boost 组合的方式达到非常好的效果,这就是 AdaBoost 的神奇之处。

现在我们想利用 AdaBoost 把决策树来组合起来。但是问题来了,首先是 error 函数如何参与决策树的分支操作,这个参与起来会比较麻烦。比较简单的做法是直接对决策树屏蔽了 \(u_n\) 参数。然后通过 \(u_n\) 参数来对训练集进行采样,来达到不同 error 函数的效果。这样决策树就是原来的决策树,不需要进行任何的修改。

另一个问题就是,很多决策树都是直接把叶子剖分到单个结点或者单个类别。这样的做法必然会导致这个决策树在测试集上面的错误率 \(\epsilon_t\) 等于 \(0\)。这样我们就没有办法通过 \(\diamond t\) 来产生下一个垃圾方法了。当然解决这个问题的方法也很简单,对决策树进行剪枝和采样数据不全部采样都是可以尝试的做法。这个方法叫做 AdaBoost-DTree。值得注意的一点是:如果我们的决策树的高度限制为 \(1\),也就是说只能做一次划分,那么这个方法就跟 AdaBoost-Stump 没有任何区别啦。也就是说 AdaBoost-Stump 是 AdaBoost-DTree 的退化。

奥妙重重的 AdaBoost

还记得上面的 \(\alpha_t\) 吗?下面就是通过推导 \(\alpha_t\) 来发现 AdaBoost 的奥妙之处了。当然过程中其实涉及到一些高深的数学知识,但是因为我都不会,所以很多地方可能会讲的很“民科”。

上面说过 \(u_n^{t+1}\) 的求法:对于正确的 \(u_n^t\) 可以乘上 \(\diamond t\),对于错误的 \(u_n^t\),可以除上 \(\diamond t\)。通过数学式子其实可以将他们归纳成一个规律:
\[u_n^{(t+1)}=u_n^{(t)}\cdot \diamond_t^{-y_ng_t(x_n)}=u_n^{(t)}\cdot exp(-y_n\alpha_tg_t(x_n))\]如果初始值 \(u_n^{(1)}=\frac1N\) 的话,就有:
\[u_n^{(T+1)}=u_n^{(1)}\cdot \prod_{t=1}^Texp(-y_n\alpha_tg_t(x_n))=\frac1N\cdot exp(-y_n\sum_{t=1}^T\alpha_tg_t(x_n))\]通过上面的式子可以发现一个很显然的事情:\(u_n^{(T+1)}\) 与 \(exp(-y_n\sum_{t=1}^T\alpha_tg_t(x_n))\) 成正比。

将 \(\sum_{t=1}^T\alpha_tg_t(x_n)\) 从另外一个角度来看,可以发现这个其实是一个对 \(x_n\) 特征转换的线性组合,跟 SVM 中的那个完全一致。其实这个式子就是没有进行正则化的分界距离,跟 \(y_n\) 相乘的话,可以感性的理解成跟 SVM 一样,这个距离越大越好。

使得 \(y_n\sum_{t=1}^T\alpha_tg_t(x_n)\) 越大越好,那么显然 \(exp(-y_n\sum_{t=1}^T\alpha_tg_t(x_n))\) 越小越好,于是 \(u_n^{(T+1)}\) 也就越小越好。

我们的目标就变成了最小化:
\[\sum_{n=1}^Nu_n^{(T+1)}=\frac1N\sum_{n=1}^Nexp(-y_n\sum_{t=1}^T\alpha_tg_t(x_n))\]

因为 \(\sum_{t=1}^T\alpha_tg_t(x_n)\) 是我们的预测项,所以这个最小化其实也是另一种错误函数,而且这个错误函数显然是 0/1 error 的上界,这个错误函数一般叫做 \(\hat{err}_{ADA}\)。

有个优化函数,下面的问题就是如何求出这个优化函数 \(\sum_{n=1}^Nu_n^{(T+1)}\) 的最小值了。

思考梯度下降的过程,我们通过泰勒展开发现梯度的反方向是要求下降的最好方向,当然梯度下降的方向是一个向量。但是我们这里的“梯度”其实是一个函数,函数跟向量其实并没有多大的区别,只是一个下标是连续的一个下标是离散的(因为数学不好,只能这么理解了)。

接下来对要最小化的式子进行推导:
\[\frac1N\sum_{n=1}^Nexp(-y_n(\sum_{t=1}^T\alpha_tg_t(x_n)+\eta h(x_n)))=\sum_{n=1}^Nu_n^Texp(-y_n\eta h(x_n))\]对这个式子进行最简单的一阶泰勒展开可以得到:\[\sum_{n=1}^Nu_n^Texp(-y_n\eta h(x_n))=\sum_{n=1}^Nu_n^t(1-y_n\eta h(x_n))=\sum_{n=1}^Nu_n^t-\eta\sum_{n=1}^Nu_n^ty_nh(x_n)\]

先忽略掉步长 \(\eta\),我们的目标就变成了找到一个好的 \(h(x_n)\) 来最小化 \(\sum_{n=1}^Nu_n^{(t)}(-y_nh(x_n))\)。

对于二分类问题,\(-y_nh(x_n)\) 的值要么是 \(-1\) 要么是 \(1\)。当 \(y_n = h(x_n)\) 时,\(\sum_{n=1}^Nu_n^{(t)}(-y_nh(x_n)) = -\sum_{n=1}^Nu_n^{(t)}\),当 \(y_n \neq h(x_n)\) 时,\(\sum_{n=1}^Nu_n^{(t)}(-y_nh(x_n)) = \sum_{n=1}^Nu_n^{(t)}\)。将这个结果稍微平移并且统一一下,可以发现一件神奇的事情:\(\sum_{n=1}^Nu_n^{(t)}(-y_nh(x_n)) = -\sum_{n=1}^Nu_n^{(t)}+2E_{in}^{u_n^{(t)}}\cdot N\)。

太有趣了。让原来的 \(\sum_{n=1}^Nu_n^{(t)}(-y_nh(x_n))\) 竟然最优的 \(h(x_n)\) 就是让 \(E_{in}^{u_n^{(t)}}\) 最小的 \(h(x_n)\),也就是我们的 AdaBoost 过程中求出的 \(g_t\)!

在之前梯度下降的时候,我们选择的是自己随便设置一个步长,但是在 AdaBoost 里面,因为我们要组合各个方法以达到最好的效果,所以这个步长其实就是最后预测式中的 \(\alpha_t\)。这个步长也就是在最佳方向上的最大步进长度,先把要求最佳步长的表达式写下来:
\[\check{E}_{ADA}=\sum_{n=1}^Nu_n^{(t)}exp(-y_n\eta g_t(x_n))\]

有两种情况需要我们考虑,分别是预测正确:\(u_n^{(t)}exp(-\eta)\),和预测错误:\(u_n^{(t)}exp(+\eta)\)。

之前我们将错误率以符号 \(\epsilon_t\) 来表示,经过简单推导统一,可以得到:
\[\check{E}_{ADA}=(\sum_{n=1}^Nu_n^{(t)})\cdot ((1-\epsilon_t)exp(-\eta)+\epsilon_t\ exp(+\eta))\]

求导,\(\frac{\partial \check{E}_{ADA}}{\partial \eta}=0\) 得到:
\[\eta_t=ln\sqrt{\frac{1-\epsilon_t}{\epsilon_t}}=\alpha_t\]这就是 \(\alpha_t = ln\sqrt{\frac{1-\epsilon_t}{\epsilon_t}}\) 的原因啦!

从 AdaBoost 到 Gradient Boosting

总结一下之前 AdaBoost 的求解过程,其实就是去优化以下式子:
\[min_{\eta}min_h\frac1N\sum_{n=1}^Nexp(-y_n(\sum_{t=1}^T\alpha_tg_t(x_n)+\eta h(x_n)))\]之前说了,这个 \(exp\) 函数其实只是错误函数的一种形式,我们也可以换成其他类型的 error 函数,比如这样:
\[min_{\eta}min_h\frac1N\sum_{n=1}^Nerr(\sum_{t=1}^T\alpha_tg_t(x_n)+\eta h(x_n), y_n)\]这个公式就是一种通用的 Gradient Boosting 啦!

接下来,我们就使用普通的 regression 错误(\(err(s,y)=(s-y)^2\))来看看 regression 情况下的 Gradient Boosting 是怎么回事吧~

我们将 \(\sum_{t=1}^T\alpha_tg_t(x_n)\) 看做 \(s_n\),那么原式通过泰勒展开之后就等于:
\[min_h\frac1N\sum_{n=1}^Nerr(s_n,y_n)+\frac1N\sum_{n=1}^N\eta h(x_n)\frac{\partial err(s,y_n)}{\partial s}\]其中的一阶导数\(\frac{\partial err(s,y_n)}{\partial s}=2(s_n-y_n)\)。

去除一堆常数项和常数因子,其实我们只需要最小化\(h(x_n)\cdot 2(s_n-y_n)\)就好了。所以只要令\(h(x_n)\)是梯度\(2(s_n-y_n)\)的反方向就好了,但是这个反方向究竟要取多大呢?回想一下我们之前的梯度下降,其实梯度只代表一个方向,多大并没有什么关系。为了防止这个梯度取到无穷大,我们需要对梯度的大小进行一下限制。参考之前的正则化思路,我们也可以通过加上一个惩罚项\(h^2(x_n)\)来得到新的优化式子,经过添加常数进行整理,可以得到我们最后关心的优化式子:
\[min\sum_{n=1}^N((h(x_n)-(y_n-s_n))^2)\]也就是说,我们利用我们的基础 regression 方法使得 \(h(x_n)\) 更加接近 \(y_n-s_n\) 就可以了。简单的来说就是对所有 \(N\) 个点 \((x_n, y_n-s_n)\) 做 regression,得到的回归方程就是我们要求的 \(g_t(x_n)\) 啦!

其中一个很重要的概念就是 \(y_n-s_n\),很多博客会把这个东西叫做残差。也就是这些残差来决定 \(g_t\)。

现在需要求出步长 \(\eta\)。这个步骤非常简单,把我们之前求出来的 \(g_t\) 代回到原来的优化式子中们可以得到:
\[min_{\eta}\frac1N\sum_{n=1}^N(s_n+\eta g_t(x_n)-y_n)^2 = \frac1N\sum_{n=1}^N((y_n-s_n)-\eta g_t(x_n))^2\]可以发现,这里又是对残差进行拟合。不过这个拟合只有一个变量,非常简单,只需要简单求个导数就可以得到我们需要的 \(\eta\) 啦!

这个 Gradient Boosting 最出名的利用方法就是我们标题中提到的大名鼎鼎的 Gradient Boosted Decision Tree(GBDT) 啦!不过我们整个推导过程中好像并没有用过决策树啊?这个决策树要在哪里使用呢?

很简单,就是我们通过决策树来做每一步的 regression 就好啦!有一个细节是,因为我们在求第一棵决策树的时候并没有残差这个东西,所以直接对各个 \((x_n, y_n)\) 做拟合就好了,从第二棵决策树开始对残差做拟合。

发表评论

电子邮件地址不会被公开。 必填项已用*标注