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$ 次，因而最多犯 $9$ 次预测错误。它不需要 IID，也不需要样本最终停止；只要同一个间隔证书一直成立，后续序列就不可能制造第十次更新。

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

失败边界与区分 ​

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

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

对一份有限的线性可分训练集，可以循环扫描并在非正间隔时更新。若始终没有一轮扫描完全无更新，累计更新就会超过定理的有限上界，产生矛盾；因此这个训练过程最终会找到分开所有训练点的权重。这是错误界导出的终止保证，仍不等于测试集上的泛化保证。

若分类器带截距，可将输入扩充为 $\tilde{x}=(x,1)$，把截距作为权重的最后一维，再应用同一证明。此时半径变为至多 $\sqrt{R^2+1}$，间隔也必须相对于扩充后的单位分离向量重新计算，不能沿用原坐标中的数值。