感知机(Perceptron)的模型非常简单，就是学习如下一个线性分类器\begin{align*} f(\boldsymbol{x}) = sign(\boldsymbol{w}^\top \boldsymbol{x})\end{align*}为了表述方便，这里省略了截距$b$。

　　若某个样本$(\boldsymbol{x}_0, y_0)$被分错了，也即$y_0 \boldsymbol{w}^\top \boldsymbol{x}_0 < 0$，其更新策略为\begin{align*} \boldsymbol{w}_{new} = \boldsymbol{w} + y_0 \boldsymbol{x}_0 \end{align*}这是基于\begin{align*} y_0 \boldsymbol{w}_{new}^\top \boldsymbol{x}_0 = y_0 \boldsymbol{w}^\top \boldsymbol{x}_0 + \boldsymbol{x}_0^\top \boldsymbol{x}_0 > y_0 \boldsymbol{w}^\top \boldsymbol{x}_0 \end{align*}可以看出$\boldsymbol{w}_{new}$在样本$(\boldsymbol{x}_0, y_0)$上的预测值比原来要有所改善，即使最终符号还是错的，但至少值比原来更接近$0$。

　　关于感知机的收敛性有如下结论：若数据集线性可分，也即存在$\boldsymbol{w}_*$满足对于任意样本$(\boldsymbol{x}, y)$有$y \boldsymbol{w}_*^\top \boldsymbol{x} \geq 0$，那么感知机算法会在有限步内中止。

　　设$R = \max_{\boldsymbol{x}} \|\boldsymbol{x}\|$，$\rho = \min_{(\boldsymbol{x},y)} y \boldsymbol{w}_*^\top \boldsymbol{x}$，由线性可分假设知$\rho \geq 0$。一方面有\begin{align*} \boldsymbol{w}_*^\top \boldsymbol{w}_{new} = \boldsymbol{w}_*^\top (\boldsymbol{w} + y_0 \boldsymbol{x}_0) = \boldsymbol{w}_*^\top \boldsymbol{w} + y_0 \boldsymbol{w}_*^\top \boldsymbol{x}_0 \geq \boldsymbol{w}_*^\top \boldsymbol{w} + \rho \end{align*}也即每更新一次$\boldsymbol{w}$，其与$\boldsymbol{w}_*$的内积至少增加$\rho$，故递推可知$\boldsymbol{w}_*^\top \boldsymbol{w}_T \geq T \rho$。另一方面有\begin{align*} \|\boldsymbol{w}_{new}\|^2 = \|\boldsymbol{w} + y_0 \boldsymbol{x}_0\|^2 = \|\boldsymbol{w}\|^2 + 2 y_0 \boldsymbol{w}^\top \boldsymbol{x}_0 + \|\boldsymbol{x}_0\|^2 < \|\boldsymbol{w}\|^2 + \|\boldsymbol{x}_0\|^2 \leq \|\boldsymbol{w}\|^2 + R^2 \end{align*}其中第一个小于号是因为$\boldsymbol{w}$在样本$(\boldsymbol{x}_0, y_0)$上出错了，递推可知$\|\boldsymbol{w}_T\| \leq T R^2$。不妨设$\boldsymbol{w}_*$是单位化向量，也即$\|\boldsymbol{w}_*\| = 1$，于是\begin{align*} \cos \langle \boldsymbol{w}_*, \boldsymbol{w}_T \rangle = \frac{\boldsymbol{w}_*^\top \boldsymbol{w}_T}{\|\boldsymbol{w}_*\| \|\boldsymbol{w}_T\|} \geq \frac{T \rho}{\sqrt{T} R} = \sqrt{T} \frac{\rho}{R} \end{align*}又$\cos \langle \boldsymbol{w}_*, \boldsymbol{w}_T \rangle \leq 1$，故
\begin{align*} T \leq \frac{R^2}{\rho^2} \end{align*}也即最多更新$R^2/\rho^2$就可得到一个无错的线性分类器。

　　实际操作时，我们不可能事先知道一个数据集是否线性可分，因此上面的分析也仅仅是一个理想化的分析。如果数据集并不是线性可分的，那么最自然的想法应该是最小化错误率，也即所谓的$0-1$损失：\begin{align*} \min_{\boldsymbol{w}} \ \ \ \sum_{m=1}^M I_{y_m \neq sign(\boldsymbol{w}^\top \boldsymbol{x}_m)} \end{align*}可惜这个问题是NP-hard的，需要引入其他替代损失如平方损失、hinge损失等等才能求解。

感知机