随机森林算法
之前的课程里曾经讲述过两种算法：bagging算法和决策树算法。这两种算法的特点都很明显：
- bagging算法需要基分类器\(g_t\)的方差尽可能大，然后它会通过投票或求均值的操作来减少最后算法\(G\)的方差
- 决策树会根据数据情况选择最佳切割点。数据有一点变化，切割点可能就会不同。因此决策树对数据很敏感，方差比较大（当决策树是完全生长的时候，尤其如此）
既然两个算法一个是能降低方差，另一个方差特别大，那么能不能把这两种算法结合在一起，取长补短？答案是可以的。这种将聚合算法做聚合的算法，称为随机森林，即随机森林是把完全生长的C&RT决策树做bagging，其中“随机”点出了bagging算法所依赖的随机性，“森林”点出了基算法是决策树的内涵。其具体过程为
对\(t=1,2,\ldots, T\)
- 通过对原始数据集\(\mathcal{D}\)做bootstrapping，得到大小为\(N'\)的数据集\(\tilde{\mathcal{D}}_t\)
- 在\(\tilde{\mathcal{D}}_t\)上运行决策树算法\(\rm Dtree\)，得到基分类器\(g_t\)
对得到的所有\(g_t\)做均匀混合，返回\(G={\rm Uniform}(\{g_t\})\)
随机森林的优点在于，其底层bagging过程可以拆开到不同机器上，而各个基分类器\(g_t\)也是独立学出来的，互相没有什么依赖关系，因此整个算法可以并行运行。加上决策树的训练效率很高，因此随机森林非常高效。该算法在继承了决策树算法优点的同时，还因为使用bagging而降低了方差，弥补了完全生长的决策树的缺点。综上，随机森林是一个非常有用的模型
除去bootstrapping中对数据做采样的随机性，随机森林还采用了另一种技术来保证底层基分类器尽量不同（回忆之前所讲的课程，基分类器越千差万别，bagging算法的效果越好）：它还会数据集的特征做随机采样。假设原始数据集\(\mathcal{D}\)有\(N\)条数据，\(d\)个特征，那么随机森林用来训练基分类器的数据集\(\tilde{\mathcal{D}}_t\)大小为\(N'\)，特征数为\(d'\)。这个对特征做采样的过程可以看作是对原始样本空间\(\mathcal{X} \in \mathbb{R}^d\)做一个特征投影，投影到一个随机子空间\(\mathcal{Z} \in \mathbb{R}^{d'}\)的过程。由于通常情况下有\(d' <\!< d\)，因此随机森林算法的效率可以得到进一步的提升（这种做法也可以用在使用其它模型做基模型的bagging算法里）。随机森林的提出者建议，对\(g_t\)的每次节点分裂\(b({\bf x})\)时都重采样一遍，使用不同的特征子空间，效果会更好
在此基础上，随机森林还可以再做进一步扩展！上面随机采样出\(d'\)个特征的过程，其实就是对原始数据\(\bf x\)乘以一个投影矩阵\(\rm P\)，做特征变换\(\boldsymbol{\Phi}\)的过程，即\(\boldsymbol{\Phi}({\bf x}) = {\rm P}\cdot {\bf x}\)，而\(\rm P\)是通过对标准正交基（natural basis）做随机采样得到的。新的扩展就在于，投影矩阵\(\rm P\)不再限定于是由标准正交基得到的矩阵，而是原始数据投影到不同的方向上，即新的特征是某些原始特征的线性组合。随机森林里考虑的投影通常是低维投影，即只选取\(d''\)个非零项做组合。注意当\(d''= 1\)，\(\rm P\)的每一行\({\bf p}_i\)都是标准正交基时，这种方法退化到了原来随机子空间的情况。随机森林的提出者建议，对\(g_t\)的每次节点分裂\(b({\bf x})\)时都做一次随机低维投影，效果会更好
袋外估计
本节对之前所讲授的bagging过程做一个更深入的探索：有前面bagging算法可知，在训练每个基分类器\(g_t\)时，都会使用一个bootstrapping得到的数据集\(\tilde{\mathcal{D}}_t\)。由于bootstrapping是有放回抽样的随机均匀采样过程，因此每个\(\tilde{\mathcal{D}}_t\)有\(1-N!/N^N\)的概率不会包含所有数据。所以，可以画一个表，来看对每个基分类器\(g_t\)，在训练它时用到了哪些数据，没有用哪些数据。下表就给出了这么一个例子
| 数据 | \(g_1\) | \(g_2\) | \(g_3\) | \(\cdots\) | \(g_T\) |
|---|---|---|---|---|---|
| \(({\bf x}_1, y_1)\) | \(\tilde{\mathcal{D}}_1\) | \(\star\) | \(\tilde{\mathcal{D}}_3\) | \(\tilde{\mathcal{D}}_T\) | |
| \(({\bf x}_2, y_2)\) | \(\star\) | \(\star\) | \(\tilde{\mathcal{D}}_3\) | \(\tilde{\mathcal{D}}_T\) | |
| \(({\bf x}_3, y_3)\) | \(\star\) | \(\tilde{\mathcal{D}}_2\) | \(\star\) | \(\tilde{\mathcal{D}}_T\) | |
| \(\cdots\) | |||||
| \(({\bf x}_N, y_N)\) | \(\tilde{\mathcal{D}}_1\) | \(\tilde{\mathcal{D}}_2\) | \(\star\) | \(\star\) |
上表中，第\(t\)列第\(n\)行的星号\(\star\)代表训练基分类器\(g_t\)时没有用到数据\(({\bf x}_n, y_n)\)，这条数据就称为\(g_t\)的袋外样本（OOB样本）。首先看抽样\(N\)次以后有多少样本是OOB的：每次抽取时，任意一条数据被抽中的概率为\(1/N\)，所以其不被抽中的概率为\(1-1/N\)。因此，任意一条样本连续\(N\)次都没被抽中的概率为\((1-1/N)^N\)。当\(N\)很大时，有 \[ \lim_{N\rightarrow +\infty}\left(1-\frac{1}{N}\right)^N = \lim_{N\rightarrow +\infty} \frac{1}{\left(\frac{N}{N-1}\right)^N} = \lim_{N\rightarrow +\infty} \frac{1}{\left(1+\frac{1}{N-1}\right)^N} = \frac{1}{e} \] 因此对大小为\(N\)的数据集做bootstrapping以后，如果得到的新数据集大小还是\(N\)，则OOB样本的数量应该约为\(N/e\)（三分之一强）
再看前面给出来的表，可以发现OOB数据有点像以前将验证时候提到的验证集：这些数据也是随机从原始数据中抽取，没有在训练中被使用，而且样本数量足够多。所以要用这些数据来验证\(g_t\)吗？理论上可以，但是实际中不需要。因为bagging的方法是模型聚合的方法，它的目的是要让最后聚合到的模型\(G\)好，因此需要找到一种方法，能够使用OOB数据来验证\(G\)的效果。由前面的知识可知，如果要用OOB数据验证\(G\)，就要保证这部分数据没有受到污染。以上表为例，\(({\bf x}_N, y_N)\)是\(g_3\)和\(g_T\)的OOB数据，那么它可以用来验证\(G_N^-({\bf x}) = {\rm average}(g_3, g_T)\)。以此类推，对每一条数据\(({\bf x}_n, y_n)\)，都可以构造出来这么一个子模型\(G_n^-\)，因此整个模型\(G\)的oob误差就可以通过下式计算 \[ E_{\rm oob}(G) = \frac{1}{N} \sum_{n=1}^N {\rm err}(y_n, G_n^-({\bf x}_n)) \] 即bagging算法的特性是，得到\(G\)后就能马上知道它的效果如何，因为它可以通过\(E_{\rm oob}\)来做一个自我验证，对超参数进行调整。与之前的验证方法相比，有了OOB数据和\(E_{\rm oob}\)以后，既不用将数据集分为两份（验证集和训练集），也不用再在确定好超参数以后重新训练模型了
特征选择
OOB数据除了可以对\(G\)做验证，还有别的用途。对于一份原始的\(d\)维数据\({\bf x} = (x_1, x_2, \ldots, x_d)\)，这里可能会有两种特征：
- 冗余特征，例如数据里可能同时有“年龄”和“生日”两项
- 不相关特征，例如做癌症推断的数据里可能有“医保类型”一项，而这一项对判断是否为癌症起不到作用
为了降低模型的复杂度，提高训练效率，需要将这些特征移除掉。尽管这些事情理论上可以手工完成，但是我们仍然希望能够通过学习的方法达到目的，即希望能学到一个特征子集的转换\(\boldsymbol{\Phi}({\bf x}) = (x_{i_1}, x_{i_2}, \ldots, x_{i_d'}), d' < d\)，然后用转换后的特征来学习\(g_t\)
特征选择的好处，首先它的效率得到了提升，而且排除掉了\(d-d'\)项噪声，降低了过拟合的可能性。最后，对\(d'\)项特征作分析可以集中在有用的特征上，提高模型的可解释性。但是从另一个角度看，特征选择也会带来风险。首先它是一个组合问题，选择最优组合的过程可能会占用额外时间；其次，如果特征选择没有做好，可能反而就会导致过拟合，得到错误的解释（或者分析时只能看到相关性不能看到因果性）。因此，这里责任最重的地方就是如何在\(d\)项特征中找到\(d'\)维特征子集。幸运的是，决策树本身自带一些特征选择的方法（因为它在训练时要决定在哪个特征上做分割是最有效的）
前面提过，特征选择本质是一个特征组合问题。有组合，就会有组合爆炸的可能性。那么如何降低这种可能性的发生，降低计算量？一种比较自然的启发式算法是，可以尝试计算每个特征的重要程度\({\rm important}(i){\rm \ for\ }i=1,2,\ldots, d\)。如果这个重要程度能够计算出来，那么只需要选\(d'\)个重要程度最大的特征\(i_1, i_2, \ldots, i_{d'}\)就可以。这种简单的方式在线性模型中很容易实现，因为重要程度可以根据模型权重向量\(\bf w\)的分量\(|w_i|\)来判断。\(|w_i|\)越大，特征的重要程度就越大。而\(\bf w\)的学习很直接，也很容易。然而，非线性模型中由于增添了特征之间的交互，特征重要性的判断通常会难很多。但是随机森林本身的一些机制，使得其成为了一种很容易做特征选择的非线性模型
使用随机森林做特征选择的基本原理是，如果特征\(i\)比较重要，那么往这个特征上塞入一些噪声，模型的表现肯定会变差。那么问题是，如何给某个特征加入一些随机值？不能给入服从均匀分布或者高斯分布的噪声，因为原始数据可能不服从这样的分布，武断地加入某个确认分布的噪声会改变数据在第\(i\)个维度上的分布\(P(x_i)\)。这里利用了类似bootstrapping的方法：为了验证某个特征\(i\)的重要性，对\(\{x_{n,i}\}_{n=1}^N\)重新生成一个排列（permutation），这样，数据在该特征上的分布\(P(x_i)\)就不会有什么变化了。记重排列特征\(i\)上的值以后得到的数据集为\(\mathcal{D}^{(p)}\)，特征\(i\)的重要性可以根据如下方式（称为排列测试 permutation test）做一粗略估计： \[ {\rm importance}(i) = {\rm performance}(\mathcal{D}) - {\rm performance}(\mathcal{D}^{(p)}) \] 这里，求\({\rm performance}(\mathcal{D}^{(p)})\)时需要用重排列后的数据集重新训练和验证模型。不过对于随机森林，可以免去验证的步骤，使用OOB就可以。甚至，可以不重新训练\(G\)，而是把OOB中的第\(i\)个特征做一个重排列。即 \[ {\rm importance}(i) = E_{\rm oob}(G) - E_{\rm oob}^{(p)}(G) \] 其中，在计算\(E_{\rm oob}(G)\)时，如果基分类器\(g(t)\)用到了第\(i\)维特征\(x_{(n, i)}\)，随机选择\(g_t\)的一个OOB数据点的第\(i\)维特征替代（这样该数据没有参与训练），就可以得到\(E_{\rm oob}^{(p)}(G)\)
随机森林实战
本节通过一些实验进一步展示了随机森林的特点：在树的数量足够多的情况下，随机森林可以学习出光滑，而且类似最大间隔的效果。而且，随机森林要求训练时用的树越多越好。理论上，用无限多棵树可以学到一个稳定的模型\(G\)，有限多的树只是能不断逼近这个结果
