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

题目详细描述：表格如下所示

编号	色泽	根蒂	敲声	好瓜
1	青绿	蜷缩	浊响	是
4	乌黑	稍蜷	沉闷	否

思路：
何为版本空间？

版本空间(version space)是概念学习中与已知数据集一致的所有假设(hypothesis)的子集集合。版本空间学习是机器学习的逻辑方法，特别是二分类（binary classification）。
版本空间学习算法搜索预定空间的假设，被视为一组逻辑语句。

对于二维空间中的“矩形”假设（下图），绿色加号代表正类样本，红色小圈代表负类样本。 GB 是最大泛化正假设边界(maximally General positive hypothesis Boundary), SB 是最大精确正假设边界(maximally Specific positive hypothesis Boundary). GB与SB所围成的区域中的矩形即为版本空间中的假设，也即GB与SB围成的区域就是版本空间。

版本空间图示

+解答：根据绪论中的表示方法，根据编号1和4的两个样例可以得到以下7种不同的版本空间

题1.1版本空间图示

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

例如

好瓜⇔

（（色泽=*） $\wedge$ （根蒂=蜷缩） $\wedge$ （敲声=*） $\bigvee$ （（色泽=乌黑） $\wedge$ （根蒂=*） $\wedge$ （敲声=沉闷））

我们吧“（色泽=青绿） $\wedge$ （根蒂=蜷缩） $\wedge$ 敲声=清脆）”以及“（（色泽=乌黑） $\wedge$ （根蒂=硬挺） $\wedge$ （敲声=沉闷））”都分类为“好瓜”。

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

题目详细描述：完整表1如下

编号	色泽	根蒂	敲声	好瓜
1	青绿	蜷缩	浊响	是
2	乌黑	蜷缩	浊响	是
3	青绿	硬挺	清脆	否
4	乌黑	稍蜷	沉闷	否

+解答：

假设一个瓜的好或不好，由三个属性确定。分别是色泽、根蒂、敲声。
其中，色泽有青绿、乌黑，2种取值，根蒂有蜷缩、稍蜷、硬挺3种取值，敲声有浊响、清脆、沉闷3种取值。
那么假设空间由形如 “(色泽=？) ∧ (根蒂=？) ∧ (敲声=？)” 的所有假设组成。
除了考虑属性色泽、根蒂、敲声分别有2 、3、3种可能取值，还要考虑到一种属性可能无论取什么值都合适（用通配符*表示），另外有一种情况就是好瓜这个概念根本不成立（用∅表示），则假设空间大小为（2 + 1）×（3 + 1）×（3 + 1）+ 1 = 49 。

因为最多包含k个合取式，因此使用0，1，2...,k个合取式表示假设空间均符合要求
故可能的假设一共有 $\sum_{n=0}^k$ $C_{49}^n$

根据二项式定理

二项式定理

令x=1，可得 $2^k$ = $\sum_{n=0}^k$ $C_{k}^n$ ，无法化简。
网上大多数答案均为 $2^{49}$ ，该答案当且仅当k只等于49时，能够得到

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

噪音数据：是指数据中存在错误或异常的数据，即无用数据
归纳偏好: 对应了学习算法本身所做出的关于“什么样的模型更好”的假设，在具体的现实问题中，假设是否成立，即算法的归纳偏好是否与问题本身的匹配，大多数直接决定了算法能否取得好的性能。

解答：由于含有噪声，故可对样本空间放宽约束。对于那些只与极少数样本不一致却与极大多数样本一致的假设，仍将其保留在版本空间中。（即当该假设的的样本准确率足够大时，也认为该假设有效）

1.4 本章1.4节在论述“没有免费的午餐”定理时，默认使用了“分类错误率”作为性能度量来对分类器进行评估。若换用其他性能度量 $\ell$ ,试证明没有免费的午餐”定理仍成立

换用其他性能度量 $\ell$ ,公式如下
$E_{ote}(\varepsilon_a|X,f)=\sum_h\sum_{x\in(\chi-X)}P(x)\ell(h(x),f(x))P(h|X,\varepsilon_a)$

证明：

在证明定理之前，先构造一个引理：
引理1：在二分类问题下，对任意性能度量指标 $\ell$ ， $\ell（h(x)=f(x)）+\ell（h(x)\neq f(x)）=A,A$ 为一常数。
证：对于二分类问题，任意性能度量中的正确分类得分与错误分类得分应该是固定的。即：
$\ell（0,0）=\ell（1,1）,\ell（0,1）=\ell（1,0）$
因此
$\ell（0,0）+\ell（0,1）=\ell（1,1）+\ell（1,0）$
设 $\ell（0,0）+\ell（0,1）=\ell（1,1）+\ell（1,0）=A$ ，即可得：
$\ell（h(x)=f(x)）+\ell（h(x)\neq f(x)）=A$
证毕。

因为 $E_{ote}(\varepsilon_a|X,f)=\sum_h\sum_{x\in(\chi-X)}P(x)\ell(h(x),f(x))P(h|X,\varepsilon_a)$
因此 $\sum_fE_{ote}(\varepsilon_a|X,f)=\sum_f\sum_h\sum_{x\in(\chi-X)}P(x)\ell(h(x),f(x))P(h|X,\varepsilon_a)$
$=\sum_{x\in(\chi-X)}P(x)\sum_hP(h|X,\varepsilon_a)\sum_f\ell(h(x),f(x))$
$=\sum_{x\in(\chi-X)}P(x)\sum_hP(h|X,\varepsilon_a)(\frac{1}{2}2^{|\chi|}\ell（h(x)=f(x)）+\frac{1}{2}2^{|\chi|}\ell（h(x)\neq f(x)）)$
$=2^{|\chi|-1}A\sum_{x\in(\chi-X)}P(x)\cdot1$
上式说明度量结果与学习算法 $\varepsilon_a$ 无关，“没有免费的午餐定理”仍然成立。
证明完毕。

关于证明的补充说明：本文的引理没有考虑第二章2.3节中的代价敏感错误。若本题中考虑代价敏感错误，则各种不同代价错误出现的概率也是满足平均分布的，引理1仍然成立，但是证明过程会更加复杂。
思考： NFL定理证明过程中假设了f均匀分布，并且目标是学习所有的真实函数f。现实生活中，具体的学习算法无需学习所有的真实函数，因为所有真实函数在现实中的映射即天底下所有问题都可以用相同的这一组特征来描述，这是不现实的。若用同一组特征来描述所有问题，那么分类结果必将杂乱无章没有任何规律可言，这也是书中假设f满足均匀分布的原因。真实情况下，也许没有任何一种分布能够描述其特征。因此NFL并不意味着好的学习算法没有意义。

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

以下答案来源
知乎| 机器学习能在互联网搜索的哪些环节起什么作用

搜索引擎

我们先得明白搜索引擎都干了啥，然后看哪些部分可以用机器学习来提高用户体验的，下图出自：第 1 章搜索引擎是如何工作的

构成搜索引擎的全部要素

1、文档管理器：存储作为检索对象的文档。当查询到相匹配的文档时，会取出该文档的一部分作为摘要。
2、索引构建器：从检索对象的文本文档中构建文本的索引。
3、索引管理器：管理带有索引结构的数据，索引结构是一种用于进行高速检索的数据结构。
4、索引检索器：利用用户的查询进行文本检索，并根据某种规则进行排序并将结果返回给应用。

除了以上的组建除外，一个完整的搜索引擎还包括：爬虫、搜索排序系统。

因为我们只是大致地了解一下机器学习在搜索引擎上的作用，所以关于搜索引擎的部分就先讲到这，然后来看看哪些地方可以优化。

机器学习对搜索引擎可进行哪些优化

根据搜索引擎的结构，我们可以进行以下的机器学习优化

文档管理器：生成更精准的摘要。本质就是文档摘要的自动生成，涉及深度学习、神经网络、NLP

索引构建器：索引构建已很成熟，但我发现仍有学者将机器学习应用于这部分，主要是用机器学习算法代替标准哈希函数，但效果还不太好[3]。

索引管理器：暂无。

索引检索器：这里涉及查询与文本间的匹配，以及搜索结果的排序，也是直接面向用户的部分。

综上分析，我们主要来看索引检索器的部分，这部分可以有哪些优化呢:

搜索引擎直接给出搜索的答案：这里用到神经网络，它可以通过分析大量数据从而完成特定的任务，如从相关网页中获取长句子和段落，然后提出有关问题答案的信息。

直接给出答案

直接进行图片、视频（等多元数据）的搜索：图片的识别已经是常见的技术了，那直接从视频中提出信息呢？谷歌推出Video Intelligence API，不仅可以从视频中提取特定的信息，还能总结视频的脉络、记录视频中的场景，从而对视频进行准确的分类。
更精准的排序（也可成为「精准营销」的部分）：如使用神经网络、决策树等为基础的网页排序算法：RankNet, LambdaRank 和LambdaMART。2015年，谷歌推出RankBrain，它可以选择最适合当前搜索类型的结果，相当于为每个搜索都提供个性化的算法组合。
对用户行为进行综合分析（如历史搜索数据、点击模式、身份信息等进行结构化信息整合）：更多使用在电子商务的搜索系统中。这在电商网站中的使用，应该是很盛行的，但具体没有调研过。
对话式智能交互搜索：如Baidu的语音搜索、利用Siri进行搜索又或者是Google Assistant等。涉及自然语言处理、知识图谱及神经网络等内容。

小爱能够回答的问题

对垃圾网站的筛选（模式识别）：这部分可以用Outlier的检测来实现，尤其对以前的标题党，或者以前针对算法进行SEO的网站进行甄别。

最理想的模型应该是：搜索引擎成为一个具备不断自我学习和改善的系统。也就是将机器学习应用于搜索引擎的所有方面，一个全自动化的搜索引擎系统。

现在的难点有哪些呢？

搜索引擎是否真正第理解自然语言查询词及文档的意义，还不得知。

仍需要大量的人工对相关数据进行标记，尤其需要大量的语言学家进行这方面的工作。

跨语的搜索精确度的问题，当然这部分也是机器学习能够改善的部分。

其他的自然语言遇到的问题，例如歧义等，讲到底还是语意的理解。

参考资料：

[1]:第 1 章搜索引擎是如何工作的

[2]:深度学习之文本摘要自动生成 - CSDN博客

[3]:The Case For Learned Indexes (Google/MIT)

[4]:AI 再造搜索３招：谷歌如何用机器学习和深度学习直接给你答案

[5]:搜索引擎如何使用机器学习:我们需要知道的9种方式 | ATYUN

机器学习（西瓜书）第一章绪论课后习题

机器学习（西瓜书）第一章绪论课后习题

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

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

好瓜⇔

（（色泽=） $\wedge$ （根蒂=蜷缩） $\wedge$ （敲声=） $\bigvee$ （（色泽=乌黑） $\wedge$ （根蒂=*） $\wedge$ （敲声=沉闷））

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

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

1.4 本章1.4节在论述“没有免费的午餐”定理时，默认使用了“分类错误率”作为性能度量来对分类器进行评估。若换用其他性能度量 $\ell$ ,试证明没有免费的午餐”定理仍成立

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

搜索引擎

机器学习对搜索引擎可进行哪些优化

现在的难点有哪些呢？

机器学习（西瓜书）第一章 绪论 课后习题

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

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

好瓜⇔

（（色泽=*）（根蒂=蜷缩）（敲声=*） （（色泽=乌黑）（根蒂=*）（敲声=沉闷））

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

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

1.4 本章1.4节在论述“没有免费的午餐”定理时，默认使用了“分类错误率”作为性能度量来对分类器进行评估。若换用其他性能度量,试证明没有免费的午餐”定理仍成立

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

搜索引擎

机器学习对搜索引擎可进行哪些优化

现在的难点有哪些呢？

机器学习（西瓜书）第一章绪论课后习题

（（色泽=） $\wedge$ （根蒂=蜷缩） $\wedge$ （敲声=） $\bigvee$ （（色泽=乌黑） $\wedge$ （根蒂=*） $\wedge$ （敲声=沉闷））

1.4 本章1.4节在论述“没有免费的午餐”定理时，默认使用了“分类错误率”作为性能度量来对分类器进行评估。若换用其他性能度量 $\ell$ ,试证明没有免费的午餐”定理仍成立