统计学习方法(二)——感知机

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

第2章 感知机

感知机（perceptron）是二分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1值。感知机将实例分为正负两类的分离超平面，属于判别模型。感知机旨在求出将训练数据进行线性可分的分离超平面，根据损失函数用梯度下降法对损失函数进行极小化，求的感知机模型。

2.1 感知机模型

感知机定义

假设输入空间是$x \in R^n$，输出空间是$y=\lbrace +1,-1 \rbrace$，输入$x \in X$是实例的特征向量，是输入空间的点，输出$y \in Y$表示实例的类别，输入输出之间的映射函数为：

$$f(x)=sign(w * x + b)$$

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

$$sign(x)= \begin{cases} +1，x \geq 0 \\ -1，x \lt 0 \end{cases}$$

感知机是一种线性分类模型，属于判别模型。感知机模型的假设空间是定义在特征空间中的所有线性分类模型（linear classification model）或线性分类器（linear classifier），即函数集合$\lbrace f|f(x) = w * x + b\rbrace$。感知机的几何解释为：线性方程

$$w * x + b = 0$$

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

2.2 感知机学习策略

2.2.1 数据集的线性可分性

线性可分性

给定一个数据集$T = {(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$，其中$x_i \in X = R^n$，$y \in Y=\lbrace +1,-1 \rbrace$，$i=1,2,…,N$，如果存在超平面S

$$w * x + b = 0$$

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

2.2.2 感知机学习策略

假定训练数据集是线性可分的，感知机的学习目标是求得一个能将训练集正负实例点完全正确分开的分离超平面。为了找出超平面，即确定模型参数w，b，需要确定学习策略，即定义损失函数并将损失函数最小化。损失函数的一个自然选择是分类点的错误数。但这样的损失函数不是连续可导函数，不易优化。因此感知机采用误分类点到超平面S的总距离作为损失函数。输入空间中任意一点$x_0$到超平面S的距离为：

$$\frac {1} {||w||} |w * x_0 + b|$$

$||w||$为w的$L_2$范数。对于误分类的数据$(x_i,y_i)$，$-y_i(w * x + b) \lt 0$始终成立。因此，误分类点$x_i$到超平面S的距离为：

$$-\frac {1} {||w||} y_i(w * x_i + b)$$

假设误分类点集合为M，M到超平面S的总距离为

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

去掉$||w||$，就得到了感知机的损失函数。感知机${sign}(w * x + b)$的损失函数为

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

损失函数L(w,b)是非负的，如果没有误分类点，损失函数为0。误分类点离超平面越近，损失函数值越小。

2.3 感知机学习算法

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

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

感知机是对以下最优化问题的算法。给定一个训练数据集$T = {(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$，其中$x_i \in X = R^n$，$y \in Y=\lbrace +1,-1 \rbrace$，$i=1,2,…,N$，求参数w，b，使其为以下损失函数极小化问题的解

$${min}_{w,b} L(w,b) = -\sum_{x_i \in M} y_i(w * x_i + b)$$

其中M为误分类点的集合。感知机学习算法是通过误分类驱动的，具体采用随机梯度下降法（stochastic gradient descent）。首先，选取任意一个超平面$w_0，b_0$，然后用梯度下降法不断的极小化目标函数。极小化过程不是一次使M中的所有误分类点的梯度下降，而是一次随机选择一个误分类点使其梯度下降。

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

$$\nabla_wL(w,b)=-\sum_{x_i \in M} y_ix_i$$

$$\nabla_bL(w,b)=-\sum_{x_i \in M} y_i$$

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

$$w \longleftarrow w + \eta y_ix_i$$
$$b \longleftarrow b + \eta y_i$$

式子中$\eta(0 < \eta \le 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 \in Y=\lbrace +1,-1 \rbrace$，$i=1,2,…,N$，学习率$\eta(0<\eta \le 1)$；输出w，b；感知机学习模型$f(x) = {sign}(w * x + b)$。

(1) 选取初值$w_0，b_0$
(2) 在训练集中选取数据$(x_i,y_i)$
(3) 如果$y_i(w * x_i + b) \le 0$

$$w \longleftarrow w + \eta y_ix_i$$

$$b \longleftarrow b + \eta y_i$$
(4) 转至(2)，知道训练集中没有误分类点。

解释：当一个实例点被误分类，即位于分离超平面的错误一侧时，则调整w，b的值，使分离超平面向该误分类点的一侧移动，以减少改误分类点与超平面间的距离，直至超平面越过该分类点使其被正确分类。

2.3.2 算法的收敛性

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

证明略。

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