Perenial youth.

一天一个机器学习概念(二)——感知机(perceptron)

一天一个机器学习概念(二)——感知机(perceptron)

昨天被问到了神经网络究竟是怎么一回事这个问题。思考了一下,决定从感知机开始入手说明。

那么先来看一下感知机(perceptron)的描述:

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

数学定义:假设输入空间(特征空间)是\(x\subseteq R^n\),输出空间是y = {+1, -1}. 输入\(x\in \chi\)表示实例的特征向量,对应于输入空间(特征空间)的点;输出\(y \in \Upsilon\)表示实例的类别。由输入空间到输出空间的如下函数称为感知机:

\(f(x) = sign(w\cdot x + b)\)

其中,w和b是感知机模型参数,\(w \in R^n\)是权重向量,\(b \in R\)是偏置bias, sign是符号函数,把x映射到1或-1上。

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

几何角度来说,线性方程\(w\cdot x + b = 0\)对应于特征空间\(R^n\)中的一个超平面S,其中w是超平面的法向量,b是超平面的截距。这个超平面将特征空间划分为两个部分,位于两部分的点(特征向量)分别被分为正,负两类:

那么感知机是如何学习的呢?它的学习策略是什么?

说到这个问题,第一个要明确的是数据集应该具有线性可分性。也就是说,对数据集\(T = {(x_1,y_1),(x_2,y_2),…,(x_n,y_n)}\),如果存在超平面S将数据集的正实例点和负实例点完全正确地划分到超平面的两侧,则数据集T为线性可分数据集,反之线性不可分。也就是说,感知机要受到数据集线性可分条件的约束。

接下来再来说具体的学习策略。我们已经说到,感知机要找到的是将正负实例点完全正确分开的分离超平面,那么损失函数的一个自然选择就是误分类点的总数,但是这样的损失函数不是连续可导的,不易优化;损失函数的另一个选择是误分类点到超平面S的总距离,这是感知机所采用的。为此,先写出输入空间\(R^n\)中任一点\(x_0\)到超平面S的距离:

\(\frac{1}{\| w\|}|w\cdot x_0 + b|\)

这里,\(\| w\|\)是w的\(L_2\)范数

因此,总距离为:

\(-\frac{1}{\| w\|}\sum_{x_i\in M}y_i(w\cdot x_0 + b)\)

其中M是误分类点的集合。不考虑\(\| w\|\),这就是感知机学习的损失函数:

\( L(w,b) = -\sum_{x_i\in M}y_i(w\cdot x_0 + b)\)

该函数显然非负。如果没有误分类点,损失函数值是0.而且,误分类点越少,误分类点离超平面越近,损失函数值就越小。因此,给定训练数据集T,损失函数L(w,b)是w,b的连续可导函数。

知道了学习策略,再来讨论一下感知机学习算法

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

为什么要用SGD而不是一般的梯度下降或者批量梯度下降?这里其实我个人觉得都行,虽然李航老师的书里说要用SGD..

随机选取一个误分类点\((x_i,y_i)\), 对w,b进行更新:

\(w\gets w+\eta y_i x_i\)

\(b\gets b+\eta y_i\)

式中\(0<\eta<=1\)是步长

算法步骤就是SGD的过程。。。懒得敲了,贴《统计学习方法》书中的算法步骤和一个例子:


算法的收敛性由Novikoff定理证明。这里不展开了。

注意的是,采用不同的初值或选取不同的误分类点,解可以不同。为了得到唯一的超平面,我们需要对分离超平面增加约束条件,这就是线性支持向量机的想法。当训练集线性不可分时,感知机学习算法不收敛,迭代结果会发生震荡。

那么感知机和神经网络有什么联系呢?实际上,感知机就是神经网络中的每一个小neuron。但是我们知道,感知机只是一个线性分类器而已,面对非线性数据,例如仅仅简单的“异或”,都没办法处理。

单层SVM无法解决这个问题

那么解决非线性的问题,第一个方法是堆叠感知机。也就是使用多层感知机,用很多直线去拟合一个曲线。在分类问题中这还勉强能用,比如说上述这张图,就可以用几个线性去划分区域,分割类别。但是更高端的方法就需要激活函数了。如果神经网络只是感知机的简单堆叠的话,实际上最后还是一个线性的东西,没有能力去拟合非线性的东西。我们知道,我们训练模型,只是为了在model space里找到最合适的函数,如果你model space就是线性的话,那也谈不上解决非线性的回归问题了。是激活函数赋予了神经网络拟合非线性的能力。感知机与SVM,logistic regression都是线性分类器,至于后两者,我之后的博客会说。

xinyu