形式陈述
算法
在线性分类器与几何间隔 公理库 线性分类器与几何间隔 Linear classifier · Geometric margin 用仿射超平面分类，并以缩放不变的几何间隔衡量分离余量。 y t ∈ { − 1 , + 1 } 向量空间 公理库 向量空间 Vector space 标量域作用下满足线性公理的加法阿贝尔群。 w 1 = 0 t sign ⟨ w t , x t ⟩
y t ⟨ w t , x t ⟩ ≤ 0 时更新
w t + 1 = w t + y t x t , 否则保持 w t + 1 = w t ( x , 1 )
有限错误证明
在错误界模型 公理库 错误界模型 Mistake-bound model 在可实现在线二分类中，对任意序列控制总预测错误数。 u y t ⟨ u , x t ⟩ ≥ γ > 0 ‖ x t ‖ ≤ R M u
⟨ w , u ⟩ = ∑ t ∈ M y t ⟨ x t , u ⟩ ≥ M γ . 另一方面，每次更新时 y t ⟨ w t , x t ⟩ ≤ 0
‖ w t + 1 ‖ 2 = ‖ w t ‖ 2 + 2 y t ⟨ w t , x t ⟩ + ‖ x t ‖ 2 ≤ ‖ w t ‖ 2 + R 2 , 即 ‖ w ‖ ≤ R M M γ ≤ R M M ≤ ( R / γ ) 2
直觉 二维更新图像
当正样本被分到负侧时，加上 x t y t = − 1 x t w
图片加载失败 误分点驱动分隔线旋转 例子与边界 边界与辨析
不可分数据上基础 Perceptron 可能无限更新；pocket、averaged Perceptron 等是另行定义的变体。这里的“收敛”指可分条件下错误更新次数有限，不代表参数收敛到唯一向量。它既不是最大间隔 SVM，也不是 logistic regression：后两者优化明确的不同目标。更新可看作某些 hinge 型损失的次梯度步，但这个联系不改变算法的在线错误界语义。
若把所有点同时乘以常数，R γ R / γ
推论与应用 上面的证明给出算法本身的有限更新保证，Perceptron 错误界 公理库 Perceptron 错误界 Perceptron mistake bound · Perceptron convergence theorem · Novikoff theorem 在线线性可分序列上，Perceptron 犯错次数至多为输入半径与归一化间隔之比的平方。 在线梯度下降 公理库 在线梯度下降 online gradient descent · OGD 在每轮凸损失揭示后走一个投影次梯度步，并以距离势函数控制 regret。
参考资料
Frank Rosenblatt, The Perceptron Psychological Review 65(6), 1958, pp. 386–408.
Albert B. J. Novikoff, “On Convergence Proofs on Perceptrons,” in Proceedings of the Symposium on the Mathematical Theory of Automata , 1962, pp. 615–622.
