阅读笔记-机器学习-第2章-概念学习和一般到特殊序

1. 问题举例
    Aldo有时会去进行水上运动，天气情况对于Aldo选择是否去水上运动有很大的作用，可以想象，如果天气好，很可能Aldo就会去，如果天气恶劣，Aldo就不会去。现在已知若干天的天气情况，和Aldo是否去参与了水上运动的记录，根据新的一天的天气情况来预测Aldo是否会去进行水上运动。下面就是一些样本：        

2. 概念学习
    概念的学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。
    布尔函数一般形式：F(b1, b2, ..., bn)，其中 bi的定义域为{0,1}i，F的值域为{0, 1}。 在一般的定义域上的，取值在 {0, 1} 中的函数也叫做布尔值函数，概念学习定义中的布尔函数指定就这个，主要是规定学习的问题目标是布尔的，反应在上面的样本中，就是Yes或者No。
    实际上，很多机器学习问题都可以归结为概念学习，对应也有很多机器学习方法，这一章主要是介绍一些机器学习的基本理论，所以，仅仅涉及了Find-S和候选消除算法这两个机器学习方法。

3. Find-S：寻找极大特殊假设
    首先，给出Find-S算法的代码

1
. 将h初始化为H中特殊的假设

2
. 对每个正例x
      对h的每个属性ai
         如果x满足ai，那么不做任何处理
          否则将h中的ai替换为x满足的下一个更一般的假设

3
. 输出假设h

    然后，应用Find-S算法到第1节中的问题
    最特殊的假设：   h = <Æ, Æ, Æ, Æ, Æ, Æ, Æ>
    经过第1个样本： h = <Sunny, Warm, Normal, Strong, Warm, Same>
    经过第2个样本： h = <Sunny, Warm, ?, Strong, Warm, Same>
    经过第3个样本： 这是一个反例，h不变。实际上Find-S忽略每一个反例。
    经过第4个样本： h = <Sunny, Warm, ?, Strong, ?, ?>
    最后，分析Find-S算法
    归纳偏置是假定目标概念在假设空间（即属性的析取式），而且目标概念是满足样本的极大特殊假设。
    只得到假设空间中的一个假设，而且是极大特殊的那个。对含有噪声的数据无能为力。要求属性值和输出值都是离散的。

4. 候选消除算法

    首先，给出算法代码
    列表候选消除算法

1
. 变型空间VersionSpace
<-
包含H中所有假设的列表

2
. 对每个训练样例
<
x, c
<
x
>>

   从变型空间中移除所有h(x)
!=
c(x)的假设h

3
. 输出 VersionSpace中的假设列表 

    使用变型空间的候选消除算法 

把G集合初始化为H中的极大一般假设
把S集合初始化为H中的极大特殊假设
对每个训练样例d，进行以下操作：
·如果d是正例
    ·从G中移去所有与d不一致的假设
    ·对S中每个与d不一致的假设s
        ·从S中移去s
        ·把s的所有的极小一般化式h加入到S中，其中h满足：h与d一致，而且G的某个成员比h更一般
        ·从S中移去所有这样的假设：它比S中另一假设更一般
·如果d是反例
    ·从S中移去所有与d不一致的假设
    ·对G中每个与d不一致的假设g
        ·从G中把移去g
        ·把g的所有极小特殊化式h加入到G中，其中h满足：h与d一致，而且S的某个成员比h更特殊
        ·从G中移去所有这样的假设：它比G中另一假设更特殊

     列表候选消除算法，使用所有样本，来排除不一致的假设。
     变型空间的候选算法，其背后的理论来自于数学中的偏序方面的知识，通过不断更新特殊集合S和一般集合G，来得到满足所有样本的假设集合。
     然后，具体举例略。
     最后，分析候选消除算法
     归纳偏置是：假设目标概念h在给定的假设空间H（比如：属性的析取）中。
     只得到假设空间中的所有与样本一直的假设集合，而不是一个假设。对含有噪声的数据无能为力。要求属性值和输出值都是离散的。
 5. 无偏学习的无用性
     学习器如果不对目标概念的形式做预先的假定，它从根本上无法对未见实例进行分类。
    一个学习器要做到无偏，那么搜索空间就是书中提到的X的幂集，其中X为样本空间的大小，以第1小节为例，X=3*2*2*2*2*2=96，搜索空间就是2^96，对于这样的搜索空间，对于任何新的预测数据，都会有K个假设预测为正例也会有K个假设预测为负例，因为无论如何候选消除，搜索空间仍旧是对称的。
    之所以有偏学习是有用的，是因为开始对目标概念的形式做了假设，比如假设目标函数是属性的析取式，这也是直观上有一定的合理性，而无偏的学习则没有这种合理的假设，是盲目的做法，因此有偏的有用性，是因为假设，有用性的大小就要看假设的准确度了，这个准确度就要看人对学习问题的理解了，理解的好，运气好，学的就好，假设空间更合理一些，或是运气差一些，假设空间就差一些。