🏠 总目录📚 本教程 03 · 感知机 ← →

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),b = -0.5x₁x₂wx=(2,0)分数 s = -2.5更新后:分对w = (1, 1),b = 0.5x₁x₂wx=(2,0)分数 s = 2.5蓝点不动;虚线是分界线,实线标出权重方向本例分数增加 5:其中 4 来自权重,1 来自偏置
同时更新权重与偏置:本例分数从 −2.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。输入始终是同样的四个点,只有标签改变。

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$;换顺序可能得到别的可行分界线。

代码里三处值得看:

  1. 更新条件是 $ys\le0$,含边界点;更新同时涉及 $w$ 和 $b$。
  2. 每轮末尾重新检查所有样本,不能把“刚刚改过的那个点”当成整批数据。
  3. 返回的 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$。

定理用到四个量,可以分开认:

$$\gamma=\min_i y_i u^\top z_i>0$$

不要求 $u$ 是“最优”方向;任取满足条件的单位分隔向量,就有对应的界。更好的间隔可能给出更紧的界。

从 $v=0$ 开始、学习率为 1、在带标签分数不大于 0 时更新,则:

$$M\le \left(\frac{R}{\gamma}\right)^2$$

读这个式子:在其他量不变时,间隔越大,上界越小。 上界更小不等于每次实际运行都更快。

🔑 这个定理为什么重要

  1. 它给的是更新次数保证。 公式没有单独出现样本数 $n$ 和维度 $d$,但它们可能改变 $R$ 与 $\gamma$;检查更多样本、计算更高维内积也需要更多时间。
  2. 它把实验现象变成了有条件的证明。 这是早期学习理论的重要结果之一,不宜称作“机器学习史上第一个学习保证”。
  3. 它突出间隔的作用。 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 的同类点处在对角位置x₁x₂(0,0):−1(1,0):+1(0,1):+1(1,1):−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:边预测,边接收答案

在线学习的顺序是:先预测,再得到标签,再决定更新。 不能先看到答案,再把这次预测算进表现。

  1. 收到一个输入 $x_t$,用当前参数预测。
  2. 收到真实标签 $y_t$,检查带标签分数。
  3. 必要时更新参数,然后处理下一条输入。

这一视角问:“整个过程中会触发多少次错误或边界更新?”它与第 9 章 PAC 学习关注的样本量、泛化问题不同,但并不互相排斥。

刚才的有限更新界需要:整个序列存在同一个固定的正间隔分隔方向,并且扩展输入长度有统一上界。 不要求顺序独立同分布,不等于可以去掉这些条件。

场景 为什么考虑在线更新 还要留意什么
流式数据 不断出现新输入,难以等所有数据收齐 特征尺度是否受控,标签是否能取得
在线广告与推荐 预测后陆续收到点击等反馈 反馈可能延迟或只来自被展示的项目,并非每次都有即时完整答案
概念漂移 目标随时间改变,需要持续适应 可能不存在同一个固定分隔方向;上面的有限界不能直接沿用

🎁 六、感知机的后代

按你遇到的问题选读,不需要一次背完名字。

方法 主要改变
带间隔的感知机 不只看分对,还要求带标签分数 $ys$ 超过一个正阈值
平均感知机 累计各个预测步骤的参数,输出平均值,减少只依赖最后状态的影响
Pegasos 用随机次梯度方法优化带 L2 正则的 SVM 原始目标,不只是原感知机换名
多层感知机 MLP 堆叠线性变换与非线性激活,通常用反向传播训练;不继承这里的单层收敛保证

平均感知机要同时处理 $w$ 和 $b$。常见平均方式包含参数没有发生更新的步骤;若只平均更新后的状态,等于换了权重方式。它可能改善表现,不保证在所有任务上更好。


🔗 七、和站内其他章的关系

你想接着解决什么 去哪里
亲手看 XOR 与多层网络 基础教程第 7 章“从线性到神经网络”
理解多层网络如何训练 基础教程第 8 章,以及数学原理第 12 章的反向传播推导
找更大间隔,而不只是任意分隔 数学原理第 7 章 SVM
看概率拟合的出发点 数学原理第 1 章最大似然
区分在线错误界与泛化保证 数学原理第 9 章 PAC 学习
资料依据:需要核对原始定义时再打开

本页 AND、XOR 和单次更新数值是可复算的教学例子,不是上述论文报告的实验结果。


✅ 检查点

  1. 什么时候更新?为什么权重和偏置都要写出来?
  2. 有限更新界需要哪些条件?$R$、$\gamma$、$M$ 分别是什么?
  3. 公式没写 $n,d$,能否解释成数据量与维度完全不影响训练?
  4. 达到轮数上限能否证明不可分?XOR 为什么不同?
  5. 感知机的历史限制该怎样理解?三条出路分别改变什么?
  6. 感知机与逻辑回归在输出、目标和解的条件上有什么不同?
  7. 在线学习的反馈顺序是什么?概念漂移时为什么不能直接套旧界?
核对答案
  1. $ys\le0$ 时更新 $w$ 和 $b$;当前样本带标签分数增加 $\|x\|^2+1$。这不保证一次分对全部样本。
  2. 零初始化、单位学习率、统一有界的扩展输入,以及固定的正间隔分隔方向。$M$ 计更新次数,不是轮数。
  3. 不能。$n,d$ 可能改变尺度和间隔,也影响遍历与内积的开销。
  4. 不能,可能只是轮数不够。XOR 的不可分由其四个点的几何关系或不等式矛盾证明,不靠程序超时证明。
  5. 单层线性限制不能否定多层网络,也不能单因解释 AI 寒冬。非线性多层改变表达能力,特征映射改变表示,软间隔允许违例。
  6. 感知机给硬标签并追求严格分对;逻辑回归拟合概率、所有点进入损失。唯一性需要条件,任意正则并不自动保证。
  7. 先输入、预测,再标签、更新。漂移可能破坏“同一个固定正间隔分隔方向”的假设。

本节回顾

先记住这三件事

下一节 👉 第 04 章:非参数方法

打卡记录保存在你的浏览器里,首页能看到总进度