感知机算法详解

今天想写一下感知机算法的详解。感知机算法由Rosenblatt在1957年提出，是一类简单的线性判别算法，通过扩展又可以与许多其他算法密切相关。如逻辑回归模型、支持向量机、前馈神经网络（多层感知机）、线性判别分析等。因此感知机算法尽管很少单独使用，但它对于理解其他模型和算法非常有用，很适合作为开始机器学习的一个切入点，同时也是建立知识体系的一个枢纽。

本文首先简要介绍感知机，然后讲解感知机的模型、策略、算法，最后分析感知机算法与各个算法之间的联系并做出总结。

感知机能做什么

为了便于应用感知机算法，我们有时会使用一些技巧，使得线性不可分的样本在某些变换下成为线性可分。这些技巧包括将样本分离到更高维空间（图2）或投影到特定的方向（图3）等，这是另一大类方法，本文主要讲解一般的感知机，此处不详细展开讨论。

图2 分离到高维空间实现线性可分

图3 投影特定方向实现线性可分

感知机模型

• 定义
  设输入空间（特征空间）为 $X\subseteq {\mathbb{R}}^n$,输出空间为 Y = { − 1 , + 1 } Y=\{-1,+1\} Y={
  −1,+1}
  输入 $x\in X$ 为实例的特征向量 输出 $y\in Y$ 为实例的类别
  由输入空间到输出空间的如下函数称为感知机
  $$f(x)=sign(wx+b)$$其中$w$和$b$为模型参数，$w\in {\mathbb{R}}^n$称为权值，$b\in \mathbb{R}$称为偏置。$sign$是符号函数。
  
  
  
  

感知机模型有直观的几何解释：线性方程 $wx+b=0$ 对应于分离超平面$S$,其中$w$为$S$的法向量，$b$为$S$的截距。求解感知机，就是要解出$w$和$b$,得到能正确分离所有正负样本的超平面$S$(见图1).

感知机策略

对于误分类点数据$(x_i,y_i)$,有$-y_i(w{x}_i+b)>0$,因为 $y_i$ 与 $w{x}_i+b$ 异号

设超平面$S$的误分类集合为$M$,则所有误分类点到超平面$S$的总距离为 $$-\frac{1}{\Vert w\Vert }\sum _{x_i\in M}{y}_i(w{x}_i+b)$$ 不考虑式中的$-\frac{1}{\Vert w\Vert }$,即得到感知机学习的损失函数。

• 损失函数
  给定训练集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\} T={
  (x1​,y1​),(x2​,y2​),...,(xN​,yN​)},其中$x_i\in X={\mathbb{R}}^n$,
  y i ∈ Y = { − 1 , + 1 } , i = 1 , 2 , . . . , N y_i\in Y=\{-1,+1\},i=1,2,…,N yi​∈Y={
  −1,+1},i=1,2,...,N.感知机学习的损失函数为
  $$L(w,b)=-\sum _{x_i\in M}{y}_i(w{x}_i+b)$$
  
  
  

易知损失函数是非负的，误分类点越少，误分类点离超平面越近，损失函数值就越小。如果没有误分类点，则损失函数值时0.感知机学习的策略是在假设空间中选取使损失函数取值最小的模型参数。

感知机学习算法

原始形式

目标：感知机学习算法的原始形式是求解最优化问题 $${min}_{w,b}L(w,b)=-\sum _{x_i\in M}{y}_i(w{x}_i+b)$$其中$M$为误分类点的集合。
算法：误分类驱动的随机梯度下降法首先选取初始超平面$w_0,b_0$,然后计算在该参数取值处的梯度，用梯度下降法不断的极小化目标函数。极小化过程中，不是一次使用$M$中所有误分类点计算梯度，而是一次随机选取一个误分类点使其梯度下降。设误分类点集合$M$是固定的，则损失函数的梯度为：$${\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$$由于采用随机梯度下降，一次随机选取一个误分类点$(x_i,y_i)$,$w,b$的更新公式为：$$w\leftarrow w+\eta y_i{x}_i,b\leftarrow b+\eta y_i$$式中$\eta （0\le \eta \le 1）$称为学习率。整理称为算法形式如下：

• 算法1
  输入：线性可分的训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\} T={
  (x1​,y1​),(x2​,y2​),...,(xN​,yN​)},
  其中$x_i\in X={\mathbb{R}}^n$, y i ∈ Y = { − 1 , + 1 } , i = 1 , 2 , . . . , N y_i\in Y=\{-1,+1\},i=1,2,…,N yi​∈Y={
  −1,+1},i=1,2,...,N. 学习率$\eta （0\le \eta \le 1）$
  输出：参数$w,b$，感知机模型$f(x)=sign(wx+b)$
  (1)选取初值$w_0，b_0$
  (2)在训练集中选取数据$(x_i,y_i)$
  (3)如果$y_i(w{x}_i+b)\le 0$$$w\leftarrow w+\eta y_i{x}_i,b\leftarrow b+\eta y_i$$
  (4)转至（2），直至训练集中没有误分类点。
  每次根据$(x_i,y_i)$调整$w,b$时，分离超平面将向该误分类点移动，以减少该误分类点与超平面的距离，越过该误分类点使其正确分类。
  
  
  
  
  
  
  
  

感知机学习算法的收敛性有定理保证，这里不再详细阐述，有兴趣的读者可以查阅相关资料。

对偶形式

感知机学习算法的原始形式是每一步直接更新参数$w,b$,经过n步达到收敛。对偶形式的基本想法是，将$w$和$b$表示为实例$x_i$和标记$y_i$的线性组合的形式，通过求解其系数而求得$w$和$b$.假设初值$w_0,b_0$均为0，对误分类点$(x_i,y_i)$通过$$w\leftarrow w+\eta y_i{x}_i$$$$b\leftarrow b+\eta y_i$$逐步修改$w,b$,设收敛过程中，第$i$个点共修改了$n_i$次，则$w,b$关于$(x_i,y_i)$的增量分别是${\alpha }_i{y}_i{x}_i$ 和 ${\alpha }_i{y}_i$,其中 ${\alpha }_i=n_i\eta$.对N个样本点上$w,b$的增量求和，有$$w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i$$$$b=\sum _{i=1}^N{\alpha }_i{y}_i$$从而感知机可以写成由系数${\alpha }_i,b$表示的形式$$f(x)=sign(\sum _{j=1}^N{\alpha }_j{y}_j{x}_j\cdot x+b)$$，上述过程整理为算法2.

• 算法2
  输入：线性可分的训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\} T={
  (x1​,y1​),(x2​,y2​),...,(xN​,yN​)},其中$x_i\in X={\mathbb{R}}^n$, y i ∈ Y = { − 1 , + 1 } , i = 1 , 2 , . . . , N y_i\in Y=\{-1,+1\},i=1,2,…,N yi​∈Y={
  −1,+1},i=1,2,...,N. 学习率$\eta （0\le \eta \le 1）$
  输出：参数$\alpha ,b$，感知机模型$f(x)=sign({\sum }_{j=1}^N{\alpha }_j{y}_j{x}_j\cdot x+b)$，其中$\alpha =({\alpha }_1,{\alpha }_2,...,{\alpha }_N{)}^T$
  (1)取初值$\alpha \leftarrow 0,b\leftarrow 0$
  (2)在训练集中选取数据$(x_i,y_i)$
  (3)如果 $y_i({\sum }_{j=1}^N{\alpha }_j{y}_j{x}_j\cdot x_i+b)\le 0$$${\alpha }_i\leftarrow {\alpha }_i+\eta$$$$b\leftarrow b+\eta y_i$$
  (4)转至（2）中直到没有误分类数据。
  
  
  
  
  
  

对偶形式算法的特点是，${\alpha }_i$每步更新差值固定，${\alpha }_i$越大更新次数越多，意味着$(x_i,y_i)$离分离超平面越近，对学习结果的影响也最大。
对偶形式中训练实例仅以内积形式出现，可以预先将实例间的内积计算出来并存储为矩阵，即Gram矩阵。$$G=[x_i\cdot x_j{]}_{N\times N}$$Gram矩阵是$N\times N$的对称矩阵

感知机与其他算法

• 感知机只能处理线性可分的数据集，线性不可分的数据集会引起分离超平面的震荡而无法收敛。
• 感知机是误分类驱动的模型，模型的解不唯一。离群点对结果影响很大。
• 感知机的判别模型由符号函数给出，无法表示更复杂的非线性映射。

为解决以上的局限性，其他算法从不同方向对感知机模型进行了扩展。

感知机与支持向量机

• 相同点
  感知机与支持向量机都是求解能正确划分样例的超平面
  
• 不同点
  感知机是误分类驱动的，其损失函数来源于误分类点到分离超平面的距离之和。数据集线性可分时，能正确划分样例的超平面有无穷多个。
  支持向量机不仅要求正确划分正负样例，还要求正负样例间隔最大，在最大间隔约束下，划分超平面（的法向量）有唯一解。
  
  
  

  图5 感知机

  图6 支持向量机

感知机优化目标： $${min}_{w,b}L(w,b)=-\sum _{x_i\in M}{y}_i(w{x}_i+b)$$ 支持向量机优化目标： $${max}_{w,b}d$$

感知机与逻辑回归

感知机与逻辑回归都是判别模型，都是对线性运算的结果进行判别，区别是采用了不同判别方式。

• 感知机用符号函数进行判别： $$w\cdot x+b\to f(x)=sign(w\cdot x+b)$$
• 逻辑回归用对数几率进行判别： $$w\cdot x+b=log\frac{p}{1-p}\to p=\frac{1}{1+e^{-(w\cdot x+b)}}$$
  如果把神经元看成是对线性输入做非线性变换并输出的算法部件，则感知机和逻辑回归可以看成是两种不同的神经元，即采用了不同的非线性变换。
  

感知机与神经网络

当把感知机看成单个神经元时，该神经元的堆叠就形成了神经网络。最常用的前馈神经网络就是感知机分层堆叠而形成的，也叫多层感知机MLP.感知机的激活函数是阶跃函数（符号函数）：$$f(x)=sign(x)=\{\begin{array}{l}1,x>0\\ -1,x\le 0\end{array}$$
目前常用神经网络的激活函数是线性整流函数(ReLU):$$f(x)=ReLU(x)=\{\begin{array}{l}x,x>0\\ -1,x\le 0\end{array}$$

图7 感知机

图8 MLP(图中每个神经元相当于一个感知机)

关于感知机算法的理论部分小编就介绍这么多，它的实现可以使用常用机器学习开源库sklearn中的模块MLPClassifier来完成。感兴趣的读者不妨去试试哦。