随机森林背后的统计数据

随机森林背后的统计数据

窥探随机合奏的内部工作原理

随机森林有一些非常独特的东西。

我们通常的方差减少技术——比如限制决策树的深度,或者在逻辑回归中添加范数惩罚——通过惩罚单个假设的复杂性来工作。然而,随机森林中的方差减少来自于同时探索多个相互竞争的假设。

请注意这里的“竞争”一词。个体预测变量之间的多样性是随机森林等集成模型性能的关键。在统计学的语言中,“多样性”对应于单个模型预测的不相关性/反相关性。

让我们做一些机器学习课程很少做的事情,并深入研究随机森林的统计数据。为此,我们将以一种对读者友好的方式在开创性的 Breiman 论文中得出一些结果,并最终回答这个棘手的问题:那又怎样?[0]

Defining Our Metric

回想一下,随机森林分类器的输出来自于对不同类别投票的单个树的比例,并选择对应比例最大的类别。因此,正确分类一个点的随机森林将使其最大比例(介于 0 和 1 之间的数量)属于正确的类别。

让我们将一个函数附加到我们的随机森林,称为边际函数;这个函数从我们的数据集的分布中获取一个(X,Y)对,并输出森林对正确类 Y 的投票比例与森林在所有错误类中的最大比例之间的差异。

关于边距函数,你只需要知道,一个点的正边距越大,意味着森林“正确性”的缓冲空间越大;然而,低于零的边距值意味着森林直接错误地分类了该点(负边距越多越差。)

示例:点 (X, Y) 的边距为 0.5 意味着森林正确选择了 Y 类,Y 的总票数比任何其他不正确的类多 50%。相反,-0.3 的边距意味着森林错误地分类了该点,错误选择的类别的总票数比正确的类别 Y 多 30%。

注意:对于本文的其余部分,我们将使用具有大量树的随机森林,即限制范围内的随机森林,因此一旦您修复了训练数据集,它们的输出实际上就不是随机的。这不会改变我们的任何结论,因为即使是中等大小的森林也会很快收敛到它们的极限,但它确实简化了我们的分析。

现在让我们定义我们的分类度量:对点 D 的训练数据集进行采样的概率,并从同一分布中独立地对单个评估点 (X, Y) 进行采样,使得拟合在 D 上的森林在 (X , Y) 点:

同样,一个点的正边距意味着森林正确地分类了该点,因此上述概率完全等于我们的森林生成过程的总体百分比准确度。 (如果您很难看到这一点,请尝试更明确的重构:如果您从总体分布中对验证集进行抽样,并且在任何随机抽样点上正确分类的概率为 Q,那么验证集的准确率百分比为大致Q。)

现在出现了一个您可能很久没有听说过的短语:切比雪夫不等式。

Statistics Power Move #1:您可以(二次)仅使用其期望和方差来限制任何随机变量的尾部概率。

借助切比雪夫不等式,我们可以仅使用边际函数的期望和方差来计算对低于零边际进行采样的概率的具体下限。直观地说,具有低方差和大正均值的边际很少会出现低于零的值,而 Chebyshev 只是使这一点变得严格。现在,只要知道我们可以调整和权衡均值和方差,以获得上述概率表达式的更大下限(我们的总体准确度)。

高水平的偏差与方差

由于边际函数的期望和方差是我们准确权衡的关键,因此我们有必要对这两者有一个直观的理解。

让我们看一下这些术语,从期望开始:

更大的期望意味着我们生成的任何森林通常都是正确的,并且比不正确的幅度更大。根据我们对概率和切比雪夫不等式的了解,更大的期望意味着低于零边际值的概率的下限更大,即总体准确度的下限更大。

一种方法是使用自举采样或特征子采样等方法随机化单个树,从而稍微降低上述期望。这是森林做出的权衡之一:略微增加“偏差”。但是我们通过增加偏见得到什么?

这就是方差的来源:

固定正均值的较小方差意味着我们生成的森林不太可能在任何采样点上具有低于零的边距。与较大的期望一样,较小的方差会增加采样低于零边际的概率的下限。

请注意,我们不能仅仅构建无限多的树来将我们的方差缩小到零;如果我们所有的树都是相同的,那么无论它有多大,我们的随机森林都无法与孤独的决策树区分开来。显然,树之间的差异很重要。这里表示“树之间的差异”的严格量是多少?

事实证明,我们只需要树错误之间的协方差。 (请注意,协方差只是一个缩放的相关性。)但是如何呢?这个协方差项从何而来?我们需要分解方差项来找出答案。

Breaking Down Variance

我们可以使用方差的矩定义来扩展边际函数的方差,如下所示:

让我们放大右边的第一个期望项。

请记住,(X, Y) 处的边际函数是树对正确类别 Y 的投票比例与其在所有错误类别中的最大投票比例之间的差值。我们真的可以将投票给某个类的总树的比例表示为随机选择的树为该类投票的概率。 (回想一下,森林是通过对单个树进行独立且相同分布的绘制从特定数据集中生长出来的。)

森林投票比例和采样概率之间的这种联系将我们带到了我们的第二个统计动力移动:

Statistics Power Move #2:所有比例(或概率)都可以重写为二进制/指标/伯努利随机变量的平均值。

重申一下,我们可以将森林对给定类 C 的投票比例写成每棵树对类 C 的二元投票的平均值——如果树投票给 C,则投票为 1,否则为 0。在极限情况下(即无限多的随机生成的树),这种“树上的平均值”变成了一个期望,接管了我们随机抽样单个树的分布。

让我们使用这个树分布和我们的频率标识来重写我们的边距函数:

快速注意,我已经将期望设置在训练数据集 D 和固定评估点 (X, Y) 上,因为左侧的边际函数是在固定 D 和固定 (X, Y) 上评估的。

在这个替换中,我们采用了输出 X 类 Y 或 K 的树的比例差异(这是我们在 X 处评估的边际函数的原始定义),并将其转化为平均值的差异随机采样树对 Y 类或 K 类的二元投票(上图有一个平均差,相当于平均差。)为了使表达式更紧凑,我们将上述期望内二元投票的差称为“与单个树相关联的原始”边距函数或“rmg”。

我们可以写出以下新恒等式,首先对两边进行平方,然后对 D 和 (X, Y) 应用期望,最后用更紧凑的原始边际函数代替二元投票的差异:

我们为什么这样做?如果你还记得,左边的期望是我们图 4 中方差公式中的第二个时刻。我们正在重写方差项。

现在我们将从上面的右手项中提取一个协方差表达式。感到兴奋!

在我们能够做到这一点之前,我们需要使用三个简短而巧妙的技巧。第一个技巧是通过引入两个独立的、同分布的树分布来重写上面表达式中的右手期望:“Trees”和“Trees-prime”。由于这些分布是 i.i.d.,它们的期望将是相同的,所以我们可以用两个(相同值的)期望的乘积代替“Trees”和“Trees-prime”来代替右手项内的平方期望。然后,我们对右手项进行以下重写:

请注意,原始边距函数是特定树的独特属性(就像边距函数是特定森林的独特属性一样),因此我将从“Trees”中采样的树的原始边距函数描述为“rmg ”以及从“Trees-prime”中采样的树的原始边距函数为“rmg-prime”。

第二个技巧利用了两个独立随机变量的期望乘积等于乘积的期望这一事实。由于分布“Trees”和它的孪生“Trees-prime”在构造上是独立的,所以上面表达式中计算的“rmg”和“rmg-prime”函数本身在树的绘制上是独立的(在固定评估点(X , Y) 和数据集 D 生成我们的树。) 然后我们可以使用第二个技巧将两个原始边际函数乘积的联合期望替换为期望乘积。因此,我们可以将表达式重写为:

最后,第三个技巧是“置换”期望,以便您对训练数据集 D 和外部的树分布有期望,对内部的评估点 (X, Y) 有期望。要了解它是如何工作的,首先整合一些术语会有所帮助。利用迭代期望定律,我们可以将上面的迭代期望重写为总期望:

现在,我们将使用 (X, Y) 独立于“Trees”、“Trees-prime”和 D 上的联合分布这一事实,将上述期望分解为新的迭代期望:

我们非常接近在此处提取协方差项(再次,这只是一个比例相关!)请注意,里面的项是两个随机变量的乘积的期望,这是一个教科书公式中的组成项对于协方差:Cov(X, Y) = E[XY]- E[X]E[Y]。让我们用协方差的形式重写期望中的术语,以获得一个新的整体表达式(对于下图中的字体大小表示歉意;我保证只要表达式会得到这个):

回想一下,从图 6 中,我们一直在计算边际函数的二阶矩。然后,我们可以将上述表达式代入图 4 中方差矩定义中的二阶矩。我将在此处保存一些重复的数学页面;只知道我们可以将上述期望中的第二项与图 4 中右侧的第二项合并。进行这种替换和合并后,我们可以得到以下边际函数方差的表达式,即仅涉及上述协方差项(包含在期望中)和一个附加方差项:

这两个分量构成了我们的森林边际函数在 D 和 (X, Y) 上的方差。让我们直观地理解每个术语:

  1. 左边的术语:粗略地说,这个术语表示任意两棵随机采样的树的“误差”在点的总体分布上“共同变化”的程度,其中该协方差是树和训练数据集的所有可能组合的平均值生产那些树。请注意,让一棵树的逐点误差不相关,甚至与另一棵树的误差相反会降低表达式的整体价值。
  2. 右边的术语:这个术语不太重要,因为对于大型训练数据集 D,森林的预期边际函数在不同训练数据集 D 上的方差很小(另一种说法是,两个大型随机森林拟合在两个 i.i.d. 大型数据集上会做出非常相似的预测。)然后我们可以合理地假设右边的项比左边的项小得多。

让我们去掉右边的项,只用左边的项来重写边际函数的方差:

惊人的!我们森林的偏差-方差权衡实际上是偏差-协方差权衡,所讨论的协方差是单个树的误差的协方差。

鬼鬼祟祟的读者可能已经注意到了更令人兴奋的事情:这个数学中没有任何部分是树木群独有的。你有没有听到我在任何地方提到“叶子”、“节点”或“分裂”?

这是正确的;您可以随机化几乎任何分类器并将它们平均在一起,以实现最佳的偏差-协方差权衡——与单独使用这些分类器中的任何一个分类器相比,它可能会为您提供更好的准确度!荒野。

An Investing Analogy

在传统的投资组合理论中,投资的一个目标是最小化您的投资回报的方差以获得固定的平均回报。

假设你的投资组合由对不同公司的一堆投资组成:谷歌、可口可乐、Reddit 等。那么,你的投资的累积回报就是各个回报的总和。我们可以将您的累积收益的方差写为:

让我们来看看右边的两个总和。

右边的第一个总和包括每只股票收益的方差之和。有道理的是,某种股票的回报波动越大,整体投资组合回报的波动也越大。您可以将收益的方差视为投资风险的粗略衡量标准。

右边的第二个和更有趣一点,它包含协方差项(你能明白我的意思吗?)如果两只股票的协变为负,它实际上会降低投资组合回报的整体方差。

这就是为什么分析师总是告诉个人投资者分散他们的投资。如果您只持有 Gamestop 的股票,那么您的命运将与 Gamestop 的命运一样剧烈波动。但是如果你持有不同行业、不同公司的股票,那么个别的涨跌在一定程度上会抵消掉,你面临的唯一风险就是整个市场下跌的风险(所谓的“系统性”风险。)多元化投资相当于不把所有的鸡蛋放在一个篮子里。

回到随机森林——我们的个体树(股票)有时可能过于投机,并以泛化为代价追逐训练准确性。然而,通过随机化这些树,我们正在探索(投资)问题中不同的、相关性较低的“部门”,并且通过取平均值,我们可以使输出(我们的投资组合)减少对任何一棵树的依赖。通过这样做,我们创建了一个强大但仍然强大的模型。

Conclusion

让我们总结一下我们的两个主要学习:

  • 随机森林采用一种独特的方差减少方法:集成具有较少相关误差的单个模型
  • 基于树的集成没有什么独特之处。您可以构建任何机器学习模型的随机集合,调整随机化以获得最佳精度

需要注意的一点是,梯度提升可能隐含地类似于第一个项目符号。在每次新的 boosting 迭代中,我们有效地对当前迭代的“错误”进行上采样并训练一个新模型;最后,我们将新模型添加到现有集合中。因为我们对上一次迭代的误差进行了上采样,增量模型在这些点上的误差往往相对较低,而在之前迭代做得好的点上的误差相对较高。这是行动中的反相关!但是请注意,这里没有提供严格的证明;我将把关于 boosting vs. random ensemles 的讨论留给实际的专家。

第二个子弹实际上很有趣。它表明,现有的每个模型都可以通过随机化和并行训练许多类似的模型来改进——这在使用更便宜的云计算时变得越来越容易。

谁知道?也许下一场大型 Kaggle 比赛将归结为一种巧妙的随机化技术。

References

[1] L. Breiman,随机森林 (2001),机器学习 45、5-32[0]

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
社会演员多的头像社会演员多普通用户
上一篇 2022年4月25日
下一篇 2022年4月25日

相关推荐