Perceptron 算法

二维更新图像 ​

当正样本被分到负侧时，加上 $x_t$ 把法向量朝该点旋转；负样本被错分时，$y_t=-1$ 使更新减去 $x_t$。算法在误分类或零间隔时移动，不需要预先写下概率模型，也不在每轮求解一个完整批目标。证明中的两条增长规律因此有清楚图像：每次更新都让 $w$ 朝真实分隔方向前进，同时其长度只能以平方根速度累积。

从 $w_1=(0,0)$ 开始，依次输入 $((1,0),+1)$、$((1,1),-1)$、$((0,1),-1)$。第一步分数为 $0$，预测 $+1$ 虽然正确，仍按零间隔规则更新到 $w_2=(1,0)$；第二步分数为 $1$，错预测为 $+1$，更新到 $w_3=(0,-1)$；第三步分数为 $-1$，预测正确且标签乘分数为 $1$，所以 $w_4=(0,-1)$。这三步共有两次更新、一次预测错误。

边界与辨析 ​

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

若把所有点同时乘以常数，$R$ 与 $\gamma$ 会同比变化，比例 $R/\gamma$ 保持不变；若只重缩放某个坐标，几何却会改变。截距增广、范数选择和特征尺度都必须与 margin 假设一起报告，否则同一个错误界公式会被赋予不同含义。

上面的证明给出算法本身的有限更新保证，Perceptron 错误界理路Perceptron 错误界Perceptron mistake bound · Perceptron convergence theorem · Novikoff theorem在线线性可分序列上，Perceptron 犯错次数至多为输入半径与归一化间隔之比的平方。进一步把其假设、常数和失败情形整理为独立定理。若关心 IID 样本上的预测风险，可继续使用间隔泛化界；若损失改为一般凸函数并加入投影，更新思路则进入在线梯度下降理路在线梯度下降online gradient descent · OGD在每轮凸损失揭示后走一个投影次梯度步，并以距离势函数控制 regret。。这些后继共享一阶更新图像，却使用不同的概率与比较器语义。