学习和使用相关性信息

19.4.2 学习和使用相关性信息

我们在本章的介绍中说过，先验知识在学习中很有用，但是它也必须经过学习。为了提供基于相关性的学习的完整情况，我们同样必须给出一个对于决定关系的学习算法。我们现在提出的学习算法是基于直接努力的：寻找与观察一致的最简单的决定关系。一个决定关系PΦQ表明任何与P相匹配的实例也一定与Q相匹配。因此如果每对与左侧的谓词所匹配的元素也与目标谓词相匹配，那么一个决定关系与一个实例集是一致的——即，属于相同的分类。例如，设想我们有对材料样本的电导率测量的实例如下：

最小一致决定是Material∧Temperature  Conductance。还有一个非最小但是一致的决定，即：Mass∧Size∧Temperature  Conductance。它与实例一致是因为质量和尺寸决定密度，而在我们的数据集中没有两种密度相同的不同材料。通常，我们需要一个更大的样本集以消除近似正确的假设。

有几个可能的算法可以用于寻找最小一致决定。最显而易见的方法是在决定关系空间上进行搜索，用一个谓词、两个谓词、依此类推，检验所有的决定关系，直到找到一个一致的决定关系。我们假定使用一个简单的基于属性的表示，如同第十八章中的决策树学习中所使用的。一个决定关系d可以用左侧的属性集合表示，因为假定目标谓词是固定的。图19.8中勾勒了基本算法。

图19.8 一个寻找最小一致决定的算法

该算法的时间复杂度取决于最小一致决定的大小。假定该决定关系有全部n个属性中的p个。那么该算法直到搜索子集A的大小为p时才能找到这个决定关系。一共有个这样的子集；因此算法复杂度是最小决定的大小的指数量级。这表明该问题是 NP 完全的，因此对于一般情况我们不可能期望做得更好。然而，在大多数领域中，可能存在p很小的充分的局部结构（局部结构化域的定义参见第十四章）。

给定一个对决定关系进行学习的算法，学习智能体就有办法构造一个最小假设，在其中可以学习目标谓词。例如，我们可以把MINIMAL-CONSISTENT-DET（最小一致决定）和DECISION-TREE-LEARNING （决策树学习）算法结合起来。于是就生成了一个基于相关性的决策树学习算法RBDTL，首先确定一个最小相关属性集，然后把该集合传递给决策树算法进行学习。与 DECISION-TREE-LEARNING不同的是，RBDTL 同时学习和使用相关性信息，从而使假设空间最小。我们期望 RBDTL 能够比DECISION-TREE-LEARNING学习得更快，事实上也是如此。图19.9显示出了两种算法在随机生成的数据上的学习性能，被学习的函数只依赖于5到16个属性。显然，当所有可用属性都相关时，RBDTL就没有优势了。

图19.9 在随机生成的数据上，RBDTL和DECISION-TREE-LEARNING之间的性能比较，被学习的函数只依赖于5到16个属性

本章只接触了陈述性偏差领域的表面，其目标是理解如何使用先验知识来确定适当的假设空间，可以在其中搜索正确的目标定义。还有很多问题没有得到解答：

• 如何扩展算法以处理噪声？

• 我们能够处理连续值的变量吗？

• 除决定关系以外，其它类型的先验知识可以如何使用？

• 如何才能生成算法以涵盖任意的一阶理论而不止是基于属性的表示？

部分问题会在下一节中着手解决。