感知机---公式推导及算法实现

作者: wensong_kevin | 来源:发表于2019-07-20 17:25 被阅读0次

一、概述

我们向感知机输入的实例是特征向量，它反馈给我们的是实例的类别，该类别取+1和-1两个值。这样一来，当我们输入包含大量样本实例的特征空间时，感知机就会求出一个分离超平面，将这些实例按照正类和负类进行线性划分。因此感知机是一种二类分类的线性模型，它分为原始形式和对偶形式两种，是支持向量机与神经网络的基础，所以很有必要牢牢地掌握感知机模型。能够熟练地推导公式以及通过简单的代码实现对少量的训练数据的分类，对原理的理解是很有帮助的。感知机的原理图如下所示：

感知机原理图

二、模型

假设输入空间(特征空间)是 $X \subseteq R^n$ ,输出空间是 $y=\{-1.+1\}$ 。输入 $x\in X$ 表示实例的特征向量，对应于输入空间中的点；输出 $y\in Y$ 表示实例的类别。输入空间到输出空间的函数如下所示：

$f(x)=sign(\omega \cdot x+b)$

其中， $\omega$ 和 $b$ 是感知机模型的参数分别代表权值和偏置， $w\cdot x$ 表示 $w$ 和 $b$ 的内积，sign是符号函数，即 $sign=\begin{cases} +1,x>=0\\-1,x</p><p>感知机属于判别模型，满足线性方程<img class=$ 。感知机的几何解释是：对应于特征空间 $R^n$ 中的一个超平面 $S$ ，其中 $w$ 是超平面的法向量， $b$ 是超平面的截距。这个超平面将特征空间划分为两个部分，位于两部分的点分别被分为正类、负类。因此分离超平面如下图所示：

感知机模型图

通过学习训练数据集 $T=\{(x_1,y_1),...,(x_n,y_n)\}$ 求出最优参数 $w，b$ ，即可得感知机模型，对于新的实例就可以给出相对准确的对应的输出类别。

三、策略

需要注意的是，训练数据集一定要是线性可分的。为了找到这样一个超平面把训练数据集的实例划分开来，即确定最优的参数 $w，b$ ，需要确定一个学习策略，也就是要定义一个损失函数并且使得损失函数最小化。损失函数的定义有两种方法，一是选择误分类点的总数，但是这种损失函数不是参数 $w，b$ 的连续可导函数，不宜优化。所以我们选择第二种，选择误分类点到超平面的距离总和作为损失函数。那么问题就来了，点到超平面距离如何计算呢？《统计学习方法》一书直接给出了距离公式：

$d=\frac{1}{||w||} |\omega \cdot x_0+b|$

其中 $||w||$ 是 $w$ 的 $L_2$ 范数， $||w||=\sqrt{\sum\nolimits_{i}^n{x_i}^2}$ 。下面我给出两种计算点到超平面的距离的求法，式子难打，就直接上图了。

由点到直线距离类比可得

点到平面距离

显然，对于误分类点 $(x_i,y_i)$ 来说， $\frac{1}{||w||} |\omega \cdot x_i+b|<0$ 。所以误分类点到超平面的距离是 $-\frac{1}{||w||} |\omega \cdot x_i+b|$ 。

我们假设误分类点的集合是 $M$ ，那么所有误分类点到超平面的距离总和就是：

$-\frac{1}{||w||}\sum\nolimits_{1}^M y_i(\omega \cdot x_i+b)$

由于 $\frac{1}{||w||}$ 恒为正，不影响算法中间过程和正负判断，所以可忽略。那么感知机的损失函数就可以定义为： $L(w，b)=-\sum\nolimits_{1}^M y_i(\omega \cdot x_i+b)$

损失函数 $L(w，b)$ 是 $w，b$ 的连续可导函数。误分类点越少时，误分类点离超平面距离越近，损失函数的值就越小。

四、算法

感知机学习算法是由误分类驱动的，具体采用随机梯度下降法不断极小化上述的损失函数。注意，极小化的过程不是一次使M中的所有误分类点的梯度下降，而实一次随机选取一个误分类点使其梯度下降。由上述的损失函数 $L(w,b)$ 求解 $w,b$ 的偏导数如下:

$\nabla_wL(w,b)=-\sum\nolimits_{1}^My_i\cdot x_i$

$\nabla_bL(w,b)=-\sum\nolimits_{1}^My_i$

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

$w=w+\eta y_ix_i$ 、 $b=b+\eta y_i$

其中 $\eta (0\le\eta \le1)$ 是自定义的步长，也可称为学习率。那么通过迭代就可以期待损失函数 $L(w,b)$ 不断减小。直至为零。综上所述，感知机原始形式的算法步骤如下：

1、选取初值 $w_0,b_0$ ；

2、在训练集中选取实例数据 $(x_i,y_i)$ ;

3、判断参数更新条件，若 $y_i(\omega \cdot x_i+b) \le0$ ，则按照上述的参数更新公式分别更新 $w,b$ ；

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

计算过程是很简单很明了的，就不给出详细的过程了。需要注意的就是，若有一个误分类点出现，更新了参数，当然模型也跟着变化了。那么就要把样本集中所有的点都要带进去验证，之前判定分类正确的的点也要重新判断，如此往复，直到样本集中不再有误分类点出现。此时才算完成了损失函数最小化，也就得到了最优参数 $w,b$ ，从而超平面也就找到了。

五、算法收敛性的证明

一个算法的迭代优化的过程必然是在有限步内完成，否则就失去了算法的意义。下面就开始感知机学习算法收敛性的证明。

感知机学习算法收敛性证明过程

想要把意思表达清楚，又为了叙述方便，所以定义了很多符号。看清楚每个符号代表的意思就好了，有些符号仅仅是个符号，替换成其他任何字母都没有关系。所以不要看着字母多就很抵触，慢慢来，顺着思路就能弄明白。

六、算法实现

感知机的学习算法相对简单，也易于实现。最关键的部分在于迭代求解最优参数，但是按照算法求解的步骤有序进行的话，也是比较容易的，下面就直接给出代码以及实现效果。

迭代求解最优参数

步长是自定义的，由于本次训练数据少，就直接初始化为1。数据量大的时候可以有小到大慢慢调试出合适的数值。

可视化展示

很清晰，没有什么复杂的地方。

实现效果图

七、小结

对偶形式与原始形式并没有本质的区别，不同之处在于对偶形式引入了Gram矩阵，计算量相对减少了很多。

网友评论

本文标题：感知机---公式推导及算法实现

本文链接：https://www.haomeiwen.com/subject/nhrylctx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！