从样例中学习 — 决策树(用一连串是/否问题做判断的流程图)、线性模型与集成
这一章讲三件事: 「学习」作为数学问题长什么样; 一个算法怎么在 12 个样例上长出一棵决策树、又怎么防止它背题; 以及真正开一个机器学习系统时,书里警告了什么。 读完你会带着一个判据去读任何学习方法:它在偏差和方差之间押了哪边?
1. 这一章讲什么
为什么要学习,书里给了两个朴素到无法反驳的理由:设计者无法预见 所有情形(迷宫机器人要应付每个新迷宫);设计者根本不知道怎么写 (你能认出家人的脸,却写不出认脸的程序)1。
监督学习(有标准答案可对的学习)的正式定义如下。
所谓训练集,就是 (x1,y1),…,(xN,yN) 这样一批带标准答案的样例(由未知的真函数 f 生成);任务是找一个假设 h 来近似真实的函数 f。h 取自假设空间 H——选 H 是比选用什么方法更根本的决定2。
2. 顶层全景
假设空间 H 的四个候选(图 19-1):直线 · 正弦 · 分段线性 · 12 次多项式
│
├─ 偏差:换数据集,预测离期望值偏多远(模型太简单 → 欠拟合)
├─ 方差:换数据集,假设本身变多少(模型太灵活 → 过拟合)
└─ 偏差-方差权衡;奥卡姆剃刀;「参数个数不是好标准」
│
三条技术路线:
决策树:信息增益选属性贪心生长,χ² 检验剪枝
线性模型:损失+梯度下降(SGD/小批量);逻辑斯谛回归做分类
非参数:kNN / SVM / 核;不写假设,记数据
│
集成:bagging/随机森林(并行)/boosting(串行纠错)
│
开发实践:数据(不平衡/离群值/增强)/经验法则/调试表/监控
3. 核心原理
3.1 主走查:12 个样例长出一棵树
主走查的输入是罗素本人的餐厅等待记录:10 个属性 (Alternate/Bar/Fri-Sat/Hungry/Patrons/Price/Raining/Reservation/Type/WaitEstimate), 输出 WillWait,共 12 个样例。书里特意算了家底: 属性组合有 9216 种,样例只有 12 个——归纳的本质是对缺失的 9204 个 输出「给出最好的猜测」3。
决策树的定义朴素:内部节点测一个属性,分支是属性值,叶子是输出4。 学习算法是贪心+分治:每个节点选「对分类影响最大」的属性。
根节点候选对比:
Type(French/Italian/Thai/Burger)→ 四个分支的正负比例一模一样:垃圾属性
Patrons(None/Some/Full) → None 分支全负、Some 分支全正、
Full 分支混合 —— 立刻砍掉两片子树!
→ 选 Patrons 做根;Full 分支里再选 Hungry;……
4 个出口条件:全正/全负→叶子;属性用尽→多数;样例空→父节点的多数
「影响最大」的量化是信息增益。熵(不确定性有多大:H(V)=−ΣP(vk)log2P(vk),越大越乱): 总是正面的硬币熵 0;公平硬币 1 位;四面骰子 2 位;99% 正面的硬币约 0.08 位 ——越不确定,熵越大。餐厅 12 样例正负各 6,根熵恰是 1 位; 按属性 A 分支后的期望剩余熵记 Remainder(A), Gain(A)=熵−Remainder(A)。Patrons 的增益最大(0.541 位), 稳坐树根6。
长出来的树(图 19-6)与罗素脑中的原树(图 19-3)不一样:它没用 Raining 和 Reservation 两个属性,还发现了一个连罗素本人都没注意的模式 ——「SR 会在周末等泰国菜」。书里借此事校正直觉:学习算法看的是样例, 不是「正确的函数」;它的假设与 12 个样例一致,而且更简单7。
过拟合(背下样例、没学到规律)在这里已经埋着:12 个样例上完美一致,不代表逼近真函数。 决策树的解药是剪枝:把 只有叶子做孩子的测试节点摘掉,判定标准是 χ² 显著性检验——零假设「该属性与分类无关」,5% 置信水平下 Δ≥7.82(3 自由度)才允许保留。Type 有 4 个值,自由度是 38。 性能的度量用学习曲线:训练集从 1 个加到 99 个,每档重复 20 次; 随机生成的餐厅数据上,准确率最终爬到 95%——书里管它叫「快乐图」9。
3.2 线性模型:梯度下降的全文
单变量回归 h=w1x+w0,平方误差损失。梯度下降——沿着误差的反方向一点点调参——的更新规则两行: w0←w0+α(y−hw(x));w1←w1+α(y−hw(x))·x——预测偏高就往下调, 输入为正就连带调斜率10。全量梯度下降每轮(epoch)扫全部 N 个样例, 损失面是凸的(无局部极小),但慢。
小份 SGD(每步只随机取 m 个样例算一次更新): N=10000、m=100 时,每步计算量降到 1/100,梯度标准误只升 √100=10 倍, 达到同等收敛要多走 10 步——总账还是快 10 倍。
这些更新还能吃满 GPU(显卡)的并行,训练提速11。
多变量版可以直接用公式一步解出最优权重:正规方程 w*=(X^⊤X)^{−1}X^⊤y;L1/L2 正则化 (惩罚|w|或 w²)把「偏好简单」写进损失12。
分类用逻辑斯谛回归:线性函数过 sigmoid 压到 (0,1),解释为概率, 损失换成交叉熵(预测分布与真实分布的差距)/负对数似然13。
它和朴素贝叶斯的对照在第 13 章 (生成 vs 判别:数据多判别赢,数据少生成赢)。
3.3 非参数与集成
kNN 不写任何假设,记下全部数据,查询时取 k 个最近邻(距离最近的样例)投票;
代价是维数灾难(高维(维度很多)空间「近」失去意义)与存储14。SVM 反其道而行, 只关心两类之间最宽的间隔,间隔边界上的点(支持向量)定义分界面; 核技巧让「在某高维空间里线性可分」不付出显式升维的代价15。
集成的两种性格:bagging/随机森林是并行——对训练集自助重采 样, 各长一棵树,投票;树之间的独立性削减方差。boosting 的现代形态——梯度提升(每轮拟合「当前模型的错误」)——是串行纠错—— 每一轮给上一轮分错的样例加权,逼下一个模型专攻它们16。 书里的在线学习一节还留了一句前瞻:错一次改一次的感知机可以长期在线, 这是「终身学习」的雏形。
3.4 开发机器学习系统:全书最实用的一节
- 数据量经验法则(书里明说这些「特殊而不严谨」但有用):困难问题 要几百万样例;一般问题约 1000;每类几百到几千;或「参数个数的 10 倍」17。
- 不平衡类:1000 万笔正常交易对 1000 笔欺诈——全判「正常」的垃圾模型 准确率高达 99.99%。药方:欠采样/过采样/加权损失/SMOTE 合成样例18。
- 离群值:一个 316 美元的餐厅混在一堆 30 美元里,线性回归全局受伤, 决策树只在局部节点里消化它——这是两类模型健壮性差异的机制解释19。
- 标签不可信:让人自报年龄的照片数据集,谎报不是随机噪声而是系统性偏差 ——弱监督(标签有噪声或缺损)学习的用武之地20。
4. 作者的判断与证据
- (书内实验) 图 19-1 的四假设空间对比、图 19-7 学习曲线(95%, 20 次平均)、Ng & Jordan 的生成/判别对比(见第 13 章)都是可复现实验9。
- (作者的方法论判断) 「仅通过参数个数衡量模型的适合程度并不是 一个好方法」——深度网络数十亿参数照样泛化,追求「合适」而非「简单」21。 这是全书对经典奥卡姆主义最明确的一次修正,也是通往第 14 章的桥。
- (书内坦白) 「表达能力与复杂性的权衡并不简单」:表达力强的语言 能让简单假设贴合数据;表达力弱的则逼出复杂假设22。
- (书内警示) 损失函数(给预测错误打分的函数)与真正目标(用户留存/收入)通常不一致, 要人工盯着这个错位23。
5. 边界与局限
- 本章所有方法假设 i.i.d.;分布漂移(用户口味、流量模式)只能在 「操作与监控」一节里以警告出现24。
- 信息增益偏爱取值多的属性(日期会把数据切成孤儿),需要增益率一类的修正。
- kNN 与核方法在小数据上漂亮,推理成本随数据线性增长,不在线上服役。
- 集成的可解释性弱于单树——诊断系统里要权衡。
6. 可带走的
- 先问「假设空间是什么」,再问「什么算法」——H 的形状决定天花板。
- 偏差=笨,方差=记性太好;过拟合的两种药:更多数据或更强的先验/正则。
- 信息增益=「这个属性能替我省多少位」;熵是它的计价单位。
- 剪枝的判据是统计检验,不是肉眼——χ² 告诉你属性值分布像不像随机。
- 小份更新 SGD 是「计算 ÷100 换噪声 ×10」的一笔稳 赚交易。
- 决策树对离群值健壮、线性模型敏感;混着用时先把长尾取对数。
- 不平衡数据上,准确率是骗人的;先定损失,再看指标。
7. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 为何学习 | 19 开篇 | text/10-fm.txt:20987(搜「两个主要的原因」) |
| 学习的形式/三反馈 | 19.1 | text/10-fm.txt:21042(搜「3 种类型的学习」) · text/10-fm.txt:21041(搜「回归」) |
| 加速一千万倍 | 19.1 | text/10-fm.txt:21021(搜「一千万倍」) |
| 监督学习定义 | 19.2 | text/10-fm.txt:21072(搜「训练集」) · text/10-fm.txt:21096(搜「测试集」) |
| 偏差与方差 | 19.2 | text/10-fm.txt:21118(搜「偏差」) · text/10-fm.txt:21124(搜「方差」) |
| 奥卡姆/爱因斯坦 | 19.2 | text/10-fm.txt:442(搜「爱因斯坦」) · text/10-fm.txt:21138(搜「奥卡姆」) |
| 参数个数不是标准 | 19.2 | text/10-fm.txt:22159(搜「数十亿个」) |
| 餐厅 12 样例 | 19.2 | text/10-fm.txt:21193(搜「12 个样例」) · text/10-fm.txt:21194(搜「9216」) |
| 决策树定义 | 19.3 | text/10-fm.txt:21217(搜「决策树」) |
| Type 差 Patrons 好 | 19.3.2 | text/10-fm.txt:21262(搜「Type 是一个较差」) |
| 4 个出口条件 | 19.3.2 | text/10-fm.txt:21267(搜「全为正」) |
| 与原树不同/周末泰国菜 | 19.3.2 | text/10-fm.txt:21284(搜「截然不同」) · text/10-fm.txt:21309(搜「泰国」) |
| 学习曲线 95% | 19.3.2 | text/10-fm.txt:21315(搜「学习曲线」) · text/10-fm.txt:21322(搜「95%」) |
| 熵与硬币 | 19.3.3 | text/10-fm.txt:21332(搜「熵」) · text/10-fm.txt:21345(搜「0.08」) |
| 信息增益 | 19.3.3 | text/10-fm.txt:21330(搜「信息增益」) |
| χ² 剪枝 | 19.3.4 | text/10-fm.txt:21387(搜「显著性检验」) · text/10-fm.txt:21402(搜「7.82」) |
| 模型选择/正则化 | 19.4 | text/10-fm.txt:21510(搜「模型选择」) · text/10-fm.txt:21646(搜「正则化」) |
| PAC/没有免费午餐 | 19.5 | text/10-fm.txt:21712(搜「学习理论」) |
| 梯度下降更新 | 19.6.2 | text/10-fm.txt:21921(搜「w0 ← w0」) |
| 小批量 SGD 账 | 19.6.2 | text/10-fm.txt:21938(搜「100」) |
| 正规方程 | 19.6.3 | text/10-fm.txt:21981(搜「w*」) |
| 逻辑斯谛回归 | 19.6.5 | text/10-fm.txt:22103(搜「逻辑斯谛回归」) |
| kNN/维数灾难 | 19.7.1 | text/10-fm.txt:22171(搜「最近邻模型」) |
| SVM | 19.7.5 | text/10-fm.txt:22328(搜「支持向量机」) |
| bagging/随机森林/boosting | 19.8 | text/10-fm.txt:22468(搜「自助聚合法」) · text/10-fm.txt:22551(搜「自适应提升法」) |
| 问题形式化(巴黎) | 19.9.1 | text/10-fm.txt:7326(搜「巴黎」) |
| 数据量经验法则 | 19.9.2 | text/10-fm.txt:1282(搜「几百万」) |
| 不平衡类 99.99% | 19.9.2 | text/10-fm.txt:22796(搜「99.99%」) |
| 离群值 316 美元 | 19.9.2 | text/10-fm.txt:22810(搜「316」) · text/10-fm.txt:1335(搜「健壮性」) |
| 弱监督/谎报年龄 | 19.9.1 | text/10-fm.txt:22742(搜「谎报」) |
| 监控与维护 | 19.9.5 | text/10-fm.txt:22980(搜「操作、监控和维护」) |