1.人工智能算法初探——感知机全解（原始形式and对偶形式）

2023-11-08

感知机（perceptron）是1957年由Rosenblatt提出，是神经网络与支持向量机的基础。感知机是二分类的线性可分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1两个值。感知机只能应用到线性可分的数据集当中，对于线性不可分的问题感知机无法解决，其原理其实很简单：在特征空间中找到一个超平面将两类样本划分到超平面两侧，实现样品种类的划分。

1.感知机模型

假设输入空间是 $\chi \subseteq R^n$ ,输出空间是 $\gamma =\begin{Bmatrix} +1,-1\\ \end{Bmatrix}$ ,输入 $x\subseteq \chi$ 表示实例的特征向量，对于输入空间的点，输出 $y\subseteq \gamma$ 表示实例的类别，感知机模型可以如下形式:

其中w和b为感知机的参数，w为权重（weight），b为偏置（bias）， $w\cdot x$ 是w与x的内积，sign为符号函数，如下

其函数形式如下图所示：

感知机是一种线性分类器，属于判别模型。感知机有如下的几何解释：

线性方程 $w\cdot x+b=0$ 对应于特征空间的一个超平面S，其中w是超平面的法向量，b是超平面的截距，这个超平面将特征空间划分为两个部分，位于超平面两侧的点被分为+1、-1两类。因此，超平面S称为分离超平面，如下图所示：

2.感知机学习策略

2.1感知机的线性可分性

对于给定数据集T，如果存在超平面S: $w\cdot x+b=0$ 能够将数据集的正负实例完全正确地划分到超平面两侧，即对所有实例存在： $y_{i}(w\cdotx+b)>0$ ,则称数据集T是线性可分数据集；否则，称数据集T线性不可分。

2.2感知机学习策略

假设数据集是线性可分的，我们需要找到一个超平面将数据集完美划分，而超平面受参数w和b控制，因此我们需要找到合适的w和b使超平面完美划分两类数据。如何找到这两个合适的参数呢，这就要用到我们前面说的损失函数，将损失函数作为评价标准，极小化损失函数。

损失函数的选择也是一个问题，对于这个问题我们最自然的选择就是选择误分点数作为损失函数，但是由于这个损失函数对w和b这两个参数不是可导的，导致后面无法优化w和b两个参数，因此不选择使用。针对感知机问题常选用的损失函数是误分点到超平面的距离。

下面给出输入空间 $R^n$ 中一点到超平面的距离：

这里||w||是w的L2范数（平方和再开方）。

其次上面已经提到了对于所有正确分类的点都有： $y_{i}(w\cdotx+b)>0$ ，那么对于误分点自然存在： $y_{i}(w\cdotx+b)>0$ ，因此误分点到超平面的距离是：

则所有误分点到超平面的距离和为：

忽略1/||w||，就得到感知机的损失函数（1/||w||是一个常数，并不影响，可以直接忽略）：

可以看出损失函数是对全部误分点到超平面距离求和，是非负的，当点全部正确分类时，损失函数为0，误分类点越少，损失函数越少。

3感知机学习算法

根据上面的推导可以得到感知机学习问题转化为求解上述损失函数的最优化问题，最优化的方式是通过随机梯度下降法，感知机学习算法包括原始形式和对偶形式两种。

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

感知机学习算法的损失函数如下：

损失函数为所有误分点到超平面的距离，下面我们采用随机梯度下降法最优化w和b两个参数。具体过程如下：

（1）随机选取初值 $w_{0}$ 和 $b_{0}$ ；

（2）选取训练数据中一组数据（ $x_{i},y_{i}$ ）;

（3）如果 $y_{i}(w\cdot x_{i}+b)\leqslant 0$ ，求解损失函数对两个参数的梯度： $\triangledown _{w}L(w,b)=-\sum y_{i}x_{i}$ 和 $\triangledown _{w}L(w,b)=-\sum y_{i}$ ，对w和b进行更新：

（4）转至（2），直至训练集中没有误分点。以上便是感知机算法原始形式的实现过程。

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

首先介绍一下对偶：对偶规划(dual programming)一类线性规划问题，指由原线性规划问题按如下对称规律构成的新线性规划问题：若原问题(P)为maxz=CTX，满足{AX≤b，x≤0 }，则对称的新问题(D)为minw=yTb，满足{yTA≥c，y≥0 }，这里y为m维列向量，新问题(D)称为原线性规划的对偶规划。

简单的将对偶形式就是将原始问题不好求解的问题转化问另一种方便求解的形式。

感知机算法中的对偶形式的基本思想是，将w和b表示为实例 $x_{i}$ 和 $y_{i}$ 的线性组合的形式，通过求解其系数而求得w和b。

在上面原始形式中，我们通过梯度下降算法对w和b进行更新：

经过n次更新后，w和b关于（xi，yi）的增量分别为axiyi和ayi，这里的 $a_{i}=n_{i}\eta$ ，不难看出最后学习到的w和b分别可以表示为：

下面给出感知机对偶形式的算法过程：

（1）a=0,b=0;

（2）选取训练集中的数据（xi，yi）；

（3）如果存在 $y_{i}(\sum{a_{j}y_{j}x_{j}\cdot x_{i}+b})\leqslant 0$ ，则进行跟新：

（4）转至（2）直至没有误分类数据。

对偶形式中的孙连实例仅仅以内积的形式出现，因此为了方便，可以预先将训练集中实例间的内积计算出来，并以矩阵形式存储起来，这个矩阵就是所谓的Gram矩阵：

以上就是对感知机算法的全部内容的讲解，这个算是对算法讲解的第一篇文章，打字辛苦，希望大家能够喜欢并支持一下~

下一篇文章将给出感知机的实现程序，有需要的小伙伴可以去取~

每天进步一点点~

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)