习题部分：参阅了网上大佬们的习题答案，然后再自己搞了一下，顺便整理出来。
                                                            表1.1 西瓜数据集

编号      色泽      根蒂      敲声      好瓜

1           青绿      蜷缩      浊响      是
2           乌黑      蜷缩      浊响      是
3           青绿      硬挺      清脆      否
4           乌黑      稍蜷     沉闷     否

1.1   表1.1中若只包含编号为1和4的两个样例，试给出相应的版本空间。

与训练集一致的“假设集合”我们称之为版本空间，首先要求出所有的假设空间，然后在搜索过程中可以不断删除与正例不一致的假设、和与反例一致的假设，最终会得到与训练集一致的假设。由于我们选定了1、4两个样例，于是属性色泽有三种可能：*、青绿、乌黑，根蒂有* 、蜷缩、稍蜷，敲声有* 、浊响、沉闷。（通配符"*"：什么值都合使）
将假设空间用二进制数表示出来，一个属性对应两位二进制数，例如：*为11，青绿为01，乌黑为10（从大佬那里学习到的）......于是假设空间如下：

二进制转十六进制（方便代码实现）如下：0x3f、0x3d、0x3e、0x37、0x3b、0x1f、0x2f、0x35、0x36、0x39、0x3a、0x1d、0x1e、0x2d、0x2e、0x17、0x1b、0x27、0x2b、0x15、0x16、0x19、0x1a、0x25、0x26、0x29、0x2a
于是假设空间可以如此计算：3×3×3+1=28 其中一个假设为，即对应此例是“好瓜”的概念不成立，即“好瓜”不存在。但训练集包含的是正例，所以这种假设不可能出现其中，于是将其剔除而只对27个假设进行讨论。化作二进制可以利用位运算符和逻辑运算符来判断其是否符合版本空间的定义，由此对样例1和4进行处理。样例1的十六进制数为0x15，样例4的十六进制数为0x2a。代码如下：

a=[0x3f,0x3d,0x3e,0x37,0x3b,0x1f,0x2f,0x35,0x36,0x39,0x3a,0x1d,0x1e,0x2d,0x2e,  0x17,0x1b,0x27,0x2b,0x15,0x16,0x19,0x1a,0x25,0x26,0x29,0x2a]
b=[0x15,0x2a]
s=0
for i in a:
    if (i|b[1]) !=i and (i|b[0]) == i:
        s+=1
        print(a.index(i)+1)
print("共",s,"个假设")

结果是序号为2、4、6、8、12、16、20共 7 个假设，分别对应上表查看即可。

1.2 与使用单个合取式来进行假设表示相比，使用“析合范式”将使得假设空间具有更强的表示能力。若使用最多包含k个合取式的析合范式来表达表1.1西瓜分类问题的假设空间，试估算有多少种可能的假设。

合取式（ conJunction）：用合取真值联结词“∧”将两个或两个以上的命题联结起来而形成的命题形式。（来自百科）
析合范式即多个合取式的析取。
此问题可以参考大佬的做法：《机器学习》（周志华）第一章课后习题参考答案，但其是用C语言进行计算实现的。
对于本题，需要去冗余。使用二进制表示每个合取式。共3×4×4=48个合取式，
其中不包含*的合取式有2×3×3=18个。这18个合取式(称为叶子合取式)可以组合成任意的析合范式、合取式。于是我们可以用它们分别与48个基本的合取式进行按位或运算（符号 | ，有1则1），若运算结果为对应的48个基本合取式本身，则记为1，否则记为0，结果为48个18位的二进制数，这些数便是析合范式的表示形式。
我们可以发现本题的假设空间足足有2¹⁸-1=262143辣么大！因为这是18位二进制数所能表达的最大范围，析合范式不考虑空集，故减去了1。
以上是对于析合范式新定义的一种表达方式。下面就是历遍的问题了。下面就参考上面链接的文章吧_{可能还未必看得懂}！
咳咳，我来梳理一遍解题思路：
1、首先有3×4×4=48种假设（合取式），然后题目要求从48种假设中取k种假设组合成一个新的假设，这些新假设放在一起，就形成一个假设空间
2、但这种假设空间是有冗余的，于是我们要剔除通配，即*造成的冗余，所以映射出2×3×3=18种叶子合取式（有具体值，不存在通配），对18种叶子假设进行析取
3、最后，再对析取出的重复项进行剔除，得到无冗余的假设空间

1.3   若数据包含噪声，则假设空间中有可能不存在与所有训练样本都一致的假设。在此情形下，设计一种归纳偏好用于假设选择。

有噪声，所以就先去噪，那么如何去噪，方法挺多的。就说一种，若出现同属性而标记不同，可以认为它属于最接近它的几个数据的属性，或者将它们去掉，又或者只去掉反例。

1.4   本章1.4节在论述“没有免费的午餐”定理时，默认使用了“分类错误率”作为性能度量来对分类器进行评估。若换用其他性能度量l，则式（1.1）将改为如P₁₉1.4题图所示
试证明“没有免费的午餐定理”仍成立。
引理1：在二分类问题下，对任意性能度量指标l，l(h(x)=f(x))+l(h(x)≠f(x))=A,A为某一常数。

对于二分类问题，NFL假设目标函数f均匀分布，对于有X个样本的二分类问题，f共有2^X种情况。
对于均匀分布即假设一致的概率 P(f(x)=h(x))=0.5。
此时， ∑fl(h(x),f(x))=0.5∗2X∗(l(h(x)=f(x))+l(h(x)≠f(x)))
其中(l(h(x)=f(x))+l(h(x)≠f(x)))应为常数A，才得到引理，“没有免费的午餐定理”仍成立。引理可由 l(0,0)=l(1,1),l(0,1)=l(1,0)推出l(0,0)+l(0,1)=l(1,1)+l(1,0)，再设l(0,0)+l(0,1)=l(1,1)+l(1,0)=A 得到。

1.5   试述机器学习能在互联网搜索的哪些环节起作用

1、对文本提取的信息进行处理，语义分析与情感分析，再反馈给搜索引擎，提交信息；
2、根据用户的点击量与浏览频率，生成推荐信息，得到用户感兴趣程度，对搜索出的内容进行综合分析排序；
3、提高问题与信息的匹配程度，提高搜索的精度，对信息匹配进行优化；