感知机

感知机（perceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取$+1$和$-1$二值。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。

感知机模型

定义

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

$$
f(x)=sign(w\cdot{x}+b)
$$

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

$$
sign(x)= \begin{cases}
+1, & x \geq 0 \
-1, & x < 0
\end{cases}
$$

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

感知机其实就是寻找一个超平面$w\cdot{x}+b=0$将特征空间划分成为两个部分。位于超平面两侧的点分别被分为正负两类。

感知机学习策略

数据集的线性可分性定义

给定一个数据集

$$
T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)},
$$

其中，$x_i\in{X}=R^n, y_i\in{Y}={+1,-1}, i=1,2,\cdots,N$，如果存在某个超平面能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，即对所有$y_i=+1$的实例$i$，有$w\cdot{x}+b>0$；对所有$y_i=-1$的实例$i$，有$w\cdot{x}+b<0$，则称数据集$T$是线性可分数据集(linear separable data set)；否则称数据集$T$线性不可分。

学习策略

损失函数是误分类点到超平面$S$的总距离，首先写出输入空间$R^n$中任一点$x_0$到超平面$S$的距离：

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

其中，$||w||$是$w$的$L_2$范数。
其次，对于误分类的数据$(x_i,y_i)$来说，有$-y_i(w\cdot{x}+b)>0$成立。因此误分类点$x_i$到超平面$S$的距离也可以表示成：

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

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

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

不考虑$\frac{1}{||w||}$就得到了感知机学习的损失函数。

给定训练数据集

$$
T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)},
$$
其中，$x_i\in{X}=R^n, y_i\in{Y}={+1,-1}, i=1,2,\cdots,N$。感知机$sign(w\cdot{x}+b)$学习的损失函数定义为

$$
L(w,b)=-\sum_{x_i\in{M}}y_i(w\cdot{x_i}+b)
$$
其中，$M$是误分类点的集合。

感知机学习算法

感知机学习算法有原始形式和对偶形式两种。

原始形式

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

$$
T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)},
$$
其中，$x_i\in{X}=R^n, y_i\in{Y}={+1,-1}, i=1,2,\cdots,N$，求解参数$w,b$，使其为以下损失函数最小化问题的解

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

其中，$M$是误分类点的集合。

感知机学习算法是误分类驱动的，具体采用随机梯度下降法（stochastic gradient descent）。

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

输入：训练数据集$T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)}$，
其中，$x_i\in{X}=R^n, y_i\in{Y}={+1,-1}, i=1,2,\cdots,N$；学习率$\eta(0<\eta\le{1})$；
输出：$w,b$；感知机模型$f(x)=sign(w\cdot{x}+b)$。
（1） 选取初值$w_0,b_0$；
（2） 在训练集中选取数据$(x_i,y_i)$；
（3） 如果$y_i(w\cdot{x}+b)\le{0}$，即$x_i$是误分类的点，那么

$$
w\leftarrow{w+\eta{y_ix_i}}\
b\leftarrow{b+\eta{y_i}}
$$

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

算法收敛性

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

定理 设训练数据集$T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)}$是线性可分的，其中存在$x_i\in{X}=R^n, y_i\in{Y}={+1,-1}, i=1,2,\cdots,N$，则
（1）存在满足条件$||\hat{w}{opt}||=1$的超平面$\hat{w}{opt}\cdot{\hat{x}}=\hat{w}{opt}\cdot{x}+b{opt}$将训练数据集完全正确分开；且存在$\gamma>0$，对所有$i=1,2,\cdots,N$

$$
y_i(\hat{w}_{opt}\cdot{\hat{x_i}})=y_i(\hat{w}{opt}\cdot{x}+b{opt})\geq\gamma
$$

（2）令$R=max_{1\le{i}\le{N}}$，则感知机算法的原始形式在训练集上的误分类次数$k$满足不等式

$$
k\le(\frac{R}{\gamma})^2
$$

即表示训练次数有上届，能够在有限次训练中找到将数据集完全正确划分的超平面。详细证明可以阅读《统计学习方法》。

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

对偶形式的基本思想是将$w$和$b$表示成实例$x_i$和标记$y_i$的线性组合的形式，通过求解其系数而求得$w$和$b$。
对于误分类点，更新$w$和$b$如下：

$$
w\leftarrow{w+\eta{y_ix_i}}\
b\leftarrow{b+\eta{y_i}}
$$

逐步更新$w,b$，假设更新$n$次，则$w,b$关于$(x_i,y_i)$的增量分别是$\alpha_iy_ix_i$和$\alpha{y_i}$，这个$\alpha_i=n_i\eta$。这样从学习过程不难看出，最后学习到的$w,b$可以分别表示为

$$
w=\sum_{i=1}^N{\alpha_iy_ix_i}\
b=\sum_{i=1}^N{\alpha_iy_i}
$$

这里，$a_i\ge0,i=1,2,\cdots,N$，当$\eta=1$时，表示第$i$个实例点由于误分而进行更新的次数。实例点更新次数越多，意味着它距离分离超平面越近，也越难正确分类。

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

输入：训练数据集$T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)}$，
其中，$x_i\in{X}=R^n, y_i\in{Y}={+1,-1}, i=1,2,\cdots,N$；学习率$\eta(0<\eta\le{1})$；
输出：$\alpha,b$；感知机模型$f(x)=sign({\sum_{j=1}^N{\alpha_jy_jx_j}}\cdot{x}+b)$。其中，$\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)^T$。
（1）$\alpha\leftarrow0,b\leftarrow0$
（2）在训练集中选取数据$(x_i,y_i)$
（3）如果$y_i({\sum_{j=1}^N{\alpha_jy_jx_j}}\cdot{x}+b)\le0$

$$
\alpha_i\leftarrow\alpha_i+\eta \
b\leftarrow{b+\eta{y_i}}
$$

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