03 · 从问题进入原章节
一次分错后,更新把分类边界往哪推?
先手算带标签的一次更新,再检查线性可分条件。XOR 不能靠增加训练轮数解决,mistake bound 也有明确前提。
读后可检查:能区分单次更新、收敛保证与模型表达能力三件事。
📑 本页目录(点开跳转)
03 · 感知机:分错之后如何更新
⏱ 22 分钟(原预计,仅供参考,可分次读) | ⭐ 神经网络的早期基础
🎯 一句话
感知机用一条直线分两类:样本分错了,或者正好落在边界上,就调整权重和偏置。
先不背收敛定理。你只要能回答:这次更新改了什么,怎样检查它有没有帮到当前样本?
这一页有三个入口:
感知机是 Rosenblatt 在 20 世纪 50 年代提出的早期学习模型,不是“人类第一个能学习的算法”。
🧠 一、先算分数,再决定要不要更新
假设每条样本有输入向量 $x$,真实标签 $y$ 只能取 $+1$ 或 $-1$。
模型先算一个分数,它不是概率:
$$s=w^\top x+b$$
| 符号 | 在这里做什么 |
|---|---|
| $x$ | 当前样本的特征,例如两个输入数 |
| $w$ | 每个特征的权重,控制分界线的方向 |
| $b$ | 偏置,允许分界线不经过原点 |
| $y$ | 正确答案,用来判断分数方向对不对 |
$s>0$ 判正类,$s<0$ 判负类。也常写成 $\hat y=\operatorname{sign}(s)$。
正好等于 0 要单独约定。 本章训练时把边界点也算作需要更新;如果用于输出预测标签,应明确把 0 归到哪一类,不能悄悄产生第三种标签。
将真实标签乘进分数,得到带标签的分数 $ys$:
| 检查结果 | 说明 | 本章的动作 |
|---|---|---|
| $ys>0$ | 严格分对 | 不更新 |
| $ys<0$ | 分错 | 更新 |
| $ys=0$ | 落在边界上 | 也更新 |
本章把学习率固定为 1。发生更新时,两项都要改:
$$w_{\mathrm{new}}=w+yx$$
$$b_{\mathrm{new}}=b+y$$
如果使用其他正学习率,两项增量都要乘上它;不要只改权重、不改偏置。
看一次具体更新
当前样本是 $x=(2,0)$、$y=+1$。从 $w=(-1,1)$、$b=-0.5$ 出发,分数是 −2.5,所以要更新。
| 检查位置 | 更新前 | 更新后 |
|---|---|---|
| 权重 $w$ | $(-1,1)$ | $(1,1)$ |
| 偏置 $b$ | $-0.5$ | $0.5$ |
| 当前样本分数 $s$ | $-2.5$ | $2.5$ |
| 对真实标签 $+1$ 的判断 | 分错 | 分对 |
看图时只追踪同一个蓝点。 点没有移动;权重与偏置改变,使分界线的位置和方向改变,这个例子中的点因此从负分变成正分。
💡 为什么这次调整有帮助
把两条更新式代回同一个样本。更新前后的分数之差是:
$$s_{\mathrm{new}}-s=y(\|x\|^2+1)$$
再乘上标签;因为 $y^2=1$,所以:
$$ys_{\mathrm{new}}-ys=\|x\|^2+1>0$$
意思是:当前样本的带标签分数一定提高。 对正类,普通分数往上走;对负类,普通分数往下走。
这里的“$+1$”来自偏置更新。若模型明确固定 $b=0$、只更新 $w$,增量才是 $\|x\|^2$,而且零向量会让这个增量为 0。
提高不等于这一次就能分对。 例如一维输入 $x=1,y=+1$,从 $w=-3,b=0$ 更新后,分数只是从 −3 变成 −1,仍然分错。
对当前样本有帮助,也不保证其他样本都变好;后续仍要继续检查整批数据。
🔨 运行:AND 能分开,XOR 不能
下面是一段可以整体复制运行的程序,需要 NumPy。输入始终是同样的四个点,只有标签改变。
- AND:两个输入都是 1,原始输出才是 1。
- XOR(异或):两个输入不同,原始输出才是 1。
- 训练前,把原始输出 0 映射为 $-1$,输出 1 映射为 $+1$。
import numpy as np
def perceptron(X, y, max_epochs=100):
X, y = np.asarray(X, dtype=float), np.asarray(y, dtype=float)
if X.ndim != 2 or len(X) == 0 or y.shape != (len(X),):
raise ValueError("X 要有多行样本,y 要与每一行对应")
if not np.isfinite(X).all() or not np.isin(y, [-1, 1]).all():
raise ValueError("输入要是有限数,标签只能是 -1 或 +1")
if not isinstance(max_epochs, int) or max_epochs < 1:
raise ValueError("max_epochs 要是正整数")
w = np.zeros(X.shape[1])
b, updates = 0.0, 0
for epoch in range(1, max_epochs + 1):
for xi, yi in zip(X, y):
if yi * (w @ xi + b) <= 0:
w += yi * xi
b += yi
updates += 1
if np.all(y * (X @ w + b) > 0):
return w, b, epoch, updates, True
return w, b, max_epochs, updates, False
X = np.array([[0, 0], [0, 1], [1, 0], [1, 1]])
for name, y in [("AND", [-1, -1, -1, 1]), ("XOR", [-1, 1, 1, -1])]:
w, b, epochs, updates, converged = perceptron(X, y, max_epochs=50)
print(f"{name}: 收敛={converged}, 轮数={epochs}, 更新={updates}")
print("w =", w, "b =", b)
运行后重点看这两行:
| 数据 | 是否全部严格分对 | 扫过数据的轮数 | 参数更新次数 |
|---|---|---|---|
| AND | True | 8 | 18 |
| XOR | False | 50 | 200 |
这里固定了样本顺序、零初始化和 50 轮上限。AND 得到 $w=(3,2),b=-4$;换顺序可能得到别的可行分界线。
代码里三处值得看:
- 更新条件是 $ys\le0$,含边界点;更新同时涉及 $w$ 和 $b$。
- 每轮末尾重新检查所有样本,不能把“刚刚改过的那个点”当成整批数据。
- 返回的 False 只表示达到轮数上限时还没有全部严格分对,不能仅凭它证明数据不可分。
本例 XOR 最后回到 $w=0,b=0$,四个点都在边界上,因此检查不通过。不要把这个结果读成“四个点都预测正确”。
🏆 二、收敛保证:先把条件对齐
对有限、线性可分的训练集,按上面的规则反复遍历,感知机会在有限次更新后找到分界线。 这里不设置一个可能过小的轮数上限。
“线性可分”指存在一组参数,使每个训练样本都有 $y_i(w^\top x_i+b)>0$。这不是对测试集正确率的保证。
先让偏置进入同一套记号
为了让定理与刚才的代码一致,把偏置作为一个额外维度:
$$z_i=(x_i,1),\qquad v=(w,b)$$
于是 $v^\top z_i=w^\top x_i+b$,两条更新合起来就是 $v_{\mathrm{new}}=v+y_i z_i$。
定理用到四个量,可以分开认:
- $R$:输入有多大。 它是所有扩展输入 $z_i$ 的最大长度。
- $u$:选定的分隔方向。 它能严格分开数据,而且是单位向量,$\|u\|=1$。
- $\gamma$:这个方向的最小带标签分数。 它必须为正,具体定义见下式。
- $M$:更新的总次数。 边界点触发的更新也计入。
$$\gamma=\min_i y_i u^\top z_i>0$$
不要求 $u$ 是“最优”方向;任取满足条件的单位分隔向量,就有对应的界。更好的间隔可能给出更紧的界。
从 $v=0$ 开始、学习率为 1、在带标签分数不大于 0 时更新,则:
$$M\le \left(\frac{R}{\gamma}\right)^2$$
读这个式子:在其他量不变时,间隔越大,上界越小。 上界更小不等于每次实际运行都更快。
🔑 这个定理为什么重要
- 它给的是更新次数保证。 公式没有单独出现样本数 $n$ 和维度 $d$,但它们可能改变 $R$ 与 $\gamma$;检查更多样本、计算更高维内积也需要更多时间。
- 它把实验现象变成了有条件的证明。 这是早期学习理论的重要结果之一,不宜称作“机器学习史上第一个学习保证”。
- 它突出间隔的作用。 SVM 会主动寻找大间隔,但常见 SVM 的几何间隔按 $\|w\|$ 归一化;本节把偏置并入向量,两者的间隔数值不能直接混用。
用刚才的 AND 数据算一个上界
扩展输入的最大长度是 $R=\sqrt3$。
取 $u=(2,2,-3)/\sqrt{17}$。对四个点计算带标签分数,最小值为 $\gamma=1/\sqrt{17}$。
所以这个方向给出 $M\le51$。程序实际用了 18 次更新,符合上界;51 不是必须用满的次数,也不是 51 轮。
证明分三步:每一步只追踪一个量
设 $v_k$ 是第 $k$ 次更新后的参数,$v_0=0$。
第一步:朝固定分隔方向的投影持续增长。
每次增量 $y_i z_i$ 与 $u$ 的内积至少是 $\gamma$。累加 $k$ 次后:
$$v_k^\top u\ge k\gamma$$
第二步:参数长度不会增长得太快。
平方长度的一次增量为:
$$2y_i v_{k-1}^\top z_i+\|z_i\|^2$$
触发更新时,第一项不大于 0;第二项不超过 $R^2$。所以:
$$\|v_k\|^2\le kR^2$$
第三步:把两个方向的限制合起来。
由柯西不等式和 $\|u\|=1$:
$$k\gamma\le \|v_k\|\le\sqrt{k}R$$
当 $k>0$,整理得到 $k\le(R/\gamma)^2$;$k=0$ 时自然满足。
🧩 三、XOR 的问题不在训练轮数
单条直线本来就无法严格分开 XOR。 增加训练轮数不能改变这个表达能力限制。
| 输入 $(x_1,x_2)$ | XOR 原始输出 | 本章训练标签 |
|---|---|---|
| $(0,0)$ | 0 | $-1$ |
| $(0,1)$ | 1 | $+1$ |
| $(1,0)$ | 1 | $+1$ |
| $(1,1)$ | 0 | $-1$ |
看两条虚线交叉的地方:两类分别占据一条对角线。 虚线只连接同类点,不是分类边界;无论怎样放一条直线,都无法把全部实心点与空心点严格分到两侧。
用四个不等式确认 XOR 不可分
若能严格分开,$(0,0)$ 的负标签要求 $b<0$。
两个正样本分别要求 $w_1+b>0$、$w_2+b>0$。相加可得:
$$w_1+w_2+2b>0$$
因此 $w_1+w_2+b>-b>0$。但 $(1,1)$ 的负标签又要求它小于 0,矛盾。
停止与不可分要分开判断:
- 对不可分数据,无上限反复遍历的基础算法不能达到“所有样本都严格分对”的停止条件。
- 实际程序通常会按轮数上限停止。达到上限也可能只是轮数不足,不能反推所有这样的数据都不可分。
你在基础教程第 7 章见过这个异或实验。Minsky 与 Papert 的 1969 年著作研究了感知机的能力与限制;不能把 AI 寒冬简单归因于一个 XOR 结论,也不能据此否定多层网络。
三条出路,各自放宽不同限制
| 出路 | 改变什么 | 继续阅读 |
|---|---|---|
| 多层加非线性激活 | 改变可表示的函数,能表达 XOR;不保证训练必然成功 | 第 12 章:反向传播 |
| 特征映射与核方法 | 换一个特征空间;不是只要升维就一定可分 | 第 6 章:核技巧 |
| 软间隔 SVM | 允许一定违例,权衡间隔与惩罚;不强求零训练错误 | 第 7 章:SVM |
一个可核算的映射例子:给 XOR 增加特征 $x_1x_2$,用分数 $x_1+x_2-2x_1x_2-0.5$。
按上表顺序,得到 −0.5、0.5、0.5、−0.5,标签方向全部正确。起作用的是新增特征的含义,不是“维度变多”这几个字。
🔬 四、感知机 vs 逻辑回归
两者都能用线性分数,但训练目标不同。 逻辑回归不是给感知机输出套一个概率,就算改完了。
| 比较点 | 感知机 | 逻辑回归 |
|---|---|---|
| 输出 | 按分数正负给标签 | 经 sigmoid 得到概率估计,不自动保证校准良好 |
| 训练关注 | 严格分错或边界上的点 | 所有样本都进入损失;具体一次更新用多少样本,取决于优化器 |
| 可分数据 | 找到严格分隔就可停,结果依赖顺序 | 不加正则时,可不断放大分隔方向,使损失趋向 0;没有有限参数达到这个下确界 |
| 不可分数据 | 不能达到零违例的停止条件 | 可以拟合概率,但不能仅凭“不可分”就保证有限、唯一且优化成功 |
| 解的唯一性 | 不保证 | 要看严格凸性等条件,不能把“加了任意正则”当作充分条件 |
想对照损失函数与正则化条件,再看这里
记 $s=w^\top x+b$。感知机损失常写为:
$$\ell_{\mathrm{perc}}=\max(0,-ys)$$
当 $ys=0$ 时损失也是 0,但本章仍选择一个非零的次梯度方向更新。因此只检查这个损失为 0 不够:零初始化就会让所有样本的该损失为 0,却没有严格分开任何点。
对 $y\in\{-1,+1\}$,逻辑回归的单样本损失是:
$$\ell_{\mathrm{log}}=\log(1+\exp(-ys))$$
它对应伯努利模型的负对数似然,见第 1 章:最大似然。
若给所有参数(包括偏置)加正系数的 L2 二次惩罚,目标会强凸并在有限处取得唯一最优解。若偏置不受罚、只用 L1,或者存在退化方向,就不能原样搬用这句话。
这里谈的是目标函数的性质;具体优化程序是否正确实现、是否给了足够迭代次数,还要另查。
和 SVM 怎么区分? 感知机找到可行分隔就满意;硬间隔 SVM 在可分情形中选取最大几何间隔,软间隔则容许违例。两者与本节定理共享“间隔重要”的思想,不代表约束和归一化完全相同。
🧩 五、Mistake Bound:边预测,边接收答案
在线学习的顺序是:先预测,再得到标签,再决定更新。 不能先看到答案,再把这次预测算进表现。
- 收到一个输入 $x_t$,用当前参数预测。
- 收到真实标签 $y_t$,检查带标签分数。
- 必要时更新参数,然后处理下一条输入。
这一视角问:“整个过程中会触发多少次错误或边界更新?”它与第 9 章 PAC 学习关注的样本量、泛化问题不同,但并不互相排斥。
刚才的有限更新界需要:整个序列存在同一个固定的正间隔分隔方向,并且扩展输入长度有统一上界。 不要求顺序独立同分布,不等于可以去掉这些条件。
| 场景 | 为什么考虑在线更新 | 还要留意什么 |
|---|---|---|
| 流式数据 | 不断出现新输入,难以等所有数据收齐 | 特征尺度是否受控,标签是否能取得 |
| 在线广告与推荐 | 预测后陆续收到点击等反馈 | 反馈可能延迟或只来自被展示的项目,并非每次都有即时完整答案 |
| 概念漂移 | 目标随时间改变,需要持续适应 | 可能不存在同一个固定分隔方向;上面的有限界不能直接沿用 |
🎁 六、感知机的后代
按你遇到的问题选读,不需要一次背完名字。
| 方法 | 主要改变 |
|---|---|
| 带间隔的感知机 | 不只看分对,还要求带标签分数 $ys$ 超过一个正阈值 |
| 平均感知机 | 累计各个预测步骤的参数,输出平均值,减少只依赖最后状态的影响 |
| Pegasos | 用随机次梯度方法优化带 L2 正则的 SVM 原始目标,不只是原感知机换名 |
| 多层感知机 MLP | 堆叠线性变换与非线性激活,通常用反向传播训练;不继承这里的单层收敛保证 |
平均感知机要同时处理 $w$ 和 $b$。常见平均方式包含参数没有发生更新的步骤;若只平均更新后的状态,等于换了权重方式。它可能改善表现,不保证在所有任务上更好。
🔗 七、和站内其他章的关系
| 你想接着解决什么 | 去哪里 |
|---|---|
| 亲手看 XOR 与多层网络 | 基础教程第 7 章“从线性到神经网络” |
| 理解多层网络如何训练 | 基础教程第 8 章,以及数学原理第 12 章的反向传播推导 |
| 找更大间隔,而不只是任意分隔 | 数学原理第 7 章 SVM |
| 看概率拟合的出发点 | 数学原理第 1 章最大似然 |
| 区分在线错误界与泛化保证 | 数学原理第 9 章 PAC 学习 |
资料依据:需要核对原始定义时再打开
- Cornell CS4780:感知机与偏置扩展:更新、扩展输入与收敛证明。
- Mohri 与 Rostamizadeh:Perceptron Mistake Bounds:有界输入、正间隔下的更新次数界及其背景。
- Minsky 与 Papert:Perceptrons,1969:感知机能力限制的历史文献。
- Soudry 等:The Implicit Bias of Gradient Descent on Separable Data:可分数据上无正则逻辑损失的梯度下降行为。
- Pegasos 原始论文:随机次梯度求解 SVM 的算法定义。
本页 AND、XOR 和单次更新数值是可复算的教学例子,不是上述论文报告的实验结果。
✅ 检查点
- 什么时候更新?为什么权重和偏置都要写出来?
- 有限更新界需要哪些条件?$R$、$\gamma$、$M$ 分别是什么?
- 公式没写 $n,d$,能否解释成数据量与维度完全不影响训练?
- 达到轮数上限能否证明不可分?XOR 为什么不同?
- 感知机的历史限制该怎样理解?三条出路分别改变什么?
- 感知机与逻辑回归在输出、目标和解的条件上有什么不同?
- 在线学习的反馈顺序是什么?概念漂移时为什么不能直接套旧界?
核对答案
- $ys\le0$ 时更新 $w$ 和 $b$;当前样本带标签分数增加 $\|x\|^2+1$。这不保证一次分对全部样本。
- 零初始化、单位学习率、统一有界的扩展输入,以及固定的正间隔分隔方向。$M$ 计更新次数,不是轮数。
- 不能。$n,d$ 可能改变尺度和间隔,也影响遍历与内积的开销。
- 不能,可能只是轮数不够。XOR 的不可分由其四个点的几何关系或不等式矛盾证明,不靠程序超时证明。
- 单层线性限制不能否定多层网络,也不能单因解释 AI 寒冬。非线性多层改变表达能力,特征映射改变表示,软间隔允许违例。
- 感知机给硬标签并追求严格分对;逻辑回归拟合概率、所有点进入损失。唯一性需要条件,任意正则并不自动保证。
- 先输入、预测,再标签、更新。漂移可能破坏“同一个固定正间隔分隔方向”的假设。
本节回顾
先记住这三件事
- 分错或落在边界上,就一起更新权重和偏置。
- 有限更新保证有前提;轮数用完不等于证明不可分。
- 直线分不开时,考虑换表示、用非线性模型,或允许违例。
下一节 👉 第 04 章:非参数方法