我已经有两年 ML 经历，这系列课主要用来查缺补漏，会记录一些细节的、自己不知道的东西。

本次笔记补充视频 BV1JE411g7XF 的缺失部分。在另一个UP主上传的2017课程BV13x411v7US中可找到。本节内容 100 分钟左右。

本节内容综述

1. 今天介绍 Ensemble ，意思就是“团队合作”。
2. 首先，来讲 Bagging ，提及了随机森林中 out-of-bag 的测试方法。
3. 接下来，是用于 Improving Weak Classifiers 的 Boosting 。主要讲了 Adaboost ，包含很多数学上的证明。接下来是 Gradient Boosting 。
4. 最后几分钟，老师介绍了下 Stacking 。

小细节

Bagging

创造出不同的 data set ，训练不同的模型。

如上，分成 4 份数据（有放回地采样），训练 4 个模型。

如上，对 testing data 做平均。

This approach would be helpful when your model is complex, easy to overfit. e.g. decision tree.

e.g. decision tree

简单的 decision tree 如上图。但是对于决策树，有许多要进行考虑的事。

比如，树的深度，只要够深，就可以拟合任意图形。

Random Forest

使用 Out-of-bag 的方法，或许可以弥补决策树“过拟合”的问题。

Boosting

Boosting 可以把正确率略高于 50% 的模型，集成起来，达到正确率 100 % 。

如上，我们是有顺序地依次训练 $f(x)$f(x) ，这与 Bagging 不同。

How to obtain different classifiers?

刚才讲过，可以用不同的训练数据，训练不同的模型。

我们可以用“重采样”的方法，也可以如上，改变训练数据的权重。优化目标中，多了权重 $u^n$un 。

Adaboost

Idea

如上，我们要找一组新的训练数据（改变数据权重），其在 $f_1(x)$f1​(x) 上的表现很差，用这个训练 $f_2(x)$f2​(x) 。

如何找呢？如上，本来，我们的错误率是低于 0.5 的（如果高于 0.5 ，则将 output 反转就可以）。接着，我们调整权重 $u$u ，让错误率等于 0.5 。用这个权重训练 $f_2(x)$f2​(x)。

直观的举例如上。

Re-weighting Training Data

如上，只需对正确的数据与错误的数据分别进行运算即可。

这个 $d_1$d1​ 如何设置呢？推导如下。

如上，推导可能比较繁琐，但是道理很简单。由最下方的式子求解 $d_1$d1​ 即可。

这里有些技巧，把下面的式子倒过来，分母移到右边去，进行整理代换，最后得到 $d_1 = \sqrt{(1-\epsilon_1)/\epsilon_1}$d1​=(1−ϵ1​)/ϵ1​ ​

Algorithm

其演算法如上。我们将权重更新式整理成 $u^{n}_{t+1}\leftarrow u^n_t \times exp(-\hat{y}^n f_t (x^n)\alpha_t)$ut+1n​←utn​×exp(−y^​nft​(xn)αt​)

如上，如何把 $f(x)$f(x) 集合在一起呢？可以：

• Uniform weight
• Non-uniform weight （用 $\alpha_t$αt​ 作为权重）

注意，计算 $\epsilon$ϵ 时，带上权重。

Math

$H(x)=sign(\sum^T_{t=1}\alpha_t f_t(x))$H(x)=sign(t=1∑T​αt​ft​(x))
$\alpha_t = ln\sqrt{(1-\epsilon_t)/\epsilon_t}$αt​=ln(1−ϵt​)/ϵt​ ​

我们将证明，当 $T$T 增加时， $H(x)$H(x) 将越来越准（在训练集上）。

Error Rate of Final Classifier

如上，把 $\sum^T_{t=1}\alpha_t f_t(x)$∑t=1T​αt​ft​(x) 记为 $g(x)$g(x) ，而如果 $\hat{y}^n g(x^n)<0$y^​ng(xn)<0 ，说明是错误的预测，因为二者异号。绿色的线代表误差函数。可以得到误差函数上界 $exp$exp 。

如上，使用一些归纳的思想，得到 $u_{T+1}^n$uT+1n​ ，进而得到 $Z_{T+1}$ZT+1​ 。进而推出，我们之前讨论的上界就是与 $Z_{T+1}$ZT+1​ 直接相关的。

接下来我们进一步讨论 $Z_t$Zt​ 。如上，最终 $Z_t$Zt​ 的递推式。因此，最后得出 $Z_{T+1}=N\prod_{t=1}^T 2\sqrt{\epsilon(1-\epsilon_t)}$ZT+1​=Nt=1∏T​2ϵ(1−ϵt​) ​

这是小于 1 的，并且随着 $T$T 变大，越来越小。

testing error still decrease?

如上，在 training data 上似乎已经没有可以学的东西，而在测试集上，error 还可以再下降。

这是为什么呢？如上，被融合的模型越多，方法越鲁棒。

如上，在模型多了（T 增大时），让 Adaboost 这个上界在减小。

如上，就算深度是 5 的决策树，这 10 棵树互补，都可以有很好的形状。

Gradient Boosting

Gradient Boosting 是一个更加 general 的版本。

如上，我们时刻在更新我们的 $g(x)$g(x) ，让其变得更好。

如上，问题来了，如何把 $\partial L(g)$∂L(g) 作为一个偏微分呢（把函数作为变量）？这在数学上其实是可行的。

如上，我们希望目标 $f_t$ft​ 与 $\sum exp(...)$∑exp(...) 的方向越一致越好。即可转换成一个以最小化问题。

我们发现，我们找的 $f$f 就是 Adaboost 中的 $f$f 。而 $\alpha_t$αt​ 怎么找呢？

如上，我们找出的 $\alpha$α 正好也是 Adaboost 的 $\alpha$α 。

此外，使用 Gradient Boost 还可以自己做些变形。

Stacking

如上，模型融合。涉及到权重的问题。可以考虑学一个 Classifier ，来调整权重。