西瓜书第一章精读：假设空间、版本空间与归纳偏好

《机器学习》这本书因为通篇拿西瓜举例，在圈子里被喊成"西瓜书"。我把这一轮精读的笔记整理成连载，戏称为"吃瓜教程"——一边啃书一边吃瓜，第一章就是这盘瓜的开胃菜。这篇读书笔记对应第一章绪论，翻开只有薄薄几十页，通篇全是定义和示意图，连一个像样的公式推导都没有，很多人读到这里会下意识加速翻过去，觉得"先看后面讲算法的部分才有意思"。真正动手做过项目之后我才明白，第一章不是序言，而是地基：它给出了整套术语体系、一个叫假设空间的抽象结构，以及一条决定所有算法命运的归纳偏好。这三个东西在后面每一章都会反复出现，你在第一章偷的懒，会在第 4 章决策树、第 8 章集成学习里连本带利还回去。

这篇笔记适合三类人：第一类是刚接触机器学习、被"属性、特征、样例、标记"这堆词绕晕的新手；第二类是做过几个调包项目、但被问到"版本空间是什么"会卡壳的实践者；第三类是想把西瓜书当教材系统过一遍、需要一份可复现笔记的读者。我会把第一章拆成术语链、假设空间、归纳偏好三块，每一块都补上教材没细说的推导和容易踩的坑，最后附上两段可以直接跑的代码，用程序把版本空间穷举出来，再亲手验证一遍"天下没有免费的午餐"到底在说什么。

1. 第一章在全书里的位置

1.1 为什么这本书叫西瓜书，第一章又为什么不能跳

先说个很多人不知道的细节：西瓜书里的西瓜不是为了可爱，而是因为这个小样本足够小，小到你可以用纸笔把假设空间全部枚举出来。一个样本只有色泽、根蒂、敲声三个属性，每个属性三个取值，加上通配符，总共六十四种组合，再加一个"世界上没有好瓜"这个特殊假设，一共六十五种假设。这个数量级刚好卡在"人脑能算、算完有收获"的甜点区。如果把属性换成一百个连续特征，你连图都画不出来，更别说理解了。

所以第一章的设计意图很明确：用一个能穷举的最小例子，把机器学习的核心矛盾暴露出来。这个矛盾是——**给定有限的训练数据，能满足条件的假设往往不止一个，而你必须选一个。**选哪一个，凭什么选，选错了会怎样，这三个问题构成了第一章的全部张力。教材后面所有章节，无论是决策树的分裂准则、支持向量机的最大间隔、还是神经网络的损失函数，本质上都在回答"怎么从一个巨大的假设空间里挑出那个更好的假设"，只是换了一种更聪明的搜索方式而已。

我在第一次读的时候，把第一章当成名词解释背了一遍，结果读到第 3 章线性模型时，看到"假设空间"四个字就懵了：这不是第一章那个东西吗？怎么又出现了。第二次读才反应过来，第一章讲的是一个和具体算法无关的通用框架，后面的章节只是往这个框架里填不同的假设表示形式。线性模型的假设空间是"所有线性函数"，决策树的假设空间是"所有树结构"，神经网络是"所有给定结构的参数组合"。框架是同一个，搜索策略不同。理解这一点之后，再读后面就会顺畅很多。

心得：读第一章的正确姿势不是记住定义，而是先建立一个"数据—假设空间—搜索—泛化"的心智模型。后面每读一个新算法，都试着回答一句："它在什么假设空间里搜索，用什么准则挑，归纳偏好是什么。"

1.2 第一章的三条主线与推荐阅读顺序

第一章的内容如果按教材顺序平铺下去，是引言、基本术语、假设空间、归纳偏好、发展历程、应用现状六节。我的建议是打乱顺序读，按"概念—结构—哲学—背景"四步走，效率会高很多。

第一步先读基本术语，也就是 1.2 节，把这套黑话打通。这一步没有任何理解难度，纯记忆，但它是后面所有讨论的语言基础，跳过它等于用外语读数学。

第二步直接跳到假设空间和版本空间。这两节是第一章唯一的"硬核"部分，也是最能体现机器学习思维方式的地方。它回答的是"学习算法把什么当成候选答案"。西瓜书在这里给出的合取式表示法，虽然简单到有点简陋，但它是后面所有假设表示法的原型：属性取值加通配符，本质上是"某些条件下必然成立"的逻辑表达。你把这个小例子彻底吃透，将来看到特征工程里的"交叉特征"、规则引擎里的"条件组合"，会有种似曾相识的感觉。

第三步读归纳偏好，这一节是第一章的思想高地。奥卡姆剃刀和 NFL 定理这两把刀，一把告诉你"多解时挑简单的"，另一把紧接着告诉你"任何偏好都不是免费的"。这两句话表面矛盾，实际上是一体两面：偏好必须存在，但偏好一定会在某些问题上害你。这个认识是后面做模型选型时的底层依据。

第四步才是引言、发展历程和应用现状。这三节读起来轻松，但不要完全跳过，它们提供的是坐标系——你至少要知道专家系统时代和统计学习时代的分界线在哪，知道为什么上世纪末机器学习会从"手写规则"转向"从数据里学规则"。这段历史不长，但是理解很多设计动机的钥匙，比如为什么评估指标里会有那么多"过拟合"相关的概念。

注意：发展历程那几页别当成科普读物一扫而过，它解释了一件事——为什么现在的主流方法都强调"从数据中学习"而不是"人工编码知识"。这个转向的理由，直接决定了你在实际项目里应该把精力花在哪里。

1.3 笔记该记什么，不该记什么

这一点说给做笔记的人听。我前几轮读技术书，习惯把定义一字不差抄下来，笔记做得像排版精美的词典，结果复习的时候根本不想翻，因为翻开全是自己已经知道的东西，没有信息增量。

后来改了方法：笔记只记三样东西——我自己复述的定义、我自己构造的例子、我自己踩过的坑。定义原文书上就有，抄一遍没有价值；但如果我用自己的话重写一遍，写不出来的地方就暴露了理解漏洞。这一点在第一章特别有效，因为第一章的定义密度极高，"属性空间"和"样本空间"到底是不是一回事，"标记"和"属性值"有什么区别，这些问题只有你动笔复述时才会发现。

比如"样本空间"和"标记空间"，书上是分两处定义的，位置上隔了好几页。我第一遍读的时候模糊地觉得都是"空间"，没什么区别。第二遍写笔记时才意识到，前者是属性张成的空间，一个样本对应其中一个点；后者是所有可能的标记构成的集合，一个样本的答案对应其中一个点。两者维度完全不同，一个是属性个数维度，一个是输出类型维度。分类任务的标记空间是离散的类别集合，回归任务的标记空间是实数集。这个区分在写代码时非常具体：你处理的是特征矩阵的形状，还是标签数组的形状，完全是两件事。

2. 术语是门槛：把第一章的定义串成一条链

2.1 从一张西瓜表格说起：数据集、样本、属性、特征向量

第一章的基本术语看起来零散，其实是一条完整的链，只要顺着一个具体例子走一遍就通了。教材里给了一张西瓜数据表，后面章节反复用到，我们就拿它当道具。

一张表就是一个数据集，记号上通常写作 D = {x₁, x₂, ..., xₘ}，m 是样本数。表里的每一行是一个样本，也叫示例，是关于一个对象的描述。表里的每一列描述对象某个方面的性质，叫属性，也叫特征。属性上的取值叫属性值。比如"色泽"是一个属性，"青绿"是它的一个属性值。

把属性张成的空间叫作属性空间，也叫样本空间或输入空间。一只西瓜的色泽、根蒂、敲声三个属性各自确定了一个维度，三个维度张成一个三维空间，每只西瓜就是这个空间里的一个点。因为空间中的每个点对应一个坐标向量，所以一个样本也叫一个特征向量。属性的个数就是这个空间的维数，也叫样本的维数。

这里有个特别容易出错的点，我当年就栽过：**属性的个数和特征向量的长度并不总是一一对应。**教材语境下它们相等，因为教材默认属性是标称型的，一个属性对应一个坐标。但真实项目里，"色泽"这种多类别属性，你一旦做独热编码，它就从一维变成三维，特征向量的长度立刻超过属性个数。所以当你看到某个模型报告的"特征维度"和原始表的列数不一致时，不要慌，先想想中间经历了什么编码操作。

注意：教材说"维数等于属性个数"，这是在有明确前提的语境下成立的。做工程时如果拿这句话去校验数据形状，很容易对不上号，因为类别编码、文本向量化、缺失值填充都会改变实际的列数。

2.2 标记、样例与输出空间：监督学习的两条腿

有了描述，还需要答案。关于样本结果的信息叫标记，也叫标签。西瓜例子里"是好瓜"和"不是好瓜"就是两个标记。所有标记的集合叫标记空间，也叫输出空间。拥有了标记的样本叫样例，这是教材里一个很讲究的用词区别——没答案的叫样本，有答案的叫样例。

标记空间的形式直接区分了任务类型。如果标记是离散的类别，任务是分类；如果标记是连续数值，任务是回归。二分类任务只有两个类别，通常一个叫正类，一个叫负类；多分类任务有三个及以上类别。教材在这里没有强调的一点是，正负类的划分在实际项目里往往是人为指定的，而且这个指定会影响你后续看指标的方式。比如把"坏瓜"当正类，那查准率衡量的是"挑出来的瓜里有多少真是坏的"，这个语义和把"好瓜"当正类完全相反。所以拿到一份数据看混淆矩阵之前，先确认正类是谁，这是新手最常见的低级错误之一，我自己也犯过，汇报时把精确率和召回率说反了，场面一度非常尴尬。

另外补充一个教材放后面讲、但在这里就需要埋下的概念：泛化。模型在训练集上学到的规律，能不能用在新样本上，这个能力就是泛化能力。训练集里的样本是老师给的，测试集里的是考试题，两者来自同一个未知的分布D。教材明确写了这个假设：样本是独立同分布地从这个分布中采样得到的。这个 i.i.d. 假设被一笔带过，但它是整个评估体系的地基。

我在实际项目里被这个假设坑过不止一次。电商的用户行为数据、金融的时序数据、工业设备的传感器序列，全都带有强烈的时间相关性，今天的样本和昨天的样本高度相关，根本不满足独立性。这种数据如果你按随机切分做训练测试划分，模型会从"未来"里学到信息，评估指标漂亮得离谱，一上线就崩。这时候必须用时间序列切分，拿过去预测未来，才接近真实部署场景。

心得：每次做数据划分前先问一句"我的样本真的独立同分布吗"。如果答案是"不完全是"，那就要重新设计验证策略，而不是继续用默认的随机切分。

2.3 分类、回归、聚类与泛化：任务类型的分岔口

沿着标记空间往下走，就分出了几条路。有标记数据叫监督学习，没有标记数据叫无监督学习。分类和回归是监督学习的两大分支，聚类则是无监督学习里最典型的任务。

这里有个很值得琢磨的问题：没有标记，模型学什么？聚类的答案是学数据内部的结构——把相似的样本归到一起，每一组叫一个簇。这个"相似"怎么定义，是聚类任务的核心问题，也是它和分类最本质的区别。分类的答案由人给定，模型只需要逼近；聚类的答案由模型自己生成，而模型生成答案的依据是你给的距离度量。换句话说，聚类的效果取决于你如何定义"像"，这是一个远比"选哪个算法"更前置的问题。我做过一个用户分群的项目，换了三种聚类算法效果都一般，最后发现问题出在特征上——某些量纲差了几百倍的字段没做标准化，距离度量全被大数值字段主导了。标准化做完，同样算法效果立刻改善。

教材里还提了一句监督学习和无监督学习的边界问题：有标记数据获取成本高，大量数据是无标记的。这个现实约束催生出了半监督学习、主动学习等方向。这部分内容第一章只是一笔带过，但它是理解"为什么工业界那么重视数据标注成本"的入口，值得在笔记里标一个记号，后面读到相关章节再回来补。

再回到泛化。第一章提泛化的时候没有给度量方式，只说"学得的模型适用于新样本的能力"。度量方式要到第 2 章才讲，但概念上必须现在就立住：训练误差低不等于泛化能力强。一个模型如果足够复杂，可以在训练集上做到零误差，代价是它把训练数据里的噪声也当成规律记了下来。这就是过拟合的雏形，第一章点到为止，第 2 章会展开。我建议在这里就写下自己的疑点，比如"怎么判断模型是不是过拟合了""训练误差和测试误差差多少算异常"，带着这些问题去读第 2 章，效率会比被动阅读高得多。

3. 假设空间、版本空间与归纳偏好

3.1 归纳与演绎：学习算法到底在做什么

第一章把"学习"这件事拆成了两种推理方式。归纳是从特殊到一般，从若干具体样例中提炼出普遍规律；演绎是从一般到特殊，从已知的一般原理推出具体结论。

机器学习做的是归纳。给定若干只好瓜和坏瓜的例子，算法试图得到一个"什么瓜是好瓜"的一般性判断。这个过程有一个绕不开的逻辑麻烦：从有限的观察出发，永远无法严格证明一个放之四海而皆准的规律。你看到的都是白天鹅，推不出"天鹅都是白的"。归纳的合理性没法靠演绎证明，只能靠额外的假设来支撑。

这个额外的假设，就是学习算法的归纳偏好。教材在这里的处理非常精妙：它不急着讲偏好，而是先引进一个结构——假设空间，让"从数据中学习"这件事变成一次有边界的搜索。理解了这个结构，你才能看清偏好到底作用在哪个环节。

具体怎么把学习变成搜索？教材用的假设表示是一个合取式，形如"（色泽 = ?）∧（根蒂 = ?）∧（敲声 = ?）"。每个问号位可以填一个具体属性值，也可以填通配符，表示"这个属性取什么值都行"。比如"（色泽 = *）∧（根蒂 = 蜷缩）∧（敲声 = *）"表达的是"只要根蒂蜷缩就是好瓜，不管颜色和声音"。所有这样的合取式构成的集合，就是假设空间。学习的过程，就是在这个空间里搜索与训练数据一致的假设。

这个表示的局限性非常明显，我第一次看到时有点不以为然——现实中好瓜的规律往往是析取的，"要么色泽青绿且敲声浊响，要么色泽乌黑且根蒂稍蜷"，这种"或"的关系合取式表达不了。教材的习题 1.2 正好就问了这个问题，让读者去估算把表示能力扩展到析合范式之后假设空间有多大。这个设计很聪明，它逼你想清楚一件事：假设空间越大，表达能力越强，搜索难度也越高，这对矛盾贯穿了整个机器学习。

心得：合取式这个例子小到可以手算，但它的思维方式值得反复咀嚼。你在特征工程里手动构造条件组合特征，本质上就是在往假设空间里加先验的结构，让它更容易表达你想要的规律。

3.2 假设空间规模怎么算：从 65 到 3073

现在算一笔具体的账。西瓜的简化例子里有三个属性，色泽、根蒂、敲声，每个属性三个取值。

对每个属性，假设中的取值有两种可能：填一个具体的属性值，或者填通配符。所以每个属性有 3 + 1 = 4 种填法，三个属性合起来是 4 × 4 × 4 = 64 种组合。除此之外还要考虑一种特殊情况：不管什么瓜都不是好瓜。教材把这个假设记作空集符号，它不属于任何一个合取式，需要单独加进来。于是假设空间的规模是：

|H| = 4 × 4 × 4 + 1 = 65

这个 65 就是我前面说的"甜点区"。现在把它扩展到完整的西瓜数据集。教材后面章节用的西瓜数据表有六个属性：色泽、根蒂、敲声、纹理、脐部都是三个取值，触感是两个取值。按同样的公式：

|H| = (3+1)⁵ × (2+1) + 1 = 4⁵ × 3 + 1 = 1024 × 3 + 1 = 3073

从 65 到 3073，属性只从三个变成六个，规模翻了将近五十倍。这就是维度增长带来的第一课：假设空间的大小随属性个数指数增长。

但更要命的事情在后面。如果允许假设中的每个属性不填单个值，而是填一组值的集合，比如"色泽属于青绿或乌黑"，那么每个三取值属性就有 2³ - 1 = 7 种非空子集可选，两取值属性有 2² - 1 = 3 种。假设空间规模变成：

7⁵ × 3 = 16807 × 3 = 50421

从 3072 到 50421，假设的语法形式几乎没有变化，只是允许了"或"的写法，规模就膨胀了十六倍多。如果再做析合范式的扩展，也就是允许若干个合取式用"或"连接起来，规模会继续爆炸。

这三个数字放在一起，指向同一个结论：**假设空间的表达能力、规模和搜索可行性之间是三方博弈，无法同时最大化。**这也是为什么后面每一章介绍的算法，实际上都是在这个博弈里做的一次具体取舍。决策树用递归划分来避开全局枚举，支持向量机用核函数在隐式空间里做搜索，神经网络用梯度下降在连续参数空间里找局部最优。它们都放弃了"穷举保证找到最优假设"这条路，换取可行性。

3.3 版本空间与归纳偏好：NFL 定理在说什么

有了假设空间，就可以定义版本空间了：与训练集一致的假设构成的集合。教材用西瓜例子演示了一遍：假设空间有 65 个假设，训练集中只有一个正例"（青绿, 蜷缩, 浊响）是好瓜"，把那些会把坏瓜误判为好瓜的假设全部剔除，剩下的就是版本空间。

我手算过一遍，与这个正例一致的假设必须满足：色泽是青绿或通配，根蒂是蜷缩或通配，敲声是浊响或通配，所以版本空间有 2 × 2 × 2 = 8 个假设。这 8 个假设在训练数据上表现完全一样，谁也没法说服谁。这时候学习算法必须做一个选择，凭的就是归纳偏好。

偏好可以有很多种。教材举的一对极端是：偏好"尽可能特殊"的假设，会挑出（青绿, 蜷缩, 浊响）；偏好"尽可能一般"的假设，会挑出（*, *, *）。两个选择都跟训练数据一致，但它们在测试数据上的表现可能天差地别。这就引出了著名的天下没有免费的午餐定理：对所有可能的问题来说，任何算法的期望性能都相同。换句话说，脱离具体问题谈算法优劣，是没有意义的。

我很喜欢教材在这个地方的逻辑节奏。它先用奥卡姆剃刀告诉你"多解时选简单的"，紧接着用 NFL 定理告诉你"任何偏好都会在某些问题上付出代价"。这两句话不冲突，它们共同描述了一个事实：**偏好不是可选项，而是必需项。**没有偏好的学习算法在版本空间里无从选择，等于不学习。而偏好一旦选定，就意味着你在某些问题上会赢，在另一些问题上会输。所谓"选模型"，说到底就是选一个和自己的问题分布匹配的偏好。

实际工作里这个道理的直接推论是：**不要迷信任何"最强算法"的说法。**我的项目上曾有个小数据集分类任务，团队一开始上复杂模型，效果好但调参极不稳定；后来换成逻辑回归加几个手工交叉特征，效果反而更稳、更可解释。这不是说复杂模型不好，而是这个具体问题的分布恰好和简单模型的偏好更对味。NFL 定理不是让你放弃优化，而是让你在优化之前先看清问题。

心得：当有人告诉你"某某算法在某某任务上吊打一切"时，追问三个问题——数据量多大、特征是什么形态、评估指标是什么。答案不同，结论往往就推翻了。

4. 把第一章跑成代码：版本空间穷举与偏好对比实验

4.1 手工构造西瓜子集与假设空间

概念读完容易飘，写代码能立刻把它按回地面。下面这段代码用三个属性构造假设空间，规模正好是 65，可以拿来验算前面的公式。

import itertools import pandas as pd # 只保留三个属性，方便穷举 ATTRIBUTES = { "色泽": ["青绿", "乌黑", "浅白"], "根蒂": ["蜷缩", "稍蜷", "硬挺"], "敲声": ["浊响", "沉闷", "清脆"], } ATTR_NAMES = list(ATTRIBUTES) WILDCARD = "*" EMPTY_HYP = "∅" # 特殊假设：不存在"好瓜"这个概念 def build_hypothesis_space(): """每个属性取 具体值 或 *，再加上空集假设""" domains = [vals + [WILDCARD] for vals in ATTRIBUTES.values()] space = [tuple(c) for c in itertools.product(*domains)] space.append(EMPTY_HYP) return space def covers(hyp, sample): """假设 hyp 是否把 sample 判为 好瓜""" if hyp == EMPTY_HYP: return False return all(h == WILDCARD or h == v for h, v in zip(hyp, sample))

顺手把数据也做成表，方便对照。需要注意的一点是，covers这个函数就是整个实验的核心，它把"假设覆盖样例"这件事翻译成了逐位比较。真实项目里这个函数会复杂得多——数值属性要比较范围，类别属性要查集合，缺失值要单独处理——但逻辑骨架完全一样。

melon = pd.DataFrame([ {"编号": 1, "色泽": "青绿", "根蒂": "蜷缩", "敲声": "浊响", "好瓜": "是"}, {"编号": 2, "色泽": "青绿", "根蒂": "稍蜷", "敲声": "沉闷", "好瓜": "否"}, ]) print(melon)

4.2 版本空间搜索的完整实现

版本空间的求解是一道筛选题：遍历假设空间，保留所有和正例一致、和负例都不一致的假设。

def version_space(space, positives, negatives=()): return [h for h in space if all(covers(h, x) for x in positives) and all(not covers(h, x) for x in negatives)] space = build_hypothesis_space() print("假设空间规模:", len(space)) # 期望 65 positives = [("青绿", "蜷缩", "浊响")] vs = version_space(space, positives) print("版本空间规模:", len(vs)) # 期望 8 for h in vs: print(dict(zip(ATTR_NAMES, h)))

跑出来的结果和我手算的一致：假设空间 65 个，版本空间 8 个，分别是三个属性各自在"具体值或通配"之间取值的八种组合。这八行输出就是第一章最容易看懂也最容易被忽略的一张图，教材用示意图画了一遍，你亲手打印一遍，印象会完全不同。

这里有个细节值得留意：如果把空集假设也算作候选，它在有正例的训练集上会被立刻剔除，因为空集表示"不存在好瓜"，与正例直接矛盾。所以最终版本空间里不会出现空集。这个小结论看起来无害，却能帮你以后理解更复杂的假设表示——比如带否定条件的规则，为什么同样会被正例一刀切掉。

注意：穷举法只在小规模假设空间里可行。我做过一次实验，把属性加到六个，规模涨到 3073，穷举还在毫秒级；再允许属性取子集，规模到五万，肉眼可见变慢；继续放大到析取式的组合，穷举就彻底不可行了。这就是为什么真实算法必须用启发式搜索代替枚举。

4.3 两个偏好各赢一局：亲手验证 NFL

现在做第一章最值得做的一个实验。版本空间里有 8 个假设，我用两种偏好各挑一个：偏好"尽可能特殊"，也就是具体值最多的那个；偏好"尽可能一般"，也就是通配符最多的那个。然后用两个测试样例分别检验。

def specificity(hyp): """具体值越多越特殊""" return float("inf") if hyp == EMPTY_HYP else sum(v != WILDCARD for v in hyp) def pick(vs, prefer): if prefer == "specific": return min(vs, key=lambda h: (-specificity(h), str(h))) return min(vs, key=lambda h: (specificity(h), str(h))) tests = [ (("青绿", "稍蜷", "浊响"), 1, "真实是好瓜"), (("乌黑", "稍蜷", "沉闷"), 0, "真实是坏瓜"), ] for prefer in ("specific", "general"): h = pick(vs, prefer) name = "空集" if h == EMPTY_HYP else dict(zip(ATTR_NAMES, h)) print(f"\n偏好 = {prefer}，挑中的假设 = {name}") for sample, label, desc in tests: pred = 1 if covers(h, sample) else 0 flag = "命中" if pred == label else "打脸" print(f" {desc}，预测 {'好瓜' if pred else '坏瓜'} -> {flag}")

跑出来的结论非常干净：偏好特殊的那个假设是"（青绿, 蜷缩, 浊响）"，它在第一个测试样例上打脸，在第二个上命中；偏好一般的那个假设是"（*, *, *）"，结果刚好反过来，第一个命中，第二个打脸。一胜一负，两边打平。

这个一胜一负的实验，就是 NFL 定理在最小规模上的现场演示。它没用任何数学，却把定理的实质说清楚了：**偏好决定你在哪类问题上赢，而不决定你赢多少。**你在测试样例 A 这类问题上希望模型更敢泛化，那么一般偏好是对的；在测试样例 B 这类问题上你希望模型更保守，那么特殊偏好是对的。而现实是你事先并不知道会遇到哪一类问题，只能根据对业务的理解去押注。

我在做风控相关的项目时对这一点体会很深。风控场景里样本极度不平衡，坏样本稀少但代价极高，这时候"宁可错杀"的偏好就是正确的，模型宁可把边界划得保守一些。换到推荐场景，目标是提高点击率，误判的代价很低，模型就该大胆泛化。"哪个偏好更好"这个问题，答案完全由代价结构决定，而不是由算法本身的先进程度决定。

5. 习题实战与常见问题速查

5.1 习题 1.1 手算详解：版本空间的通用算法

第一章的习题 1.1 是这么问的：在西瓜数据表里只保留编号 1 和编号 4 两个样例，给出相应的版本空间。这道题看着简单，但它检验的正是你有没有真正掌握"与训练集一致"这个定义。我把手算过程完整写下来，这是一套可以套用到任何类似问题上的通用算法。

第一步，确定每个属性在这两个正例上的取值。编号 1 是（青绿, 蜷缩, 浊响, 清晰, 凹陷, 硬滑）；编号 4 是（青绿, 蜷缩, 沉闷, 清晰, 凹陷, 硬滑）。如果你的教材版本取值不同，把下面的数字按同一方法重算即可，逻辑不变。

第二步，看每个属性取值是否相同。色泽两例都是青绿，所以假设该属性只能取"青绿"或通配符，两个选项。根蒂两例都是蜷缩，同理两个选项。敲声一个是浊响一个是沉闷，所以三个选项：浊响、沉闷或通配。纹理、脐部、触感三列两例取值相同，各两个选项。

第三步，把每个属性的选项数乘起来：

2 × 2 × 3 × 2 × 2 × 2 = 96

所以按合取式表示，版本空间里有 96 个假设。因为训练集中有正例，空集假设与正例矛盾，需要剔除，所以不用加进这个数。

这个"每个属性独立确定选项数、再连乘"的思路，可以处理绝大多数版本空间问题，包括带负例的情形——带负例时不能简单连乘了，需要逐个属性分析哪些组合会把负例覆盖进去然后剔除。我在教别人做题时发现，最容易错的不是乘法，而是漏掉"属性取值不同时要额外算一个选项"这一步。原理很简单：两个样例在某属性上取值不同，说明这个属性的取值不能固定，但又要覆盖两个正例，所以只能取通配符，而这个"通配"档和已有的两个具体值档并列，一共三档。想清楚这一层，就不会数错了。

注意：这 96 里包含通配符全填的那一种，也就是"任何瓜都是好瓜"。它在两个正例上都一致，所以合法。这提醒我们，版本空间里的假设质量参差不齐，全都是"与数据一致"的，但泛化表现可以差到天上去。

5.2 习题 1.2 的估算思路与坑

习题 1.2 问的是：如果允许用最多 k 个合取式的析合范式表示假设，假设空间有多大。这道题教材自己都说是"估算"，因为精确计数非常困难。但它背后的思路很有价值，我把我的分析过程摊开讲。

第一步先算单合取式的语法数量。六个属性，五个三取值、一个两取值，每个属性取具体值或通配符，得到 4 × 4 × 4 × 4 × 4 × 3 = 3072。注意这个 3072 是"语法形式"的数量，每一种形式唯一对应一种语义，所以语法和语义在这里是一一对应的。

第二步算单合取式的语义数量，也就是允许属性取任意非空子集。三取值属性有 2³ - 1 = 7 种非空子集，两取值属性有 2² - 1 = 3 种。所以语义层面有 7⁵ × 3 = 50421 种不同的单合取式。从 3072 到 50421，数量级没变，但差距有十六倍，这个差距全部来自"允许属性值取集合"这一个改动。

第三步才是难点：把 k 个单合取式用"或"连起来，不同的组合会大量重复。重复至少来自三个源头——直接重复，比如同一个合取式写两遍；包含关系，也就是集合的包含产生吸收，比如 A 的覆盖范围包含 B，那么 A 或 B 就等于 A；还有语义巧合，不同的一组盒子恰好覆盖同一批实例。要把这三类冗余全部扣干净，需要处理一个难度不低的组合计数问题。

我的建议是这道题不要死磕精确值，把三个层次想清楚就达到了目的：语法形式 3072、语义形式 50421、析取组合的组合级增长，然后用包含排斥的思路给出一个上界。你会发现即使只取 k = 2，上界也已经到了百万量级，这足以说明问题——表达能力的提升代价是搜索空间的爆炸式膨胀，这也是为什么后来主流的思路从"枚举假设"转向了"在连续参数空间里做优化"。

5.3 新手最容易搞混的五组概念

第一章的术语密度高，混淆点也就特别集中。我把教学过程中被问到最多的五组概念整理成表，每组给出一个可操作的分辨方法。

针对最后一行补充一句：很多人以为版本空间是"更小的假设空间"，这个说法不准确。版本空间是会随训练数据变化的，同一条假设在数据集 A 里属于版本空间，在数据集 B 里可能就被剔除了。假设空间则是由假设表示方式决定的，和数据无关——你换了数据，假设空间还是那 65 个。这个区分在理解"模型容量"这个概念时有直接作用：假设空间决定容量上限，训练数据决定你在容量里挑到哪一个。

5.4 常见问题速查表

下面这张表来自我和身边人读第一章时真实卡过的点，按被问到的频率排序。

心得：这六个问题里，真正会在实际工作中造成损失的只有两条——独立同分布假设不成立、以及偏好与问题分布不匹配。其余四条是理解问题，想通了就没有后患。所以读书时的时间分配也该按这个比例来，不必在术语细节上过度纠结。

6. 读书笔记怎么写才不白写

6.1 我的三栏笔记模板

前面提过笔记只记三样东西，这里给一个具体格式。我用的是三栏结构：第一栏写概念名和教材原文的页码定位；第二栏写我自己的复述，不看书，凭理解写，写不出来就说明没懂；第三栏写一个我自己构造的例子，而且这个例子要和教材里的例子不一样。

第一章我用这套模板写过一条典型的记录。"假设空间"这个概念，我的复述是"由假设表示方式决定的所有候选规律的集合，与数据无关"；我自己构造的例子是"用线性函数当假设表示时，假设空间是所有直线，不管手里有没有数据，直线都在那里"。这条记录的价值不在于它多深刻，而在于它让我在第 3 章读到线性模型时能立刻接上——原来线性模型的工作就是在那个我第一章就画好的直线集合里搜索。

第三栏的"自己构造例子"是我认为最有价值的一环。教材的西瓜例子只有一个，你如果也只用西瓜例子，很容易把理解绑定在这个具体场景上。换一个例子，比如"判断一封邮件是不是垃圾邮件"，你会发现假设空间的表示方式必须调整，因为关键词是稀疏高维的，合取式表示会失效，你必须换一种表示。这个换例子的过程，才是真正把一个概念从教材里搬到你脑子里的过程。

6.2 复习节奏与自测清单

技术书的复习不能靠重读，重读会带来虚假的熟悉感。我的做法是准备一份自测清单，每隔一段时间口头回答一遍，答不上来的地方才回去翻书。

第一章的清单我写了这么几条：假设空间和版本空间的区别是什么；为什么假设空间要加空集；三属性西瓜的假设空间规模是多少，六属性呢；NFL 定理说的是什么，它为什么不是"算法都差不多"的意思；奥卡姆剃刀和 NFL 定理矛盾吗，为什么不矛盾；i.i.d. 假设在真实数据上什么时候会失效。最后一条是我自己加的，教材没问，但它是我从项目经验里提炼的问题，价值比前几条都高。

复习节奏上，我的间隔大致是一周、一个月、三个月。第一章的内容在后面章节会反复出现，所以实际复习次数会远超这个安排——每次读到"假设空间"这个词，就顺手在脑子里过一遍定义，这种穿插式复习比集中重读有效得多。

6.3 从第一章往第 2 章走时要带着的问题

第一章读完，第 2 章讲模型评估与选择，是全书第二个理论高地。带着问题去读，效率会高很多。我列几个第一章留下的问题：训练误差低但泛化差，这个差距怎么量化；假设空间的容量和过拟合是什么关系；奥卡姆剃刀在具体算法里是怎么被翻译成数学目标的；既然 NFL 说没有免费的午餐，那交叉验证是在干什么。

最后一个问题我特别想强调，因为它连接了第一章和整个实践体系。交叉验证不能违反 NFL 定理，它做的事情是在你手上的这个具体数据集上，用有限的数据估计不同偏好的表现，然后选一个更适配当前问题的。它没有变出免费的午餐，只是用数据帮你找到这顿午餐在哪。想通这一点，你就不会对"某个模型在某个数据集上表现最好"感到困惑，也不会盲目地把这个结论搬到别的数据集上。

代码部分我建议第 2 章继续沿用，把第 4 章那两段代码扩一扩：把穷举版本空间的分支保留，再写一个按属性取值子集展开的版本，亲眼看一看规模从 3073 跳到 50421 的过程。跑一次不到一秒，但这个从数字到直观的转化，是任何图表都替代不了的。