3. 感知机——学习算法之原始形式：算法解说

3.1 学习问题

• 给定训练数据集：
  T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) ⋯ , ( x N , y N ) } T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right) \cdots,\left(x_{N}, y_{N}\right)\right\} T={(x1​,y1​),(x2​,y2​)⋯,(xN​,yN​)}
  其中 x i ∈ X ⊆ R n , Y I ∈ Y = { + 1 , − 1 } x_i\in\mathcal{X}\subseteq\mathbb{R}^n,Y_I\in\mathcal{Y}=\{+1,-1\} xi​∈X⊆Rn,YI​∈Y={+1,−1}，$+1$代表的是正类点，$-1$代表的是负类点，$N$为样本数。
• 损失函数：
  $$L(w,b)=-\sum _{x_i\in M}{y}_i\left(w\cdot x_i+b\right)$$
  其中，$M$代表所有误分类点的集合。其中$w\cdot x_i$代表向量的内积运算。
• 模型参数估计：
  $$\underset{w,b}{\mathrm{argmin}}L(w,b)$$
  也就是寻找使损失函数$L$最小的参数$w$和$b$.

【注】参数估计是统计学中的一个重要概念，它指的是通过样本数据来推测总体（整个群体）中某些未知的特征值（比如平均值、方差等）的过程。简单来说，参数估计就是通过已有的数据来推测你关心的某些未知值。

3.2 原始形式：随机梯度下降法

3.2.1 随机梯度下降与批量梯度下降法

我们选取随机梯度下降法进行迭代计算。

• 损失函数：
  $$L(w,b)=-\sum _{x_i\in M}{y}_i\left(w\cdot x_i+b\right)$$
• 梯度（对$L$求偏导）：
  $${\nabla }_{w}L(w,b)=-\sum _{x_i\in M}{y}_i{x}_i;{\nabla }_{b}L(w,b)=-\sum _{x_i\in M}{y}_i$$
• 参数更新：
  • 批量梯度下降法（Batch Gradient Descent）：每次迭代时使用所有误分类点来进行参数更新。
    $$w\leftarrow w+\eta \sum _{x_i\in M}{y}_i{x}_i;b\leftarrow b+\eta \sum _{x_i\in M}{y}_i$$
    其中，$\eta (0<\eta ⩽1)$代表步长。
  • 随机梯度下降法（Stochastic Gradient Descent）：每次随机选取一个误分类点。
    $$w\leftarrow w+\eta y_i{x}_i;b\leftarrow b+\eta y_i$$
    相比较批量梯度下降法，它每一轮迭代的速度都会快一些。这是感知机算法用的选择参数更新的方法。

3.2.2 原始形式：算法

• 输入：训练集
  T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) ⋯ , ( x N , y N ) } T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right) \cdots,\left(x_{N}, y_{N}\right)\right\} T={(x1​,y1​),(x2​,y2​)⋯,(xN​,yN​)}
  其中， x i ∈ X ⊆ R n , Y I ∈ Y = { + 1 , − 1 } x_i\in\mathcal{X}\subseteq\mathbb{R}^n,Y_I\in\mathcal{Y}=\{+1,-1\} xi​∈X⊆Rn,YI​∈Y={+1,−1}，步长$\eta (0<\eta ⩽1)$
• 输出：$w,b$；感知机模型$f(x)=\text{sign}(w\cdot x+b)$
• 算法步骤：
  （1）选取初始值$w_0,b_0$，即下图中蓝色的直线代表初始的分离超平面；
  （2）于训练集中随机选取数据$(x_i,y_i)$，图中没有分类到正确类的点都是误分类点，比如蓝色线为例，有一个点没有在蓝色直线上方，这就是误分类点；
  （3）若$y_i(w\cdot x_i+b)⩽0$，$w\leftarrow w+\eta y_i{x}_i;b\leftarrow b+\eta y_i$；（正类点代入后是正的，负类点代入和，因为符合方程，所以也是正的，只有错误分类点代入后是负的）
  （4）转到（2），直到训练集中没有误分类点。
  
  最后得到一个橙色的线将所有的样本点随机分类。

3.3 例题分析

• 输入：训练集：
  T = { ( x 1 , + 1 ) , ( x 2 , + 1 ) , ( x 3 , − 1 ) } T=\left\{\left(x_{1},+1\right),\left(x_{2},+1\right),\left(x_{3},-1\right)\right\} T={(x1​,+1),(x2​,+1),(x3​,−1)}
  其中， x 1 = { 3 , 3 } T , x 2 = ( 4 , 3 ) T , x 3 = ( 1 , 1 ) T x_1=\{3,3\}^{T},x_2=(4,3)^{T},x_3=(1,1)^{T} x1​={3,3}T,x2​=(4,3)T,x3​=(1,1)T，假设$\eta =1$，也就是训练集中有三个样本，其中$x_1,x_2$是正类点样本，$x_3$是负类点样本。
• 输出：$w,b$；感知机模型$f(x)=\text{sign}(w\cdot x+b)$

• 学习问题：通过使下面的损失函数来求得相应的参数$w,b$.
  $$\underset{w,b}{\mathrm{argmin}}L(w,b)=\underset{w,b}{\mathrm{argmin}}\left[-\sum _{x_i\in M}{y}_i\left(w\cdot x_i+b\right)\right]$$

（1）选取初始值$w_0=(0,0{)}^T,b_0=0$；
（2）对于点$x_1$，有：
$$y_1(w_0\cdot x_1+b_0)=\pm 1\times ((0,0{)}^T\cdot (3,3{)}^T+0)=0$$
- 更新参数，
$$w_1=w_0+\eta y_1{x}_1=(3,3{)}^T,b_1=b_0+\eta y_1=1$$
- 模型：
$$w_1\cdot x+b=3x^{(1)}+3x^{(2)}+1$$

（3）对于点$x_1$，有
$$y_1\left(w_1\cdot x_1+b_1\right)=+1\times \left(3x_1^{(1)}+3x_1^{(2)}+1\right)=19>0$$
所以$x_1$分类正确。
对于点$x_2$，有
$$y_2\left(w_1\cdot x_2+b_1\right)=+1\times \left(3x_2^{(1)}+3x_2^{(2)}+1\right)=22>0$$
所以$x_2$分类正确。
对于点$x_3$，有
$$y_3\left(w_1\cdot x_3+b_1\right)=-1\times \left(3x_3^{(1)}+3x_3^{(2)}+1\right)=-7<0$$
所以$x_3$是误分类点。
- 更新参数，利用误分类点$x_3$进行参数更新。
$$w_2=w_1+\eta y_3{x}_3=(2,2{)}^T,b_2=b_1+\eta y_3=0$$
- 模型，
$$w_2\cdot x+b_2=2x^{(1)}+2x^{(2)}$$

（4）重复以上步骤，直到没有误分类点：

迭代到第7次之后就没有误分类点了。

• 得到参数：
  $$w_7=(1,1{)}^T,b_7=-3$$

• 模型，
  $$w_7\cdot x+b_7=x^{(1)}+x^{(2)}-3$$

• 结果：

  • 分离超平面：
    $$x^{(1)}+x^{(2)}-3=0$$
  • 感知机模型：
    $$f(x)=\mathrm{sign}\left(x^{(1)}+x^{(2)}-3\right)$$

• 注

  • 若误分类点依次取$x_1,x_3,x_3,x_3,x_1,x_3,x_3$，可以得到分离超平面。
    $$x^{(1)}+x^{(2)}-3=0$$
  • 若误分类点依次取$x_1,x_3,x_3,x_3,x_2,x_3,x_3,x_3,x_1,x_3,x_3$，可以得到分离超平面：
    $$2x^{(1)}+x^{(2)}-5=0$$

【注】采用不同的误分类点顺序，所得到的解是不同的，随机选取的误分类点导致结果也具有一定的随机性。