18.5.2 决策表学习
决策表是一种受限形式的逻辑表达式。它包含一系列的测试，每个测试都是文字的合取式。如果一个测试在应用于某个实例描述时是成功的，那么决策表将指定返回该数值。如果测试失败，则用表中的下一个测试继续进行处理[6]。决策表与决策树类似，但是它们的整体结构比较简单。相反，单独的测试则比较复杂。图18.13中所示的决策表表示了如下假设：
图18.13 餐馆问题的决策表
如果我们允许测试的规模是任意的，那么决策表可以表示任意的布尔函数（参见习题18.15）。另一方面，如果我们限制每个测试最多包含k个文字，那么学习算法从少量实例进行成功的归纳是可能的。我们称这种语言为k-DL。图18.13中的实例是2-DL的。很容易证明（参见习题18.15），k-DL包含作为子集的语言k-DT，即所有深度至多为k的决策树的集合。需要牢记的是，源于k-DL的特定语言是依赖于用来描述实例的属性的。我们将用符号k-DL(n)表示一个使用n个布尔属性的k-DL语言。
首要的任务是证明k-DL是可学习的——也就是说，在用合理数量的实例进行训练之后，k-DL中的任何一个函数都可以是近似正确的。为了实现这个目标，我们需要计算语言中假设的数目。令测试语言——使用n个属性的至多包含k个文字的合取式——为Conj(n, k)。因为决策表是由测试构成的，而每个测试都有Yes或No两种输出，或者该测试不在决策表中，因此最多有3|Conj(n, k)|个不同的成分测试集合。这些测试集合中的每一个都可以按照任意顺序出现，因此
|k-DL(n)|≤ 3|Conj(n,k)||Conj(n,k)|!
由n个属性组成的k个文字的合取式的个数是
因此，经过某些工作，我们得到
我们把上式代入到公式（18.1）中，以证明对一个k-DL函数进行PAC学习所需要的实例个数是n的多项式量级的：
因此，任何一个能返回一致性决策表的算法都能够对于k值较小的情况，用合理数量的实例完成一个k-D L函数的PA C学习。
下一个任务是找到一个能返回一致性决策表的有效算法。我们将采用一个被称为DECISION-LIST-LEARNING（决策表学习）的贪婪算法，该算法重复地寻找一个与训练集的某个子集完全一致的测试。一旦找到这样的测试，它就将该测试添加到正在构建的决策表中，并删除相应的实例。然后用剩余的实例构造决策表的其余部分。重复上述过程直到没有剩余的实例。该算法如图18.14所示。
图18.14 决策表学习算法
这个算法并没有指定选择下一个要添加到决策表中的测试的方法。尽管前面给出的形式化结果是不依赖于选择方法的，但是看起来，优先选择能与大规模的均匀分类的实例集合相匹配的小规模测试比较合理，所以整个决策表要尽可能的紧凑。最简单的策略是，在不考虑子集规模的情况下，找到能匹配任意均匀分类的子集的最小测试t。如图18.15所示，即使这样简单，方法已经很有效了。
图18.15 基于餐馆数据的DECISION-LIST-LEARNING算法的学习曲线。并显示了DECISION-TREE-LEARNING算法的曲线作为比较
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
