CS229-6 The Perceptron and Large Margin

创建：2026/6/7 科研机器学习 CS229

感知机

1. Batch Learning vs Online Learning

1.1 Batch Learning

前面的大多数算法都是 batch learning。

比如 logistic regression、SVM、GDA、Naive Bayes，通常都是：

{(x^{(i)}, y^{(i)})}_{i = 1}^{m}

全部训练数据先给你，然后你训练模型 $h_{θ} (x)$ ，最后在测试集上评估。

这种学习方式关注的是 training error 和 generalization error。

1.2 Online Learning

Online learning 的流程是：

第 1 步，给模型看 $x^{(1)}$ ，模型先预测 ${\hat{y}}^{(1)}$ ，然后真实标签 $y^{(1)}$ 被揭晓。如果预测错了，模型更新参数。
接着给模型看 $x^{(2)}$ ，再预测、揭晓、更新。
一直到 $x^{(m)}$ 。

在 online learning 中，我们关心的是 number of mistakes——也就是总共犯了多少次错，而不是单纯关心最后模型在测试集上的表现。

2. Perceptron Algorithm：感知机算法

感知机模型为：

h_{θ} (x) = g (θ^{T} x)

其中：

g (z) = {\begin{cases} 1, & z \geq 0 \\ - 1, & z < 0 \end{cases}

2.1 Perceptron Update Rule

给定一个训练样本 $(x, y)$ ：

如果预测正确 $h_{θ} (x) = y$ ，那么不更新参数。
如果预测错误 $h_{θ} (x) \neq y$ ，则更新：

θ := θ + y x

CS229 notes6 中给出的更新规则正是：如果预测正确则不改变参数；如果预测错误，则执行 $θ := θ + y x$ 。

2.2 为什么更新是 $θ := θ + y x$ ？

我们希望正确分类时满足：

y (θ^{T} x) > 0

如果某个样本被分错，说明：

y (θ^{T} x) \leq 0

更新后 $θ_{n e w} = θ + y x$ ，于是：

\begin{aligned} y (θ_{n e w}^{T} x) & = y ((θ + y x)^{T} x) \\ = y θ^{T} x + y^{2} x^{T} x \\ = y θ^{T} x + ∥ x ∥^{2} (∵ y^{2} = 1) \end{aligned}

也就是说，更新之后，这个样本的分类 margin 至少往正确方向增加了 $∥ x ∥^{2}$ 。

所以这个更新规则的直觉是：

如果正样本被误判为负，就把 $θ$ 往 $x$ 的方向推；
如果负样本被误判为正，就把 $θ$ 往 $- x$ 的方向推。

3. Online Mistake Bound：感知机犯错次数上界

这是 note6 的核心定理。

假设存在一个单位向量 $u$ （ $∥ u ∥_{2} = 1$ ），并且对所有样本满足：

y^{(i)} (u^{T} x^{(i)}) \geq γ

这表示数据不仅线性可分，而且存在一个 margin 至少为 $γ$ 的分隔超平面。

同时假设所有输入都有界：

∥ x^{(i)} ∥ \leq D

那么感知机算法在整个序列上犯错次数至多为：

{(\frac{D}{γ})}^{2}

3.1 第一部分：证明 $θ$ 沿着正确方向增长

考虑 $(θ^{(k + 1)})^{T} u$ 。由更新式 $θ^{(k + 1)} = θ^{(k)} + y^{(i)} x^{(i)}$ ，有：

(θ^{(k + 1)})^{T} u = (θ^{(k)})^{T} u + y^{(i)} (x^{(i)})^{T} u

由于假设存在 margin $y^{(i)} u^{T} x^{(i)} \geq γ$ ，因此：

(θ^{(k + 1)})^{T} u \geq (θ^{(k)})^{T} u + γ

每犯一次错，参数向量在正确方向 $u$ 上的投影至少增加 $γ$ 。所以经过 $k$ 次错误后：

(θ^{(k + 1)})^{T} u \geq k γ

CS229 notes6 里也是通过这个归纳得到 $(θ^{(k + 1)})^{T} u \geq k γ$ 。

3.2 第二部分：证明 $∥ θ ∥$ 增长不会太快

现在看参数范数。由更新式 $θ^{(k + 1)} = θ^{(k)} + y^{(i)} x^{(i)}$ ：

\begin{aligned} ∥ θ^{(k + 1)} ∥^{2} & = ∥ θ^{(k)} + y^{(i)} x^{(i)} ∥^{2} \\ = ∥ θ^{(k)} ∥^{2} + ∥ x^{(i)} ∥^{2} + 2 y^{(i)} (θ^{(k)})^{T} x^{(i)} \end{aligned}

因为这一步发生在"犯错"的样本上，所以 $y^{(i)} (θ^{(k)})^{T} x^{(i)} \leq 0$ ，交叉项 $\leq 0$ 。因此：

∥ θ^{(k + 1)} ∥^{2} \leq ∥ θ^{(k)} ∥^{2} + ∥ x^{(i)} ∥^{2}

又因为 $∥ x^{(i)} ∥ \leq D$ ，所以：

∥ θ^{(k + 1)} ∥^{2} \leq ∥ θ^{(k)} ∥^{2} + D^{2}

每次犯错，参数范数平方最多增加 $D^{2}$ 。经过 $k$ 次错误后：

∥ θ^{(k + 1)} ∥^{2} \leq k D^{2} \Rightarrow ∥ θ^{(k + 1)} ∥ \leq \sqrt{k} D

CS229 notes6 的证明中也用犯错条件得到交叉项不大于 0，从而推出 $∥ θ^{(k + 1)} ∥^{2} \leq k D^{2}$ 。

3.3 第三部分：把两个不等式合起来

我们已有 $(θ^{(k + 1)})^{T} u \geq k γ$ 和 $∥ θ^{(k + 1)} ∥ \leq \sqrt{k} D$ 。

由 Cauchy-Schwarz inequality（ $∥ u ∥ = 1$ ）：

(θ^{(k + 1)})^{T} u \leq ∥ θ^{(k + 1)} ∥ ∥ u ∥ = ∥ θ^{(k + 1)} ∥

因此：

k γ \leq (θ^{(k + 1)})^{T} u \leq ∥ θ^{(k + 1)} ∥ \leq \sqrt{k} D

即 $k γ \leq \sqrt{k} D$ ，两边除以 $\sqrt{k} γ$ 得 $\sqrt{k} \leq \frac{D}{γ}$ ，平方得：

k \leq {(\frac{D}{γ})}^{2}

这就证明了 perceptron 最多犯 ${(\frac{D}{γ})}^{2}$ 次错误。

4. Perceptron 和 Neural Network 的关系

Perceptron 可以看成最简单的神经元：

h_{θ} (x) = g (θ^{T} x)

其中 $g$ 是 step function。现代神经网络把这个想法推广成：

h (x) = σ (W x + b)

区别在于：

Perceptron	Neural Network
step function，不可微	使用 sigmoid / tanh / ReLU / SiLU 等可训练激活函数
只能处理线性分类	多层组合可以表达非线性函数
无反向传播	通过 backpropagation 训练

LOADING