详解感知机模型

感知机(Perceptron)

​ 感知机于1957年由Rosenblatt提出，是神经网络与支持向量机算法的基础，事实上，感知机可以看做是单层神经网络，也是支持向量机的基础。感知机是二类分类的线性分类模型，属于监督学习 ，输入为特征向量，输出为实例类别，通常取 + 1 +1 +1和 − 1 -1 −1二值。感知机通过学习获得一个分离超平面，用以划分训练数据。

1. 感知机模型

• 定义

  假设输入空间(特征空间)是 χ ⊆ R n \chi \subseteq R^n χ⊆Rn，输出空间是 Y = { + 1 , − 1 } Y=\{+1,-1\} Y={+1,−1}.输入 x ∈ χ x\in \chi x∈χ表示实例的特征向量，对应于输入空间的点；输出 y ∈ Y y\in Y y∈Y 表示实例的类别，由输入空间到输出空间的如下函数 f ( x ) = s i g n ( w ⋅ x + b ) f(x)=sign(w·x+b) f(x)=sign(w⋅x+b) 称为感知机。其中 w w w和 b b b为感知机模型参数， w ∈ R n w\in R^n w∈Rn叫做权值或权值向量， b ∈ R b\in R b∈R叫做偏置 ( b i a s ) (bias) (bias) ， s i g n sign sign是符号函数 s i g n ( x ) = { + 1 , x ≥ 0 − 1 , x < 0 sign(x) = \begin{cases} +1,\quad x\geq0 \\-1 ,\quad x<0 \end{cases} sign(x)={+1,x≥0−1,x<0​

• 几何意义

  • 感知机是一种线性分类模型，属于判别模型，感知机模型的假设空间是定义在特征空间中的所有线性分类模型或线性分类器，即函数集合 { f ∣ f ( x ) = w ⋅ x + b } \{f|f(x)=w·x+b\} {f∣f(x)=w⋅x+b}

  • 线性方程 w ⋅ x + b = 0 w·x+b=0 w⋅x+b=0 对应于特征空间 R n R^n Rn中的一个超平面 S S S，其中 w w w是超平面的法向量， b b b是超平面的截距，这个超平面将特征空间划分为两个部分，位于两部分的点(特征向量)分别被分为正负两类。因此超平 S S S称为分离超平面，如下图所示

  

  感知机学习，通过训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\} T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)} 其中, x i ∈ χ = R n ， y i ∈ Y = { + 1 , − 1 } ， i = 1 , 2 , ⋯   , N x_i\in \chi=R^n，y_i\in Y=\{+1,-1\}，i=1,2,\cdots,N xi​∈χ=Rn，yi​∈Y={+1,−1}，i=1,2,⋯,N得到感知机模型，即求得模型参数 w , b w,b w,b，从而实现对新输入实例的类型输出

2. 感知机学习策略

• 数据集的线性可分性

  给定一个数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } ， T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}， T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}， 其中, x i ∈ χ = R n ， y i ∈ Y = { + 1 , − 1 } ， i = 1 , 2 , ⋯   , N x_i\in \chi=R^n，y_i\in Y=\{+1,-1\}，i=1,2,\cdots,N xi​∈χ=Rn，yi​∈Y={+1,−1}，i=1,2,⋯,N 如果存在某个超平面 S S S

  w ⋅ x + b = 0 w·x+b=0 w⋅x+b=0 能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，即对所有 y i = + 1 y_i=+1 yi​=+1的实例 i i i，有 w i ⋅ x i + b ≥ 0 w_i·x_i+b\geq0 wi​⋅xi​+b≥0，对所有 y i = − 1 y_i=-1 yi​=−1的实例 i i i，有 w i ⋅ x i + b < 0 w_i·x_i+b<0 wi​⋅xi​+b<0，则称数据集 T T T为线性可分数据集，否则数据集 T T T线性不可分。 很显然，感知器只能处理数据集线性可分的情况

• 感知机损失函数

  假设数据集是线性可分的，感知机学习的目的是将数据集的正负实例完全正确的划分开来，因此其损失函数很容易想到使用误分类点的总数，但是这样的损失函数不是 w , b w,b w,b的连续可导函数，不方便优化，因此我们选择误分类点到超平面的总距离，作为损失函数，为此，首先写出输入空间 R n R^n Rn中任一点 x 0 x_0 x0​到超平面 S S S的距离

  1 ∥ w ∥ ∣ w ⋅ x 0 + b ∣ ， \frac{1}{\begin{Vmatrix}w\end{Vmatrix}}|w·x_0+b|， ∥∥​w​∥∥​1​∣w⋅x0​+b∣，

  其次，对于误分类的数据 ( x i , y i ) (x_i,y_i) (xi​,yi​)来说，有 − y i ( w ⋅ x i + b ) > 0 -y_i(w·x_i+b) >0 −yi​(w⋅xi​+b)>0成立，因为当 w ⋅ x i + b > 0 w·x_i+b>0 w⋅xi​+b>0时，对于误分类点有 y i = − 1 y_i=-1 yi​=−1，而当 w ⋅ x i + b < 0 w·x_i+b<0 w⋅xi​+b<0时， y i = + 1 y_i=+1 yi​=+1，因此误分类点 x i x_i xi​到超平面 S S S的距离是 − 1 ∥ w ∥ y i ( w ⋅ x i + b ) ， -\frac{1}{\begin{Vmatrix}w\end{Vmatrix}}y_i(w·x_i+b)， −∥∥​w​∥∥​1​yi​(w⋅xi​+b)， 这一步成功将距离中的绝对值去掉，方便后续求导计算。这样，假设超平面 S S S的误分类点集合为 M M M，那么所有误分类点到超平面 S S S的总距离为 − 1 ∥ w ∥ ∑ x i ∈ M y i ( w ⋅ x i + b ) ， -\frac{1}{\begin{Vmatrix}w\end{Vmatrix}}\sum\limits_{x_i\in M}y_i(w·x_i+b)， −∥∥​w​∥∥​1​xi​∈M∑​yi​(w⋅xi​+b)，不考虑 1 ∥ w ∥ \frac{1}{{\begin{Vmatrix}w\end{Vmatrix}}} ∥w​∥1​ ，就得到了感知机学习的损失函数：

  给定一个数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } ， T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}， T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}， 其中, x i ∈ χ = R n ， y i ∈ Y = { + 1 , − 1 } ， i = 1 , 2 , ⋯   , N x_i\in \chi=R^n，y_i\in Y=\{+1,-1\}，i=1,2,\cdots,N xi​∈χ=Rn，yi​∈Y={+1,−1}，i=1,2,⋯,N ，感知机 s i g n ( w ⋅ x + b ) sign(w·x+b) sign(w⋅x+b)学习的损失函数定义为 L ( w , b ) = − ∑ x i ∈ M y i ( w ⋅ x i + b ) ， L(w,b)=-\sum\limits_{x_i\in M}y_i(w·x_i+b)， L(w,b)=−xi​∈M∑​yi​(w⋅xi​+b)，其中 M M M是误分类点的集合，这个损失函数就是感知机学习的经验风险函数。

  ​ 显然，损失函数 L ( w , b ) L(w,b) L(w,b)是非负的，如果没有误分类点，损失函数值是0，而且误分类点越少，误分类点离超平面越近，损失函数值就越小。一个特定的样本点的损失函数：在误分类时是参数 w , b w,b w,b的线性函数，在正确分类时是0，因此给定训练数据集 T T T，损失函数 L ( w , b ) L(w,b) L(w,b)是 w , b w,b w,b的连续可导函数

• 在确定损失函数时，为什么可以不考虑 1 ∥ w ∥ \frac{1}{{\begin{Vmatrix}w\end{Vmatrix}}} ∥w​∥1​ ，目前我的解释如下：

  • 解释1，感知机要求数据要线性可分，且损失函数是误分类点驱动的，即只有有误分类点的情况下，损失函数才不为零，因此，我们只需要知道有没有误分类点即 − y i ( w ⋅ x i + b ) -y_i(w·x_i+b) −yi​(w⋅xi​+b)是否大于零即可，因此损失函数可以直接简化成 L ( w , b ) = − ∑ x i ∈ M y i ( w ⋅ x i + b ) L(w,b)=-\sum\limits_{x_i\in M}y_i(w·x_i+b) L(w,b)=−xi​∈M∑​yi​(w⋅xi​+b)

  • 解释2，我们虽然用点到平面的距离来引出损失函数，但是对于感知机来说，我们真正关心的是误分类点，我们并不关心这个距离的大小是多少，因此可以不考虑 1 ∥ w ∥ \frac{1}{{\begin{Vmatrix}w\end{Vmatrix}}} ∥w​∥1​

  • 解释3，我们知道，平面 w ⋅ x + b = 0 w·x+b=0 w⋅x+b=0和平面 a ( w ⋅ x + b ) = 0 ， a ≠ 0 a(w·x+b)=0，a\neq0 a(w⋅x+b)=0，a​=0表示同一个平面，即平面 w ⋅ x + b = 0 w·x+b=0 w⋅x+b=0和平面 1 ∥ w ∥ ( w ⋅ x + b ) = 0 ， ∥ w ∥ ≠ 0 \frac{1}{{\begin{Vmatrix}w\end{Vmatrix}}}(w·x+b)=0，\begin{Vmatrix}w\end{Vmatrix} \neq0 ∥w​∥1​(w⋅x+b)=0，∥∥​w​∥∥​​=0 表示同一平面，因此我们总是可以对平面参数进行缩放，使得 ∥ w ∥ = 1 \begin{Vmatrix}w\end{Vmatrix}=1 ∥∥​w​∥∥​=1 ，也能很直接的得到 L ( w , b ) = − ∑ x i ∈ M y i ( w ⋅ x i + b ) L(w,b)=-\sum\limits_{x_i\in M}y_i(w·x_i+b) L(w,b)=−xi​∈M∑​yi​(w⋅xi​+b)

3. 感知机学习算法

• 感知机学习算法是对以下最优化问题的解法

  给定一个数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } ， T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}， T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}， 其中, x i ∈ χ = R n ， y i ∈ Y = { + 1 , − 1 } ， i = 1 , 2 , ⋯   , N x_i\in \chi=R^n，y_i\in Y=\{+1,-1\}，i=1,2,\cdots,N xi​∈χ=Rn，yi​∈Y={+1,−1}，i=1,2,⋯,N ，求参数 w , b w,b w,b，使其为以下损失函数极小化问题的解 min ⁡ w , b L ( w , b ) = − ∑ x i ∈ M y i ( w ⋅ x i + b ) \min\limits_{w,b}L(w,b)=-\sum\limits_{x_i\in M}y_i(w·x_i+b) w,bmin​L(w,b)=−xi​∈M∑​yi​(w⋅xi​+b)，其中 M M M是误分类点的集合。

• 梯度下降法求解 w , b w,b w,b

  损失函数 L ( w , b ) L(w,b) L(w,b)的梯度为

  ∇ w L ( w , b ) = − ∑ x i ∈ M y i x i \nabla_wL(w,b) = -\sum\limits_{x_i\in M}y_ix_i ∇w​L(w,b)=−xi​∈M∑​yi​xi​

  ∇ b L ( w , b ) = − ∑ x i ∈ M y i \nabla_bL(w,b) = -\sum\limits_{x_i\in M}y_i ∇b​L(w,b)=−xi​∈M∑​yi​

  随机选取一个误分类点 ( x i , y i ) (x_i,y_i) (xi​,yi​)，对 w , b w,b w,b进行更新：

  w ← w + η y i x i w \leftarrow w+\eta y_ix_i w←w+ηyi​xi​

  b ← b + η y i b \leftarrow b +\eta y_i b←b+ηyi​

  式中 η ( 0 < η ≤ 1 ) \eta(0<\eta \leq1) η(0<η≤1)是步长，在统计学习中又称为学习率，这样通过迭代可以期待损失函数 L ( w , b ) L(w,b) L(w,b)不断减小，直到为0，综上所述，得到以下算法：

• 感知机学习算法的原始形式

  输入：训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } ， T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}， T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}， 其中, x i ∈ χ = R n ， y i ∈ Y = { + 1 , − 1 } ， i = 1 , 2 , ⋯   , N x_i\in \chi=R^n，y_i\in Y=\{+1,-1\}，i=1,2,\cdots,N xi​∈χ=Rn，yi​∈Y={+1,−1}，i=1,2,⋯,N ，学习率 η ( 0 < η ≤ 1 ) \eta(0<\eta \leq1) η(0<η≤1)

  输出： w , b w,b w,b；感知机模型 f ( x ) = s i g n ( w ⋅ x + b ) f(x)=sign(w·x+b) f(x)=sign(w⋅x+b)

  ( 1 ) (1) (1) 选取初始值 w 0 , b 0 w_0,b_0 w0​,b0​

  ( 2 ) (2) (2) 在训练集中选取数据 ( x i , y i ) (x_i,y_i) (xi​,yi​)

  ( 3 ) (3) (3) 如果 y i ( w ⋅ x i + b ) ≤ 0 y_i(w·x_i+b)\leq0 yi​(w⋅xi​+b)≤0

  w ← w + η y i x i w \leftarrow w+\eta y_ix_i w←w+ηyi​xi​

  b ← b + η y i b \leftarrow b +\eta y_i b←b+ηyi​

  ( 4 ) (4) (4) 转至 ( 2 ) (2) (2)，直至训练集中没有误分类点

• 算法几何解释

  当一个实例点被误分类时，即位于分离超平面的错误一侧是，则调整 w , b w,b w,b的值，使得超平面往误分类点的一侧移动，以减少该误分类点与超平面间的距离，直至超平面越过该误分类点使其被正确分类。

  为了方便理解，我们将模型方程中的 b b b也写进权值向量 w w w中，即 w ∗ = ( w , b ) w^* = (w,b) w∗=(w,b)，此时 x ∗ = ( x , 1 ) x^*=(x,1) x∗=(x,1) 模型函数可表示为

  f ( x ) = s i g n ( w ⋅ x + b ) = s i g n ( w ∗ ⋅ x ∗ ) \begin{aligned} f(x)&=sign(w·x+b)\\&=sign(w^*·x^*) \end{aligned} f(x)​=sign(w⋅x+b)=sign(w∗⋅x∗)​

  对于误分类点，需要调整参数 w ∗ w^* w∗，使得超平面往误分类点方向移动，直至超平面越过该误分类点使其被正确分类

如上图所示，

• 对于正实例被误分类的点，此时 y i ∗ = + 1 y_i^*=+1 yi∗​=+1，但 w t ∗ ⋅ x i ∗ < 0 w_t^*·x_i^*<0 wt∗​⋅xi∗​<0，此时我们可以通过 w t ∗ + η x i ∗ w_t^* + \eta x_i^* wt∗​+ηxi∗​的方式更新 w t ∗ w_t^* wt∗​即 w t + 1 ∗ = w t ∗ + η x i ∗ w_{t+1}^* = w_t^*+\eta x_i^* wt+1∗​=wt∗​+ηxi∗​ ，通过这样的更新，超平面由 S t S_t St​变化至 S t + 1 S_{t+1} St+1​ ，很明显， S t + 1 S_{t+1} St+1​ 距离点 x i ∗ x_i^* xi∗​ 更近了，经过多次更新，即可使超平面越过点 x i ∗ x_i^* xi∗​，使其被正确分类
• 对于负实例被误分类点，即此时 y i ∗ = − 1 y_i^*=-1 yi∗​=−1，但 w t ∗ ⋅ x i ∗ ≥ 0 w_t^*·x_i^*\geq0 wt∗​⋅xi∗​≥0，此时我们可以通过 w t ∗ − η x i ∗ w_t^* - \eta x_i^* wt∗​−ηxi∗​的方式更新 w t ∗ w_t^* wt∗​即 w t + 1 ∗ = w t ∗ − η x i ∗ w_{t+1}^* = w_t^*-\eta x_i^* wt+1∗​=wt∗​−ηxi∗​ ，通过这样的更新，超平面由 S t S_t St​变化至 S t + 1 S_{t+1} St+1​ ，很明显， S t + 1 S_{t+1} St+1​ 距离点 x i ∗ x_i^* xi∗​ 更近了，经过多次更新，即可使超平面越过点 x i ∗ x_i^* xi∗​，使其被正确分类

结合图形分析，我们发现，在误分类点对 w t ∗ w_t^* wt∗​ 进行更新时，有 w t + 1 ∗ = { w t ∗ + η x i ∗ , y i ∗ = + 1 w t ∗ − η x i ∗ , y i ∗ = − 1 w_{t+1}^* = \begin{cases} w_t^*+\eta x_i^* ,\quad y_i^* = +1 \\ w_t^*-\eta x_i^*,\quad y_i^* = -1 \end{cases} wt+1∗​={wt∗​+ηxi∗​,yi∗​=+1wt∗​−ηxi∗​,yi∗​=−1​

我们可以把上式合并，得到 w t + 1 ∗ = w t ∗ + η y t ∗ x i ∗ w_{t+1}^* = w_t^*+\eta y_t^*x_i^* wt+1∗​=wt∗​+ηyt∗​xi∗​ 即 ( w t + 1 , b t + 1 ) = ( w t , b t ) + η y i ∗ ( x i , 1 ) \begin{aligned} (w_{t+1},b_{t+1}) = (w_t,b_t)+\eta y_i*(x_i,1) \end{aligned} (wt+1​,bt+1​)=(wt​,bt​)+ηyi​∗(xi​,1)​ 从这里也能看出来 w t + 1 = w t + η y i x i w_{t+1} = w_t+\eta y_ix_i wt+1​=wt​+ηyi​xi​

b t + 1 = b t + η y i b_{t+1} = b_t+\eta y_i bt+1​=bt​+ηyi​

4. 算法收敛性

• 线性可分数据集感知机学习算法原始形式收敛，即经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面以及感知机模型，为了便于叙述和推导，将偏置 b b b并入权重向量 w w w ，记做 w ^ = ( w T , b ) T \hat{w}=(w^T,b)^T w^=(wT,b)T，同样也将输入向量加以扩充，加进常数 1 1 1，记做 x ^ = ( x T , 1 ) T \hat{x}=(x^T,1)^T x^=(xT,1)T，这样, x ^ ∈ R n + 1 , w ^ ∈ R n + 1 \hat{x}\in R^{n+1},\hat{w}\in R^{n+1} x^∈Rn+1,w^∈Rn+1，显然， w ^ ⋅ x ^ = w ⋅ x + b \hat{w}·\hat{x} = w·x+b w^⋅x^=w⋅x+b

• N o v i k o f f Novikoff Novikoff定理

  设训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } ， T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}， T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}，是线性可分的， 其中, x i ∈ χ = R n ， y i ∈ Y = { + 1 , − 1 } ， i = 1 , 2 , ⋯   , N x_i\in \chi=R^n，y_i\in Y=\{+1,-1\}，i=1,2,\cdots,N xi​∈χ=Rn，yi​∈Y={+1,−1}，i=1,2,⋯,N ，则

  (1) 存在满足条件 ∥ w ^ o p t ∥ = 1 {\begin{Vmatrix}\hat{w}_{opt}\end{Vmatrix}}=1 ∥∥​w^opt​​∥∥​=1的超平面 w ^ o p t ⋅ x ^ = w o p t ⋅ x + b o p t = 0 \hat{w}_{opt}·\hat{x} = w_{opt}·x+b_{opt}=0 w^opt​⋅x^=wopt​⋅x+bopt​=0将训练数据集完全正确分开；且存在 γ > 0 , \gamma>0, γ>0, 对所有 i = 1 , 2 , ⋯   , N i=1,2,\cdots,N i=1,2,⋯,N y i ( w ^ o p t ⋅ x i ^ ) = y i ( w o p t ⋅ x i + b o p t ) ≥ γ y_i(\hat{w}_{opt}·\hat{x_i})=y_i(w_{opt}·x_i+b_{opt})\geq\gamma yi​(w^opt​⋅xi​^​)=yi​(wopt​⋅xi​+bopt​)≥γ

  (2) 令 R = max ⁡ 1 ≤ i ≤ N ∥ x i ^ ∥ R=\max\limits_{1\leq i \leq N}{\begin{Vmatrix}\hat{x_i}\end{Vmatrix}} R=1≤i≤Nmax​∥∥​xi​^​​∥∥​ ，则感知机算法在训练数据集上的误分类次数 k k k满足不等式 k ≤ ( R γ ) 2 k \leq \big(\frac{R}{\gamma}\big)^2 k≤(γR​)2

  证明

  (1) 由于训练数据集是线性可分的，因此，存在超平面可以将训练数据集完全正确分开，取此超平面为 w ^ o p t ⋅ x ^ = w o p t ⋅ x + b o p t = 0 \hat{w}_{opt}·\hat{x} = w_{opt}·x+b_{opt}=0 w^opt​⋅x^=wopt​⋅x+bopt​=0， 使 ∥ w ^ o p t ∥ = 1 {\begin{Vmatrix}\hat{w}_{opt}\end{Vmatrix}}=1 ∥∥​w^opt​​∥∥​=1. 由于对于有限的 i = 1 , 2 , ⋯   , N i=1,2,\cdots,N i=1,2,⋯,N，均有 y i ( w ^ o p t ⋅ x i ^ ) = y i ( w o p t ⋅ x i + b o p t ) ≥ 0 y_i(\hat{w}_{opt}·\hat{x_i})=y_i(w_{opt}·x_i+b_{opt})\geq0 yi​(w^opt​⋅xi​^​)=yi​(wopt​⋅xi​+bopt​)≥0

  所以存在 γ = min ⁡ i { y i ( w o p t ⋅ x i + b o p t ) } \gamma = \min\limits_{i}\{y_i(w_{opt}·x_i+b_{opt})\} γ=imin​{yi​(wopt​⋅xi​+bopt​)} 使得

  y i ( w ^ o p t ⋅ x i ^ ) = y i ( w o p t ⋅ x i + b o p t ) ≥ γ [ 4.1 ] y_i(\hat{w}_{opt}·\hat{x_i})=y_i(w_{opt}·x_i+b_{opt})\geq\gamma \quad [4.1] yi​(w^opt​⋅xi​^​)=yi​(wopt​⋅xi​+bopt​)≥γ[4.1] 成立

  (2) 感知机算法从 w 0 ^ = 0 \hat{w_0}=0 w0​^​=0开始，如果实例被误分类，则更新权重，令 w ^ k − 1 \hat{w}_{k-1} w^k−1​是第 k k k个误分类实例之前的扩充权值向量，即 w ^ k − 1 = ( w k − 1 T , b k − 1 ) T \hat{w}_{k-1} = (w_{k-1}^T,b_{k-1})^T w^k−1​=(wk−1T​,bk−1​)T，则第 k k k个误分类实例的条件是 y i ( w ^ k − 1 ⋅ x i ^ ) = y i ( w k − 1 ⋅ x i + b k − 1 ) ≤ 0 [ 4.3 ] y_i(\hat{w}_{k-1}·\hat{x_i})=y_i(w_{k-1}·x_i+b_{k-1})\leq0 \quad [4.3] yi​(w^k−1​⋅xi​^​)=yi​(wk−1​⋅xi​+bk−1​)≤0[4.3]

  若 ( x i , y i ) (x_i,y_i) (xi​,yi​)是被 w ^ k − 1 = ( w k − 1 T , b k − 1 ) T \hat{w}_{k-1} = (w_{k-1}^T,b_{k-1})^T w^k−1​=(wk−1T​,bk−1​)T 误分类的数据，则更新 w , b w,b w,b

  w k ← w k − 1 + η y i x i w_k \leftarrow w_{k-1}+\eta y_ix_i wk​←wk−1​+ηyi​xi​

  b k ← b k − 1 + η y i b_k \leftarrow b_{k-1} +\eta y_i bk​←bk−1​+ηyi​

  即 w ^ k = w ^ k − 1 + η y i x ^ i [ 4.2 ] \hat{w}_k = \hat{w}_{k-1} + \eta y_i\hat{x}_i \quad [4.2] w^k​=w^k−1​+ηyi​x^i​[4.2]

  由 [ 4.1 ] 、 [ 4.2 ] [4.1]、[4.2] [4.1]、[4.2] 式子可知

  w ^ k ⋅ w ^ o p t = w ^ k − 1 ⋅ w ^ o p t + η y i x ^ i ⋅ w ^ o p t ≥ w ^ k − 1 ⋅ w ^ o p t + η γ \begin{aligned}\hat{w}_k ·\hat{w}_{opt} &= \hat{w}_{k-1}·\hat{w}_{opt} + \eta y_i\hat{x}_i·\hat{w}_{opt} \\ &\geq \hat{w}_{k-1}·\hat{w}_{opt} + \eta \gamma \end{aligned} w^k​⋅w^opt​​=w^k−1​⋅w^opt​+ηyi​x^i​⋅w^opt​≥w^k−1​⋅w^opt​+ηγ​

  由此递推可知

  w ^ k ⋅ w ^ o p t ≥ w ^ k − 1 ⋅ w ^ o p t + η γ ≥ w ^ k − 2 ⋅ w ^ o p t + 2 η γ ≥ ⋯ ≥ k η γ [ 4.4 ] \begin{aligned}\hat{w}_k ·\hat{w}_{opt} \geq \hat{w}_{k-1}·\hat{w}_{opt} + \eta \gamma \geq \hat{w}_{k-2}·\hat{w}_{opt} + 2\eta \gamma \geq \cdots \geq k\eta \gamma &\end{aligned} \quad [4.4] w^k​⋅w^opt​≥w^k−1​⋅w^opt​+ηγ≥w^k−2​⋅w^opt​+2ηγ≥⋯≥kηγ​​[4.4]

  由 [ 4.2 ] 、 [ 4.3 ] [4.2]、[4.3] [4.2]、[4.3] 式子可知

  ∥ w ^ k ∥ 2 = ∥ w ^ k − 1 ∥ 2 + 2 η y i x ^ i ⋅ w ^ k − 1 + η 2 ∥ x i ^ ∥ 2 ≤ ∥ w ^ k − 1 ∥ 2 + η 2 ∥ x i ^ ∥ 2 ≤ ∥ w ^ k − 1 ∥ 2 + η 2 R 2 ≤ ∥ w ^ k − 2 ∥ 2 + 2 η 2 R 2 ≤ ⋯ ≤ k η 2 R 2 \begin{aligned} \begin{Vmatrix}\hat{w}_k\end{Vmatrix}^2 &= \begin{Vmatrix}\hat{w}_{k-1}\end{Vmatrix}^2 + 2\eta y_i\hat{x}_i · \hat{w}_{k-1} +\eta^2\begin{Vmatrix}\hat{x_i}\end{Vmatrix}^2 \\& \leq \begin{Vmatrix}\hat{w}_{k-1}\end{Vmatrix}^2 + \eta^2\begin{Vmatrix}\hat{x_i}\end{Vmatrix}^2 \\&\leq \begin{Vmatrix}\hat{w}_{k-1}\end{Vmatrix}^2 + \eta^2R^2 \\& \leq \begin{Vmatrix}\hat{w}_{k-2}\end{Vmatrix}^2 + 2\eta^2R^2 \leq \cdots \\&\leq k\eta^2R^2\end{aligned} ∥∥​w^k​​∥∥​2​=∥∥​w^k−1​​∥∥​2+2ηyi​x^i​⋅w^k−1​+η2∥∥​xi​^​​∥∥​2≤∥∥​w^k−1​​∥∥​2+η2∥∥​xi​^​​∥∥​2≤∥∥​w^k−1​​∥∥​2+η2R2≤∥∥​w^k−2​​∥∥​2+2η2R2≤⋯≤kη2R2​

  即 ∥ w ^ k ∥ 2 ≤ k η 2 R 2 [ 4.5 ] \begin{Vmatrix}\hat{w}_k\end{Vmatrix}^2 \leq k\eta^2R^2 \quad [4.5] ∥∥​w^k​​∥∥​2≤kη2R2[4.5]

  由 [ 4.4 ] 、 [ 4.5 ] [4.4]、[4.5] [4.4]、[4.5] 式子可知

  k η γ ≤ w ^ k ⋅ w ^ o p t ≤ ∥ w ^ k ∥ ∥ w ^ o p t ∥ ≤ k η R \begin{aligned} k\eta \gamma \leq \hat{w}_k ·\hat{w}_{opt} \leq \begin{Vmatrix}\hat{w}_k\end{Vmatrix}\begin{Vmatrix}\hat{w}_{opt}\end{Vmatrix} \leq \sqrt{k}\eta R \end{aligned} kηγ≤w^k​⋅w^opt​≤∥∥​w^k​​∥∥​∥∥​w^opt​​∥∥​≤k ​ηR​

  因此

  k ≤ ( R γ ) 2 k \leq \big(\frac{R}{\gamma}\big)^2 k≤(γR​)2

5. 感知机学习算法的对偶形式

​ 我们在进行算法学习是，设定 w 0 = 0 , b 0 = 0 w_0=0,b_0=0 w0​=0,b0​=0 ，对于误分类点 ( x i , y i ) (x_i,y_i) (xi​,yi​)，通过

w ← w + η y i x i w \leftarrow w+\eta y_ix_i w←w+ηyi​xi​

b ← b + η y i b \leftarrow b +\eta y_i b←b+ηyi​

逐步调整 w , b w,b w,b的值，假设样本点 ( x i , y i ) (x_i,y_i) (xi​,yi​)在整个更新过程中被错误分类 n i n_i ni​次，则 w , b w,b w,b关于 ( x i , y i ) (x_i,y_i) (xi​,yi​)的增量分别为 n i η y i x i n_i\eta y_ix_i ni​ηyi​xi​和 n i η y i n_i\eta y_i ni​ηyi​ ，则最后学习到的 w , b w,b w,b分别为

w = ∑ i = 1 N n i η y i x i [ 5.1 ] w = \sum\limits_{i=1}^{N}n_i\eta y_ix_i \quad [5.1] w=i=1∑N​ni​ηyi​xi​[5.1]

b = ∑ i = 1 N n i η y i [ 5.2 ] b = \sum\limits_{i=1}^{N}n_i\eta y_i \quad [5.2] b=i=1∑N​ni​ηyi​[5.2]

n i n_i ni​越大，表明数该数据点距离分离超平面越近，也就越难分类，超平面只要稍微变动一下，该点就从正样本变成了负样本或者相反，这样的点往往对最终的超平面影响越大

将式 [ 4.1 ] 、 [ 4.2 ] [4.1]、[4.2] [4.1]、[4.2]带入感知器模型 f ( x ) = s i g n ( w ⋅ x + b ) f(x)=sign(w·x+b) f(x)=sign(w⋅x+b)中，得到：

f ( x ) = s i g n ( ∑ i = 1 N n i η y i x i + ∑ i = 1 N n i η y i ) [ 5.3 ] f(x) = sign(\sum\limits_{i=1}^{N}n_i\eta y_ix_i+\sum\limits_{i=1}^{N}n_i\eta y_i) \quad [5.3] f(x)=sign(i=1∑N​ni​ηyi​xi​+i=1∑N​ni​ηyi​)[5.3]

此时模型中的参数由 w , b w,b w,b 变成了 n i n_i ni​

• 对偶问题描述

  输入：线性可分数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } ， x i ∈ R n , y i ∈ { − 1 , + 1 } , i = 1 , 2 , ⋯   , N T = \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}，\quad x_i \in R^n,\quad y_i \in\{-1,+1\},\quad i =1,2,\cdots,N T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}，xi​∈Rn,yi​∈{−1,+1},i=1,2,⋯,N

  ​ 学习率 η ∈ ( 0 , 1 ] \eta \in (0,1] η∈(0,1] ；

  输出： n n n；感知机模型 f ( x ) = s i g n ( ∑ j = 1 N n j η y j x j ⋅ x + ∑ j = 1 N n j η y j ) f(x) = sign(\sum\limits_{j=1}^{N}n_j\eta y_jx_j ·x+\sum\limits_{j=1}^{N}n_j\eta y_j) f(x)=sign(j=1∑N​nj​ηyj​xj​⋅x+j=1∑N​nj​ηyj​)

  1. 初始化 n = 0 n=0 n=0

  2. 在训练数据集中，选取数据 ( x i , y i ) (x_i,y_i) (xi​,yi​)

  3. 如果 y i ( ∑ j = 1 N n j η y j x j ⋅ x i + ∑ j = 1 N n j η y j ) ≤ 0 y_i(\sum\limits_{j=1}^{N}n_j\eta y_jx_j·x_i+\sum\limits_{j=1}^{N}n_j\eta y_j) \leq 0 yi​(j=1∑N​nj​ηyj​xj​⋅xi​+j=1∑N​nj​ηyj​)≤0

     n i ← n i + 1 n_i \leftarrow n_i+1 ni​←ni​+1

  4. 转至2直到没有误分类数据

• 对偶形式中训练实例仅以内积的形式出现，为了方便，可以预先将训练集中实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是所谓的 G r a m Gram Gram矩阵

  G = [ x i ⋅ x j ] N ∗ N = [ x 1 ⋅ x 1 x 1 ⋅ x 2 ⋯ x 1 ⋅ x N x 2 ⋅ x 1 x 2 ⋅ x 2 ⋯ x 2 ⋅ x N ⋮ ⋮ ⋮ ⋮ x N ⋅ x 1 x N ⋅ x 2 ⋯ x N ⋅ x N ] \begin{aligned} G &= [x_i · x_j]_{N*N}\\ \\&=\begin{bmatrix} x_1 · x_1 & x_1 · x_2 & \cdots & x_1 · x_N \\x_2 · x_1 & x_2 · x_2 & \cdots & x_2 · x_N \\ \vdots & \vdots & \vdots & \vdots \\x_N · x_1 & x_N · x_2 & \cdots & x_N · x_N \end{bmatrix} \end{aligned} G​=[xi​⋅xj​]N∗N​=⎣⎢⎢⎢⎡​x1​⋅x1​x2​⋅x1​⋮xN​⋅x1​​x1​⋅x2​x2​⋅x2​⋮xN​⋅x2​​⋯⋯⋮⋯​x1​⋅xN​x2​⋅xN​⋮xN​⋅xN​​⎦⎥⎥⎥⎤​​

文章参考李航老师的《统计学习方法》