线性模型

这一章是西瓜书里最"友好"的一章，也是最容易被读快的一章。原因很矛盾：公式看起来都认识，但每一步之间的跳跃其实不小——比如 3.2 里两个偏导数是怎么变成闭式解的，3.3 里似然函数怎么化简成那个样子，3.4 里为什么 w = S_w^-1(μ₀-μ₁) 就冒出来了。

所以这份讲义的做法是：先把每段话翻译成人话，再逐个符号解释，最后补上被省略的中间步骤。你可以把它当成"带旁白的西瓜书第 3 章"。

本章地图先看全局，再进细节

第 3 章从头到尾只在回答一个问题：怎么用"加权求和"这一个动作，去干完机器学习里几乎所有的基础任务？

看这张图的顺序很重要：3.2 解决"回归"，3.3 和 3.4 解决"二分类"（两条完全不同的路线），3.5 把二分类拼成多分类，3.6 修补 3.5 留下的一个漏洞。这也是原书那句"我们先从回归任务开始，然后讨论二分类和多分类任务"的意思。

3.1 基本形式全章的地基

先看定义。给定一个样本 x，它有 d 个属性（比如西瓜的色泽、根蒂、敲声……一共 d 个），那么：

这句话的人话版：每个属性乘上它自己的分量（权重），全部加起来，再补一个底数。就这么简单。

举个具体的：假设判断一个西瓜甜不甜，只看三个属性——糖度 12、水分 80、重量 5。模型是 0.8×糖度 + 0.1×水分 − 0.3×重量 + 2，那预测值就是 9.6 + 8 − 1.5 + 2 = 18.1。模型干的全部事情，就是这一行加法。

三个符号，逐个说清

然后是向量写法。把 w 和 x 各自打包成一个有序的列表（这就是"向量"），式 (3.1) 那串加法就能写成：

为什么这么简单的东西值得单独一节？

书给了三条理由，值得一条条体会：

1. 它是很多强模型的骨架。原书说"许多功能更为强大的非线性模型可在线性模型的基础上通过引入层级结构或高维映射而得"。翻译一下：神经网络的一层，本质就是 w^Tx+b 再套一个非线性函数（第 5 章）；支持向量机能处理非线性，靠的是先把数据映射到高维再在这个高维空间里做线性划分（第 6 章）。所以这一章没读懂，第 5、6 章会很痛苦。
2. 它可解释。这是线性模型独有的优势。书里的例子：若学得
   f_好瓜(x) = 0.2·色泽 + 0.5·根蒂 + 0.3·敲声 + 1，
   因为根蒂的权重 0.5 最大，敲声 0.3 次之，色泽 0.2 最小，所以可以读成："根蒂最要紧，敲声比色泽更重要。"权重的大小直接就是重要性排序，这在深度神经网络里是拿不到的。
3. 它形式简单、易于建模。参数只有 d+1 个，训练快，不容易过拟合，出了问题也好排查。

3.2 线性回归让模型输出一个实数

回归任务的意思是：要预测的东西是连续的实数——房价、温度、西瓜的含糖量。这类任务里，"线性模型"就叫"线性回归"（linear regression）。

数据集的写法先熟悉一下：

读作：一共有 m 个样本，第 i 个样本有 d 个属性（记作向量 x_i），它的正确答案是实数 y_i。m 是样本个数，d 是属性个数，这两个数在这一章里反复出现，别搞混。

动笔之前：离散属性怎么变成数字

模型只会做加减乘，所以属性必须是数。但现实里的属性常常是"高/中/低""西瓜/南瓜/黄瓜"。书里给了两条规则，分界线只有一条：这些取值之间有没有"序"（大小顺序）。

先解最简单的情况：只有一个属性

这时候样本就是一个数 x_i，模型是一条直线：

那个 ≃ 是"约等于"，很关键——它承认了不可能全部拟合准，能接近就行。

第一步：先定义什么叫"差"

要挑最好的 w 和 b，得先能比较"谁更好"。书里用的是均方误差（第 2.2 节讲过，回归任务最常用的性能度量），也就是把所有样本的误差平方加起来：

符号解释：arg min 的意思是"让后面那坨东西取到最小值的那个参数"。所以整句读作：找一组 (w, b)，使所有样本的误差平方和最小。那个带星号的 w^*、b^* 就是最优解。

把这个误差和记作 E_(w,b)。基于"最小化均方误差"来求解的方法，就叫最小二乘法（least square method）。

书里还说了一句几何意义：均方误差"对应了常用的欧几里得距离"。这里要稍微抠一下——严格说，它对应的是每个样本到直线的竖直方向距离（也就是残差）的平方和，不是垂直距离。垂直距离要除以 √(1+w²)，那会变成另一个问题（叫"正交回归"）。做作业和考试时按"竖直距离"理解就不会错。

第二步：为什么可以"求导置零"就完事

因为 E_(w,b) 是个凸函数。凸函数你可以想成一个碗：只有一个最低点，没有别的小坑。所以只要找到"斜率为 0"的地方，那一定是全局最低点，不用怕掉进局部最优。

书里给的严格定义是：对区间上任意两点 x₁、x₂，若

则称 f 为凸函数。人话：取两点的中点，函数在这个中点的高度，不超过"两点连线的中点高度"。碗的形状正是这样——碗底比弦低。

怎么判断？书给了实用判据（一元函数）：二阶导数 ≥ 0 就是凸函数；如果二阶导恒大于 0，叫严格凸函数。f(x) = x² 的二阶导是 2 > 0，所以它是典型的凸函数，形状是 U 型。

第三步：动手求导（书里跳过的中间步骤在这里）

书直接给出了两个偏导数。我们把它补全。误差和是：

对 w 求偏导——把 b 当常数，用链式法则（外面平方的导数 × 里面式子的导数）：

对 b 求偏导——把 w 当常数，里面式子的导数是 −1：

令两个偏导都等于 0，得到两个方程。先看第二个（对 b 的那个），除以 −2：

这里用了 ∑_i b = m b（b 是常数，加了 m 次）。再把 x̄ = (1/m)∑x_i、ȳ = (1/m)∑y_i 代进去，就得到一句非常好记的话：

现在把 b = ȳ − w x̄ 代回第一个方程，解 w：

于是得到闭式解（闭式解 = 能直接用公式算出来，不用一步步迭代试）：

把这句话画出来

更一般的情况：有 d 个属性

现在样本是一个向量了，模型变成：

这叫多元线性回归（multivariate linear regression）。思路和一元完全一样，只是记号要升一级。

关键技巧：把 b 藏进 w 里

每处理一次 b 都很啰嗦。有个惯用招式：给每个样本人为补一个恒等于 1 的属性，同时给 w 补上 b 这一项。于是：

验证一下：把最后那个乘 1 的项展开，就是 … + b·1，正好是 b。所以b 就这样被"吸收"进去了，之后不用单独管它。代价是参数从 d 个变成 d+1 个。

把整个数据集写成矩阵 X，大小是 m × (d+1)——每一行是一个样本，前 d 列是 d 个属性，最后一列全是 1：

再把所有答案摞成一个列向量 y = (y₁; y₂; …; y_m)。于是目标变成：

人话：Xŵ 是所有样本的预测值（一列），y 是真实值（一列），两者相减就是每个样本的误差（一列）。(…)^T(…) 就是把这一列误差各自平方再求和——和式 (3.4) 的平方和是一回事，只是写成矩阵形式。

对 ŵ 求导（这一步书里也是直接给结果）：

令它为零：X^TXŵ = X^Ty。两边同时左乘 (X^TX)^-1，得到那个必须记住的公式：

最后把 ŵ^* 拆回 w 和 b，模型就学完了：

但是：那个逆矩阵不一定存在

式 (3.12) 里有一步"求逆"。求逆的前提是 X^TX 满秩（full-rank）或正定（positive definite）。书上接着就说了：现实任务中它往往不满秩。

什么时候不满秩？两种典型情况：

• 属性比样本多（d+1 > m）。书里的例子很生动：生物信息学的基因芯片数据，动辄上万个属性（基因），但样本只有几十上百个。
• 属性之间有线性关系。比如你同时把"身高（厘米）"和"身高（米）"放进模型——信息完全重复，矩阵必然不满秩。

后果是什么？会解出无穷多组 ŵ，它们让均方误差同样小（都等于最小值）。就像方程 x + y = 1 有无数个解一样，条件不够，定不下来唯一解。

这时候要选哪一个？原书说："将由学习算法的归纳偏好决定，常见的做法是引入正则化项"。

最后一步：从"线性回归"到"广义线性模型"

到这里 y = w^Tx + b 已经能拟合了。但书在这里拐了个弯，问了一个很好的问题：

"可否令模型预测值逼近 y 的衍生物呢？"

举个场景：某个量是指数增长的（人口、复利、细菌繁殖）。它长得像 e^x 那种曲线，用一条直线去拟合，怎么都不像。但如果把它取对数，指数就变成了直线。

于是不拟合 y，改拟合 ln y：

这叫对数线性回归（log-linear regression）。它想让 e^wTx+b 去逼近 y——注意，是对 e^(…) 逼近 y，而不是直线逼近 y。

把这个"联系"抽象出来：取一个单调可微的函数 g(·)，令

这就叫广义线性模型（generalized linear model），g(·) 叫联系函数（link function）。

• 为什么 g 要单调？因为要能反解回去（单调才有一一对应，才有反函数 g^-1），而且要保持"顺序不乱"。
• 为什么要可微？因为要能求导、能用优化算法（下一节全靠这个）。
• 对照一下：对数线性回归就是 g(·) = ln(·) 的特例。因为 ln y = w^Tx+b 两边取 exp 就是 y = e^wTx+b，即 y = g^-1(w^Tx+b)。

3.3 对数几率回归名字叫回归，干的是分类

上一节解决的是"输出一个实数"。可如果任务是分类呢？比如判断"是不是好瓜"，答案是 0 或 1。

原书在这里只用了一句话转折："答案蕴涵在式 (3.15) 的广义线性模型中：只需找一个单调可微函数将分类任务的真实标记 y 与线性回归模型的预测值联系起来。"

把这句话拆开：线性模型算出来的 z = w^Tx + b 是个实数（可能是 −7.3，可能是 0.02，也可能是 1.4），而我们要的 y 只能是 0 或 1。所以缺的不是模型，缺的是一个"翻译器"——也就是式 (3.15) 里那个 g^-1。

先想想"最理想的翻译器"长什么样

最符合直觉的翻译显然是：z 是正的，就判 1；z 是负的，就判 0。这就是单位阶跃函数（unit-step function，也叫 Heaviside 函数）：

书里的说法：预测值 z 大于零就判为正例，小于零判为反例，恰好等于临界值（0）时可以任意判别。看着很完美，对吧？

但它有个致命问题：不连续。在 z = 0 这一点上，函数值"啪"地一下从 0 跳到 1，中间没有过渡。而广义线性模型要求 g 单调可微——不可导，就没法求梯度，没法用优化算法去训练它。

所以原书说：希望找一个"替代函数"（surrogate function）——能在一定程度上近似阶跃函数，同时单调可微。

对数几率函数：一个"圆滑版"的阶跃

这个替代品就是对数几率函数（logistic function）：

它就是深度学习里那个 sigmoid。书里对 sigmoid 的解释是"形似 S 的函数"，对数几率函数是其中最重要的代表（第 5 章讲神经网络时会再遇到它）。

它有三个性质，正好对上需求：

• z = 0 时 y = 0.5（和阶跃函数在临界点的 0.5 对上了）；
• z → +∞ 时 y → 1；z → −∞ 时 y → 0（两头饱和）；
• 在 z = 0 附近变化最陡——"最陡"意味着最敏感，不确定性最大的地方它给出最干脆的判断。

把它当作 g^-1 代进式 (3.15)：

"对数几率回归"这个名字是怎么来的

把式 (3.18) 变形一下（两边取倒数、移项、再取对数）。这一步书里是"类似于式 (3.14)，式 (3.18) 可变化为"，我们来真的变一次：

而 z 就是 w^Tx + b，所以：

接着把三个术语串起来（这三个名字务必分清）：

为什么它好用：书里给了三条

1. 直接对分类可能性建模，无需事先假设数据分布。对比一下：朴素贝叶斯（第 7 章）要先假设"数据服从某种分布"，如果假设错了，模型就跟着错。对率回归不假设分布，所以"避免了假设分布不准确所带来的问题"。
2. 得到的是近似概率预测，不是硬邦邦的类别。它输出 0.87，你就知道"这个样本有 87% 的可能是好瓜"。这对很多需要概率辅助决策的任务很有用——比如医疗诊断里，0.51 和 0.99 虽然都判"有病"，但处置方式完全不同。
3. 目标函数是任意阶可导的凸函数。数学性质好，现有的数值优化算法都能直接用。

怎么把 w 和 b 求出来：极大似然法

先把式 (3.18) 里的 y 明确成"类后验概率估计"，也就是 p(y=1 | x)——"在已知 x 的条件下，它是正例的概率"。于是式 (3.19) 可以重写为：

由于两者加起来必须等于 1，解一下就能分别写出它们：

注意这两个式子和 (3.18) 长得几乎一样，只是分母的指数上少了个负号——因为 (3.18) 那个式子是给"y=1"用的，(3.24) 是 1 减掉它。

书里一句话点明："即令每个样本属于其真实标记的概率越大越好。" 这就是式 (3.25) 的全部含义。

一个式子同时写两种情况的技巧

麻烦在于：y_i 有时候是 1，有时候是 0，难道要分两种情况写？书里用一个很巧的办法绕过去了。先做记号简化：

又是"把 b 吸收进去"那一招（和 3.2 一模一样）。再令 p₁(x̂; β) 表示判为正例的概率，p₀ = 1 − p₁ 表示反例的概率。于是：

化简成最终形状（书里跳了，这里补上）

把式 (3.26) 代入式 (3.25)，用式 (3.23)(3.24) 展开。分两种情况看 ln p 长什么样：

看这两行——它们的区别只在于前面那一项在 y_i=1 时是 β^Tx̂_i，在 y_i=0 时是 0。那正好就是 y_i · β^Tx̂_i。所以两种情况可以合并成一行：

最大化这个和，等于最小化它的相反数（加个负号、翻个个儿）。于是得到：

怎么解：没有闭式解，只能迭代

注意一个本质区别：3.2 的线性回归有闭式解（代公式一步算出），而式 (3.27) 因为那个 ln(1+e^(·)) 的存在，没法直接解出 β。只能一步步逼近。

好消息是它是"关于 β 的高阶可导连续凸函数"，所以梯度下降法、牛顿法这些经典数值优化算法都能用。原书以牛顿法为例：

这个公式别硬背，看它的结构：新位置 = 老位置 − （曲率）^-1 × （斜率）。

书里给了一阶导和二阶导：

一阶导那个式子有个特别漂亮的读法："误差 × 特征"。括号里 y_i − p₁ 就是"真实标签减去预测概率"，也就是这一条样本的误差；乘以 x̂_i 就是"这条样本的特征"。所有样本的"误差×特征"加起来，就是梯度。误差大的样本对参数的拉动更大——这和直觉完全一致。

二阶导那个式子也值得看一眼：因为 p₁(1−p₁) 永远 ≥ 0（概率在 0 和 1 之间），所以这个 Hessian 是正定的。正定意味着什么？意味着这个碗是"开口朝上"的——确实是个凸问题，牛顿法不会跑偏。

3.4 线性判别分析换一条完全不同的路

3.3 的思路是"算概率"。3.4 的思路完全不同：不去算概率，而是去找一个"最好的观察角度"。

线性判别分析（Linear Discriminant Analysis，LDA）在二分类问题上最早由 Fisher 在 1936 年提出，所以也叫"Fisher 判别分析"。

原书说它的思想"非常朴素"，确实朴素，但要想透需要一点空间想象力：

把"投影"写成数学

先摆记号。数据 D = {(x_i, y_i)}，y_i ∈ {0, 1}。对第 i 类（i 取 0 或 1），记：

现在把点投影到方向 w 上。投影的数学操作就是点积（内积）。所以：

• 类 0 的中心投影后，变成一个数：w^Tμ₀；
• 类 1 的中心投影后，变成 w^Tμ₁；
• 类 0 的"散开程度"投影后，变成 w^TΣ₀w；
• 类 1 的"散开程度"投影后，变成 w^TΣ₁w。

书上有一句容易被匆匆扫过的话："由于直线是一维空间，因此 w^Tμ₀、w^Tμ₁、w^TΣ₀w 和 w^TΣ₁w 均为实数。"

这句话看着像废话，其实是提醒你别在后面的式子推导中把标量当向量处理。二维向量点积一个方向向量，结果是一个数（在直线上的坐标）；矩阵夹在两个 w 中间变成二次型，结果也是一个数（散开的程度）。

把两个愿望写成一个分数

LDA 有两个"愿望"，恰好是一对矛盾：

一个要小一个要大，怎么同时优化？让它们相除：分子要大、分母要小，整体就大。于是得到目标函数：

两个"散度矩阵"

为了写得清爽，书里定义了两个矩阵。它们是这一节的主角，一定要认识：

用人话说这两个东西：

• S_w（类内）：把每一类的样本都减去自己类的中心，然后"自己乘自己的转置"再加起来。它在量的是"每一类自己有多散"。
  顺便说一句：如果你把 ∑(x−μ)(x−μ)^T 除以样本数 m，得到的就是协方差矩阵。所以散度矩阵和协方差矩阵只差一个常数倍。
• S_b（类间）：只用两个类的中心，量的是"两个类的中心离多远"。注意它是一个"秩为 1"的矩阵——因为它只是同一个方向向量的外积。

于是式 (3.32) 可以重写成非常漂亮的样子：

这个形式的学名叫广义瑞利商（generalized Rayleigh quotient）。名字很唬人，但你只要记住它是"类间 ÷ 类内"就行，越大越好。

怎么解这个最大化问题

先注意一个性质，书里用了一个脚注来提："若 w 是一个解，则对于任意常数 α，αw 也是式 (3.35) 的解。"

书里的做法是："不失一般性，令 w^TS_ww = 1"。这样分母就固定成 1 了，最大化 J 就等价于最大化分子，而最大化分子又等价于最小化负的分子：

这是一个"带约束的优化"，标准解法是拉格朗日乘子法（附录 B.1）。做法是：把约束乘上一个系数 λ 加进目标里，变成无约束问题，再求导置零。

这个式子的形式叫"广义特征值问题"。如果 S_w 是单位矩阵，它就退化成普通的求特征值 S_bw = λw。

最后一步：从 λ 到 S_w^-1(μ₀−μ₁)

这一步是全书最像"变魔术"的地方，但其实只用了两个观察。

观察一：S_bw 的方向是固定的。把 S_b = (μ₀−μ₁)(μ₀−μ₁)^T 代进去：

下面画线的那一坨 (μ₀−μ₁)^Tw 是一个数（两个向量点乘）。一个数乘上一个向量，结果还是那个方向的向量。所以 S_bw 的方向永远等于 (μ₀−μ₁) 的方向，不管 w 取什么。书里那句"注意到 S_bw 的方向恒为 μ₀−μ₁"，就是这个意思。

观察二：既然方向一样，就可以把那个标量整体记作 λ。于是令：

把这个代回式 (3.37)：

推广到多分类

二分类时是把数据投到一条线上。多分类时，一条线不够了——N 个类挤在一条线上会重叠。所以要投到一个低维空间里去。思路完全一样，只是"数"变成了"矩阵"。

先定义全局散度矩阵（所有样本相对于总均值的散度）：

其中 μ 是所有样本的均值向量（不分类别）。这个等式 S_t = S_b + S_w 很有意思：总散度 = 类间散度 + 类内散度。就像"总方差 = 组间方差 + 组内方差"，是很自然的一个分解。

然后把类内散度矩阵重新定义成"每一类的散度加起来"：

再借 S_t = S_b + S_w 反推出类间散度矩阵：

（m_i 是第 i 类的样本数。为什么这里要乘 m_i？因为类间散度要把每类的"中心偏移"按该类的样本数量加权——大类的影响应该更大。这个 m_i 是推出来的，书里跳了中间步骤。）

书里说："显然，多分类 LDA 可以有多种实现方法：使用 S_b、S_w、S_t 三者中的任何两个即可。"理由是它们满足 S_t = S_b + S_w，知道两个就能算出第三个。

常见的一种实现是：

符号：W ∈ ℝ^d×(N−1) 是投影矩阵（把 d 维投到 N−1 维），tr(·) 是迹——矩阵对角线元素之和。为什么用迹？因为二分类时分子分母都是标量，直接除就行；多分类时它们是矩阵，得想办法变成一个数来比较。迹正好是"所有特征值之和"，可以理解为"总能量"，是标量除法的自然推广。

解法还是广义特征值问题：

而 W 的闭式解是：S_w⁻¹S_b 的 N−1 个最大广义特征值所对应的特征向量组成的矩阵。

最后，原书点出了 LDA 的第二个身份："若将 W 视为一个投影矩阵，则多分类 LDA 将样本投影到 N−1 维空间，N−1 通常远小于数据原有的属性数。于是，可通过这个投影来减小样本点的维数，且投影过程中使用了类别信息，因此 LDA 也常被视为一种经典的监督降维技术。"

3.5 多分类学习只会二分类怎么办

前面两节（3.3、3.4）解决的都是二分类：只有"是/不是"两种答案。但现实中经常是 N 类：这个瓜是西瓜、南瓜、冬瓜还是黄瓜？

书里说得很实在："有些二分类学习方法可直接推广到多分类，但在更多情形下，我们是基于一些基本策略，利用二分类学习器来解决多分类问题。"

这一节讲的就是这些"基本策略"。核心思路只有两个字：拆解。

策略一：OvO（一对一）

One vs. One，读作"一对其一"。数据集是 D = {(x₁,y₁), …}，y_i ∈ {C₁, C₂, …, C_N}。

怎么拆：把 N 个类别两两配对。每配一对，就造一个二分类任务——"是 C_i 还是 C_j？"，其中 C_i 的样例当正例，C_j 的样例当反例。

一共多少个？从 N 个里挑 2 个的组合数：

比如 4 个类，就是 4×3/2 = 6 个分类器：{C₁C₂}、{C₁C₃}、{C₁C₄}、{C₂C₃}、{C₂C₄}、{C₃C₄}。

怎么合：测试时，新样本同时喂给所有分类器，得到 N(N−1)/2 个预测。然后投票——被预测得最多的类别就是最终结果。

策略二：OvR（一对其余）

One vs. Rest，读作"一对其余"（书里也提了另一个名字 OvA = One vs. All，但原书说 OvA 这个说法不严格，因为不可能把"所有类"都当反类）。

怎么拆：每次把一个类的样例当正例，其余所有类的样例当反例。这样每个类造一个任务，共 N 个分类器。

怎么合：书里分了两种情况：

• 只有一个分类器预测为正 → 那个类就是答案。
• 有多个分类器都预测为正 → "通常考虑各分类器的预测置信度，选择置信度最大的类别标记作为分类结果"。

OvO 和 OvR 到底怎么选

书里这一段信息密度很高，几乎每一句都是考点，我们拆成表格看：

这个表格里有个反直觉的地方，值得停下来想一下：分类器多的 OvO，训练时间居然可能更小？

原因就在"每个分类器用多少样本"这一行。OvO 的每个分类器只看两类样本（比如 m=10000 个样本、10 个类，每个分类器可能只看 2000 个），而 OvR 的每个分类器要看全部 10000 个。虽然 OvO 要训 45 个模型，但每个都小得多。类别越多、每类样本越少，这个差距越明显。

策略三：MvM（多对多）

Many vs. Many：每次把若干个类当正类、另外若干个类当反类。

显然 OvO 和 OvR 都是 MvM 的特例（OvO 是"1 个对 1 个"，OvR 是"1 个对其余"）。

但书里紧接着说了一句关键的限定："MvM 的正、反类构造必须有特殊的设计，不能随意选取。"为什么不能随便？

ECOC：把"纠错码"的思想搬过来

纠错输出码（Error Correcting Output Codes，ECOC）是最常用的 MvM 技术，由 Dietterich 和 Bakiri 在 1995 年提出。

书里一句话点明了它的野心："将编码的思想引入类别拆分，并尽可能在解码过程中具有容错性。"

它的工作过程分两步，这两步一定要分清：

第一步：编码（训练阶段）

对 N 个类别做 M 次划分。每次划分把一部分类划为正类、一部分划为反类，形成一个二分类训练集。M 次划分 → M 个训练集 → 训练出 M 个分类器。

这些划分用一个编码矩阵记录下来：每一行是一个类别，每一列是一个分类器。格子里的值表示"这个分类器把这个类当正例还是反例"。

读法："+1" 表示该分类器把这个类的样本当正例，"−1" 表示当反例。

按这张表，f₂ 那一列是 (+1, −1, +1, −1)，意思是：分类器 f₂ 把 C₁ 和 C₃ 的样例作为正例，C₂ 和 C₄ 的样例作为反例——这正是原书图 3.5(a) 里的描述。每一行则是一个类别的"身份证"：C₃ 的编码是 (−1, +1, +1, −1, +1)。

编码矩阵有两种常见形式：

书里举了三元码的例子："在图 3.5(b) 中，分类器 f₄ 将 C₁ 类和 C₄ 类的样例作为正例，C₃ 类的样例作为反例"——剩下的 C₂ 就是被"停用"了（矩阵里对应位置是 0）。

第二步：解码（测试阶段）

M 个分类器各自对测试样本给出一个预测（是/否），把这些预测按顺序排成一个长度 M 的编码。然后拿这个"预测编码"和每个类别自己的编码逐一比较距离，距离最小的那个类别就是答案。

距离怎么算？常用欧氏距离或海明距离（数不同位置的个数）。书里的例子说"若基于欧氏距离，预测结果将是 C₃"。

为什么叫"纠错"？一个具体例子

这是本节最精彩的部分，一定要跟着算一遍。

假设测试样本真实的类别是 C₃，那它的正确编码应该是 (−1, +1, +1, −1, +1)（看表里 C₃ 那一行）。

现在假设分类器 f₂ 判错了——它本该输出 +1，却输出了 −1。于是我们拿到的编码变成：

距离为 1（只有 f₂ 那一位不同），是所有类别里最小的——所以最终仍然判为 C₃，正确答案。

码长 M 的取舍

书里给了两条权衡，方向相反：

• M 越大，纠错能力越强。因为编码之间的差异位更多，能容忍更多分类器同时出错。
• 但 M 越大，代价也越大。"编码越长，意味着所需训练的分类器越多，计算、存储开销都会增大。"

还有一条更微妙的限制："对有限类别数，可能的组合数目是有限的，码长超过一定范围后就失去了意义。"

两个容易忽略的深层提醒

3.6 类别不平衡问题给 3.5 打的补丁

这一节的位置很讲究。它放在多分类学习之后，因为多分类的拆解过程会自己制造不平衡问题。但更根本的原因是：前面所有方法都建立在一个从未明说的假设上。

先看清问题有多严重

书里用了一个极端的例子，非常值得慢慢读：

998 个反例，2 个正例。现在有一个"聪明"的学习器，它的策略是——永远预测"反例"。

它的精度是多少？

99.8% 的精度！听起来是个近乎完美的模型。

但它一个正例都找不出来。书里的评价是："然而这样的学习器往往没有价值，因为它不能预测出任何正例。"

从"决策门槛"看这个问题（本节最漂亮的一段）

书里说"从线性分类器的角度讨论容易理解"。我们就顺着这个角度走一遍。

用 y = w^Tx + b 对新样本分类时，本质上是在拿预测出的 y 和一个阈值比较：通常 y > 0.5 判正例，否则判反例。

为什么是 0.5？因为 y 表达的是"正例的可能性"，那么 y/(1−y) 就是"正例可能性与反例可能性的比值"。阈值设成 0.5，等价于要求这个比值大于 1：

而 "> 1" 的含义是：分类器认为真实正、反例的可能性相同——这是一个 1:1 的赌注。

但训练集里的比例不是 1:1 啊！令 m⁺ 是正例数，m⁻ 是反例数，那么观测几率是 m⁺/m⁻。

书里用了一个假设（注意，这个假设后来被证明很关键）："由于我们通常假设训练集是真实样本总体的无偏采样，因此观测几率就代表了真实几率。"

于是正确的决策规则应该改成：只要预测几率高于观测几率，就判为正例：

再缩放：把门槛"挪"到正确的地方

问题是：我们的分类器是按式 (3.46)（门槛 1）训练出来的。要让它执行式 (3.47)（门槛 m⁺/m⁻），怎么办？

书里的做法极简洁："只需令"：

这叫再缩放（rescaling），是类别不平衡学习的一个基本策略。

把这个系数的意义说白：m⁻/m⁺ 是一个"补偿倍数"。正例越少（m⁺ 越小），这个倍数越大，模型就越倾向于判正例——正好抵消了训练集里正例稀缺带来的偏见。

三类实际做法

因为"改公式"这条路受假设限制，所以实践中主要靠"改数据"或"改决策"。书里归成三类：

两个代表算法，值得记住名字

书里各给了一个，思路都很聪明：

顺便：这跟"代价敏感学习"是什么关系

书里最后一段把两个概念连了起来："'再缩放'也是'代价敏感学习'（cost-sensitive learning）的基础。在代价敏感学习中将式 (3.48) 中的 m⁻/m⁺ 用 cost⁺/cost⁻ 代替即可。"

不过书里也强调了一个区分（这里对应 Zhou & Liu, 2006b）："非均等代价和类别不平衡性虽然都可借助'再缩放'技术，但两者本质不同。"

不同在哪？类别不平衡是"数据里样本多寡"的问题；非均等代价是"犯错后果轻重"的问题。前者是客观的分布，后者是人为的定价。两者恰好都能用同一个公式处理，但不该混为一谈。书里还补了一句：类别不平衡学习中通常是"较小类的代价更高，否则无需进行特殊处理"。

3.7 阅读材料每一条都是一个岔路口

这一节篇幅很短，但每段都在指向后面的章节或一个研究方向。我们按原书顺序逐段过，不跳过。

① 稀疏表示与 LASSO

"稀疏表示"近年来很受关注，但即便对多元线性回归这样简单的模型，获得具有最优"稀疏性"的解也并不容易。稀疏性问题本质上对应了 L₀ 范数的优化，这在通常条件下是 NP 难问题。LASSO 通过 L₁ 范数来近似 L₀ 范数，是求取稀疏解的重要技术。

什么是"稀疏"？就是让学到的 w 里大部分分量恰好等于 0。好处有两个：模型只依赖少数几个特征（简单、不容易过拟合），而且你能直接看出"到底哪几个特征有用"（可解释）。

为什么难？"最优稀疏"要数一数 w 里非零元素的个数，这就是 L₀ 范数。而"数个数"这个操作是跳变的（从 0 个变 1 个），没法求导，也没法用梯度方法优化——事实上它是 NP 难的（组合爆炸）。

LASSO 的巧劲：用 L₁ 范数（各分量绝对值之和）来近似 L₀。L₁ 是凸的、可优化的，而且它天然会把一些系数"压到恰好 0"——这个性质很神奇，第 11 章会讲清楚原理。Tibshirani 1996 那篇论文就是它的出处。

② ECOC 的理论进展

这一段有四层信息：

1. OvO 和 OvR 都是 ECOC 的特例（Allwein et al., 2000）。这个结论挺漂亮——说明 3.5 讲的三种策略其实是同一框架下的不同选择。
2. 人们以往希望设计"通用"的编码法。但 Crammer & Singer (2002) 提出要考虑问题本身的特点，设计"问题依赖"的编码法，并证明寻找最优的离散编码矩阵是一个 NP 完全问题。
3. 此后出现了多种问题依赖的 ECOC 编码法，通常思路是"找出具有代表性的二分类问题来进行编码"（Pujol et al., 2006, 2008）。也就是说，不是随便拆，而是优先拆那些"最容易分"的二分类问题。
4. Escalera et al. (2010) 开发了一个开源 ECOC 库，可以直接用。

③ MvM 的其他实现

"MvM 除了 ECOC 还可有其他实现方式，例如 DAG 拆分法（Platt et al., 2000）将类别划分表达成树形结构，每个结点对应于一个二类分类器。"

DAG 是"有向无环图"。用大白话说：不是让所有分类器同时投票，而是像走迷宫一样一层层排除——第一层的分类器先把候选缩小，第二层再缩小，直到只剩一个。好处是测试时不用跑所有分类器。

另外还有一批工作"致力于直接求解多分类问题"，比如多类支持向量机（Crammer & Singer, 2001；Lee et al., 2004）——不去拆，直接改算法本身。

④ 代价敏感学习的边界

这一段信息量很大，逐句看：

• "代价敏感学习中研究得最多的是基于类别的'误分类代价'，代价矩阵如表 2.2 所示；本书在提及代价敏感学习时，默认指此类情形。"
• "已经证明，对二分类任务可通过'再缩放'获得理论最优解（Elkan, 2001）"——所以 3.6 那个公式在二分类下不只是"启发式"，是有理论保证的。
• "但对多分类任务，仅在某些特殊情形下存在闭式解（Zhou & Liu, 2006a）"——多分类的代价敏感问题要难得多。
• "非均等代价和类别不平衡性虽然都可借助'再缩放'技术，但两者本质不同（Zhou & Liu, 2006b）。"
• "需注意的是，类别不平衡学习中通常是较小类的代价更高，否则无需进行特殊处理。"

⑤ 多标记学习：一个容易混淆的邻居

最后一段澄清了一个概念区别，非常值得记：

附：书里那个小故事——最小二乘法是谁发明的

这一段看着像闲笔，其实讲的是"一个方法为什么会被记住"。

1801 年，意大利天文学家皮亚齐发现了 1 号小行星"谷神星"。但跟踪观测 40 天后，谷神星转到太阳背后，他失去了它的位置。许多天文学家试图重新找到它，都徒劳无获。

这事引起了高斯（1777—1855）的注意。他发明了一种方法，根据皮亚齐的观测数据计算出了谷神星的轨道。后来德国天文学家奥伯斯在高斯预言的时间和星空领域，重新找到了谷神星。

1809 年，高斯在《天体运动论》中发表了这种方法——即最小二乘法。

1805 年，法国数学家勒让德（1752—1833）发表了《计算彗星轨道的新方法》，其附录中描述了最小二乘法。但勒让德的书里没有涉及最小二乘法的误差分析。

而高斯 1809 年的著作包括了这方面的内容——书里的评价是："这对最小二乘法用于数理统计、乃至今天的机器学习有极为重要的意义。"

由于这一重大贡献，加上高斯声称自己 1799 年就已开始使用这个方法，很多人将发明优先权归之于高斯。两位大数学家发生了著名的优先权之争，此后有许多数学史家专门研究，但至今也没弄清到底是谁最先发明了最小二乘法。

章末自查合上书，看能不能讲出来

读完不等于学会。下面这 12 条是这一章的"骨架"，建议你合上文档，逐条口头讲一遍。讲不出来的，就是还没真正拿下的地方——回去看对应小节。