Perceptron 算法

算法 ​

标签取 $y_t\in \{-1,+1\}$，初始化 $w_1=0$。第 $t$ 轮以 $\mathrm{sign}⟨w_t,x_t⟩$ 预测；本文把零 margin 也视为错误，并在

$$y_t⟨w_t,x_t⟩\le 0$$

时更新

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

否则保持 $w_{t+1}=w_t$。若需要截距，可把输入扩展为 $(x,1)$，但其范数界也随之改变。

二维更新图像 ​

当正样本被分到负侧时，加上 $x_t$ 把法向量朝该点旋转；负样本被错分时，$y_t=-1$ 使更新减去 $x_t$。算法只在错误处移动，不需要预先写下概率模型，也不在每轮求解一个完整批目标。

有限错误证明 ​

假设存在单位向量 $u$ 使所有样本满足 $y_t⟨u,x_t⟩\ge \gamma >0$，且 $\Vert x_t\Vert \le R$。若算法已更新 $M$ 次，则沿 $u$ 的投影至少线性增长：

$$⟨w,u⟩=\sum _{t\in \mathcal{M}}{y}_t⟨x_t,u⟩\ge M\gamma .$$

另一方面，每次更新时 $y_t⟨w_t,x_t⟩\le 0$，所以

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

即 $\Vert w\Vert \le R\sqrt{M}$。由 Cauchy–Schwarz，$M\gamma \le R\sqrt{M}$，故 $M\le (R/\gamma {)}^2$。

边界与辨析 ​

不可分数据上基础 Perceptron 可能无限更新；pocket、averaged Perceptron 等是另行定义的变体。这里的“收敛”指可分条件下错误更新次数有限，不代表参数收敛到唯一向量。它既不是最大间隔 SVM，也不是 logistic regression：后两者优化明确的不同目标。更新可看作某些 hinge 型损失的次梯度步，但这个联系不改变算法的在线错误界语义。

参考资料

• Frank Rosenblatt, The Perceptron, Psychological Review, 1958.
• Albert B. J. Novikoff, On Convergence Proofs on Perceptrons, 1962.