随机森林模型笔记

首先从机器学习模型的误差开始，对于机器学习模型，它的误差包括三部分，bias、variance和噪声。
error = bias + variance + 噪声
随机森林主要是通过降低variance来降低整体的error(而boosting算法是通过降低bias来降低模型error)。
看一下随机森林的算法流程：

For i = 1 to B:
  (a) 对全体数据集，采取bootstrap，获得N个样本
  (b) 训练第b颗树，对于树中每个分裂结点：
      (1) 随机选取m个特征(可能对选中的特征做随机投影)
      (2) 选择最佳分裂特征和分裂点(每次分裂都选择随机特征)
return B颗树
// 预测过程
回归：取B颗树结果的均值
分类：B颗树做投票，要返回类别就是投票树最多的类别，要返回每一类的概率就是这个类别的投票数/B

随机森林模型是两种方法的合成，即树模型和bagging。树模型，特别是完全生长的树，能够学到较低bias的结果，但是容易过拟合，也就是模型的variance较大。bagging，多个模型bagging后，bias的期望和子模型的bias的期望是一致的，bagging有降低variance的效果，所以bagging能够在不降低bias的情况下降低variance，从而降低整体的error。

要想降低variance，我们来看一下bagging后模型的variance的计算方法。
在每个模型同分布的情况(不需要相互独立)下，假设每个模型贡献的variance是 $σ^2$ ，共有B个模型做bagging，每个模型预测结果之间的相关性是ρ，则bagging后模型的variance是：

bagging模型variance的计算

分析上面的式子。对于第二项，随着B的增加，会逐渐变小，这告诉我们bagging需要较多的子模型来把第二项降低。对于第一项，可以通过降低ρ，即子模型之间的相关性来降低variance。
对应到随机森林中，每次训练子模型采用了bootstrap，它的作用就是为了同分布子模型满足同分布的性质；每个子模型的random的操作，包括数据和特征，它的作用就是为了减少相关性，也就是降低ρ。
随机森林中特征重要性的计算
这里主要有两个概念和一个trick
- 第一个概念是OOB(out-of-bag)
  对于每一颗树，我们的训练数据都是从全体数据中bootstrap获得而来的，假设数据量为N，每次自助采样没用到的样本比例是(1-1/N)^N，当N很大的时候这个比例约为1/e(推导过程很简单，就是让分母变成1加上一个很小的数)。
  对于每一条样本，如果它没有被用作第t颗树的训练，则称这个样本是这个 $g_t$ 模型的袋外数据(out-of-bag)。对于每一条样本，可以获得这条样本的label，以及没有用到这条样本作为训练集的所有子树的结果，把这些结果的平均/投票作为这条样本的预测，和label可以计算一个err，把所有样本的err求平均，获得整体模型的袋外数据的误差，称为Eoob(G)。
- 第二个概念是permutation
  permutation的作用是为了保持原有特征列的数值分布。
  对于一个特征，我们把这个特征对应的值保持不变，但是改变这个特征值所属的样本称为permutation。例如对特征f1，假设有四个样本，对第1-4个样本他们的f1原始值分别为1234，做permutation后，第1-4个样本他们的f1特征的值可能为2314。
- 为了计算特征的重要性，我们每次改变样本中的其中一个特征，对这个特征做permutation，然后计算做了permutation前后在袋外数据的误差，分别为Eoob(G)和Eoob(Gp)，通过计算误差的差值，可以获得特征的重要性，如果特征比较重要，那么这个差值会比较大。但是这样计算Eoob(Gp)需要对模型重新进行一次训练，这里有一个trick，我们不去计算Eoob(Gp) ，而是改为计算Eoob_p(G)。也就是说不对训练数据的特征做permutation，让训练数据保持不变，训练好的模型不变，对袋外数据做permutation，然后计算对袋外数据做permutation前后的误差的差值，用这个差值来判断特征的重要性。具体来说，就是在model.predict的时候，对输入样本的第i维特征进行permutation。这样可以提高计算速度。
随机森林的优点：可以并行，这个也是bagging模型共有的优点，每个子模型可以并行去计算，然后把结果合并。
拓展
随机森林的随机性还可以包括在随机选取特征的时候做线性组合(加投影矩阵），这个在台大的机器学习技法里也有提到。

利用投影矩阵来生成随机特征
后续
boost和bagging的区别
L1正则和L2正则的区别
参考文献
1. 机器学习技法课程及ppt
2. The Elements of Statistical Learning
3. NTUML 26. 随机森林