感知机是二分类的线性分类模型，输入为实例的特征向量，输出为实例的类别（取+1和-1）。感知机对应于输入空间中将实例划分为两类的分离超平面，属于 判别模型。

感知机旨在求出将训练数据进行线性划分的分离超平面，为求得超平面导入了基于误分类的损失函数，利用梯度下降法对损失函数进行最优化。

感知机算法分为原始形式和对偶形式，感知机预测是用学习得到的感知机模型对新的输入实例进行分类。

感知机模型对线性可分的数据集比较有效。

1. 感知机模型

定义2.1 (感知机) 假设输入空间(特征空间)是$X\in R^n$ ， 输出空间是y={+1,−1}y=\{+1,-1\}y={+1,−1}。输入$z\in X$表示实例的特征向量，对应于输入空间(特征空间)的点；输出$y\in Y$表示实例的类别。由输入空间到输出空间的如下函数:
$$f(x)=sign(w\cdot x+b)$$
称为感知机。其中$w$和$b$为感知机模型参数，$w\in R^n$叫作权值(weight)或者权值向量(weight vector)，$b\in R$叫作偏置（bias），$w\cdot x$表示w和x的内积，sign是符号函数，即
$$sign(x)=\{\begin{array}{ll}+1& \text{ if }x>=0\\ -1& \text{ if }x<0\end{array}$$

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

感知机又如下集合解释：线性方程$$w\cdot x+b=0$$对应于特征空间$R^n$中的一个超平面$S$，其中$w$是超平面的法向量，$b$是超平面截距。这个超平面将特征空间划分为两个部分，位于两部分的点（特征向量）分别被分为正、负两类。因此，超平面$S$被称为分离超平面（sparating hyperplane），如下图所示：

感知机学习，由训练数据集（实例的特征向量及类别）T={(x1,y1),(x2,y2),...,(xN,yN)}T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}，其中$x_i\in X=R^n$，yi∈Y={+1,−1},i=1,2,...,Ny_i\in Y=\{+1,-1\},i=1,2,...,Nyi​∈Y={+1,−1},i=1,2,...,N，求得感知机模型$f(x)=sign(w\cdot x+b)$，即求得模型参数$w,b$。感知机预测，通过学习得到的感知机模型，对于新的输入实例给出其对应的输出类别。

2. 感知机学习策略

**定义2.2（数据集的线性可分性）**给定数据集$$T=(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)$$，其中$x_i\in X=R^n,y_i\in Y=+1,-1,i=1,2,\cdots ,N$，如果存在某个超平面 S 满足：$$w\cdot x+b=0$$能将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，即对所有$y_i=+1$的实例 $x_i$，有$w\cdot x_i+b>0$；对所有$y_i=-1$的实例$x_i$，有$w\cdot x_i+b<0$，则称数据集$T$为线性可分数据集 ；否则，称数据集$T$线性不可分。

在学习感知机模型中，需要确保数据集线性可分，才能够找到一个完全将正实例点和负实例点正确分开的分离超平面，即才能够确定感知机模型参数$w,b$。

为了确定感知机模型（超平面）参数 $w,b$ ，需要确定一个学习策略，即定义（经验）损失函数并将损失函数极小化。

感知机学习的策略：在假设空间中选取使损失函数式最小的模型参数， 即感知机模型。

损失函数的选择：

• 损失函数的一个自然选择是误分类点的总数，但是这样的损失函数不是参数$w，b$的连续可导函数，不易优化。
• 损失函数的另一个选择是误分类点到超平面S的总距离，这是感知机所采用的。

点到超平面S的距离：首先，输入空间$R^n$中任一点$x^0$到超平面S的距离如下式所示，这里$||w||$表示L2范数。
$$\frac{1}{||w||}|w\cdot x_0+b|$$

误分类点到超平面S的距离：其次，对于误分类数据$(x_i,y_i)$来说，$$-y_i(w\cdot x_i+b)>0$$成立。因为当$w\cdot x_i+b>0$时，$y_i=-1$,而$w\cdot x_i+b<0$时，$y_i=+1$。因此，误分类点$x_i$到超平面S的距离为
$$-\frac{1}{||w||}{y}_i(w\cdot x_i+b)$$
假设超平面S的误分类点集合为M，那么所有误分类点到超平面S的总距离为$$-\frac{1}{||w||}\sum _{x_i\in M}{y}_i(w\cdot x_i+b)$$，不考虑$\frac{1}{||w||}$,就得到了感知机学习的损失函数。

给定训练数据集T={(x1,y1),(x2,y2),⋯,(xN,yN)}T=\{(x_1,y_1),(x_2,y_2),⋯,(x_N,y_N)\}T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}，其中$x_i\in X=R^n,y_i\in Y=+1,-1,i=1,2,\cdots ,N$。感知机$sign(w\cdot x+b)$学习的损失函数定义为$$L(w,b)=-\sum _{x_i\in M}{y}_i(w\cdot x_i+b)$$，其中M为误分类点的集合。这个损失函数就是感知机学习的经验分线函数。

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

感知机学习的策略是在假设空间中选取使损失函数$L(w,b)=-{\sum }_{x_i\in M}{y}_i(w\cdot x_i+b)$最小的模型参数w,b，即感知机模型。

3. 感知机学习算法

感知机学习问题转化为求解损失函数式$L(w,b)=-{\sum }_{x_i\in M}{y}_i(w\cdot x_i+b)$的最优化问题，最优化的方法是随机梯度下降法。

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

给定一个训练数据集T={(x1,y1),（x1,y2),...,(xN,yN)}T=\{(x_1,y_1),（x_1,y_2), ..., (x_N,y_N)\}T={(x1​,y1​),（x1​,y2​),...,(xN​,yN​)}，其中$x_i\in \chi =R^{\ast }$，yi∈y={−1,1}，i=1,2,...,Ny_i \in y = \{-1,1\}， i=1,2,...,Nyi​∈y={−1,1}，i=1,2,...,N，求参数$w,b$，使其为以下损失函数极小值问题的解：
$$\underset{w,b}{\min }L(w,b)=-\sum _{x_i\in M}{y}_i(w\cdot x_i+b)$$
其中M为误分类点的集合。

感知机学习算法是误分类驱动的，采用随机梯度下降法。首先，任意选取一个超平面$w_0,b_0$，然后用梯度下降法不断地极小化目标函数。极小化过程中不是一次使M中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。

假设误分类点集合M是固定的，那么损失函数$L(w,b)$的梯度由：
$${\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<\eta <=1)$是步长，在统计学中又称为学习率（learning rate）。通过迭代可以期待损失函数$L\left(w,b\right)$不断减小，直到为0。

算法2.1 感知机学习算法的原始形式：
输入：训练数据集T={(x1,y1),(x2,y2),...,(xN,yN)}T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}，其中$x_i\in \chi =R^n$，yi∈Y={−1,+1}，i=1,2,...,,Ny_i∈Y=\{−1,+1\}， i=1,2,...,,Nyi​∈Y={−1,+1}，i=1,2,...,,N； 学习率$\eta (0<\eta ⩽1)$；
输出：$w,b$；感知机模型$f(x)=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），直至训练集中没有误分类点。

这种学习算法直观上有如下解释：当一个实例点被误分类，即位于分离超平面的错误一侧时，则调整w,b的值，使分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面间的距离，直至超平面越过该误分类点使其被正确分类。

3.2 算法的收敛性

对于线性可分数据集感知机学习算法的收敛性，即经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型。

为了便于叙述与推导，将偏置$b$并入权重向量$w$，记作$\hat{w}\leftarrow (w^T,b^T)$，同时将输入向量加以扩充，加进常数1，记作$\hat{x}\leftarrow (x^T,1{)}^T$，这样$\hat{x}\in R^{n+1},\hat{w}\in R^{n+1}$。此时$\hat{w}\cdot \hat{x}\leftarrow (w\cdot x+b)$。

定理（Novikoff）：设训练数据集T={(x1,y1),(x2,y2),...,(xN,yN)}T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}是线性可分的，其中$x_i\in \chi =R^n$，yi∈Y={−1,+1}，i=1,2,...,Ny_i\in Y = \{-1,+1\}，i=1,2,...,Nyi​∈Y={−1,+1}，i=1,2,...,N，则
（1）存在满足条件$||\widehat{w_{opt}}||=1$的超平面$\widehat{w_{opt}}\cdot \hat{x}=w_{opt}\cdot x+b_{opt}=0$将训练数据集完全正确分开；且存在条件$\gamma >0$，对所有$i=1,2,...,N$，
$$y_i(\widehat{w_{opt}}\cdot \widehat{x_i})=y_i(w_{opt}\cdot x+b_{opt})>=\gamma$$
（2）令$R={\max }_{1<=i<=N}||\widehat{x_i}||$，则感知机算法$f(x)=sign(w\cdot x+b)$在训练数据集上的误分类次数$k$满足不等式$$k<=(\frac{R}{r}{)}^2$$

定理表明，误分类的次数$k$是有上届的，经过有限次搜索可以找到将训练数据完全正确分开的分离超平面。也就是说，当训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的。

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

对偶形式的基本想法是：将$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$，设修改n次，则w,b关于$(w_i,y_i)$的增量分别是${\alpha }_i{y}_i{x}_i$和${\alpha }_i{y}_i$，这里令${\alpha }_i=n_i\eta$。这样，最后学习到的$w,b$可以分别表示为$$w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i$$$$b=\sum _{i=1}^N{\alpha }_i{y}_i$$，其中${\alpha }_i\ge 0,i=1,2,...,N$，当$\alpha =1$时表示第$i$个实例点由于误分而进行更新的次数。实例点更新次数越多，意味着它距离分离超平面越近，也就越难以正确分类。

算法2.2 感知机学习算法的对偶形式
输入：线性可分的数据集T={(x1,y1),(x2,y2),...,(xN,yN)}T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}，其中$x_i\in R^n$，yi∈{−1,+1}，i=1,2,...,Ny_i\in \{-1,+1\}，i=1,2,...,Nyi​∈{−1,+1}，i=1,2,...,N；学习率$\eta （0<=\eta <=1）$；
输出：$\alpha ,b$；感知机模型$f(x)=sign{\sum }_{j=1}^N{\alpha }_j{y}_j{x}_j\cdot x+b$
（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)<=0$$${\alpha }_i\leftarrow {\alpha }_i+\eta$$$$b\leftarrow b+\eta y_i$$
（4）转至（2）直到没有误分类数据
对偶形式中训练实例仅以内积的形式出现。为了方便，可以预先将训练集中实例间的内积计算出来并以矩阵的形式存储，称之为Gram矩阵（Gram matrix）$$G=[x_i\cdot x_y{]}_{M\times N}$$

总结

1. 感知机是根据输入实例的特征向量$x$对其进行二类分类的线性模型：$$f(x)=sign(w\cdot x+b)$$，感知机模型对应于输入空间（特征空间）中的分离超平面$w\cdot x+b=0$。
2. 感知机学习的策略是极小化损失函数$$\underset{w,b}{\min }L(w,b)=-\sum _{x_i\in M}{y}_i(w\cdot x+b)$$，损失函数对应于误分类点到分离超平面的总距离。
3. 感知机学习算法是基于随机梯度下降法的对损失函数的最优化算法，有原始形式和对偶形式。在原始形式中，首先任意选取一个超平面，然后用梯度下降法不断极小化目标函数。在这个过程中一次随机选取一个误分类点使其梯度下降。
4. 当训练数据集线性可分时，感知机学习算法是收敛的。感知机算法在训练数据集上的误分类次数k满足不等式$$k<=(\frac{R}{r}{)}^2$$，当训练数据集线性可分时，感知机学习算法存在无穷多个解，其解由于不同的初值或不同的迭代顺序而可能有所不同。
5. 感知机的扩展学习方法包括口袋算法（pocket algorithm）、表决感知机（voted perceptron）、带边缘感知机（perceptron with margin）。

参考资料

1. https://blog.csdn.net/weixin_54814385/article/details/122462070
2. https://zhuanlan.zhihu.com/p/307094622
3. https://blog.csdn.net/qq_45761584/article/details/114680687
4. 《统计学习方法》 李航 著
5. https://www.cnblogs.com/BlairGrowing/p/14791795.html