📑 本页目录（点开跳转）
03 · 感知机：第一个学习算法
⏱ 22 分钟 ｜ ⭐ 神经网络的祖先
🎯 一句话
感知机是 1957 年发明的第一个能从数据中学习的算法，规则简单到一行： 猜错了就朝正确方向挪一下。 它有一个漂亮的保证——只要数据线性可分，它一定在有限步内收敛。
🧠 一、算法本身（真的只有一行）
模型：ŷ = sign(w·x + b) ← 大于0判正类，小于0判负类
训练：遍历样本
├─ 预测对了 → 什么都不做 ⭐ 注意这一条
└─ 预测错了 → w ← w + y·x
（y 是真实标签 +1 或 −1）
💡 为什么这个更新是对的（自己验证一遍）
假设真实标签 y = +1，但你预测成了 −1
→ 说明 w·x < 0（分数太小了）
更新：w_new = w + y·x = w + x
再算这个样本的分数：
w_new·x = (w + x)·x = w·x + ‖x‖²
↑ 一定是正数（模长的平方）
→ 分数变大了，更可能判对 ✅
y = −1 的情况同理（更新是 w − x，分数会减小）。
这就是「朝正确方向挪一下」的严格含义。
🔨 十行实现
import numpy as np
def perceptron(X, y, max_epochs=100):
w = np.zeros(X.shape[1]); b = 0.0
for epoch in range(max_epochs):
errors = 0
for xi, yi in zip(X, y):
if yi * (w @ xi + b) <= 0: # 分错了（含正好在边界上）
w += yi * xi # ⭐ 核心就这两行
b += yi
errors += 1
if errors == 0:
return w, b, epoch # 收敛了
return w, b, max_epochs # 没收敛（可能线性不可分）
🏆 二、感知机收敛定理
如果数据线性可分，感知机保证在有限步内停止，且犯错次数有上界：
$$\text{错误次数} \le \left(\frac{R}{\gamma}\right)^2$$
- $R$ = 数据点到原点的最大距离（数据的"尺度"）
- $\gamma$ = 间隔（margin）——最优分界线到最近点的距离
💡 人话翻译：
两类分得越开（γ 大），学得越快；数据分布越散（R 大），学得越慢。
🔑 这个定理为什么重要（三点）
① 它和【数据量 n】无关，也和【维度 d】无关 ⭐
→ 100 万个样本和 100 个样本，错误次数上界一样
→ 1000 维和 10 维，上界一样
→ 这在当时是非常反直觉的结果
② 它是机器学习史上第一个【学习保证】
不是"实验上跑得不错"，而是"数学上保证会成功"
→ 这条思路后来长成了整个【学习理论】（第 9-10 章）
③ 「间隔 γ」这个量后来成了 SVM 的核心 ⭐
在这里它决定【收敛速度】
在 SVM 里它成了【优化目标本身】（第 7 章）
📐 证明思路（想看再点）
设存在最优解 $w^*$（单位向量），间隔 $\gamma = \min_i y_i (w^{*\top} x_i)$。
第 k 次犯错后，从两个方向夹逼 $\|w_k\|$：
下界（内积单调增长）： $$w_k^\top w^* = (w_{k-1} + y_i x_i)^\top w^* \ge w_{k-1}^\top w^* + \gamma \;\Rightarrow\; w_k^\top w^* \ge k\gamma$$
上界（模长增长有限）：因为犯错时 $y_i(w_{k-1}^\top x_i) \le 0$， $$\|w_k\|^2 = \|w_{k-1}\|^2 + 2y_i w_{k-1}^\top x_i + \|x_i\|^2 \le \|w_{k-1}\|^2 + R^2 \;\Rightarrow\; \|w_k\|^2 \le kR^2$$
合起来（用柯西不等式 $w_k^\top w^* \le \|w_k\|$）： $$k\gamma \le \|w_k\| \le \sqrt{k}R \;\Rightarrow\; k \le (R/\gamma)^2$$
💀 三、致命缺陷：线性不可分就永远不停
数据线性可分 → ✅ 有限步收敛
数据线性不可分 → ❌ 永远震荡，不收敛，【也不会告诉你】
⚠️ 「也不会告诉你」是实践中最坑的一点： 你只能看到它一直在跑，无法区分「快收敛了」和「永远不会收敛」。
而异或（XOR）就是线性不可分的：
x2
1 │ ●(0,1)=1 ○(1,1)=0
│
0 │ ○(0,0)=0 ●(1,0)=1
└──────────────► x1
0 1
画不出一条直线把 ● 和 ○ 分开
🔗 你在基础教程第 7 章见过那个异或实验—— 1969 年 Minsky 和 Papert 指出感知机连异或都学不了，直接导致了第一次「AI 寒冬」。
三条出路，对应了后来的三个方向
| 出路 | 变成了什么 | 在哪讲 |
|---|---|---|
| 堆多层 + 非线性激活 | 神经网络 | 第 12 章 |
| 把数据映射到高维使其可分 | 核方法 ⭐ | 第 6 章 |
| 允许犯错，但让间隔最大 | SVM 的软间隔 | 第 7 章 |
🔬 四、感知机 vs 逻辑回归（易混）
| 感知机 | 逻辑回归 | |
|---|---|---|
| 输出 | 硬的 ±1 | 概率 0~1 |
| 损失 | 感知机损失 max(0, −y·w·x) |
交叉熵 |
| 更新时机 | 只在犯错时 ⭐ | 每个样本都更新 |
| 可分时的行为 | 找到任意一条分界线就停 | 会继续推向更"自信"（权重发散） |
| 不可分时 | 不收敛 | 正常收敛 |
| 概率解释 | 无 | ✅ 有（第 1 章的 MLE） |
| 解的唯一性 | ❌ 取决于初始化和数据顺序 | ✅ （加正则后）唯一 |
💡 关键差异：感知机只要分对就满意，SVM 则问「哪条分界线最好」—— 这个问题的答案就是「间隔最大的那条」，而间隔正是收敛定理里那个 γ。
三者的关系：
感知机：分对就行 → 解不唯一 逻辑回归：让概率尽量对 → 关心所有点 SVM：让间隔最大 → 只关心边界附近的点
🧩 五、Mistake Bound：另一种学习理论视角
感知机开创了一个理论分支：不问「要多少数据」，而问「会犯多少次错」。
【在线学习】设定：
样本一个一个来 → 你预测 → 告诉你答案 → 你更新 → 下一个
问：整个过程你总共会犯多少次错？
感知机的答案：≤ (R/γ)² ← 与数据量无关！
这个视角在哪些场景有用：
| 场景 | 为什么 |
|---|---|
| 流式数据 | 没有"训练集"，只有源源不断的数据流 |
| 在线广告 / 推荐 | 每次展示都是一次预测 + 一次反馈 |
| 概念漂移 | 数据分布会变，"训练完再用"的范式不成立 |
🔗 这和第 9 章 PAC是学习理论的两条并行路线： PAC 问「要多少样本」，Mistake Bound 问「会犯多少错」。
🎁 六、感知机的后代（了解即可）
| 算法 | 改进了什么 |
|---|---|
| 带间隔的感知机 | 不只要求分对，还要求分数 > 某个阈值 → 更接近 SVM |
| 平均感知机 | 输出所有迭代中 w 的平均，而不是最后一个 → 更稳定，实践中常明显更好 |
| Pegasos | 用随机梯度下降解 SVM，兼具感知机的简单和 SVM 的间隔 |
| 多层感知机 MLP | 堆叠 + 非线性 → 神经网络 |
💡 平均感知机值得一提：一行改动（累加 w 再除以次数）， 效果常常显著优于原版——因为它降低了「最后一次更新恰好很糟」的风险。
🔗 七、和站内其他章的关系
| 相关的地方 | 这里的位置 |
|---|---|
| 基础教程第 7 章「异或问题」 | 感知机的致命缺陷，催生了神经网络 |
| 基础教程第 8 章反向传播 | 多层感知机的训练方法 |
| SVM 的"最大间隔" | 就是这里的 γ |
| 在线学习 / 流式训练 | Mistake bound 视角 |
| 逻辑回归 | 感知机的概率版本 |
✅ 检查点
- 感知机的更新规则是什么？为什么它朝正确方向挪？（能自己推一遍吗）
- 收敛定理保证了什么？错误次数的上界和什么有关、和什么无关？
- 这个定理为什么在当时是反直觉的？
- 线性不可分时感知机会怎样？为什么这在实践中特别坑？
- 异或问题导致了什么历史事件？三条出路各变成了什么？
- 感知机和逻辑回归最大的三个区别？
- Mistake Bound 视角适合什么场景？
👀 答案
- 猜错时
w ← w + y·x。推导：若 y=+1 但预测为负（w·x<0），更新后 w_new·x = w·x + ‖x‖²，一定增大，更可能判对。 - 线性可分时保证有限步收敛，错误次数 ≤ (R/γ)²。和数据量 n、维度 d 都无关，只和数据尺度 R 与间隔 γ 有关。
- 因为直觉上样本越多、维度越高应该越难学，但这个界完全不依赖它们——只依赖数据的几何结构（尺度和间隔）。
- 永远震荡不收敛。坑在于它不会告诉你——你无法区分"快收敛了"和"永远不会收敛"。
- 第一次 AI 寒冬（1969 年 Minsky & Papert）。三条出路：多层+非线性→神经网络；映射到高维→核方法；允许犯错但最大化间隔→SVM。
- ①感知机只在犯错时更新，逻辑回归每个样本都更新 ②感知机输出硬标签无概率解释，逻辑回归有 MLE 基础 ③感知机的解不唯一（取决于初始化和顺序），逻辑回归（加正则后）唯一。
- 流式数据、在线广告/推荐、概念漂移——即没有固定"训练集"、数据源源不断到来的场景。
🛑 可以停在这里
⚡ 走神救援
感知机 = 1957 年第一个能从数据中学习的算法，规则一行：ŷ = sign(w·x + b)，预测对了什么都不做，错了就 w ← w + y·x。为什么它朝正确方向挪：y=+1 却预测成负时，更新后该样本分数 w·x + ‖x‖² 一定变大。⭐收敛定理：只要数据线性可分就保证有限步内停止，且犯错次数 ≤ (R/γ)²——R 是数据到原点的最大距离，γ 是间隔（分界线到最近点的距离）；也就是两类分得越开学得越快，数据越散学得越慢。三个要害：①它和数据量 n、维度 d 都无关（100 万个样本和 100 个样本上界一样），当时极其反直觉；②这是机器学习史上第一个学习保证，后来长成了整个学习理论；③间隔 γ 后来成了 SVM 的核心：这里它决定收敛速度，在 SVM 里成了优化目标本身。💀致命缺陷：线性不可分时永远震荡不收敛，⚠️而且它不会告诉你——你无法区分「快收敛了」和「永远不会收敛」。异或就学不了：1969 年 Minsky 和 Papert 据此发难，直接导致第一次 AI 寒冬。三条出路长成了后来三个方向：多层 + 非线性 → 神经网络、映射到高维 → 核方法、允许犯错但让间隔最大 → SVM 软间隔。和逻辑回归的差异：输出硬 ±1、没有概率解释、只在犯错时更新（逻辑回归每样本都更新）、可分时找到任意一条线就停，解不唯一（取决于初始化和顺序）。一句话：感知机分对就行，逻辑回归关心所有点，SVM 只关心边界附近的点。它还开创了 Mistake Bound 视角：不问「要多少数据」而问「总共会犯多少次错」，适合流式与在线场景——PAC 问要多少样本，Mistake Bound 问会犯多少错。💡后代里最值得记的是平均感知机：输出所有迭代中 w 的平均而非最后一个，一行改动常明显更好。
下一节 👉 04-非参数方法.md