5.1 线性预测、间隔与感知机

二元线性分类的原创补充笔记。

1. 输出是标签，而不是拟合的数值

回归与分类可以使用同一批特征向量，却解不同的数学问题。回归分数的好坏取决于其数值多接近响应；二元分类器则用分数在两个标签中作选择。把负一和正一这些数值拟合得好，未必把决策边界放在合适位置。

所需基础是实向量与内积、Cauchy–Schwarz、仿射函数、有限和，以及有限维 Euclidean 空间中有界序列的子序列紧性。既有最小二乘笔记提供第一题重用的设计矩阵和正规方程结果。Fisher 判别已从有标签散布选取分数，其目标不同于下文的分隔不等式。度量学习使用平方距离间隔，也必须与到超平面的距离区分。

固定有限且非空的训练列表

$$(x_i,y_i),\qquad i=1,\ldots,m,\qquad x_i\in\mathbb R^d,\quad y_i\in\{-1,+1\}, \quad m\geq1,\quad d\geq1.$$

容许重复输入，且它们的标签可能不一致。本节所有结论都针对这个固定有限列表，不假定抽样分布，也不声称未来预测误差的保证。

分数与预测约定。 参数对 $(w,b)\in\mathbb R^d\times\mathbb R$ 定义仿射分数及分类器

$$f_{w,b}(x)=w^\top x+b,\qquad h_{w,b}(x)= \begin{cases} +1,&f_{w,b}(x)\geq0,\\ -1,&f_{w,b}(x)<0. \end{cases}$$

所以零分数预测正类。分数对参数是线性的，但当截距 b 非零时，对 x 是仿射的。经验分类错误率为

$$\operatorname{err}(w,b) =\frac1m\sum_{i=1}^m 1_{\{h_{w,b}(x_i)\ne y_i\}}.$$

它不是最小二乘目标 $\sum\limits_i(y_i-f_{w,b}(x_i))^2$。后者惩罚数值偏差的大小，前者则数出阈值化后的错误标签。第一题给出两者结论不同的精确数据。

带符号分数 $y_i f_{w,b}(x_i)$ 很方便：正值表示样本离开边界且分类正确。但零值本身不能判定正确与否。按我们的规则，正标签的零分数正确，负标签的零分数则错误。因此，对所有 i 有 $y_i f_{w,b}(x_i)\geq0$，并不等价于此平局约定下的零分类错误。

若存在某 $(w,b)$，使每个 i 都有 $y_i f_{w,b}(x_i)>0$，称列表为严格仿射可分。严格分隔比仅接受正类平局更强；这正是间隔及停止定理使用的假设。

2. 距离、函数间隔与几何间隔

先设 $w\ne0$。方程 $w^\top x+b=0$ 定义真正的超平面 H。它非空，因 $-bw/\|w\|^2$ 位于其中。w 不仅给出法向方向，亦指定定向：正分数位于 w 指向的一侧。

距离命题。 对每个 $x\in\mathbb R^d$，其在 H 上的唯一最近点和到 H 的距离为

$$p(x)=x-\frac{f_{w,b}(x)}{\|w\|^2}w,\qquad \operatorname{dist}(x,H)=\frac{|f_{w,b}(x)|}{\|w\|}.$$

代入可得 $w^\top p(x)+b=0$。对任意 $q\in H$， $w^\top(x-q)=f_{w,b}(x)$，所以 Cauchy–Schwarz 给 $\|x-q\|\geq |f_{w,b}(x)|/\|w\|$。上述 p 达到此界。要明确证唯一性，分解 $x-q=(x-p)+(p-q)$。第一个向量平行 w，第二个垂直 w，故 $\|x-q\|^2=\|x-p\|^2+\|p-q\|^2$。要等于最小距离，必须 $q=p$。

特别地，原点到 H 的距离是 $|b|/\|w\|$，一般不是 b。原点的最近点为 $-bw/\|w\|^2$，其沿定向单位法向量的坐标是 $-b/\|w\|$。

距离计算例。 取 $w=(3,4)^\top$、$b=-10$、$x=(2,2)^\top$。则 $\|w\|=5$、$f(x)=4$，且

$$p=\left(\frac{38}{25},\frac{34}{25}\right)^\top, \qquad 3p_1+4p_2=10,\qquad \|x-p\|=\frac45.$$

若此点的标签为正一，而原点标签为负一，两者带标签符号的距离分别为 $4/5$ 和二，最小值遂为 $4/5$。

对固定列表，定义函数间隔 $a(w,b)=\min\limits_i y_i f_{w,b}(x_i)$。当 $w\ne0$，定义带符号几何间隔

$$\delta(w,b)=\frac{a(w,b)}{\|w\|} =\min_i\frac{y_i(w^\top x_i+b)}{\|w\|}.$$

若 $a>0$，几何间隔是训练点到超平面的最小距离，而且全部位于指定侧。若 $a\leq0$，它是带符号量，不是正的稳健半径。

对 $\lambda>0$，以 $(\lambda w,\lambda b)$ 代 $(w,b)$，会保持每个预测和超平面，把 a 乘 $\lambda$，并保持 $\delta$。因此，严格正的函数间隔可以通过参数伸缩变得任意大，而决策边界完全不动。w 和 b 必须一起伸缩。例如 $2x+2=0$ 与 $x+1=0$ 的边界相同，但只改 w 就会变成 $x+2=0$。负伸缩会反转边界外的分数符号；边界上仍沿用正类平局约定。

有限数据稳健性。 若 $\delta(w,b)>0$ 且 $\|r_i\|<\delta(w,b)$，扰动后的训练点 $x_i+r_i$ 仍严格分类正确。事实上，

$$y_i f_{w,b}(x_i+r_i) =y_i f_{w,b}(x_i)+y_i w^\top r_i \geq\|w\|\big(\delta(w,b)-\|r_i\|\big)>0.$$

半径条件是严格的。对达到有限最小值的点，取 $r_i=-y_i\delta(w,b)w/\|w\|$ 便把它移到超平面。该处失去严格分隔，由平局规则决定预测；沿同方向稍加位移便会越过边界。这是已观测列表上的确定性扰动结论，不是概率界或泛化定理。

当 $w=0$，分数为常数。其零点集不是整个 $\mathbb R^d$ 就是空集，并非非退化超平面；不能除以 $\|w\|$。含两种标签的列表不可能由常数分数严格分隔，但单一类别的列表可以，所以两种情形必须分开。

3. 增广感知机：先固定更新，再作证明

把截距放在最后一个坐标：

$$z_i=(x_i,1)\in\mathbb R^{d+1},\qquad \theta=(w,b),\qquad \theta^\top z_i=f_{w,b}(x_i),\qquad R=\max_i\|z_i\|=\max_i\sqrt{\|x_i\|^2+1}.$$

有限数 R 至少为一。若只用未增广 x 的最大范数，便漏去截距坐标。

假设存在单位向量 $v\in\mathbb R^{d+1}$ 及数 $\gamma>0$，使

$$\|v\|=1,\qquad y_i v^\top z_i\geq\gamma \quad\text{对每个 }i.$$

每个有限严格可分列表都有此类一对参数：任取非零严格分隔参数 $\theta_*$，令 $v=\theta_*/\|\theta_*\|$，并取 $\gamma=\min\limits_i y_i\theta_*^\top z_i/\|\theta_*\|$。有限多个严格正值的最小值仍正。反过来，此假设本身亦提供严格分隔器。Cauchy–Schwarz 还给 $\gamma\leq R$，所以无须先知道最优间隔或先解间隔优化问题。

以下是一个确切算法。

1. 设 $\theta=0$，更新次数 $t=0$。
2. 完整扫描指标 $1,\ldots,m$ 一轮，开始时把更新旗标设为假。
3. 到指标 i 时，若 $y_i\theta^\top z_i\leq0$，便以 $\theta+y_i z_i$ 代 $\theta$，把 t 加一，并把旗标设为真；否则保持不变。
4. 若整轮没有更新便停止；否则再作完整一轮。

这里刻意包含平局。若从零开始却只在严格负分数更新，第一次更新根本不会发生。我们的条件亦会更新正标签的零分数，即使预测规则把它判为正类。因此我们数的是误分类或平局更新。真正预测错误是其中一部分，两者的次数未必相等。

更新之间没有归一化。单位步长和零初始化都是所证算法的一部分。

更新次数界

令 $\theta_t$ 指恰好 t 次更新后的参数，不论已访问多少数据点。若下一次更新的指标是 i，则

$$\theta_{t+1}^\top v =\theta_t^\top v+y_i z_i^\top v \geq\theta_t^\top v+\gamma.$$

由 $\theta_0=0$ 归纳，对每个真正发生的更新次数 T，都有 $\theta_T^\top v\geq T\gamma$。同一次更新又有

$$\begin{aligned} \|\theta_{t+1}\|^2 &=\|\theta_t\|^2+2y_i\theta_t^\top z_i+y_i^2\|z_i\|^2\\ &\leq\|\theta_t\|^2+R^2, \end{aligned}$$

因更新条件使中间项非正，而 $y_i^2=1$。再次归纳得 $\|\theta_T\|^2\leq TR^2$。

若 $T=0$，下述界立即成立。若 $T>0$，对单位 v 用 Cauchy–Schwarz：

$$T\gamma\leq\theta_T^\top v\leq\|\theta_T\| \leq R\sqrt T, \qquad T\leq\left(\frac R\gamma\right)^2.$$

这界控制总更新次数，所以亦控制此算法所遇的真正预测错误次数。证明包含初始零向量，从没有除以它的范数，也不要求 v 是最大间隔向量。

为何这个扫描真的停止

此界对每段真正发生的有限更新前缀都成立。若有无限更新，便可取长度大于 $(R/\gamma)^2$ 的整数长度前缀，矛盾。完整轮巡算法不可能永远运行：每个非末轮都有更新，无限多非末轮便给无限多更新。

若总更新数为 T，非末轮至多 T 轮，再加一个末轮，所以访问数据点的次数至多 $m(T+1)$。末轮参数从未改变，每个访问指标都满足 $y_i\theta^\top z_i>0$。所有 m 个指标已检查，故最后参数严格分隔整个训练列表。

非空列表迫使至少一次更新，因初始全部带符号分数皆零。因此最后参数非零，亦可从 $\theta_T^\top v\geq T\gamma>0$ 看出。可以最后才除以其正范数而不改预测；若每次更新后都这样做，会改变递推，须另作证明。

另一算法可以每步完整搜索有限列表，任选一个违反条件的指标，并仅在找不到时停止；同一更新界适用。但不公平地一直略过违反条件点的扫描，没有这种证书。固定迭代上限亦不是证书，除非检查全部最终不等式。次数界不会把任意扫描或停止规则自动变成本算法。

一个有用的常数预测情形

只有一个正标签样本 $x_1=0$ 时，$z_1=(0,1)$、$R=1$，而 $v=(0,1)$ 有 $\gamma=1$。第一次更新给 $\theta=(0,1)$，再一轮无更新，恰达到 $T\leq1$ 的界。结果是常数分数一：增广参数非零，但特征法向量 w 为零。它是有效感知机结果，却不能套特征空间超平面距离公式。增广不会消除这个区别。

4. 标准硬间隔：存在性必须处理截距

本节额外假设两种标签均出现，而有限列表严格仿射可分。标准硬间隔问题为

$$\min_{w\in\mathbb R^d,\ b\in\mathbb R}\frac12\|w\|^2 \quad\text{满足}\quad y_i(w^\top x_i+b)\geq1,\quad i=1,\ldots,m.$$

截距 b 不受惩罚。这不是在增广空间最小化 $\|\theta\|^2/2=(\|w\|^2+b^2)/2$。

可行集非空：若 $(u,c)$ 严格分隔，且 $a=\min\limits_i y_i(u^\top x_i+c)>0$，则 $(u/a,c/a)$ 可行。反过来，可行即严格分隔。两种标签皆有时，可行参数不能有 w 零，因正标签要求 $b\geq1$，负标签却要求 $b\leq-1$。

有界可行次水平集上的取到性

选一组可行 $(w_0,b_0)$，令 $C=\|w_0\|>0$。固定一个正标签指标 p、一个负标签指标 q。每组 $\|w\|\leq C$ 的可行参数，其对应两个约束给

$$b\geq1-w^\top x_p\geq1-C\|x_p\|, \qquad b\leq-1-w^\top x_q\leq-1+C\|x_q\|.$$

故即使目标不惩罚 b，相关次水平集上的 b 仍有界。令 K 为满足 $\|w\|\leq C$ 且 b 在此固定闭区间中的可行参数。选定基准在 K。每个约束是连续仿射不等式，所以 K 闭；上述界使它在有限维 $\mathbb R^{d+1}$ 有界。

完整而言，取 K 中目标值趋于下确界的序列。有限维有界序列的子序列紧性给收敛子序列；闭性使极限在 K，$\|w\|^2/2$ 连续遂给 K 上最小值。任何 K 外可行参数必有 $\|w\|>C$，因在此范数球内的可行参数早已符合 b 的界。其目标因此大于基准值，故 K 上最小值也是所有可行参数的全局最小值。

这才证明取到。仅说约束闭，在无界集上不足够；若没有两种标签，单靠 w 的惩罚亦不会自动把 b 控制住。

法向量唯一

可行集凸，因两个可行参数的任何凸组合都满足各仿射约束。设 $(w_1,b_1)$、$(w_2,b_2)$ 都最小化，其可行中点的目标为

$$\frac12\left\|\frac{w_1+w_2}{2}\right\|^2 =\frac12\left(\frac{\|w_1\|^2}{2}+\frac{\|w_2\|^2}{2}\right) -\frac18\|w_1-w_2\|^2.$$

若 $w_1\ne w_2$，便严格小于共同最小值，矛盾，故最小化的 w 唯一。此论证没有惩罚 b，也未证对 b 严格凸，不能从中推断 b 的一般结论。第四题的特定约束将直接确定该例的 b 唯一。

为何这正是几何间隔所需的范数

任取最优 $(w_*,b_*)$，令 $a_*=\min\limits_i y_i(w_*^\top x_i+b_*)$。可行给 $a_*\geq1$。若 $a_*>1$，把两参数都除 $a_*$，仍可行且因 $w_*\ne0$ 而严格降低目标，矛盾。故 $a_*=1$，并且

$$\delta(w_*,b_*)=\frac1{\|w_*\|}.$$

对任何严格分隔 $(u,c)$，两种标签迫使 $u\ne0$。令 $a=\min\limits_i y_i(u^\top x_i+c)>0$，可行参数 $(u/a,c/a)$ 的法向量范数为 $\|u\|/a=1/\delta(u,c)$。由 $w_*$ 最优， $\|w_*\|\leq1/\delta(u,c)$，即 $\delta(u,c)\leq1/\|w_*\|$。最优参数本身达到等号，所以最大几何间隔真正存在并被取到。

反过来，若严格分隔器达到此最大几何间隔，把它伸缩至函数间隔一，目标便是 $1/(2\delta^2)$，等于最优值。因此在所列假设下，硬间隔形式与特征空间几何间隔最大化等价。伸缩的是参数，不是观测特征坐标。

5. 增广几何是另一种几何

感知机以 $\sqrt{\|w\|^2+b^2}$ 范数，估计相对于 $\mathbb R^{d+1}$ 单位向量的进展。其分隔假设在增广空间；标准硬间隔则最小化特征法向量范数 $\|w\|$，不惩罚 b。

即使约束同为 $y_i(w^\top x_i+b)\geq1$，最小化 $(\|w\|^2+b^2)/2$ 仍是不同目标。其距离在增广空间量度，而数据最后一坐标固定为一；它不自动等于只扰动原特征可得到的距离。第四题会在同一对观测上导出不同最优参数和特征空间间隔。

两种标签的条件亦有实质作用。只有一个正样本时，w 零、$b\geq1$ 使标准目标最小为零，而 b 可无界。最小化参数确实存在，但其特征超平面退化；刚证的几何间隔等价性不适用此情形。若相同输入有相反标签，两个硬约束则直接矛盾，没有可行参数。下列例子会明示分隔假设如何失效。

6. 定理究竟证明什么

感知机定理在严格可分有限数据上，保证有限次误分类或平局更新，以及指定公平扫描的停止。其证明没有最小化标准硬间隔目标，也没有说最后参数是最大间隔解。

硬间隔定理在明确的可行模型中给出被取到的最优值，并证特征法向量唯一。它没有说每个分类数据集皆可分，也没有说完美训练分隔器能准确预测新数据。没有使用软间隔、核、对偶、KKT、概率界或浮点稳定性结果。

因此，常用检查是模型本身的数学检查：

• 解释零带符号分数前，先写平局约定。
• 计算感知机半径 R 时，包含常数坐标。
• 分开数更新与访问，并验证完整无更新一轮。
• 比较同一超平面时，同时归一化 w 和 b。
• 检查目标是否惩罚截距。
• 套间隔最优定理时，核对两种标签及严格分隔假设。

7. Questions 与完整详解

Question 1: 最小二乘分数可选错边界

取一维输入 $x=(-1,0,1,100)$、标签 $y=(-1,-1,+1,+1)$。用既有正规方程定理拟合仿射最小二乘分数 $b+wx$。写出二乘二系统，按正类平局规则计算四个预测，并与分数 $x-1/2$ 比较。解释零分数对两种标签各如何预测，以及为何零特征法向量没有超平面距离公式。

详解. 设计矩阵的行是 $(1,x_i)$，系数向量为 $(b,w)^\top$。直接有限求和得

$$A^\top A= \begin{bmatrix}4&100\\100&10002\end{bmatrix}, \qquad A^\top y=\begin{bmatrix}0\\102\end{bmatrix}.$$

第一正规方程给 $b=-25w$。代入第二式，$(10002-2500)w=102$，故

$$w=\frac{51}{3751},\qquad b=-\frac{1275}{3751},\qquad (f(x_1),f(x_2),f(x_3),f(x_4)) =\frac1{3751}(-1326,-1275,-1224,3825).$$

四个分数都非平局，阈值化得 $(-1,-1,-1,+1)$，只有输入一分错，经验错误率 $1/4$。正规方程保证的是数值平方损失问题的最优值，不是标签错误数目的最优值。

同一批输入的分数 $g(x)=x-1/2$ 为 $(-3/2,-1/2,1/2,199/2)$。各带符号分数都正，故分类错误零。它在100的大数值输出可令平方损失昂贵，同时仍是正确的正类预测；两目标并不矛盾。

分数零时，分类器输出正一：正标签正确、负标签错误，但两者带符号乘积皆零，不能分辨。最后，w 零使分数为常数；其零水平集不是空集就是整条直线，不能除 $|w|$。常数预测规则可以定义，但非零法向量距离命题不适用。

Question 2: 用更新界前先追踪每次访问

使用固定顺序 $((1,0),+1),((0,1),-1),((1,1),+1)$。以 $\theta=(0,0,0)$ 初始化上述增广感知机，$z=(x_1,x_2,1)$。记录每次访问的带符号分数和结果参数，仅在完整一轮无更新后停止。给出单位分隔器、R 和 $\gamma$，比较实际更新与访问数及其界。

详解. 每次带符号分数都在该次更新之前计算。完整过程如下：

例如第二次访问用 $z_2=(0,1,1)$、负一标签，所以从 $(1,0,1)$ 减去此向量。第三次访问标签正、分数零；即使正类平局规则已正确预测，仍会更新。

共有 $T=4$ 次更新、三轮、九次访问。取

$$v=\frac1{\sqrt5}(2,-1,0),\qquad (y_1v^\top z_1,y_2v^\top z_2,y_3v^\top z_3) =\frac1{\sqrt5}(2,1,1).$$

故 $\gamma=1/\sqrt5$。首两个增广向量范数 $\sqrt2$，第三个 $\sqrt3$，所以 $R=\sqrt3$。定理给 $T\leq R^2/\gamma^2=15$，有效但不紧。以实际 T 得访问界 $m(T+1)=3(5)=15$，实际只有九次。

末轮很重要：三个正带符号分数，对同一固定参数验证整个列表。若更早只看到某一点正分数就停止，没有此证书。最后参数严格分隔，但此计算没有证明最大间隔最优性。

Question 3: 不同输入的不可分与不一致标签循环

先把 $(1,1),(-1,-1)$ 标为正类，$(1,-1),(-1,1)$ 标为负类，证没有仿射分数严格分隔此 XOR 数据。再把同一一维输入零列两次，依次标正一、负一。明确展示零初始化感知机在重复扫描下的循环，并指出失效的定理假设。

详解. 记仿射参数为 $(w_1,w_2,b)$。正类约束须有 $w_1+w_2+b>0$ 及 $-w_1-w_2+b>0$，相加得 $2b>0$。负类约束须有 $w_1-w_2+b<0$ 及 $-w_1+w_2+b<0$，相加得 $2b<0$，不可能。输入互异并不保证仿射严格可分。

重复零输入的两个增广向量都是 $(0,1)$，标签相反。从 $(w,b)=(0,0)$ 开始，第一个正类带符号分数零，更新得 $(0,1)$。负例随后带符号分数负一，减去 $(0,1)$ 又得 $(0,0)$。每个完整轮次都重复

$$(0,0)\longrightarrow(0,1)\longrightarrow(0,0).$$

每轮都有更新，故指定停止测试永不成功。不可能存在单位 v 和正 $\gamma$，同时满足 $v^\top(0,1)\geq\gamma$、$-v^\top(0,1)\geq\gamma$，因相加会得 $0\geq2\gamma$。所以更新定理不适用，反复出现的零参数亦不能归一化。

第二列表不只是仿射几何失效：任何确定性标签规则在同一输入都不能同时输出两个不同标签。引用分隔假设不成立的定理，不能解决两例。本节没有声称任何非线性或核构造。

Question 4: 偏置惩罚会改变分隔线

一维中，正例在一、负例在负五。推导不惩罚 b 的标准硬间隔最优解和特征空间几何间隔，再在同一约束下最小化 $(w^2+b^2)/2$，比较边界和间隔。最后删去负例，解释退化情形，不可错称不存在最小值。

详解. 两个约束是

$$w+b\geq1,\qquad 5w-b\geq1.$$

相加给 $6w\geq2$，所以 $w\geq1/3$。标准目标 $w^2/2$ 因此在 $w=1/3$ 最小，只需验可行。该处两约束分别要求 $b\geq2/3$ 和 $b\leq2/3$，故 $b=2/3$。两式均等号，证明可行，亦证本特例的 b 唯一。边界是 $x=-b/w=-2$，两点到它皆距离三；等价地，函数间隔一而 $\delta=1/|w|=3$。标准目标值为 $1/18$。

对增广目标，正类约束及 Cauchy–Schwarz 给

$$w^2+b^2\geq\frac{(w+b)^2}{2}\geq\frac12.$$

等号须 $w=b$ 且 $w+b=1$，唯一可能是 $w=b=1/2$。它亦符合另一约束，因 $5/2-1/2=2\geq1$。所以它是唯一增广范数最优解，目标值 $1/4$。

其边界为 $x=-1$，正点距离二、负点距离四，故最小特征空间间隔二。两分类器训练错误都零，但标准特征间隔三较大。目标值来自不同目标，不能当成同一损失的竞争量度。

$(1/2,1/2)$ 的增广间隔是 $1/\sqrt{1/2}=\sqrt2$，特征间隔却是二。标准参数的增广范数为 $\sqrt5/3$，故增广间隔 $3/\sqrt5$。这些数值明确展示两种几何。

若删去负例，仅余约束 $w+b\geq1$。所有 $w=0,b\geq1$ 都把标准目标取到零。存在性没有失败，但 b 不唯一，特征法向量为零。非退化超平面间隔定理假设两种标签，不能套在此处。事实上固定单位法向量 $w=1$ 并增大 b，此单点的特征间隔任意大，所以真正超平面之间没有有限的最大间隔。这正是常数预测最优值与两标签几何等价性的不同情形。

8. 知识连接与补充范围

同一实特征表可用于数值回归、有标签投影、学习距离几何及二元分类。由目标与输出决定哪种计算合适。Fisher 方向未必解硬间隔约束，近邻平方距离间隔亦不是本节推导的几何量。

要计算光滑二次损失，可读二次函数的梯度下降法；要区分拟合与评估，可读模型验证与岭回归。这些连接不会把本节有限数据定理变成统计预测保证。

已证的端点是二元仿射几何、指定感知机的更新及停止界，以及有限严格可分且两种标签皆有时被取到的标准硬间隔。软间隔、核、对偶形式、多类模型及概率泛化是其他主题。上述四道题及完整详解都是原创。