【课程学习】《统计学习方法》之感知机

  感知机（perceptron）是一种二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，通常取$+1$和$-1$两值。感知机学习目的是求出将训练数据进行线性划分的分离超平面。

感知机模型

超平面

  对于超平面，我们常用以下的方程来表示：
$$\omega\cdot x+b=0$$
  其中，$\omega$是超平面的法向量，这决定超平面的方向，$b$是超平面的截距，决定超平面到原点的距离。
  一般来说，超平面维度都大于3。百度百科上解释超平面是$n$维空间到$n-1$维空间的映射，因为超平面的自由度比空间维数小1，其中自由度大体是指给多少分量值才可以确定位置。
  超平面将一个空间划分成两部分，位于两部分的点分别被分成正、负两类，这也恰好说明了感知机是一种二类分类的线性分类器。

模型

  假设特征空间是$X\subseteq {R}^{n}$，输出空间是$Y={+1,-1}$。则感知机模型是由输入空间到输出控件的如下函数：
$$f(x)=sign(\omega \cdot  x + b) $$
  其中，$\omega \in {R}^{n}$被称为权值或权值向量，$b \in {R}^{n}$被称为偏置。$\omega \cdot  x$为$\omega$和$x$的内积，$sign$是符号函数，两者的具体计算公式如下：
$$\omega \cdot  x= \omega_1x_1+\omega_2x_2+…+\omega_nx_n$$
$$sign(x)=\left\{\begin{matrix}
+1 & x\geq 0 & 超平面上或正面 \\
-1 & x < 0 & 超平面的背面
\end{matrix}\right.$$

感知机学习策略

数据集的线性可分性

假设给定一个数据集，如果存在某个超平面能将数据集中的正实例点和负实例点正确地划分到数据集的两侧，则称这个数据集是线性可分数据集，否则称这个数据集线性不可分。

感知机学习策略

  之前提过，策略是评判一个模型的标准。感知机的学习目标是求得一个能够正确分离数据点的分离超平面。而为了找到这样的一个超平面，即确定超平面的参数$omega$和$b$，我们需要确定一个学习策略。
  输入空间中的任何一个点$x_0$到超平面的距离为：
$$\frac{1}{\begin{Vmatrix}
\omega
\end{Vmatrix}}\begin{vmatrix}
\omega \cdot {x}_{0} +b
\end{vmatrix}$$
  而对于误分类点来说，
$$-y_i(\omega \cdot x_i +b)>0$$
  所以我们可以将误分类点到超平面的距离统一写成如下形式：
$$-\frac{1}{\begin{Vmatrix}
\omega
\end{Vmatrix}} y_i(\omega \cdot x_i +b)$$
  所以，假设超平面的误分类点集合为$M$，所有误分类点到超平面的距离总和为：
$$-\frac{1}{\begin{Vmatrix}
\omega
\end{Vmatrix}}\sum_{x_i \in M}^{} y_i(\omega \cdot x_i +b)$$
  不考虑$\frac{1}{\begin{Vmatrix}
\omega
\end{Vmatrix}}$，就可以得到感知机的损失函数为：
$$L(\omega ,b)=-\sum_{x_i \in M}^{} y_i(\omega \cdot x_i +b)$$
  显然，损失函数$L(\omega ,b)$是非负的。如果没有误分类点，则损失函数的值为0.误分类点个数越少，误分类点离超平面越近，损失函数值就越小。一个特定样本点的损失函数：在误分类时是参数$\omega$、$b$的线性函数，在正确分类时是0.因此，对于给定的训练数据集$T$，损失函数$L(\omega ,b)$是$\omega$、$b$的连续可导函数。

感知机学习算法

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

  感知机学习算法是误分类驱动的，要想最小化感知机的损失函数，可以采用随机梯度下降算法。梯度下降算法在coursera上的Machine Learning课程的一开始有很详细的讲解。

  感知机学习算法的原始形式
输入：训练数据集$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)$;
输出：$\omega ,b$；感知机模型$f(x)=sign(\omega \cdot  x + b)$
(1) 选取初始值$\omega _0, b_0$
(2) 在训练集中选取数据$(x_i, y_i)$     （2、3两步是根据误分类点调整参数，一般我们选点还是按照1至N的顺序选）
(3) 如果$y_i(\omega \cdot x_i +b)\leq 0$
$$\omega \leftarrow \omega +\eta y_ix_i$$
$$b\leftarrow b +\eta y_i$$
(4) 转至(2)，直至训练集中没有误分类点

  这个算法直观上有如下解释：当一个实例点被误分类，就调整参数值，让超平面向该误分类点移动，以减少两者之间的距离，直到超平面将该误分类点正确分类。

算法的收敛性

  用变量$\hat{\omega }$ 表示$(\omega ^T, b)^T$。这里存在两个定理（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）存在满足条件$\begin{Vmatrix}
\hat{\omega _{opt}}
\end{Vmatrix}=1$的超平面$\hat{\omega _{opt}\cdot \hat{x}=\omega _{opt}\cdot x + b_{opt}=0$将训练数据集完全分开；且存在$\gamma >0$，对所有$i=1,2,…，N$，有
$$y_i (\hat{\omega _{opt}\cdot \hat{x_i})=y_i(\omega _{opt}\cdot x_i + b_{opt})\geq \gamma $$
  （2）令$R=\max \begin{Vmatrix}
\hat{x_i}
\end{Vmatrix}$，则原始感知机算法在训练数据集上的误分类次数$k$满足不等式
$$k\leq (\frac{R}{\gamma })^2$$
  这个定理表示，误分类次数是有上界的，所以当训练数据集线性可分时，感知机学习算法的原始形式的收敛的。

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

  感知机的对偶形式的基本思想是，将参数$\omega ,b$用实例$x_i$和标记$y_i$的线性组合表示，通过求解其系数而得到参数$\omega ,b$。
$$\omega =\sum_{i=1}^{N}\alpha _iy_ix_i$$
$$b=\sum_{i=1}^{N}\alpha _i y_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)$;
输出：$\omega ,b$；感知机模型$f(x)=sign(\omega \cdot  x + b)$
其中，$\alpha =(\alpha _1,\alpha _2,…,\alpha _N)^T$
(1) 初始化$\alpha \leftarrow 0,b\leftarrow 0$
(2) 在训练集中选取数据$(x_i, y_i)$     （2、3两步是根据误分类点调整参数，一般我们选点还是按照1至N的顺序选）
(3) 如果$y_i(\sum_{N}^{j=1}\alpha _jy_jx_j\cdot x_i+b)\leq 0$
$$\alpha _i\leftarrow \alpha _i+\eta $$
$$b\leftarrow b +\eta y_i$$
(4) 转至(2)，直至训练集中没有误分类点

  在计算的时候，可以预先计算出训练集中实例之间的内积存储在矩阵中，这个矩阵就是Gram矩阵。