随机决策树算法的基本思想与一般学习算法有很大的不同，是违反一般监督学习理论的常识的。因为在决策树的结构构建中，根本没有利用监督信息，从常识出发，该算法产生的模型不应该有预测能力。 但在实践中，随即决策树算法的预测精度是可以跟经典的算法相媲美的。随机决策树为什么能有学习能力，一直是令我着迷的一个问题。其相关文献都只有一些在理论上都不够严谨的说明和分析。本节将简要介绍个人对这个问题的理解。
机器学习和统计学机器学习是伴随着计算机的发明而出现的，上世纪 40 年代现代计算机发明后，50 年代就兴起了第一波机器学习的研究浪潮。在计算机出现以前，统计学已经建立了严密的体系和方法。这些方法在小样本量和很少维度的数据上，能够有很多不错的结果。到现在我们大学里学的统计学都是专注在研究这些小样本量和 1-2 维的问题。在理论上，把统计学的方法往高维空间中推广并没有困难，但在实际上这些方法往多维推广遇到了维数诅咒问题。统计学很重要的一个工作就是估计概率密度函数，也提供了很多概率密度函数的模型，如最典型的正态分布函数。实质上概率密度函数估计就是函数拟合。但是随着维度的增加，达到同样估计精度需要的样本数量几何数级的增加，这就是维数诅咒问题。在多维情况下，经典的统计学工具无法有效解决问题。为此，机器学习在处理这些问题时，采用了两种不同的策略。一种是放弃对估计精度的严格要求，采用简单、强假设的、线性模型来拟合，典型的如朴素贝叶斯和逻辑回归（Logistic Regression）。另一个方法，就如 Vapnik 所说，为了解决一个问题，不应该去解决比这个更难的问题。就分类问题而言，就是应该直接找分类界面而不是估计类别的分布概率函数。典型的算法就是 SVM, 而决策树算法也可以归为这一类。总之，机器学习实际上是统计在多维情况下对维数诅咒问题的妥协。
上面讨论的机器学习和统计学主要涉及参数估计方法，也是我们在大学统计学教材中主要讨论的方法。但是在统计学上有另外一套概率密度函数估计的方法，那就是非参数估计方法。非参数估计不需要假设数据是服从哪种分布模型的，因此该方法的适应性要强很多。但同时，非参数估计得出的模型相比参数模型则复杂很多，从数学上看也比较丑陋。最简单的非参数估计方法就是直方图。直方图的缺点是估计出来的函数图形是阶梯壮的，两个方柱之间估计结果是断层跳跃的，这就使得直方图的估计精度比较粗糙。为了克服直方图的问题，Parzen Window 方法又在直方图划分的箱中引入了高斯核来平滑直方图的估计。但是其计算开销也远大于直方图。 而另一种比较小众的非参数估计方法，平衡了这两种方法的优缺点。这个方法就是 Averaged Shifted Histogram（平均偏移直方图）。简单来说 ASH 方法就是把多个直方图的结果做简单平均，这些直方图的规格都是一样的，不同的是这些直方图之间有平移，也就是说用一组有平移关系的直方图融合起来做概率估计。图 2 中 ASH 的例子，展示了从一个直方图到 32 个直方图时估计的概率密度函数的变化。显然，随着直方图数量的增加，概率函数的估计越来越平滑。虽然非参数估计有自身的优点，但是同样受制于维数诅咒的问题，难以扩展到多维问题上。
随机决策树算法的理论探讨回过头来看随机决策树算法。如果我们把随机决策树算法用在一维的问题上，就会发现其跟 ASH 非常相似。一个一维问题的决策树，实际上就是对一维空间做了分段，然后统计每个分段里的类别出现频率。这在形式上与直方图是十分相似的。唯一的不同是一维的决策树不要求每个段的宽度是一样的。显然， 多棵一维随机决策树算法也跟 ASH 算法相似，实际上也是一种非参数估计方法。