Perceptron 错误界

每次犯错都会把权重沿 $y_t{x}_t$ 推一步。统一分离向量 $u$ 看到的投影至少增加 $\gamma$，所以犯错 $M$ 次后积累出 $M\gamma$ 的定向进展；而错误条件让交叉项非正，权重平方范数每次至多增加 $R^2$，总长度只有 $R\sqrt{M}$。

同一个向量不可能既在 $u$ 方向投影至少 $M\gamma$，又整体短于 $R\sqrt{M}$，除非 $M\le (R/\gamma {)}^2$。界的核心图像正是“进展线性增长、范数只按平方根增长”，而不是数据最终会被某次迭代静态拟合。

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

取 $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 · 在线到批学习转换利用当前在线预测器只依赖过去样本的独立性，把平均在线遗憾转为批学习的期望超额风险。，并明确输出随机迭代、平均预测或投票的方式。

错误界与序列长度无关，因此在线对手可以任意重排、重复已见点，只要统一的半径与间隔证书始终成立。同步缩放全部输入会同时缩放 $R$ 与 $\gamma$，比值不变，说明控制量是归一化几何而非坐标单位。

在带噪或不可分数据上，硬间隔进展失效；常见扩展把错误数与某个比较向量的 hinge loss 共同控制。该扩展需要重新保留松弛项，不能把本页的 $M\le (R/\gamma {)}^2$ 直接套到只有大多数样本可分的序列。