Perceptron 错误界

定理 ​

给定任意顺序的序列 $(x_t,y_t)$，其中 $x_t\in {\mathbb{R}}^d$、$y_t\in \{-1,+1\}$，且 $\Vert x_t{\Vert }_2\le R$。假设存在单位向量 $u$ 与 $\gamma >0$，使每轮

$$y_t⟨u,x_t⟩\ge \gamma .$$

Perceptron 从 $w_1=0$ 开始，以 $\mathrm{sign}⟨w_t,x_t⟩$ 预测；犯错（包括零间隔）时更新

$$w_{t+1}=w_t+y_t{x}_t,$$

否则不变。则任意长序列上的总犯错次数 $M$ 满足

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

界与轮数 $T$ 和样本出现顺序无关，但分离向量必须同时分开整条实际序列。

两个量夹住犯错次数 ​

只在犯错轮编号 $t_1,\dots ,t_M$ 上看权重。每次更新沿正确分离方向至少前进 $\gamma$：

$$⟨w_{M+1},u⟩=\sum _{j=1}^M{y}_{t_j}⟨x_{t_j},u⟩\ge M\gamma .$$

另一方面，犯错意味着 $y_t⟨w_t,x_t⟩\le 0$，所以

$$\Vert w_{t+1}{\Vert }_2^2=\Vert w_t{\Vert }_2^2+2y_t⟨w_t,x_t⟩+\Vert x_t{\Vert }_2^2\le \Vert w_t{\Vert }_2^2+R^2.$$

迭代得 $\Vert w_{M+1}{\Vert }_2\le R\sqrt{M}$。最后由 Cauchy–Schwarz 不等式公理库Cauchy–Schwarz 不等式Cauchy–Schwarz inequality · 柯西–施瓦茨不等式内积的绝对值不超过两向量范数之积，且等号精确刻画线性相关。，

$$M\gamma \le ⟨w_{M+1},u⟩\le \Vert w_{M+1}{\Vert }_2\Vert u{\Vert }_2\le R\sqrt{M},$$

若 $M>0$，约去 $\sqrt{M}$ 即得结论。证明中的“进展线性增长、范数只按平方根增长”是整个错误界的概念图像。

一个顺序无关的具体例子 ​

取 $u=(1,0)$，数据满足正例第一坐标至少 $1$、负例第一坐标至多 $-1$，且所有点范数不超过 $3$。于是 $\gamma =1,R=3$，不论对手怎样重排或重复这些点，Perceptron 最多犯 $9$ 次错。它不需要 IID，也不需要样本最终停止；只要同一个间隔证书一直成立，后续序列就不可能制造第十次错误。

对同一批线性可分点，把所有 $x$ 同时乘以常数 $c$ 会把 $R$ 与 $\gamma$ 都乘以 $c$，比值不变。这说明真正控制界的是归一化几何，而不是坐标单位。不同数据集即使线性分类器的 VC 维相同，间隔不同也可有完全不同的实际错误界。

失败边界与区分 ​

若 $\gamma =0$ 或序列不可由同一超平面分开，证明的进展下界消失，Perceptron 可能无限循环。存在少量噪声时可改用与最佳分离向量的 hinge loss 相联系的软间隔错误界，但那是额外定理。

$M$ 是在线协议中的累计预测错误数，不是 IID 测试风险，也不是训练结束后分类器的高概率泛化误差。要从随机顺序上的在线保证得到批风险，需要 Online-to-Batch 转换公理库Online-to-Batch 转换Online-to-batch conversion · 在线到批学习转换利用当前在线预测器只依赖过去样本的独立性，把平均在线遗憾转为批学习的期望超额风险。，并明确输出随机迭代、平均预测或投票的方式。

参考资料

• Albert Novikoff, “On Convergence Proofs on Perceptrons,” 1962.
• Nicolò Cesa-Bianchi and Gábor Lugosi, Prediction, Learning, and Games.