如图所示的训练数据集，其正样本是${\mathbf{x}}_1=(3,3{)}^{\top }$，${\mathbf{x}}_2=(4,3{)}^{\top }$，负样本是${\mathbf{x}}_3=(1,1{)}^{\top }$，使用感知器算法的随机梯度法求判别函数$f(\mathbf{x})=\text{sgn}(\mathbf{w}\cdot \mathbf{x}+b)$。

解答
构建最优化问题：

$$\underset{\mathbf{w},b}{\min }L(\mathbf{w},b)=-\sum _{{\mathbf{x}}_i\in {\mathcal{X}}_k}{y}_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)$$
求解$\mathbf{w}$，$b$。$\alpha =1$。

(1) 取初值${\mathbf{w}}_0=0$，$b_0=0$；

(2) 对${\mathbf{x}}_1=(3,3{)}^{\top }$，$y_1({\mathbf{w}}_0\cdot {\mathbf{x}}_1+b_0)=0$，未能被正确分类，更新$\mathbf{w}$，$b$：

$${\mathbf{w}}_1={\mathbf{w}}_0+y_1{\mathbf{x}}_1=(3,3{)}^{\top }{b}_1=b_0+y_1=1$$

得到线性模型：

$${\mathbf{w}}_1\cdot \mathbf{x}+b_1=3x^{(1)}+3x^{(2)}+1$$

(3) 对${\mathbf{x}}_1$，${\mathbf{x}}_2$，显然，$y_i({\mathbf{w}}_1\cdot {\mathbf{x}}_i+b_1)>0$，被正确分类，不修改$\mathbf{w}$，$b$；对${\mathbf{x}}_3=(1,1{)}^{\top }$，$y_3({\mathbf{w}}_1\cdot {\mathbf{x}}_3+b_1)<0$，被错分类，更新$\mathbf{w}$，$b$：

$${\mathbf{w}}_2={\mathbf{w}}_1+y_3{\mathbf{x}}_3=(2,2{)}^{\top }{b}_2=b_1+y_3=0$$

得到线性模型：

$${\mathbf{w}}_2\cdot \mathbf{x}+b_2=2x^{(1)}+2x^{(2)}$$
如此继续下去，直到

$${\mathbf{w}}_7=(1,1{)}^{\top },b_7=-3$$

$${\mathbf{w}}_7\cdot \mathbf{x}+b_7=x^{(1)}+x^{(2)}-3$$

对所有数据点$y_i({\mathbf{w}}_7\cdot {\mathbf{x}}_i+b_7)>0$，没有错分类点，损失函数达到极小。

判别函数为$f(\mathbf{x})=\text{sgn}(x^{(1)}+x^{(2)}-3)$。

迭代过程见表。

表 求解的迭代过程

这是在计算中错分类点先后取${\mathbf{x}}_1,{\mathbf{x}}_3,{\mathbf{x}}_3,{\mathbf{x}}_3,{\mathbf{x}}_1,{\mathbf{x}}_3,{\mathbf{x}}_3$ 得到的分离超平面和判别函数。如果在计算中错分类点依次取${\mathbf{x}}_1,{\mathbf{x}}_3,{\mathbf{x}}_3,{\mathbf{x}}_3,{\mathbf{x}}_2,{\mathbf{x}}_3,{\mathbf{x}}_3,{\mathbf{x}}_1,{\mathbf{x}}_3,{\mathbf{x}}_3$，那么得到的分离超平面是$2x^{(1)}+x^{(2)}-5=0$。

可见，感知器算法由于采用不同的初值或选取不同的错分类点，解可以不同。