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

表1.1 西瓜数据集

1. 求假设空间
   (1)每一个属性的所有取值分别组合形成所有可能性结果。
   “色泽” ： “青绿”、“乌黑”
   “根蒂” ： “蜷缩”、“稍蜷”
   “敲声” ： “浊响”、“沉闷”
   总共结果个数：\(2∗2∗2=8\)

色泽＝青绿，根蒂＝蜷缩，敲声＝浊响
色泽＝青绿，根蒂＝蜷缩，敲声＝沉闷
色泽＝青绿，根蒂＝稍蜷，敲声＝浊响
色泽＝青绿，根蒂＝稍蜷，敲声＝沉闷
色泽＝乌黑，根蒂＝蜷缩，敲声＝浊响
色泽＝乌黑，根蒂＝蜷缩，敲声＝沉闷
色泽＝乌黑，根蒂＝稍蜷，敲声＝浊响
色泽＝乌黑，根蒂＝稍蜷，敲声＝沉闷

(2)属性取值至少含一个为“无论去什么值都合适”（即属性值为通配符“*”）的结果集合
“色泽” ：“*”、 “青绿”、“乌黑”
“根蒂” ：“*”、 “蜷缩”、“稍蜷”
“敲声” ：“*”、 “浊响”、“沉闷”
总共结果个数：\(3∗3∗3-8=19\)

色泽＝*，   根蒂＝*，   敲声＝*
色泽＝青绿，根蒂＝*，   敲声＝*
色泽＝乌黑，根蒂＝*，   敲声＝*
色泽＝*，   根蒂＝蜷缩，敲声＝*
色泽＝*，   根蒂＝稍蜷，敲声＝*
色泽＝*，   根蒂＝*，   敲声＝浊响
色泽＝*，   根蒂＝*，   敲声＝沉闷
色泽＝青绿，根蒂＝蜷缩，敲声＝*
色泽＝青绿，根蒂＝稍蜷，敲声＝*
色泽＝乌黑，根蒂＝蜷缩，敲声＝*
色泽＝乌黑，根蒂＝稍蜷，敲声＝*
色泽＝青绿，根蒂＝*，   敲声＝浊响
色泽＝青绿，根蒂＝*，   敲声＝沉闷
色泽＝乌黑，根蒂＝*，   敲声＝浊响
色泽＝乌黑，根蒂＝*，   敲声＝沉闷
色泽＝*，   根蒂＝蜷缩，敲声＝浊响
色泽＝*，   根蒂＝蜷缩，敲声＝沉闷
色泽＝*，   根蒂＝稍蜷，敲声＝浊响
色泽＝*，   根蒂＝稍蜷，敲声＝沉闷

(3)所有属性值都无法取到的结果，即为空集，一个假设空间有且仅有一个
“色泽” ： “Ø”
“根蒂” ： “Ø”
“敲声” ： “Ø”
总共结果个数：1

色泽＝Ø，根蒂＝Ø，敲声＝Ø

假设空间共有：\(8+19+1=28\) 或 \((2+1)*(2+1)*(2+1)+1=28\)

色泽＝青绿，根蒂＝蜷缩，敲声＝浊响
色泽＝青绿，根蒂＝蜷缩，敲声＝沉闷
色泽＝青绿，根蒂＝稍蜷，敲声＝浊响
色泽＝青绿，根蒂＝稍蜷，敲声＝沉闷
色泽＝乌黑，根蒂＝蜷缩，敲声＝浊响
色泽＝乌黑，根蒂＝蜷缩，敲声＝沉闷
色泽＝乌黑，根蒂＝稍蜷，敲声＝浊响
色泽＝乌黑，根蒂＝稍蜷，敲声＝沉闷
色泽＝*，   根蒂＝*，   敲声＝*
色泽＝青绿，根蒂＝*，   敲声＝*
色泽＝乌黑，根蒂＝*，   敲声＝*
色泽＝*，   根蒂＝蜷缩，敲声＝*
色泽＝*，   根蒂＝稍蜷，敲声＝*
色泽＝*，   根蒂＝*，   敲声＝浊响
色泽＝*，   根蒂＝*，   敲声＝沉闷
色泽＝青绿，根蒂＝蜷缩，敲声＝*
色泽＝青绿，根蒂＝稍蜷，敲声＝*
色泽＝乌黑，根蒂＝蜷缩，敲声＝*
色泽＝乌黑，根蒂＝稍蜷，敲声＝*
色泽＝青绿，根蒂＝*，   敲声＝浊响
色泽＝青绿，根蒂＝*，   敲声＝沉闷
色泽＝乌黑，根蒂＝*，   敲声＝浊响
色泽＝乌黑，根蒂＝*，   敲声＝沉闷
色泽＝*，   根蒂＝蜷缩，敲声＝浊响
色泽＝*，   根蒂＝蜷缩，敲声＝沉闷
色泽＝*，   根蒂＝稍蜷，敲声＝浊响
色泽＝*，   根蒂＝稍蜷，敲声＝沉闷
色泽＝Ø，   根蒂＝Ø，   敲声＝Ø

2. 求版本空间
   (1) 删除与正例不一致的假设。
   正例：色泽＝青绿，根蒂＝蜷缩，敲声＝浊响，好瓜=是
   要删除的项：

2.	色泽＝青绿，根蒂＝蜷缩，敲声＝沉闷
3.	色泽＝青绿，根蒂＝稍蜷，敲声＝浊响
4.	色泽＝青绿，根蒂＝稍蜷，敲声＝沉闷
5.	色泽＝乌黑，根蒂＝蜷缩，敲声＝浊响
6.	色泽＝乌黑，根蒂＝蜷缩，敲声＝沉闷
7.	色泽＝乌黑，根蒂＝稍蜷，敲声＝浊响
8.	色泽＝乌黑，根蒂＝稍蜷，敲声＝沉闷
11.	色泽＝乌黑，根蒂＝*，   敲声＝*
13.	色泽＝*，   根蒂＝稍蜷，敲声＝*
15.	色泽＝*，   根蒂＝*，   敲声＝沉闷
17.	色泽＝青绿，根蒂＝稍蜷，敲声＝*
18.	色泽＝乌黑，根蒂＝蜷缩，敲声＝*
19.	色泽＝乌黑，根蒂＝稍蜷，敲声＝*
21.	色泽＝青绿，根蒂＝*，   敲声＝沉闷
22.	色泽＝乌黑，根蒂＝*，   敲声＝浊响
23.	色泽＝乌黑，根蒂＝*，   敲声＝沉闷
25.	色泽＝*，   根蒂＝蜷缩，敲声＝沉闷
26.	色泽＝*，   根蒂＝稍蜷，敲声＝浊响
27.	色泽＝*，   根蒂＝稍蜷，敲声＝沉闷
28.	色泽＝Ø，   根蒂＝Ø，   敲声＝Ø

保留的项：

1.	色泽＝青绿，根蒂＝蜷缩，敲声＝浊响
9.	色泽＝*，   根蒂＝*，   敲声＝*
10.	色泽＝青绿，根蒂＝*，   敲声＝*
12.	色泽＝*，   根蒂＝蜷缩，敲声＝*
14.	色泽＝*，   根蒂＝*，   敲声＝浊响
16.	色泽＝青绿，根蒂＝蜷缩，敲声＝*
20.	色泽＝青绿，根蒂＝*，   敲声＝浊响
24.	色泽＝*，   根蒂＝蜷缩，敲声＝浊响

(2) 删除与反例一致的假设。
反例：色泽＝乌黑，根蒂＝稍蜷，敲声＝沉闷，好瓜=否
要删除的项：

9.	色泽＝*，   根蒂＝*，   敲声＝*

保留的项：

1.	色泽＝青绿，根蒂＝蜷缩，敲声＝浊响
10.	色泽＝青绿，根蒂＝*，   敲声＝*
12.	色泽＝*，   根蒂＝蜷缩，敲声＝*
14.	色泽＝*，   根蒂＝*，   敲声＝浊响
16.	色泽＝青绿，根蒂＝蜷缩，敲声＝*
20.	色泽＝青绿，根蒂＝*，   敲声＝浊响
24.	色泽＝*，   根蒂＝蜷缩，敲声＝浊响

则版本空间为：

1.	色泽＝青绿，根蒂＝蜷缩，敲声＝浊响
10.	色泽＝青绿，根蒂＝*，   敲声＝*
12.	色泽＝*，   根蒂＝蜷缩，敲声＝*
14.	色泽＝*，   根蒂＝*，   敲声＝浊响
16.	色泽＝青绿，根蒂＝蜷缩，敲声＝*
20.	色泽＝青绿，根蒂＝*，   敲声＝浊响
24.	色泽＝*，   根蒂＝蜷缩，敲声＝浊响

---

1.2 与使用单个合取式来进行假设表示相比，使用“析合范式”将使得假设空间具有更强的表示能力。例如

好瓜←→（(色泽=)∧(根蒂=蜷缩)∧(敲声=)）∨（(色泽=乌黑)∧(根蒂=*)∧(敲声=沉闷)）会把“（(色泽=青绿)∧(根蒂=蜷缩)∧(敲声=清脆)）”以及“（(色泽=乌黑)∧(根蒂=硬挺)∧(敲声=沉闷)）”都分类为“好瓜”。

若使用最多包含k个合取式的析合范式来表达表1.1西瓜分类问题的假设空间，试估算共有多少种可能的假设。

合取：\(\wedge\)，求交集
析取：\(\vee\)，求并集
析合范式：多个合取式进行析取
合析范式：多个析取式进行合取

(1) 假设空间大小：\((2+1)*(3+1)*(3+1)+1=49\)，但样例中已经包含了正例，所以可以不考虑空集情况，即假设空间大小为48，所以k的取值为[1, 48]。
但这种情况明显存在冗余。若不考虑冗余情况，假设总数就是从48个合取式中，取出k个进行组合并求和，共有\(\sum_{k=1}^{48}C_{48}^k-1=2^{48}-1\)(这里排除了空集的情况，所以需要减一)。
(2) 这里题目要求注意冗余的情况，即\((A=a)\vee(A=*)\)与\((A=*)\)等价。其实去除冗余情况，就是只考虑属性值都为确定值的情况，而不考虑通配的情况。
冗余举例：

[(色泽=*)∧(根蒂=蜷缩)∧(敲声=沉闷)] ∨ [(色泽=乌黑)∧(根蒂=蜷缩)∧(敲声=沉闷)]
= (色泽=*)∧(根蒂=蜷缩)∧(敲声=沉闷)

西瓜三种属性，共有\(2*3*3=18\)种组合，任何一个组合互不相干。而对于西瓜的判断只有“好瓜”和“坏瓜”两种，是典型的二分类问题，所以可以构造一个\(2^{18}\)的函数空间，其假设总数的最大值也就是\(\sum_{k=1}^{18}C_{18}^k-1=2^{18}-1=262143\)（这里也要排除空集的情况）。

---

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

噪声数据：数据中存在着错误或异常(偏离期望值)的数据。其实就是脱离真实目标函数的点。
解决方法无非就是对数据降噪。（这里对题目的理解可能不太对，题目好像是希望在一个完全不符合训练样本的假设空间中，重新定义一种归纳偏好，这里还需要进行探讨）
(1) 即对偏离训练样本距离过远的假设进行删除，选择与训练集中正例最大程度一致的假设作为其归纳偏好。
(2) 也可以选择属性值相同，但结果不同的几组样例，根据训练集进行调整，符合的保留，不符合的删除。

---

1.4 本章1.4节在论述“没有免费的午餐”定理时，默认使用了“分类错误率”作为性能度量来对分类器进行评估。若换用其他性能度量l，则式（1.1）将改为

\(E_{ote}(ε_a|X,f)=\sum_h\sum_{x∈\chi-X}P(x)l(h(x),f(x))P(h|X,ε_a)\)

试证明“没有免费的午餐定理”仍成立。

其中，

\[l(h(x),f(x))= \begin{cases} a, & \text{h(x) = f(x)} \\ b, & \text{h(x) ≠ f(x)} \end{cases} \]

（在指示函数Ⅱ(·)中，a,b分别取值为0,1，此处l(·)与其大致相同）
故令\((l(h(x)=f(x))+(l(h(x)≠f(x))=C(C为固定常数，由l(·)的定义来决定)\)

\[\sum_fE_{ote}(ε_a|X,f)=\sum_f\sum_h\sum_{x∈\chi-X}P(x)l(h(x),f(x))P(h|X,ε_a)\\ =\sum_{x∈\chi-X}P(x)\sum_hP(h|X,ε_a)\sum_fl(h(x),f(x))\\ =\sum_{x∈\chi-X}P(x)\sum_hP(h|X,ε_a)({1\over2}2^{|\chi|}(l(h(x)=f(x)))+{1\over2}2^{|\chi|}(l(h(x)≠f(x)))\\ ={1\over2}2^{|\chi|}·C·\sum_{x∈\chi-X}P(x)\sum_hP(h|X,ε_a)\\ ={1\over2}2^{|\chi|}·C·\sum_{x∈\chi-X}P(x)·1 \]

由此，即证“没有免费的午餐定理”成立。

---

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

(1) 首先要理解互联网搜索引擎是如何工作的。这里引用博客园一位博主的一篇回答
搜索引擎的工作原理
大致意思就是，“蜘蛛”在互联网上爬取网页，将网页放到临时数据库中；
临时数据库再对符合检索规则的网页放入索引数据库，而将不符合规则的清除；
通过一些逻辑规则，将索引库中的网页进行分类、归档、评分、排名等一系列操作，生成索引列表；
用户在搜索引擎上查询时，搜素引擎就将索引数据库中返回的查询数据反馈给用户。
(2) 机器学习的引入可以对搜索引擎、索引库、以及他俩之间的交互进行优化。其中包括

• 搜索引擎对自然语言的理解和处理，市面上成熟的AI（Siri这类的）已经具备了有限的自然语言理解能力，可以实时对用户提出的问题进行反馈，包括对网页内容的检索。
• 搜索引擎对图片、视频、音乐等多元化数据的处理及检索。机器学习在图像领域的发展其实有目共睹，人脸识别、车牌识别、AI智能美颜等等已经深入到生活的点点滴滴，听歌识曲等对音频文件的处理也充分展示了机器学习在多元化数据处理领域的优势。
• 用户画像，更个性化的搜索排序。机器学习对用户数据进行收集和分析，在用户搜索时，按照用户个性化需求对搜索结果进行排序（在电商领域可以实现精准营销）。
• 对垃圾网站的甄别。并非所有含有搜索关键字的网站都可以满足用户需求，为了减少不必要的对无用信息的查询，对垃圾网站的甄别逐渐成为了用户所需。
• 还有更多的应用，欢迎各位补充。