Random Forest OOB

随机森林模型基于Bagging(Boostrap Aggregation)思想，学习多棵树，聚合结果来减少模型的variance。其中模型的diversity非常重要，一种增加diversity的手段是对原始数据集采样，然后在采样后数据集上训练模型。

Boostrap

Random Forest中采样用的是统计学中boostraping技术，即有放回采样。

Bootstrap sample $\tilde D_t$: Re-sample $N$ examples from $D$ uniformly with replacement – can also use arbitrary $N_0$ instead of original $N$.

OOB

一个问题是，out-of-bag（OOB理解为未采样到的样本）的样本大致数量是多少？如下图中红色星星所示即为OOB。

可以近似计算。假设$N’=N$，则单个样本$(x_n, y_n)$是OOB的概率为：

如果$N$足够大，上述值存在极限。

所以OOB大小约为