决策树的表达能力

18.3.2 决策树的表达能力

从逻辑上说，表示WillWait目标谓词的任意一个特定决策树假设都可以被视为如下形式的断言：

∀ s WillWait(s) ⇔ (P1(s)∨P2(s)∨ ... ∨Pn(s))

其中每个条件Pi(s)都是测试的一个合取式，对应一条从树的根节点到具有正输出的叶节点的路径。虽然这看起来和一阶逻辑语句很像，但是在某种意义上，它是命题式的，因为它只包含一个变量而且所有的谓词都是一元的。决策树真实地描述了WillWait和一些属性值的逻辑组合之间的关系。我们不能用决策树表示涉及两个或更多的不同目标的测试，例如：

∃r2Nearby(r2, r)∧Price(r, p)∧Price(r2, p2)∧Cheaper(p2, p)

（附近是否有更便宜的餐馆？）。显然，我们可以添加另外一个布尔属性，名称为CheaperRestaurantNearby，但是添加全部类似属性是不可操作的。第十九章将对在一阶逻辑中正确学习的问题进行深入的研究。

在命题语言的分类中，决策树具有完备的表示能力；即任何一个布尔函数都能够写成一棵决策树。这可以通过下述方法轻易实现：令函数真值表中的每行对应于树中的一条路径。这将产生指数级大小的决策树表示，因为真值表行数是指数级的。无疑，决策树可以用规模小一些的树表示很多函数。

然而对于某些函数而言，这确实是一个问题。例如，如果函数是一个奇偶校验函数，即当且仅当输入中有偶数个1的时候该函数返回值为1，那么则需要一棵指数级大小的决策树。用决策树表示多数函数也很困难，该函数只有当超过一半的输入是1的时候才会返回1。

换句话说，决策树对某些函数比较有用，而对另外一些效果不好。难道没有任何一个对所有类型的函数都有效的表示方法吗？不幸的是，答案是“没有”。我们可以用一种很一般的方式来解释这个问题。考虑n个属性上的所有布尔函数的集合。在这个集合中有多少个不同的函数？这也就是我们能写下来的不同真值表的数目，因为这些函数是由其真值表定义的。真值表有2n行，因为每个输入情况都用n个属性加以描述。我们可以认为表的“答案列”是一个定义该函数的2n位的数字。无论我们用何种表示方法表示这些函数，总有一些函数（实际上，最多是所有的函数）至少需要那么多位来表示。

如果用2n位来定义函数，那么n个属性上就有个不同的函数。这是很可怕的数字。例如，如果仅有6个布尔属性，就会有=18446744073709551616个不同的待选函数。因此我们需要一些巧妙的算法在如此巨大的空间中发现那些一致的假设。