【摘要】：尽管决定关系支持了关于所有巴西人或者给定温度下所有铜块的一般结论，但是它们当然无法从单一实例中为所有国籍或所有温度和材料生成一个一般性的预测理论。它们的主要影响可以视为对学习智能体需要考虑的假设空间加以限定。决定关系指定了一个充分的基本词汇表，根据它可以构造出关于目标谓词的假设。直观地，假设空间规模的缩减能够使目标谓词的学习更容易。
尽管决定关系支持了关于所有巴西人或者给定温度下所有铜块的一般结论，但是它们当然无法从单一实例中为所有国籍或所有温度和材料生成一个一般性的预测理论。它们的主要影响可以视为对学习智能体需要考虑的假设空间加以限定。例如，在对电导率进行预测时，只需要考虑材料和温度而可以忽略质量、所有者、一周的不同日期、现任总统等等。假设当然可以包含那些依次由材料和温度决定的项目，诸如分子结构、热能或自由电子密度等。决定关系指定了一个充分的基本词汇表，根据它可以构造出关于目标谓词的假设。这个陈述可以这样来证明：证明一个给定的决定关系与下面的陈述在逻辑上是等价的——目标谓词的正确定义是所有可以用出现在决定关系左侧的谓词来表达的定义集中的一个元素。
直观地，假设空间规模的缩减能够使目标谓词的学习更容易。使用计算学习理论（第18.5节）的基本结果，我们可以量化可能的收益。首先，回忆一下对于布尔函数，需要 log (|H|)个实例才能收敛到一个合理的假设，其中|H|是假设空间的大小。如果学习者有n个用来构造假设的布尔特征，则在没有更多的限制条件的时候，|H|=O(22n )，所以实例的个数是O(2n)。如果决定关系的左侧包含d个谓词，那么学习者只需要O(2d)个实例，减少了O(2n − d)。对于有偏差的假设空间来说，比如合取的有偏差空间，缩减不会这么剧烈，但是仍然很显著。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
