归纳偏好

机器学习本质上是归纳推理。从有限的已知数据得到普遍的知识，不能从逻辑推理得到。比如从犹太人a很聪明，犹太人b很聪明，犹太人c很聪明，推出所有犹太人都很聪明。这个推理不是必然成立的，里面包含了某种偏好它才能成立。

机器学习中把这样的偏好称为归纳偏好。归纳偏好的严格定义：已知数据+归纳偏好T机器学习的结果。这里的T表示演绎推理，归纳偏好是使得上面这个推理式成立的最弱的命题。

如果没有归纳偏好，从数据到学习结果是归纳推理，加上偏好，数据就能通过演绎推理得到结果。任何的机器学习算法，都存在归纳偏好。不同的算法，归纳偏好可能不一样，机器学习的结果也不一样。

作为搜索的概念学习

下面通过具体的例子来说明什么是归纳偏好。

目标概念：适合水上运动

样例   天气   温度   湿度  风力   水温   天气预报    适合水上运动

1        晴       暖       中      强       暖       相同          是

2        晴       暖       高      强       暖       相同          是

3        雨       冷       高      强       暖       变化          否

4        晴       暖       高      强       冷       变化          是

这里一共有六个属性：天气，温度，湿度，风力，水温，天气预报。

天气的取值范围为：晴、阴、雨；

温度的取值：热、冷；

湿度的取值：中、高；

风力的取值：强、弱；

水温取值：热、冷；

天气预报取值：相同、变化。

适合运动这个概念实际上是个六元函数，各个变元的取值范围如上所示，而函数的取值为“是”或“否”，也可看作1或0。满足这些条件的六元函数数量很多，机器学习就是从这些样本中总结出规律，找到目标函数（亦即学会目标概念），使得对新的样例，亦可以判断出那天是否适合运动。

学习的过程可看作在假设空间搜索（人工智能把这些函数构成的集合称为假设空间），目标是搜到正确的假设。由于假设空间往往包含数量极多的假设，所以需要合适的搜索策略，才能更快地找到目标假设。

包含是概念或假设之间一种很重要的关系。比如动物这个概念包含人这个概念，生物又包含人这个概念。用专业的术语，包含关系定义了假设空间的一个偏序（即这个关系是自反、反对称和传递的）。利用这个偏序关系，能有效地搜索假设空间。

下面介绍两种具体的学习算法。

Find-S算法

在Find-S算法中，假设可这样表示：

<晴，冷，中，强，暖，变化>，这时表示只有当每个属性取这个相应的值，才适合运动。

也可用问号代替某个值，比如，<晴，？，中，？，暖，变化>，问号表示相应的属性取任意一个值都行。

极端的情况是，<？，？，？，？，？，？>，表示任何情况都适合运动，即每一个样例都是正例。

另一种极端的情况是，<Æ，Æ，Æ，Æ，Æ，Æ>，表示任何情况都不适合运动，即每个样例都是反例。

能用上面方式表示的假设构成了假设空间H。

Find-S算法将h初始化为最特殊的假设

h←<Æ，Æ，Æ，Æ，Æ，Æ>，即任何一个样例都是反例

第一个样例是正例（晴，暖，中，强，暖，相同），所以将h泛化，使它能容纳这个样例。

h←<晴，暖，中，强，暖，相同>，即除了这个样例外，其他样例都是反例

第二个样例（晴，暖，高，强，暖，相同）也是正例，所以将h进一步泛化，使其能容纳这个例子

h←<晴，暖，？，强，暖，相同>

第三个是反例（雨，冷，高，强，暖，变化），所以h无需改变。假设h简单地忽略每个反例，看上去有点奇怪。请注意，事实上这时假设仍与这个样例一致，即正确地将其划分为反例。

第四个是正例（晴，暖，高，强，冷，变化），进一步将h泛化，

h←<晴，暖，？，强，？，？>

h=<晴，暖，？，强，？，？>，这就是Find-S算法在这些样例上学到的概念，即当天气为晴天、气温为暖和、风力为强风时适合水上运动，水温湿度天气预报等因素没有影响。

       Find-S算法实际上是寻找和训练样例一致的最特殊的假设。

候选消除算法

候选消除算法和Find-S算法的假设表示方法相同。Find-S算法只是输出和训练样例一致的多个假设中的一个，而候选消除算法输出H中所有和训练样例一致的假设。

Find-S算法从最特殊的假设出发，逐步将其泛化。候选消除算法，则同时从最特殊假设和最一般假设出发，遇到正例则将特殊假设泛化，遇到反例则将一般假设特殊化。最后假设空间H剩下的和特殊假设以及一般假设一致的那些假设就是学习的结果。

以上面的适宜运动概念为例。

S0：  <Æ，Æ，Æ，Æ，Æ，Æ>

                                ↑

G0:   <？，？，？，？，？，？>

   第一个样例为正例：（晴，暖，中，强，暖，相同），所以将S0泛化，G0不变：

S1：  <晴，暖，中，强，暖，相同>

                                ↑

G1:   <？，？，？，？，？，？>

第二个样例为正例：（晴，暖，高，强，暖，相同），将S1泛化，G1不变：

S2：  <晴，暖，？，强，暖，相同>

                                ↑

G2:   <？，？，？，？，？，？>

第三个样例为反例：（雨，冷，高，强，暖，变化），S2不变，将G2特殊化。注意，将G2特殊化时，它的假设要比S2更一般，否则不能覆盖以前的正例。

S3：                       <晴，暖，？，强，暖，相同>

                                   ↗                  ↑              ↖

G3:   <晴，?，?，?，?，?>，<?，暖，?，?，?，?>，<?，?，?，?，?，相同>

第四个样例为正例：（晴，暖，高，强，冷，变化），将S3泛化，再将G3中和S4不一致的假设删掉，得到

S4：                    <晴，暖，？，强，？，？>

                                   ↗                       ↖

G4:              <晴，?，?，?，?，?>， <?，?，?，?，?，相同>

训练完毕，所以H空间和S4、G4同时保持一致的假设有六个：

S4：                     <晴，暖，？，强，？，？>

↗            ↑          ↖

     <晴，?，?，强，?，?>，<晴，暖，?，?，?，?>，<?，暖，?，强，?，?>      

                        ↖         ↗                  ↖        ↗

G4:              <晴，?，?，?，?，?>， <?，?，?，?，?，相同>

这就是使用候选消除算法学习的结果，它包含六个假设，还没学到目标概念。那么如何使用呢？比如，对于下面新的样例，它将如何判断？

样例   天气   温度   湿度  风力   水温   天气预报    适合水上运动

a       晴      暖      中     强      冷      变化           ？

b       雨      冷      中     弱      暖      相同           ？

c       晴      暖      中     弱      暖      相同           ？

d       晴      冷      中     强      暖      相同           ？

所有假设都将样例a划成正例，将样例b划成反例。有2个假设将样例d划成正例，4个假设将其划成反例，所以我们倾向于将其划成反例。一半假设将样例c划成正例，一半将其划成反例，所以无法判断。

两种算法的归纳偏好

上面两种算法中，假设空间H都没有包含所有假设，目标概念有可能不在假设空间H中。

比如当天气为晴或者气温为暖时，适合水上运动。这个概念就无法用上面的方法表示。因为上面的假设表示方法只能表示属性的合取，无法表示属性的析取。

适合水上运动这概念涉及六个属性，各个属性的取值分别有3、2、2、2、2、2种可能。以这六个属性的取值为变量，0和1为因变量的六元函数一共有2^(3x2x2x2x2x2)个。而按上面的表示法，假设空间H一共有4x3x3x3x3+1个假设，即只有这么多函数。如果目标概念不在假设空间H中，则这两种算法都无法搜索到。

所以目标概念在空间H中，是两种算法共同的归纳偏好。除此之外，Find-S算法包含了更多的偏好，它倾向于将新样例视为反例。