感知机(perceptron) 是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。感知机对应于输入空间(特征空间)中将实例划分为正负两类的分离超平面，属于判别模型。感知机旨在求出将训练数据进行线性划分的分离超平面。为此，导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。

感知机模型

定义1(感知机) 假设输入空间(特征空间)是X⊆Rn，输出空间是Y={+1,−1}。输入x∈X表示实例的特征向量，对应于输入空间(特征空间)的点，输出y∈Y表示实例的类别。由输入空间到输出空间的如下函数

称为感知机。其中，w和b为感知机模型参数，w∈Rn叫做权值(weight)或权值向量(weight vector)，b∈R叫做偏置(bisa)¹，w⋅x表示w和x的内积。sign是符号函数，即

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

感知机有如下几何解释:线性方程

对应于特征空间Rn中的一个超平面S，其中w是超平面的法向量，b是超平面的截距。这个超平面将特征空间划分两个部分，位于两部分的点(特征向量)分别被分为正、负两类。因此，超平面S称为分离超平面(separating hyperplane)。 如图所示:

感知机学习策略

数据集的线性可分

定义(数据集的线性可分性) 给定一个数据集

其中，xi∈X=Rn,yi∈Y={+1,−1},i=1,2,⋯,N,如果存在某个超平面S

能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，即对所有yi=+1的实例i，有w⋅xi+b>0，对所有yi=−1的实例i，有w⋅xi+<0，则称数据集T为线性可分数据集(linearly separable data set),否则，称数据集T线性不可分。

感知机学习策略

感知机的学习的目标是找到一个能够将训练正实例点和负实例点完全正确分离的超平面，即确定感知机模型参数w,b，我们需要确定一个学习策略，也即定义(经验)损失函数并将损失函数极小化。

感知机所采用的损失函数是误分类点到超平面S的总距离³。为此，首先写出输入空间Rn中任一点x0到超平面S的距离:

这里，‖w‖是w的L2范数⁴。

其次，对于误分类的数据(xi,yi)来说

成立，因为对误分点来说，yi与(wi⋅xi+b)是异号。因此，误分类点到超平面S的距离是:

这样假设超平面S的误分类点集合为M，那么所有误分类点到超平面S的总距离为

不考虑1‖w‖，就得到感知机学习的损失函数。⁵

给定训练数据集

其中，xi∈X=Rn，yi∈Y={+1,−1},i=1,2,⋯,N.。感知机sign(w⋅x+b)学习的损失函数定义为:

其中，M为误分点的集合。这个损失函数就是感知机学习的经验风险函数。

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

感知机学习的策略是在假设空间中选取使损失函数(???)最小的模型参数w,b，即感知机模型。

感知机学习算法

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

感知机学习算法是对以下最优化问题的算法，给定一个训练数据集

其中，xi∈X=Rn,y∈Y={−1,+1},i=1,2,⋯,N,求参数w,b，使其为以下损失函数极小化问题的解

其中M为误分类点的集合。

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

假设误分类点集合M是固定的，那么损失函数L(w,b)的梯度由

给出。

随机选取一个误分类点(xi,yi)，对w,b进行更新:

式中η(0≤η≤1)是步长，在统计学习中又称为学习率(learning rate)。这样，通过迭代可以期待损失函数L(w,b)不断减小，直到为0.

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

输入: 训练数据集T={(x1,x2),(x2,y2),⋯,(xN,yN)}，其中xi∈X=Rn,yi∈Y={−1,+1},i=1,2,⋯,N；学习率η(0<η≤1)。

输出:w,b；感知机模型f(x)=sign(w⋅x+b)。

(1) 选取初值w0,b0

(2) 在训练集中选取数据(xi,yi)

(3) 如果yi(w⋅xi+b)≤0,则

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

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

算法的收敛性

现在要证明，对于线性可分数据集感知机学习算法原始形式收敛，即经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面感知机模型。 为了便于叙述，将偏置b并入权重向量w，记作

，同样也将输入向量加以扩充，加进常数1，记作

。这样，

，显然，

。

定理(Novikoff): 设训练数据集T={(x1,y1),(x2,y2),⋯,(xN,yN)}是线性可分的，其中xi∈X=Rn,yi∈Y={−1,+1},i=1,2,⋯,N，则

(1) 存在满足条件

的超平面

将训练数据集完全正确分开；且存在γ>0，对所有i=1,2,⋯,N

(2)令

，则感知机算法在训练数据集上的误分类次数k满足不等式

证明 (1) 由于训练数据集是线性可分的，按照定义，存在超平面可将训练数据集完全分开，取此超平面为

，使

，由于对有限的i=1,2,⋯,N，均有⁶

所以存在

使

(2)感知机算法从

开始，如果实例被误分类，则更新权重。令

是第k个误分类实例之前的扩充权重向量，即

则第k个误分类实例的条件是

若(xi,yi)是被

误分类的数据，则w和b的更新是

即

接下来进行两个不等式的推导

(1)

由式(???)及式(???)得

由此递推即得不等式(???)

(2)

由式(???)及式(???)得

结合不等式(???)及不等式(???)即得

于是

定理表明，误分类的次数k是有上界的，经过有限次搜索可以找到将训练数据完全正确分开的分离超平面。也就是说，当训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的。感知机学习算法存在许多解，这些解既依赖于初值的选择，也依赖于迭代过程中误分类点的选择顺序。为了得到唯一的超平面，需要对分离超平面增加约束条件。当训练集线性不可分时，感知机算法不收敛，迭代结果会发生震荡。

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

对偶形式的基本思想是，将w和b表示为实例xi和标记yi的线性组合的形式，通过求解其系数而求得w和b。不是一般性，在原始算法中，可假设初值w0,b0均为0.对误分类点(xi,yi)通过

逐步修改w,b，则w,b关于(xi,yi)的增量分别是αiyixi。这里αi=niη。这样，从学习过程不难看出，最后学习到的w,b可以分别表示为⁷

⁸这里αi≥0,i=1,2,⋯,N,当η=1时，表示第i个实例点由于误分而进行更新的次数。实例点更新次数越多，意味着它距离超平面越近，也就越难正确分类。

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

输入: 线性可分的数据集T=(x1,y1),(x2,y2),⋯,(xN,yN),其中xi∈Rn,yi∈{−1,+1},i=1,2,⋯,N;学习率η(0<η≤1)

输出: α,b；感知机模型f(x)=sign(∑Nj=1αjyjxj⋅x+b)。其中α=(α1,α2,⋯,αN)T

(1)α←0,b←0

(2)在训练集中选取数据(xi,yi)

(3)如果yi(∑Nj=1αjyjxj⋅xi+b)≤0

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

Share on: Twitter ❄ Facebook ❄ Email

---

---