两棵决策树之和是否等于一棵决策树?

机器算法验证 回归 机器学习 大车
2022-02-11 23:47:32

假设我们有两个映射输入的回归树(树 A 和树 B)xRd输出y^R. y^=fA(x)对于树 A 和fB(x)对于树 B。每棵树都使用二元分裂,超平面作为分离函数。

现在,假设我们对树的输出进行加权求和:

fC(x)=wA fA(x)+wB fB(x)

是函数fC相当于一个(更深的)回归树?如果答案是“有时”,那么在什么条件下?

理想情况下,我想允许倾斜超平面(即对特征的线性组合进行分割)。但是,如果这是唯一可用的答案,假设单特征拆分可能是可以的。

例子

这是在二维输入空间上定义的两个回归树:

在此处输入图像描述

该图显示了每棵树如何划分输入空间,以及每个区域的输出(以灰度编码)。彩色数字表示输入空间的区域:3、4、5、6 对应于叶节点。1 是 3 和 4 的并集,以此类推。

现在假设我们平均树 A 和 B 的输出:

在此处输入图像描述

平均输出绘制在左侧,树 A 和 B 的决策边界叠加。在这种情况下,可以构建一棵更深的树,其输出等于平均值​​(绘制在右侧)。每个节点对应于输入空间的一个区域,该区域可以由树 A 和 B 定义的区域构成(由每个节点上的彩色数字表示;多个数字表示两个区域的交集)。请注意,这棵树不是唯一的——我们可以从树 B 而不是树 A 开始构建。

此示例表明存在答案为“是”的情况。我想知道这是否总是正确的。

1个回答

是的,回归树的加权和等效于单个(更深)回归树。

通用函数逼近器

回归树是一种通用函数逼近器(参见例如cstheory)。大多数关于通用函数逼近的研究都是在具有一个隐藏层的人工神经网络上完成的(阅读这篇精彩的博客)。然而,大多数机器学习算法都是通用函数逼近。

作为通用函数逼近器意味着可以近似表示任何任意函数。因此,无论函数变得多么复杂,通用函数逼近都可以以任何所需的精度表示它。在回归树的情况下,您可以想象一个无限深的树。这棵无限深的树可以将任何值分配给空间中的任何点。

由于回归树的加权和是另一个任意函数,因此存在另一个表示该函数的回归树。

创建这样一棵树的算法

知道这样一棵树的存在真是太好了。但我们也想要一个配方来创建它们。这样的算法将结合两个给定的树T1T2并创建一个新的。解决方案是复制粘贴T2在每个叶节点T1. 那么新树的叶子节点的输出值就是叶子节点的加权和T1(在树的中间某处)和叶节点T2.

下面的示例显示了添加权重 0.5 的两个简单树。请注意,永远不会到达一个节点,因为不存在小于 3 和大于 5 的数字。这表明这些树可以改进,但不会使它们无效。

在此处输入图像描述

为什么使用更复杂的算法

@usεr11852 在评论中提出了一个有趣的附加问题:如果每个函数都可以用简单的回归树建模,我们为什么要使用提升算法(或者实际上是任何复杂的机器学习算法)?

回归树确实可以表示任何函数,但这只是机器学习算法的一个标准。另一个重要的属性是它们的泛化程度。深度回归树容易过度拟合,即它们不能很好地泛化。随机森林平均有很多深树来防止这种情况。