拓冰网站定制 
《机器学习》这本书因为通篇拿西瓜举例在圈子里被喊成西瓜书。我把这一轮精读的笔记整理成连载戏称为吃瓜教程——一边啃书一边吃瓜第一章就是这盘瓜的开胃菜。这篇读书笔记对应第一章绪论翻开只有薄薄几十页通篇全是定义和示意图连一个像样的公式推导都没有很多人读到这里会下意识加速翻过去觉得先看后面讲算法的部分才有意思。真正动手做过项目之后我才明白第一章不是序言而是地基它给出了整套术语体系、一个叫假设空间的抽象结构以及一条决定所有算法命运的归纳偏好。这三个东西在后面每一章都会反复出现你在第一章偷的懒会在第 4 章决策树、第 8 章集成学习里连本带利还回去。这篇笔记适合三类人第一类是刚接触机器学习、被属性、特征、样例、标记这堆词绕晕的新手第二类是做过几个调包项目、但被问到版本空间是什么会卡壳的实践者第三类是想把西瓜书当教材系统过一遍、需要一份可复现笔记的读者。我会把第一章拆成术语链、假设空间、归纳偏好三块每一块都补上教材没细说的推导和容易踩的坑最后附上两段可以直接跑的代码用程序把版本空间穷举出来再亲手验证一遍天下没有免费的午餐到底在说什么。1. 第一章在全书里的位置1.1 为什么这本书叫西瓜书第一章又为什么不能跳先说个很多人不知道的细节西瓜书里的西瓜不是为了可爱而是因为这个小样本足够小小到你可以用纸笔把假设空间全部枚举出来。一个样本只有色泽、根蒂、敲声三个属性每个属性三个取值加上通配符总共六十四种组合再加一个世界上没有好瓜这个特殊假设一共六十五种假设。这个数量级刚好卡在人脑能算、算完有收获的甜点区。如果把属性换成一百个连续特征你连图都画不出来更别说理解了。所以第一章的设计意图很明确用一个能穷举的最小例子把机器学习的核心矛盾暴露出来。这个矛盾是——**给定有限的训练数据能满足条件的假设往往不止一个而你必须选一个。**选哪一个凭什么选选错了会怎样这三个问题构成了第一章的全部张力。教材后面所有章节无论是决策树的分裂准则、支持向量机的最大间隔、还是神经网络的损失函数本质上都在回答怎么从一个巨大的假设空间里挑出那个更好的假设只是换了一种更聪明的搜索方式而已。我在第一次读的时候把第一章当成名词解释背了一遍结果读到第 3 章线性模型时看到假设空间四个字就懵了这不是第一章那个东西吗怎么又出现了。第二次读才反应过来第一章讲的是一个和具体算法无关的通用框架后面的章节只是往这个框架里填不同的假设表示形式。线性模型的假设空间是所有线性函数决策树的假设空间是所有树结构神经网络是所有给定结构的参数组合。框架是同一个搜索策略不同。理解这一点之后再读后面就会顺畅很多。心得读第一章的正确姿势不是记住定义而是先建立一个数据—假设空间—搜索—泛化的心智模型。后面每读一个新算法都试着回答一句它在什么假设空间里搜索用什么准则挑归纳偏好是什么。1.2 第一章的三条主线与推荐阅读顺序第一章的内容如果按教材顺序平铺下去是引言、基本术语、假设空间、归纳偏好、发展历程、应用现状六节。我的建议是打乱顺序读按概念—结构—哲学—背景四步走效率会高很多。第一步先读基本术语也就是 1.2 节把这套黑话打通。这一步没有任何理解难度纯记忆但它是后面所有讨论的语言基础跳过它等于用外语读数学。第二步直接跳到假设空间和版本空间。这两节是第一章唯一的硬核部分也是最能体现机器学习思维方式的地方。它回答的是学习算法把什么当成候选答案。西瓜书在这里给出的合取式表示法虽然简单到有点简陋但它是后面所有假设表示法的原型属性取值加通配符本质上是某些条件下必然成立的逻辑表达。你把这个小例子彻底吃透将来看到特征工程里的交叉特征、规则引擎里的条件组合会有种似曾相识的感觉。第三步读归纳偏好这一节是第一章的思想高地。奥卡姆剃刀和 NFL 定理这两把刀一把告诉你多解时挑简单的另一把紧接着告诉你任何偏好都不是免费的。这两句话表面矛盾实际上是一体两面偏好必须存在但偏好一定会在某些问题上害你。这个认识是后面做模型选型时的底层依据。第四步才是引言、发展历程和应用现状。这三节读起来轻松但不要完全跳过它们提供的是坐标系——你至少要知道专家系统时代和统计学习时代的分界线在哪知道为什么上世纪末机器学习会从手写规则转向从数据里学规则。这段历史不长但是理解很多设计动机的钥匙比如为什么评估指标里会有那么多过拟合相关的概念。注意发展历程那几页别当成科普读物一扫而过它解释了一件事——为什么现在的主流方法都强调从数据中学习而不是人工编码知识。这个转向的理由直接决定了你在实际项目里应该把精力花在哪里。1.3 笔记该记什么不该记什么这一点说给做笔记的人听。我前几轮读技术书习惯把定义一字不差抄下来笔记做得像排版精美的词典结果复习的时候根本不想翻因为翻开全是自己已经知道的东西没有信息增量。后来改了方法笔记只记三样东西——我自己复述的定义、我自己构造的例子、我自己踩过的坑。定义原文书上就有抄一遍没有价值但如果我用自己的话重写一遍写不出来的地方就暴露了理解漏洞。这一点在第一章特别有效因为第一章的定义密度极高属性空间和样本空间到底是不是一回事标记和属性值有什么区别这些问题只有你动笔复述时才会发现。比如样本空间和标记空间书上是分两处定义的位置上隔了好几页。我第一遍读的时候模糊地觉得都是空间没什么区别。第二遍写笔记时才意识到前者是属性张成的空间一个样本对应其中一个点后者是所有可能的标记构成的集合一个样本的答案对应其中一个点。两者维度完全不同一个是属性个数维度一个是输出类型维度。分类任务的标记空间是离散的类别集合回归任务的标记空间是实数集。这个区分在写代码时非常具体你处理的是特征矩阵的形状还是标签数组的形状完全是两件事。2. 术语是门槛把第一章的定义串成一条链2.1 从一张西瓜表格说起数据集、样本、属性、特征向量第一章的基本术语看起来零散其实是一条完整的链只要顺着一个具体例子走一遍就通了。教材里给了一张西瓜数据表后面章节反复用到我们就拿它当道具。一张表就是一个数据集记号上通常写作 D {x₁, x₂, ..., xₘ}m 是样本数。表里的每一行是一个样本也叫示例是关于一个对象的描述。表里的每一列描述对象某个方面的性质叫属性也叫特征。属性上的取值叫属性值。比如色泽是一个属性青绿是它的一个属性值。把属性张成的空间叫作属性空间也叫样本空间或输入空间。一只西瓜的色泽、根蒂、敲声三个属性各自确定了一个维度三个维度张成一个三维空间每只西瓜就是这个空间里的一个点。因为空间中的每个点对应一个坐标向量所以一个样本也叫一个特征向量。属性的个数就是这个空间的维数也叫样本的维数。这里有个特别容易出错的点我当年就栽过**属性的个数和特征向量的长度并不总是一一对应。**教材语境下它们相等因为教材默认属性是标称型的一个属性对应一个坐标。但真实项目里色泽这种多类别属性你一旦做独热编码它就从一维变成三维特征向量的长度立刻超过属性个数。所以当你看到某个模型报告的特征维度和原始表的列数不一致时不要慌先想想中间经历了什么编码操作。术语教材定义西瓜例子实际项目里的对应数据集样本的集合整张西瓜表一份 csv一个 DataFrame样本/示例关于一个对象的描述一行西瓜记录表里的一行属性/特征反映对象某方面性质的事项色泽、根蒂、敲声表头的一列属性值属性上的取值青绿、蜷缩、浊响单元格内容属性空间属性张成的空间三维的瓜空间特征矩阵的列空间特征向量样本在属性空间中的坐标(青绿, 蜷缩, 浊响)一行 numpy 数组维数属性的个数3编码后的列数注意教材说维数等于属性个数这是在有明确前提的语境下成立的。做工程时如果拿这句话去校验数据形状很容易对不上号因为类别编码、文本向量化、缺失值填充都会改变实际的列数。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| (31)⁵ × (21) 1 4⁵ × 3 1 1024 × 3 1 3073从 65 到 3073属性只从三个变成六个规模翻了将近五十倍。这就是维度增长带来的第一课假设空间的大小随属性个数指数增长。但更要命的事情在后面。如果允许假设中的每个属性不填单个值而是填一组值的集合比如色泽属于青绿或乌黑那么每个三取值属性就有 2³ - 1 7 种非空子集可选两取值属性有 2² - 1 3 种。假设空间规模变成7⁵ × 3 16807 × 3 50421从 3072 到 50421假设的语法形式几乎没有变化只是允许了或的写法规模就膨胀了十六倍多。如果再做析合范式的扩展也就是允许若干个合取式用或连接起来规模会继续爆炸。这三个数字放在一起指向同一个结论**假设空间的表达能力、规模和搜索可行性之间是三方博弈无法同时最大化。**这也是为什么后面每一章介绍的算法实际上都是在这个博弈里做的一次具体取舍。决策树用递归划分来避开全局枚举支持向量机用核函数在隐式空间里做搜索神经网络用梯度下降在连续参数空间里找局部最优。它们都放弃了穷举保证找到最优假设这条路换取可行性。假设表示属性取值选项三值属性规模6 属性西瓜特点单值或通配符43073教材主线可手算属性取值的任意非空子集750421表达或规模膨胀最多 k 个合取式的析取组合级增长难以精确计数表达能力强搜索困难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, keylambda h: (-specificity(h), str(h))) return min(vs, keylambda 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 这类问题上你希望模型更保守那么特殊偏好是对的。而现实是你事先并不知道会遇到哪一类问题只能根据对业务的理解去押注。我在做风控相关的项目时对这一点体会很深。风控场景里样本极度不平衡坏样本稀少但代价极高这时候宁可错杀的偏好就是正确的模型宁可把边界划得保守一些。换到推荐场景目标是提高点击率误判的代价很低模型就该大胆泛化。哪个偏好更好这个问题答案完全由代价结构决定而不是由算法本身的先进程度决定。偏好挑中的假设测试样例 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 新手最容易搞混的五组概念第一章的术语密度高混淆点也就特别集中。我把教学过程中被问到最多的五组概念整理成表每组给出一个可操作的分辨方法。易混概念本质区别一句话分辨法样本空间 vs 标记空间前者由属性张成后者由答案取值构成看维度属性维度 vs 输出维度样本 vs 样例有没有标记有标签的那一行才叫样例属性 vs 特征向量一个是列一个是行一列是属性一行的坐标是特征向量分类 vs 回归标记空间是离散还是连续问一句答案能不能取小数版本空间 vs 假设空间前者是后者的子集版本空间一定和训练数据完全一致针对最后一行补充一句很多人以为版本空间是更小的假设空间这个说法不准确。版本空间是会随训练数据变化的同一条假设在数据集 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 的过程。跑一次不到一秒但这个从数字到直观的转化是任何图表都替代不了的。 西瓜书第一章精读：假设空间、版本空间与归纳偏好
《机器学习》这本书因为通篇拿西瓜举例在圈子里被喊成西瓜书。我把这一轮精读的笔记整理成连载戏称为吃瓜教程——一边啃书一边吃瓜第一章就是这盘瓜的开胃菜。这篇读书笔记对应第一章绪论翻开只有薄薄几十页通篇全是定义和示意图连一个像样的公式推导都没有很多人读到这里会下意识加速翻过去觉得先看后面讲算法的部分才有意思。真正动手做过项目之后我才明白第一章不是序言而是地基它给出了整套术语体系、一个叫假设空间的抽象结构以及一条决定所有算法命运的归纳偏好。这三个东西在后面每一章都会反复出现你在第一章偷的懒会在第 4 章决策树、第 8 章集成学习里连本带利还回去。这篇笔记适合三类人第一类是刚接触机器学习、被属性、特征、样例、标记这堆词绕晕的新手第二类是做过几个调包项目、但被问到版本空间是什么会卡壳的实践者第三类是想把西瓜书当教材系统过一遍、需要一份可复现笔记的读者。我会把第一章拆成术语链、假设空间、归纳偏好三块每一块都补上教材没细说的推导和容易踩的坑最后附上两段可以直接跑的代码用程序把版本空间穷举出来再亲手验证一遍天下没有免费的午餐到底在说什么。1. 第一章在全书里的位置1.1 为什么这本书叫西瓜书第一章又为什么不能跳先说个很多人不知道的细节西瓜书里的西瓜不是为了可爱而是因为这个小样本足够小小到你可以用纸笔把假设空间全部枚举出来。一个样本只有色泽、根蒂、敲声三个属性每个属性三个取值加上通配符总共六十四种组合再加一个世界上没有好瓜这个特殊假设一共六十五种假设。这个数量级刚好卡在人脑能算、算完有收获的甜点区。如果把属性换成一百个连续特征你连图都画不出来更别说理解了。所以第一章的设计意图很明确用一个能穷举的最小例子把机器学习的核心矛盾暴露出来。这个矛盾是——**给定有限的训练数据能满足条件的假设往往不止一个而你必须选一个。**选哪一个凭什么选选错了会怎样这三个问题构成了第一章的全部张力。教材后面所有章节无论是决策树的分裂准则、支持向量机的最大间隔、还是神经网络的损失函数本质上都在回答怎么从一个巨大的假设空间里挑出那个更好的假设只是换了一种更聪明的搜索方式而已。我在第一次读的时候把第一章当成名词解释背了一遍结果读到第 3 章线性模型时看到假设空间四个字就懵了这不是第一章那个东西吗怎么又出现了。第二次读才反应过来第一章讲的是一个和具体算法无关的通用框架后面的章节只是往这个框架里填不同的假设表示形式。线性模型的假设空间是所有线性函数决策树的假设空间是所有树结构神经网络是所有给定结构的参数组合。框架是同一个搜索策略不同。理解这一点之后再读后面就会顺畅很多。心得读第一章的正确姿势不是记住定义而是先建立一个数据—假设空间—搜索—泛化的心智模型。后面每读一个新算法都试着回答一句它在什么假设空间里搜索用什么准则挑归纳偏好是什么。1.2 第一章的三条主线与推荐阅读顺序第一章的内容如果按教材顺序平铺下去是引言、基本术语、假设空间、归纳偏好、发展历程、应用现状六节。我的建议是打乱顺序读按概念—结构—哲学—背景四步走效率会高很多。第一步先读基本术语也就是 1.2 节把这套黑话打通。这一步没有任何理解难度纯记忆但它是后面所有讨论的语言基础跳过它等于用外语读数学。第二步直接跳到假设空间和版本空间。这两节是第一章唯一的硬核部分也是最能体现机器学习思维方式的地方。它回答的是学习算法把什么当成候选答案。西瓜书在这里给出的合取式表示法虽然简单到有点简陋但它是后面所有假设表示法的原型属性取值加通配符本质上是某些条件下必然成立的逻辑表达。你把这个小例子彻底吃透将来看到特征工程里的交叉特征、规则引擎里的条件组合会有种似曾相识的感觉。第三步读归纳偏好这一节是第一章的思想高地。奥卡姆剃刀和 NFL 定理这两把刀一把告诉你多解时挑简单的另一把紧接着告诉你任何偏好都不是免费的。这两句话表面矛盾实际上是一体两面偏好必须存在但偏好一定会在某些问题上害你。这个认识是后面做模型选型时的底层依据。第四步才是引言、发展历程和应用现状。这三节读起来轻松但不要完全跳过它们提供的是坐标系——你至少要知道专家系统时代和统计学习时代的分界线在哪知道为什么上世纪末机器学习会从手写规则转向从数据里学规则。这段历史不长但是理解很多设计动机的钥匙比如为什么评估指标里会有那么多过拟合相关的概念。注意发展历程那几页别当成科普读物一扫而过它解释了一件事——为什么现在的主流方法都强调从数据中学习而不是人工编码知识。这个转向的理由直接决定了你在实际项目里应该把精力花在哪里。1.3 笔记该记什么不该记什么这一点说给做笔记的人听。我前几轮读技术书习惯把定义一字不差抄下来笔记做得像排版精美的词典结果复习的时候根本不想翻因为翻开全是自己已经知道的东西没有信息增量。后来改了方法笔记只记三样东西——我自己复述的定义、我自己构造的例子、我自己踩过的坑。定义原文书上就有抄一遍没有价值但如果我用自己的话重写一遍写不出来的地方就暴露了理解漏洞。这一点在第一章特别有效因为第一章的定义密度极高属性空间和样本空间到底是不是一回事标记和属性值有什么区别这些问题只有你动笔复述时才会发现。比如样本空间和标记空间书上是分两处定义的位置上隔了好几页。我第一遍读的时候模糊地觉得都是空间没什么区别。第二遍写笔记时才意识到前者是属性张成的空间一个样本对应其中一个点后者是所有可能的标记构成的集合一个样本的答案对应其中一个点。两者维度完全不同一个是属性个数维度一个是输出类型维度。分类任务的标记空间是离散的类别集合回归任务的标记空间是实数集。这个区分在写代码时非常具体你处理的是特征矩阵的形状还是标签数组的形状完全是两件事。2. 术语是门槛把第一章的定义串成一条链2.1 从一张西瓜表格说起数据集、样本、属性、特征向量第一章的基本术语看起来零散其实是一条完整的链只要顺着一个具体例子走一遍就通了。教材里给了一张西瓜数据表后面章节反复用到我们就拿它当道具。一张表就是一个数据集记号上通常写作 D {x₁, x₂, ..., xₘ}m 是样本数。表里的每一行是一个样本也叫示例是关于一个对象的描述。表里的每一列描述对象某个方面的性质叫属性也叫特征。属性上的取值叫属性值。比如色泽是一个属性青绿是它的一个属性值。把属性张成的空间叫作属性空间也叫样本空间或输入空间。一只西瓜的色泽、根蒂、敲声三个属性各自确定了一个维度三个维度张成一个三维空间每只西瓜就是这个空间里的一个点。因为空间中的每个点对应一个坐标向量所以一个样本也叫一个特征向量。属性的个数就是这个空间的维数也叫样本的维数。这里有个特别容易出错的点我当年就栽过**属性的个数和特征向量的长度并不总是一一对应。**教材语境下它们相等因为教材默认属性是标称型的一个属性对应一个坐标。但真实项目里色泽这种多类别属性你一旦做独热编码它就从一维变成三维特征向量的长度立刻超过属性个数。所以当你看到某个模型报告的特征维度和原始表的列数不一致时不要慌先想想中间经历了什么编码操作。术语教材定义西瓜例子实际项目里的对应数据集样本的集合整张西瓜表一份 csv一个 DataFrame样本/示例关于一个对象的描述一行西瓜记录表里的一行属性/特征反映对象某方面性质的事项色泽、根蒂、敲声表头的一列属性值属性上的取值青绿、蜷缩、浊响单元格内容属性空间属性张成的空间三维的瓜空间特征矩阵的列空间特征向量样本在属性空间中的坐标(青绿, 蜷缩, 浊响)一行 numpy 数组维数属性的个数3编码后的列数注意教材说维数等于属性个数这是在有明确前提的语境下成立的。做工程时如果拿这句话去校验数据形状很容易对不上号因为类别编码、文本向量化、缺失值填充都会改变实际的列数。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| (31)⁵ × (21) 1 4⁵ × 3 1 1024 × 3 1 3073从 65 到 3073属性只从三个变成六个规模翻了将近五十倍。这就是维度增长带来的第一课假设空间的大小随属性个数指数增长。但更要命的事情在后面。如果允许假设中的每个属性不填单个值而是填一组值的集合比如色泽属于青绿或乌黑那么每个三取值属性就有 2³ - 1 7 种非空子集可选两取值属性有 2² - 1 3 种。假设空间规模变成7⁵ × 3 16807 × 3 50421从 3072 到 50421假设的语法形式几乎没有变化只是允许了或的写法规模就膨胀了十六倍多。如果再做析合范式的扩展也就是允许若干个合取式用或连接起来规模会继续爆炸。这三个数字放在一起指向同一个结论**假设空间的表达能力、规模和搜索可行性之间是三方博弈无法同时最大化。**这也是为什么后面每一章介绍的算法实际上都是在这个博弈里做的一次具体取舍。决策树用递归划分来避开全局枚举支持向量机用核函数在隐式空间里做搜索神经网络用梯度下降在连续参数空间里找局部最优。它们都放弃了穷举保证找到最优假设这条路换取可行性。假设表示属性取值选项三值属性规模6 属性西瓜特点单值或通配符43073教材主线可手算属性取值的任意非空子集750421表达或规模膨胀最多 k 个合取式的析取组合级增长难以精确计数表达能力强搜索困难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, keylambda h: (-specificity(h), str(h))) return min(vs, keylambda 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 这类问题上你希望模型更保守那么特殊偏好是对的。而现实是你事先并不知道会遇到哪一类问题只能根据对业务的理解去押注。我在做风控相关的项目时对这一点体会很深。风控场景里样本极度不平衡坏样本稀少但代价极高这时候宁可错杀的偏好就是正确的模型宁可把边界划得保守一些。换到推荐场景目标是提高点击率误判的代价很低模型就该大胆泛化。哪个偏好更好这个问题答案完全由代价结构决定而不是由算法本身的先进程度决定。偏好挑中的假设测试样例 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 新手最容易搞混的五组概念第一章的术语密度高混淆点也就特别集中。我把教学过程中被问到最多的五组概念整理成表每组给出一个可操作的分辨方法。易混概念本质区别一句话分辨法样本空间 vs 标记空间前者由属性张成后者由答案取值构成看维度属性维度 vs 输出维度样本 vs 样例有没有标记有标签的那一行才叫样例属性 vs 特征向量一个是列一个是行一列是属性一行的坐标是特征向量分类 vs 回归标记空间是离散还是连续问一句答案能不能取小数版本空间 vs 假设空间前者是后者的子集版本空间一定和训练数据完全一致针对最后一行补充一句很多人以为版本空间是更小的假设空间这个说法不准确。版本空间是会随训练数据变化的同一条假设在数据集 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 的过程。跑一次不到一秒但这个从数字到直观的转化是任何图表都替代不了的。