集成学习顾名思义，就是把一堆垃圾方法集成起来变成一个牛逼的方法。集成学习主要分为两种思路：Bagging 和 Boosting。Bagging 的话就是一堆独立的垃圾方法，比如随机森林，就是通过不同的采样和不同的特征抽取方法产生一堆独立的决策树，然后把他们的决策进行投票。而 Boosting 则是通过一个垃圾方法来产生下一个垃圾方法，最知名的方法就是 AdaBoost 了。
看上去傻傻的 AdaBoost
对于普通的集成学习来说，其实最后的结果就是不同方法的线性组合，以二分类问题（1，-1）为例，最后的结果在数学上可以表示为： \[G=sign(\sum_{t=1}^T\alpha_t g_t(x_n))\]
上面的 \(g_t\) 就代表不同的学习方法，而 \(\alpha_t\) 代表着每个学习方法的权重。 在 AdaBoost 中，最关键的一点就是对于错误函数的修改。AdaBoost 使用的是带权重的错误函数，\(u_n\) 代表着每个样本点犯错误的权重： \[E_{in}^u(h)=\frac1N\sum_{n=1}^N u_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)\) 做拟合就好了，从第二棵决策树开始对残差做拟合。