【Method】感知机

原理

感知机（perceptron）是二分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。

感知机对应于输入空间（特征空间）中将实例划分为正负两类的分类超平面，属于判别模型。

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

感知机学习算法具有简单而易于实现的优点，分为原始形式和对偶形式。

感知机预测是用学习得到的感知机模型对新的输入实例进行分类。

感知机1957年由Rosenblatt提出，是神经网络与支持向量机的基础。

感知机模型

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

\[f(x) = sign(w \bullet x +b)\]

称为感知机。其中，w和b为感知机模型参数，\(w \in R^n\)叫作权值（weight）或权值向量（weight vector），\(b \in R\)叫作偏置（bias），\(w \bullet x\)表示w和x的内积。sign是符号函数。

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

感知机有如下集合解释：线性方程

\[w \bullet x + b =0\]

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

感知机学习，由训练数据集（实例的特征向量及类别）

\[T = {(x_1, y_1),(x_2, y_2), ...,(x_N,y_N)}\]

其中，\(x_i \in X = R^n, y_i \in Y = {+1, -1}, i=1,2,...,N\)，求得感知机模型，即求得模型参数w，b。感知机预测，通过学习得到的感知机，对于新的输入实例给出其对应的输出类别。

数据集的线性可分性

数据集的线性可分性：给定一个数据集

\[T = {(x_1, y_1),(x_2, y_2), ...,(x_N,y_N)}\]

其中，\(x_i \in X = R^n, y_i \in Y = {+1, -1}, i=1,2,...,N\)，如果存在某个超平面S

\[w \bullet x + b =0\]

能够将数据集的正实例点与负实例点完全正确地划分到超平面的两侧，即对所有\(y_i = +1\)的实例i，有\(w \bullet x + b >0\)，对所有\(y_i = -1\)的实例i，有\(w \bullet x + b <0\)，则称数据集T为线性可分数据集（linearly separable data set）；否则，称数据集T线性不可分。

感知机学习策略

假设训练数据是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点与负实例点完全正确分开的分类超平面。为了找出这样的超平面，即确定感知机模型参数w，b，需要确定一个学习策略，即定义（经验）损失函数并将损失函数极小化。

损失函数的一个自然选择是误分类点的总数。但是，这样的损失函数不是参数w，b的连续可导函数，不易优化。损失函数的另一个选择是误分类点到超平面S的总距离，这是感知机所采用的。为此，首先写出输入空间\(R^n\)中任一点\(x_0\)到超平面S的距离：

\[\frac{1}{\| w \|} \mid w \bullet w_0 + b \mid\]

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

其次，对于误分类的数据\((x_i, y_i)\)来说，

\[-y_i(w \bullet x_i +b) > 0\]

成立。因为当\(w \bullet x_i +b > 0\)时，\(y_i = -1\)，而当\(w \bullet x_i +b < 0\)时，\(y_i = +1\)。因此，误分类点\(x_i\)到超平面S的距离是

\[-\frac{1}{\| w \|} y_i(w \bullet x_i +b)\]

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

\[-\frac{1}{\| w \|}\sum_{x_i \in M} y_i(w \bullet x_i +b)\]

不考虑\(\frac{1}{\| w \|}\)，就得到感知机学习的损失函数（在支持向量机中称为样本点的函数间隔）。

给定训练集

\[T = {(x_1, y_1),(x_2, y_2), ...,(x_N,y_N)}\]

其中，\(x_i \in X = R^n, y_i \in Y = {+1, -1}, i=1,2,...,N\)，感知机\(sign(w \bullet x +b)\)学习的损失函数定义为

\[L(w,b)= -\sum_{x_i \in M} y_i(w \bullet x_i +b)\]

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

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

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

感知机学习算法

感知机学习问题转化为求解损失函数式的最优化问题，最优化的方法是随机梯度下降法。

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

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

\[T = {(x_1, y_1),(x_2, y_2), ...,(x_N,y_N)}\]

其中，\(x_i \in X = R^n, y_i \in Y = {+1, -1}, i=1,2,...,N\)，求参数w，b，使其为以下损失函数极小化问题的解

\[min_{w,b} L(w,b) = -\sum_{x_i \in M} y_i(w \bullet x_i +b)\]

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

感知机学习算法是误分类驱动的，具体采用随机梯度下降法（stochastic gradient descent）。首先，任意选取一个超平面\(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 \gets w + \eta y_i x_i\] \[b \gets b + \eta y_i\]

式中\(\eta(0 < \eta \leq 1)\)是步长，在统计学习中又称为学习率（learning rate）。这样，通过迭代可以期待损失函数L(w,b)不断减小，直到为0。综上所述，得到如下算法：

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

输入： 训练数据集\(T = {(x_1, y_1),(x_2, y_2), ...,(x_N,y_N)}\)，其中，\(x_i \in X = R^n, y_i \in Y = {+1, -1}, i=1,2,...,N\)；学习率\(\eta(0 < \eta \leq 1)\)；

输出： w，b；感知机模型\(f(x) = sign(w \bullet x +b)\)

(1) 选取初值\(w_0,b_0\)

(2) 在训练集中依次选取数据\((x_i, y_i)\)

(3) 如果\(y_i(w \bullet x_i +b) \leq 0\)

\[w \gets w + \eta y_i x_i\] \[b \gets b + \eta y_i\]

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

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

感知机学习算法由于采取不同的初值或选取不同的误分类点，解可以不同。

算法的收敛性

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

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

Novikoff定理：设训练数据集\(T = {(x_1, y_1),(x_2, y_2), ...,(x_N,y_N)}\)是线性可分的，其中，\(x_i \in X = R^n, y_i \in Y = {+1, -1}, i=1,2,...,N\)，则

(1) 存在满足条件\(\| \hat{w}_{opt} \| =1\)的超平面\(\hat{w}_{opt} \bullet \hat{x} = w_{opt} \bullet x +b_{opt} = 0\)将训练数据集完全正确分开；且存在\(\gamma >0\)，对所以i=1,2,…,N

\[y_i(\hat{w}_{opt} \bullet \hat{x}) = y_i(w_{opt} \bullet x +b_{opt}) \geq \gamma\]

(2) 令\(R=max_{1 \leq i \leq N} \| \hat{x_i} \|\)，则感知机算法在训练集上的误分类次数k满足不等式

\[k \leq (\frac{R}{\gamma})^2\]

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

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

感知机学习算法的原始形式和对偶形式与支持向量机学习算法的原始形式和对偶形式相对应。

对偶形式的基本想法是，将w和b表示为实例\(x_i\)和标记\(y_i\)的线性组合的形式，通过求解其系数而求得w和b。不失一般性，可假设初始值\(w_0, b_0\)均为0.对误分类点\((x_i, y_i)\)通过

\[w \gets w + \eta y_i x_i\] \[b \gets b + \eta y_i\]

逐步修改w,b，设修改n次，则w,b关于\((x_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 \geq 0, i=1,2,...,N\)，当\(\eta = 1\)时，\(n_i\)表示第i个实例点由于误分而进行更新的次数。实例点更新次数越多，意味着它距离分离超平面越远，也就越难正确分类。换句话说，这样的实例对学习结果影响最大。

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

输入： 训练数据集\(T = {(x_1, y_1),(x_2, y_2), ...,(x_N,y_N)}\)，其中，\(x_i \in X = R^n, y_i \in Y = {+1, -1}, i=1,2,...,N\)；学习率\(\eta(0 < \eta \leq 1)\)；

输出： \(\alpha,b\)；感知机模型\(f(x) = sign(\sum_{j=1}^N \alpha_j y_j x_j \bullet x +b)\)

其中\(\alpha = (\alpha_1, \alpha_2, ..., \alpha_N)^T\)

(1) \(\alpha \gets 0, b gets 0\)

(2) 在训练集中依次选取数据\((x_i, y_i)\)

(3) 如果\(y_i(\sum_{j=1}^N \alpha_j y_j x_j \bullet x +b) \leq 0\)

\[\alpha_i \gets \alpha_i + \eta\] \[b \gets b + \eta y_i\]

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

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

\[G=[x_i \bullet x_j]_{N \times N}\]

参考文献

• 统计学习方法 李航 第2章