📑 本页目录（点开跳转）
03 · 感知机：第一个学习算法
⏱ 22 分钟 ｜ ⭐ 神经网络的祖先
🎯 一句话
感知机是 1957 年发明的第一个能从数据中学习的算法，规则简单到一行： 猜错了就朝正确方向挪一下。 它有一个漂亮的保证——只要数据线性可分，它一定在有限步内收敛。
🧠 一、算法本身（真的只有一行）
关键信息
- 模型：ŷ = sign(w·x + b) 大于0判正类，小于0判负类
- 训练：遍历样本
- 预测对了 → 什么都不做 ⭐ 注意这一条
- 预测错了 → w w + y·x
- （y 是真实标签 +1 或 −1）
💡 为什么这个更新是对的（自己验证一遍）
结果对照
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 大），学得越慢。
🔑 这个定理为什么重要（三点）
操作步骤
📐 证明思路（想看再点）
设存在最优解 $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）就是线性不可分的：
图下说明
- 1 ●(0,1)=1 ○(1,1)=0
- 0 ○(0,0)=0 ●(1,0)=1
- 画不出一条直线把 ● 和 ○ 分开
🔗 你在基础教程第 7 章见过那个异或实验—— 1969 年 Minsky 和 Papert 指出感知机连异或都学不了，直接导致了第一次「AI 寒冬」。
三条出路，对应了后来的三个方向
🔬 四、感知机 vs 逻辑回归（易混）
| 感知机 | 逻辑回归 | |
|---|---|---|
| 输出 | 硬的 ±1 | 概率 0~1 |
| 损失 | 感知机损失 max(0, −y·w·x) |
交叉熵 |
| 更新时机 | 只在犯错时 ⭐ | 每个样本都更新 |
| 可分时的行为 | 找到任意一条分界线就停 | 会继续推向更"自信"（权重发散） |
| 不可分时 | 不收敛 | 正常收敛 |
| 概率解释 | 无 | ✅ 有（第 1 章的 MLE） |
| 解的唯一性 | ❌ 取决于初始化和数据顺序 | ✅ （加正则后）唯一 |
💡 关键差异：感知机只要分对就满意，SVM 则问「哪条分界线最好」—— 这个问题的答案就是「间隔最大的那条」，而间隔正是收敛定理里那个 γ。
三者的关系：
感知机：分对就行 → 解不唯一 逻辑回归：让概率尽量对 → 关心所有点 SVM：让间隔最大 → 只关心边界附近的点
🧩 五、Mistake Bound：另一种学习理论视角
感知机开创了一个理论分支：不问「要多少数据」，而问「会犯多少次错」。
流程图
这个视角在哪些场景有用：
| 场景 | 为什么 |
|---|---|
| 流式数据 | 没有"训练集"，只有源源不断的数据流 |
| 在线广告 / 推荐 | 每次展示都是一次预测 + 一次反馈 |
| 概念漂移 | 数据分布会变，"训练完再用"的范式不成立 |
🔗 这和第 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 基础 ③感知机的解不唯一（取决于初始化和顺序），逻辑回归（加正则后）唯一。
- 流式数据、在线广告/推荐、概念漂移——即没有固定"训练集"、数据源源不断到来的场景。
🛑 可以停在这里
⚡ 走神救援
先记住这几件事
- 感知机用线性分数分类，在误分类时沿样本方向更新权重。
- 有限步收敛保证依赖线性可分等条件，不能用于证明不可分数据也会收敛。
- 它找到可行分界线就可以停止；核方法、多层网络和软间隔分别放宽不同限制。
下一节 👉 04-非参数方法.md