1.1 表1.1中若只包含编号为1和4的两个样例，试给出相应的版本空间。
解：对应的样本数据集如下
色泽有3（青绿，乌黑，* ）种取值，根蒂有3(蜷缩，稍蜷，* ）种取值，敲声3（浊响，沉闷，* ）种，那么假设规模一共有
（考虑空集)，28种
对应的版本空间为7种
分别为
1.色泽=青绿 根蒂=蜷缩 敲声=浊响
2.色泽=青绿 根蒂=蜷缩 敲声= *
3.色泽=青绿 根蒂=* 敲声= 浊响
4.色泽= * 根蒂= 蜷缩 敲声= 浊响
5.色泽= * 根蒂= * 敲声= 浊响
6.色泽= * 根蒂= 蜷缩 敲声= *
7.色泽= 青绿 根蒂= * 敲声= *
1.2 与使用单个合取式来进行假设表示相比，使用“析合范式”将使得假设空间具有更强的表示能力。
例如：
好瓜←→（(色泽=)∧(根蒂=蜷缩)∧(敲声=)）∨（(色泽=乌黑)∧(根蒂=*)∧(敲声=沉闷)）会把“（(色泽=青绿)∧(根蒂=蜷缩)∧(敲声=清脆)）”以及“（(色泽=乌黑)∧(根蒂=硬挺)∧(敲声=沉闷)）”都分类为“好瓜”。若使用最多包含k个合取式的析合范式来表达表1.1西瓜分类问题的假设空间，试估算共有多少种可能的假设。
解：西瓜的三个不同属性的特征分别记为(A1,A2),(B1,B2,B3),(C1,C2,C3)，这样一共有2x3x3,18种不同的组合，如果将属性泛化考虑 进去，(A1,A2，* ),(B1,B2,B3，* ),(C1,C2,C3，* )那么一共就有3x4x4,48种不同的组合。
48种情况分别包括
基本组合：18种
一个属性泛化假设：2x3+3x3+2x3,21种
两种属性泛化假设：2+3+3，8种
三个属性泛化假设：1种
如果不考虑冗余则一共有
但是书本中提醒了还要考虑冗余情况，情况就没有那么简单了。
首先我们可以很轻松确定k的上界，k的最大取值为18，能表达最小的假设空间为18种基本组合，如果加入第19种的话，那么必然会产生表达冗余。因此k的取值范围为【1，18】
考虑最极端也最简单的情况，当k=1时，相当于在48个种排列组合取一种，必然不会有冗余的考虑即
k=1时，有48种
k=18时，有1种
中间的2~17的取值范围考虑起来会相当复杂，一种朴素的思想就算用计算机暴力迭代，遍历所有的排列组合，然后判断他们是否冗余。但是在计算机表达上也是有一定的转换
一 、首先构造一个18x48的矩阵来表达数据，比如
100000000000000000 表示（青绿，蜷缩，浊响）
111111111111111111 表示 （ * ， * ，*）
二、用itertools.combinations方法放回所有的排列组合迭代器
三、将每一种迭代结果相加(析取运算），存放在一个数组中，该数组的作用相当于一个set，不允许出现重复的元素
代码
import itertools
import time
#将数存储为数组
def method(value):
# 将字符串变成数字列表，使其具有数字加法运算
result = []
for i in range(len(value)):
result.append(eval(value[i]))
return result
#用类表示编码，并定义重载的运算符 + 为析取
class WMcode:
val = ''
len = 0
def __init__(self, strv):
self.val = method(strv)
def __add__(self,other): #析取运算
strv = []
for i in range(len(self.val)):
addr = self.val[i]+other.val[i]
if addr >= 2:
addr = 1
strv.append(str(addr))
return WMcode(strv)
#对48中假设进行编码
nodes = [WMcode('100000000000000000'),WMcode('010000000000000000'),WMcode('001000000000000000'),
WMcode('000100000000000000'),WMcode('000010000000000000'),WMcode('000001000000000000'),
WMcode('000000100000000000'),WMcode('000000010000000000'),WMcode('000000001000000000'),
WMcode('000000000100000000'),WMcode('000000000010000000'),WMcode('000000000001000000'),
WMcode('000000000000100000'),WMcode('000000000000010000'),WMcode('000000000000001000'),
WMcode('000000000000000100'),WMcode('000000000000000010'),WMcode('000000000000000001'),
WMcode('100000000100000000'),WMcode('010000000010000000'),WMcode('001000000001000000'),
WMcode('000100000000100000'),WMcode('000010000000010000'),WMcode('000001000000001000'),
WMcode('000000100000000100'),WMcode('000000010000000010'),WMcode('000000001000000001'),
WMcode('111000000000000000'),WMcode('000111000000000000'),WMcode('000000111000000000'),
WMcode('000000000111000000'),WMcode('000000000000111000'),WMcode('000000000000000111'),
WMcode('100100100000000000'),WMcode('010010010000000000'),WMcode('001001001000000000'),
WMcode('000000000100100100'),WMcode('000000000010010010'),WMcode('000000000001001001'),
WMcode('111000000111000000'),WMcode('000111000000111000'),WMcode('000000111000000111'),
WMcode('100100100100100100'),WMcode('010010010010010010'),WMcode('001001001001001001'),
WMcode('111111111000000000'),WMcode('000000000111111111'),WMcode('111111111111111111')]
# （青绿，蜷缩，浊响） （青绿，稍蜷，浊响） （青绿，硬挺，浊响）
# （青绿，蜷缩，清脆） （青绿，稍蜷，清脆） （青绿，硬挺，清脆）
# （青绿，蜷缩，沉闷） （青绿，稍蜷，沉闷） （青绿，硬挺，沉闷）
# （乌黑，蜷缩，浊响） （乌黑，稍蜷，浊响） （乌黑，硬挺，浊响）
# （乌黑，蜷缩，清脆） （乌黑，稍蜷，清脆） （乌黑，硬挺，清脆）
# （乌黑，蜷缩，沉闷） （乌黑，稍蜷，沉闷） （乌黑，硬挺，沉闷）
# （*，蜷缩，浊响） （*，稍蜷，浊响） （*，硬挺，浊响）
# （*，蜷缩，清脆） （*，稍蜷，清脆） （*，硬挺，清脆）
# （*，蜷缩，沉闷） （*，稍蜷，沉闷） （*，硬挺，沉闷）
# (青绿，*，浊响) （青绿，*，清脆） （青绿，*，沉闷）
# (乌黑，*，浊响) （乌黑，*，清脆） （乌黑，*，沉闷）
# (青绿，蜷缩，*) （青绿，稍蜷，*） （青绿，硬挺，*）
# (乌黑，蜷缩，*) （乌黑，稍蜷，*） （乌黑，硬挺，*）
# (*,*,浊响) (*,*,清脆) (*,*,沉闷)
# (*,蜷缩，*) (*,稍蜷,*) (*,硬挺,*)
# (青绿，*，*) （乌黑，*，*） （*，*，*）
#合取式数量k
for k in [1,2,3,4]:
#存储最终结果的集合A
A = []
time_start=time.time() #开始计时
comb = list(itertools.combinations(nodes,k))
for i in range(len(comb)):
WMadd = WMcode('000000000000000000')
for j in range(k):
WMadd = WMadd + comb[i][j]
for allval in A: #若A中已经存在当前假设，则舍去，因为这是亢余
if WMadd.val == allval.val:
break
else:
A.append(WMadd)
time_end=time.time() #结束计时
print("K={},一共有{}组合".format(str(k),str(len(A))))
print('花费时间',time_end-time_start)
最后由于这是一种规模是指数级的迭代，当k规模大的时候就跑不动了，看图，当k的取值为4的时候就已经需要10多分钟了
1.3 若数据包含噪声，则假设空间中有可能不存在与所有训练样本都一致的假设。在此情形下，试设计一种归纳偏好用于假设选择。
解：归纳偏好以我个人的理解就是对于不同的算法而言，a算法的效果比b好，但是a的内存开销和时间开销比b大，如何评价对于同一个问题算法的好坏，就是看重视哪一方面，重视效果（准确率）那么就认为a好，折中考虑效率就认为b好。因此归纳偏好在我理解就是最佳模型的基准。
回到问题，对于此情况，我认为精度高的归纳偏好为假设选择，即和训练样本假设最接近的。
1.4 本章1.4节在论述“没有免费的午餐”定理时，默认使用了“分类错误率”作为性能度量来对分类器进行评估。若换用其他性能度量l,试证明没有免费的午餐”定理仍成立。
解：证明：
在证明定理之前，先构造一个引理：
引理1：在二分类问题下，对任意性能度量指标l，l(h(x)=f(x))+l(h(x)≠f(x))=A,Al(h(x)=f(x))+l(h(x)≠f(x))=A,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
即可得：
l(h(x)=f(x))+l(h(x)≠f(x))=A
证毕.
现在证明定理：
1.5 试述机器学习能在互联网搜索的哪些环节起作用
解：机器学习对搜索引擎可进行的优化
1.搜索引擎直接给出搜索的答案：这里用到神经网络，它可以通过分析大量数据从而完成特定的任务，如从相关网页中获取长句子和段落，然后提出有关问题答案的信息。
2.直接进行图片、视频（等多元数据）的搜索：图片的识别已经是常见的技术了，那直接从视频中提出信息呢？谷歌推出Video Intelligence API，不仅可以从视频中提取特定的信息，还能总结视频的脉络、记录视频中的场景，从而对视频进行准确的分类。
3.更精准的排序（也可成为「精准营销」的部分）：如使用神经网络、决策树等为基础的网页排序算法：RankNet, LambdaRank 和LambdaMART。2015年，谷歌推出RankBrain，它可以选择最适合当前搜索类型的结果，相当于为每个搜索都提供个性化的算法组合。
4.对用户行为进行综合分析（如历史搜索数据、点击模式、身份信息等进行结构化信息整合）
5.对垃圾网站的筛选（模式识别）
参考文章：
https://zhuanlan.zhihu.com/p/27900874
https://blog.csdn.net/qq_26371477/article/details/102292685
https://blog.csdn.net/dicker6315/article/details/81265066
