人可以通过经验学习，比方说“朝霞不出门，晚霞行千里”，就是通过经验得来的知识。获得知识后，即使在不同的地点，不同的时间，看到不同的霞，我们也能作出正确的判断。那么，机器是否也能学习并利用经验，从而对一些未出现过的情况，在不通过显式编程（人作出判断并告诉机器）的情况下也能作出正确的预测呢？答案是可以的，这就是机器学习。
对于机器来说，经验是通过数据传达的。机器学习的主要研究内容就是从数据中产生模型的算法，也即学习算法。Mitchell给出一个更为形式化的定义，假设我们用P来表示程序处理任务T时的性能，如果程序通过利用经验E提高了在任务T上的性能，则称该程序对E进行了学习。
在本书中，模型泛指所有从数据中学得的结果，在别的文献中，也有对模型和模式作出区分的，模型指学得的全局性结果（比如一棵决策树），模式指学得的局部性结果（比如一条规则）。
要进行机器学习，首先要有数据，我们可以收集一组结构相同的记录，这组记录的集合就称为数据集。比如下面这个西瓜数据集：
| 编号 | 色泽 | 根蒂 | 敲声 |
|---|---|---|---|
| 001 | 青绿 | 蜷缩 | 浊响 |
| 002 | 乌黑 | 稍蜷 | 沉闷 |
| 003 | 浅白 | 硬挺 | 清脆 |
注：实际使用数据时往往需要先进行编码，即把文本改为数值（比如青绿=1，乌黑=2，等等），以便计算机进行处理。
接下来给出一些基本概念的定义：
数据集中的每条记录是对一个事件或对象（比如这里的西瓜）的描述，也称作示例或者样本。特别地，有时会把整个数据集称为一个样本，因为数据集可以看作是从样本空间中抽样所得。这时候就需要根据上下文信息来进行判断了。
对象具备一些性质，并由此可以进行区分，这些性质就称为属性或者特征，比方说表格中的色泽、根蒂和敲声。不同对象在这些属性上会有不同的取值，这个取值就称为属性值。
由属性张成的空间，比方说上面的表格中有3个属性，那就可以张成一个3维空间，每个样本都可以用空间中的一个点来表示，这个点对应于一个坐标向量，所以有时也把一个样本称为一个特征向量。
即数据集中每个样本拥有的特征数目。
从数据中获的模型的过程。在这个过程中使用的数据称为训练数据，里面的每个样本称为一个训练样本，也称训练示例或训练例。训练样本的集合就是训练集。
模型有时也称为学习器，可以看作一组参数的有序集合，能够把属性空间映射到输出空间上。每一个模型对应于一个假设，也即数据存在的某种规律。真相指的是真正存在的规律，学习就是为了接近真相。
如果我们希望通过机器学习来实现预测(prediction)，那么只有样本是不够的，要让机器明白怎样的样本会产生怎样的结果，还需要为每个样本设置标记，标记有可能是离散值（分类任务），也可能是连续值（回归任务）。带标记的数据集如下：
| 编号 | 色泽 | 根蒂 | 敲声 | 标记 |
|---|---|---|---|---|
| 001 | 青绿 | 蜷缩 | 浊响 | 好瓜 |
| 002 | 乌黑 | 稍蜷 | 沉闷 | 坏瓜 |
| 003 | 浅白 | 硬挺 | 清脆 | 坏瓜 |
标记指示的是对象的类别或者事件的结果，样本和标记组合起来就是样例。所有标记的集合称为标记空间，也称为输出空间。
根据预测值的不同，可以把任务分为几种不同的类别。若预测的是离散值，比如“好瓜”，“坏瓜”，则该任务称为分类任务；若预测的是连续值，比如瓜的重量，则该任务称为回归任务；还有一种聚类任务，旨在基于某种度量将样本分为若干个簇(cluster)，使得同一簇内尽量相似，不同簇间尽量相异。聚类任务不需要对样本进行标记。
特别地，只涉及两种类别的分类任务称为二分类任务(binary classification)，通常称一个类为正类(positive class)，另一个类为反类或者负类(negative class)。涉及到多个类别的分类任务就称为多分类(multi-class classification)任务。
训练完成后，使用模型预测新样本的标记这个过程称为测试。测试中使用到的样本称为测试样本，也称测试示例或测试例。
根据训练样本是否标记可以把任务分为两大类，需要标记的是监督学习，不需要标记的是无监督学习。前者的代表是回归和分类，后者的代表是聚类。
让机器进行学习的目标并不仅仅是为了让模型能在训练数据上有好的表现，我们更希望模型在新的样本上也能有良好的表现。模型适用于新样本的能力就称为泛化能力，泛化能力好的模型能够更好地适用于整个样本空间。
一般来说，训练数据只占训练空间很少的一部分，当我们希望这一小部分的采样能够很好地反映整个样本空间的情况，从而令学得的模型具有良好的泛化能力。通常假设样本空间中的所有样本都服从于一个未知的分布(distribution)，并且训练样本都是从该分布上独立采样所得，这就称为独立同分布。训练样本越多，越能反映该分布的特性，从而能学得泛化能力更强的模型。
类似由样本构成的样本空间和由标记构成的标记空间，所有的假设共同构成了假设空间。学习的过程就可以看作是在假设空间中搜索最能**匹配(fit)**训练集的假设。
假设空间的规模有多大呢？举个例子，样本空间维度是3，也即每个样本由3个特征来表示。这三个属性可能的取值分别为3，2，2。那么假设空间的规模就是 4 × 3 × 3 + 1 = 37，为什么呢？因为除了可能的取值之外，每个属性还有一种选择就是使用通配符*号表示，即无论取何值都可以。所以一个有3种可能取值的属性在排列组合时有4种情形。最后的加一表示的是**$\varnothing$假设**，它对应的是一种无论属性取何值都不可能达到目的的状况。比方说，前面的假设都是假设怎样的瓜会是好瓜，而$\varnothing$假设则对应于好瓜根本不存在。
有时候会出现多个假设都能匹配训练集的情形，这些假设的集合就称为版本空间(version space)。版本空间是假设空间的子空间。
对于学习算法来说，要产生一个模型就意味着要从版本空间中挑选出一个假设。但是版本空间中的假设都和训练集一致，无法直接分辨出哪一个更好，这时候归纳偏好，简称偏好就起作用了。
注意区分偏好和特征选择，前者是基于某种领域知识而产生的，后者则是基于对训练样本的分析进行的。
偏好指的是，在多个假设等效时，学习算法会认为某一种假设更优，并选择这种假设来建立最终的模型。如果一个学习算法没有偏好，比方说每次随机地从版本空间中选择一个假设，则它所给出的结果是时好时坏，自相矛盾的。所以任何一个有效的学习算法都应当有自己的归纳偏好。
怎样确定归纳偏好呢？一个常用的原则是奥卡姆剃刀(Occam's razor)，用一句话概述就是：若多个假设与观察一致，则选最简单的那个。注意，奥卡姆剃刀并不是唯一的准则，并且如何诠释“最简单”也是待考虑的。
给定基于某种归纳偏好的算法产生的模型A和基于另一种归纳偏好的算法产生的模型B，有时我们会注意到，A和B在不同的样本集上的表现各有好坏，有时候A的效果更好，有时候B的效果更好。甚至一个随机产生的模型都有可能在某个样本集上表现得优于我们精心设计的算法所产生的模型。怎样去定位这个问题呢？
书中使用NFL定理(No Free Lunch Theorem)来解答了这个问题，有一个关键点就是总误差与学习算法无关，证明在书上有，这里主要解析一下书中想要表达的思路。当我们考虑样本空间的所有可能分布，并认为它们都以相同的概率出现或同等重要时，无论使用什么模型，造成的总误差都是相同的，与学习算法无关！
但是！现实中并不是这样的，我们只考虑样本空间服从同一种分布的情形。打个比方，模型A是精心设计的算法产生的，模型B则简单地设定为把任何样本预测为负类。那么对于按照样本分布抽样所得的测试集，模型A效果会比B好；但是如果只抽取负类样本作为测试集，则模型B优于A。显然这种情况下模型B没有任何意义，因为我们根本就不care全是负类这种分布！
所以说，若考虑所有潜在的问题，则所有算法都一样好。**要谈论算法的优劣，必须结合具体问题！**学习算法的归纳偏好和问题是否相配，往往起到决定性的作用。
关于发展历程和应用状况，属于阅读材料，所以这里不作详细的笔记了。这个小节再补充一点其他内容。
归纳（induciotn）和演绎（deduction）是科学推理的两大基本手段，前者是从特殊到一般的泛化（generalization），后者是从一般到特殊的特化（specialization）。举个例子：
大前提：人都会死
小前提：苏格拉底是人
结论： 苏格拉底会死
演绎是一个层层递进的过程，条件A指出一个可能，条件B指出另一种可能，互相交叉，构成大小前提，一直往下，从而推出新的可能。数学公理系统中，新的定理就是通过一组公理的演绎得出的。
事件1：苏格拉底死了
事件2：柏拉图死了
事件3：阿基米德死了
结论： 人终有一死
归纳是从一组平等的事物中发现普遍规律/联系的过程。机器学习中从样例学习就属于归纳推理。
**注：**对于提到的人名，我很抱歉T.T
归纳学习有广义和狭义之分。广义上，只要是从样例中学习就都属于归纳学习；狭义上，不仅要从样例中学习，还要求学得概念（concept），因此也称为概念学习。概念学习技术目前应用和研究都比较少，因为要学得泛化性能好且语义明确的概念太难了。现在的技术大多都是产生黑箱模型，难以明白学得的是什么，只知道它确实有用。
简要带过以下归纳学习（广义）的几大主流技术，最早期的主流是符号主义学习，例如决策树，能直接模拟人类对概念进行判定的流程，有良好的解释性很强大的表示能力。但是表示能力太强也直接导致了假设空间太大，复杂度极高的缺陷。问题规模较大时难以进行有效的学习。
接下来发展的另一主流技术是连接主义学习，例如神经网络。与符号主义学习能产生明确的概念不同，连接主义产生的是“黑箱”模型。连接主义学习涉及到大量的参数设置，而参数设置缺乏理论指导，只能依靠手动调参，参数的设置是差之毫厘谬以千里，参数的一点点差别体现在结果上可能是极其巨大的。因此，试错性大大地限制了连接主义学习的发展。
再往后，统计学习技术就闪亮登场了，例如支持向量机。它与连接主义学习有密切的联系，但没有连接主义学习那么大的局限性。
而现在最火的深度学习技术，其实就属于连接主义学习技术，可以简单地理解为多层神经网络。深度学习的模型复杂度非常高，以至于使用者只要下功夫调参，性能往往就会很好。为什么深度学习会突然变得热门呢？有两大支持，一是数据支持，深度学习模型参数极多，如果数据不够，很容易会过拟合，但这是一个大数据时代，海量的数据允许我们构造出精准的模型；二是计算支持，随着计算机技术的发展，现代计算机具备了足够的计算海量数据的能力。
问：表1.1中若只包含编号为1和4的两个样例，试给出相应的版本空间。
此时训练集如下：
| 编号 | 色泽 | 根蒂 | 敲声 | 好瓜 |
|---|---|---|---|---|
| 1 | 青绿 | 蜷缩 | 浊响 | 是 |
| 4 | 乌黑 | 稍蜷 | 沉闷 | 否 |
由于好瓜的3个属性值与坏瓜都不同。所以能与训练集一致的假设就有很多可能了，从最具体的入手，往上逐层抽象可得：
问：与使用单个合取式来进行假设表示相比，使用“析合范式”将使得假设空间具有更强的表示能力 。例如：
$$好瓜 \quad \leftrightarrow \quad \lgroup (色泽=) \wedge (根蒂=蜷缩) \wedge (敲声=)\rgroup \ \vee \lgroup (色泽=乌黑) \wedge (根蒂=*) \wedge (敲声=沉闷)\rgroup$$
会把 “$(色泽=) \wedge (根蒂=蜷缩) \wedge (敲声=)$” 以及 “$(色泽=乌黑) \wedge (根蒂=*) \wedge (敲声=沉闷)$” 都分类为好瓜。若使用最多包含
$k$ 个合取式的析合范式来表达表1.1西瓜分类问题的假设空间，试估算有多少种可能的假设。
首先要理解题意，“使用最多包含
表1.1：
| 编号 | 色泽 | 根蒂 | 敲声 | 好瓜 |
|---|---|---|---|---|
| 1 | 青绿 | 蜷缩 | 浊响 | 是 |
| 2 | 乌黑 | 蜷缩 | 浊响 | 是 |
| 3 | 青绿 | 硬挺 | 清脆 | 否 |
| 4 | 乌黑 | 稍蜷 | 沉闷 | 否 |
这里色泽有2种取值，根蒂有3种取值，敲声有3种取值。因为每个属性还可以用通配符表示取任何值都行，所以实际上这三个属性分别有3，4，4种选择。因此，在只考虑单个合取式的情况下，有
现在我们考虑题目的条件，这实际上是一个组合问题。我们可以从48个基本假设中任意去1个到k个组合为新的假设：
使用1个合取式：$\binom{48}{1} = 48$ 种假设；
使用2个合取式：$\binom{48}{2} = \frac{4847}{21} = 1128$ 种假设；
...
使用k个合取式：$\binom{48}{k} = \frac{4847...*(48-k+1)}{k!}$ 种假设；
把以上求得的各情形下的假设个数进行求和就得到问题的答案了。
问：若数据包含噪声，则假设空间中有可能不存在与所有训练样本都一致的假设。在此情形下，试设计一种归纳偏好用于假设选择。
归纳偏好是在无法断定哪一个假设更好的情况下使用的。既然问题是存在噪声，那么如果能知道噪声的分布（例如高斯噪声），就可以将这些性能相同的假设对应的误差减去由噪声引起的部分，此时再使用奥卡姆剃刀原则或者多释原则来进行假设选择就好了。更常见的做法是引入**正则化（regularization）**项，在建立模型时避免拟合噪声。
问：本章1.4节在论述“没有免费的午餐”定理时，默认使用了“分类错误率”作为性能度量来对分类器进行评估。若换用其他性能度量
$\ell$ ，则式(1.1)将改为
$$E_{ote}(\mathfrak{L}a | X,f) = \sum_h \sum{x \in \chi-X} P(x)\ell(h(x), f(x))P(h|X, \mathfrak{L})$$
试证明“没有免费的午餐定理”仍成立。
回顾NFL的证明可以发现，关键是要证明，在考虑所有可能的目标函数（对应所有可能的问题，或者说样本空间的所有分布情况）时，模型的性能变得与学习算法无关。
也即证明
当我们考虑所有可能的f，并且f均匀分布时，任务就失去了优化目标，无论使用哪一种算法，所得模型的平均性能会变得相同。
如果想看更严谨的推导可以看Wolpert, D.H., Macready, W.G当初写的论文"No Free Lunch Theorems for Optimization"。
事实上我对这个定理存有疑问，NFL定理是否适用于所有性能度量？。比方说，推荐系统中使用到的覆盖率，可以简单理解为生成的推荐结果包含的商品数与训练集中出现的商品数的比率。对于这样一个性能度量，倾向于推荐更多商品的算法会明显比其他算法更优。并且，即使考虑所有可能的f，我们依然对这些算法存在偏好。
问：试述机器学习能在互联网搜索的哪些环节起什么作用。
这题比较开放，机器学习能起到的作用有很多，例如利用机器学习知识进行数据挖掘，从应用的角度来说，可以构建推荐系统、赛事预测、语音识别等等。