[强基计划] 统计学习方法之感知机Perceptron

感知机

2.1 感知机模型

感知机模型属于一种判别模型，感知机的定义如下：

（定义2.1）感知机：假设输入空间（特征空间）为 $X\subseteq R^n$ ，输出空间为y={+1,-1}，那么函数:
$f(x)=sign(w\cdot x+b) \tag {2.1}$
被称为感知机，可见感知机的本质就是一个符号化函数，其中：
$sign(x)=\left\{ \begin{array} +1, x\ge 0,\\ -1, x<0. \end{array} \right. \tag {2.2}$
显然，感知机是一种线性分类器。

2.2 数据集的线性可分特性，感知器学习方法

（定义2.2）数据集的线性可分性：对一个数据集 $T=\{(x_1,y_1),(x_2,y_2),(x_N,y_N)\}$ ，其中， $x_i \in X \subseteq R^n$ ， $y_i \in \{+1,-1\}$ , 如果存在某一个超平面S，使 $w\cdot x+b=0$ 能够把数据的正实例与负实例完全正确划分，那么我们就说这个数据集是线性可分的。

在数据集可以被线性区分的前提下，我们开始设计感知机的损失函数。一个非常直观的想法是用区分错误的点来作为感知机损失函数的依据。如果使用区分错误的点的总数作为损失函数的话，的确可以优化感知机，但是无法微分，很难快速进行优化。目前的感知机采用误分类的点到超平面S的距离作为损失函数，它的表达式很容易推导，首先，对输入的样本中任意一点 $x_0 \in R^n$ ，根据距离公式得：
$distance = \frac{1}{||w||}|w\cdot x_0+b| \tag{2.3}$
也就是它到超平面的距离等于它代入平面方程计算出的绝对值，除以超平面法向量的内积（ $L_2$ 范数 norms）。对于误分类的数据 $(x_i,y_i)$ 来说，如果它是+，错误的分到了-，那么有
$-y_i(w\cdot x_i+b)→-\times+\times->0 \tag{2.4}$
同理，上式对-分为+也有效，之所以求这个是为了说明绝对值的微分情况，于是对点 $x_i$ ，(2.3)式脱绝对值有：
$distance = -\frac{1}{||w||}(w\cdot x_i+b)$
误分类的点（集合M）的总距离就为
$distance_{all}=-\frac{1}{||w||}\sum_{x_i\in M}y_i(w\cdot x_i+b) \tag{2.5}$
由于 $-\frac{1}{||w||}$ 为常数，所以在偏导数运算中可以忽略。故有最终的Loss 函数：
$L(w,b)=-\sum_{x_i \in M}y_i(w\cdot x_i+b) \tag {2.6}$
其实损失函数也可以为负数，不过优化方向就有点诡异（不断增大），这样还不如设定为正方便。

2.3 感知机的学习算法

感知机的学习算法其实就是要达成一个目标，使
$\min\limits_{w,b} L(w,b)=-\sum_{x_i \in M} y_i(w\cdot x+b) \tag{2.7}$
通用的感知器学习算法是误分类驱动的（误分类调整损失函数），并使用随机梯度下降方法（stochastic gradient descent）。算法初始条件是超平面 $w_0,b_0$ 。对于固定的误分类点集合M，损失函数的梯度为（对上面的w，b进行微分）：
$\triangledown_w L(w,b)= -\sum_{x_i\in M} y_ix_i \tag{2.8}$

$\triangledown_b L(w,b)=-\sum_{x_i \in M} y_i \tag {2.9}$

之所以叫随机梯度下降算法，是因为它每次随机选取一个误分类点 $(x_i,y_i)$ ，对w,b进行更新，如下：
$w \leftarrow w+\eta y_i x_i \tag{2.10}$

$b\leftarrow b +\eta y_i \tag {2.11}$

你可能会疑惑 $\eta$ 是什么，它是学习率（learning rate），调整内部参数更新的速度，属于超参数。

感知机算法将会运行直到误分类集合M清空。（也可能提前被炼丹师终止）。感知机所得到的解不一定相同（求一个试试，比如 $x_1 = (2,2)^T +, x_2 = (1.0)^T -$ .

感知机算法是收敛的（经过有限次迭代在线性可分数据集可以得到解），记 $\hat w = (w^T,b)^T$ , $\hat x=(x^T, 1)^T$ ，则 $\hat w \hat x = w\cdot x +b$ （线性代数的一种方法）。在此基础上，有定理2.1 （Novikoff)。它说明，存在 $w_{opt}，\gamma$ ，可以正确区分T中所有数据，（满足 $\hat w_{opt} \hat x=0$ )使得对所有的i=1,2,...,N，点 $x_i$ ，有
$y_i(\hat w_{opt}\cdot \hat x_i)=y_i (w_{opt}\cdot x_i + b_{opt})\ge \gamma \tag{2.12}$
令 $R=\max\limits_{1\le i\le N}||x_i||$ ，则感知机的误分类次数应该满足 $k\le (\frac{R}{\gamma})^2$ 。证明如下：

对于线性可分的数据集，显然是存在 $\hat w_{opt}$ 的，但怎么理解 $\hat w_{opt} \hat x=0$ 时候却有(2.12)成立呢？其实我们由之前的定义知道， $\hat x =(x^T,1)^T$ ，这样只要调整b，使 $||\hat w_{opt}||$ =1，那么对于有限的i=1，2，...，N，显然
$y_i(\hat w_{opt} \cdot \hat x_i) >0$
因为数据都被正确分类，所以自然标签和分类结果的符号一致，所以必定>0,这样，只要取 $\gamma = \min\limits_i \{y_i(\hat w_{opt}\cdot \hat x_i)\}$ ，那么就可以确保(2.12)式子成立。

（2）对于第k-1次误分类，由(2.4)有
$y_i(\hat w_{k-1}\cdot \hat x_i)=y_i(w_{k-1}\cdot x_i + b_{k-1}) \le 0 \tag {2.13}$
这样，w,b的权值更新为：
$w_k \leftarrow w_{k-1}+\eta y_i x_i$

$b_k \leftarrow b_{k-1} + \eta y_i$

综合上面两个式子为向量，也就是
$\hat w_k \leftarrow \hat w_{k-1} + \eta y_i \hat x_i \tag {2.14}$
假设 $\hat w_{opt}$ 存在，那么由(2.14),(2.12)有
$\hat w_k \cdot \hat w_{opt} = \hat w_{k-1} \cdot \hat w_{opt} + \eta y_i \hat w_{opt} \cdot \hat x_i \ge \hat w_{k-1}\cdot \hat w_{opt} + \eta \gamma$
由，数学归纳法有
$\hat w_k \cdot \hat w_{opt} \ge \hat w_{k-1} \cdot \hat w_{opt} +\eta\gamma \ge \hat w_{k-2} \cdot \hat w_{opt} +2\eta\gamma \ge ... \ge k\eta\gamma \tag {2.15}$
由(2.13)和(2.14)，可以得到另一个不等式
$||\hat w_k||^2 = ||\hat w_{k-1}||^2+2\eta y_i \hat x_i \hat w_{k-1}+\eta^2 ||\hat x_i||^2 (因为y_i 的平方为1)\le \\ ||\hat w_{k-1}||^2 +\eta^2 ||x_i||^2 \le ||\hat w_{k-1}||^2 + \eta^2R^2\le(重复以上操作)||\hat w_{k-2}||^2+2\eta^2R^2\le...\le k\eta^2R^2 \tag {2.16}$
结合(2.15)和(2.16)，我们可以发现，
$k\eta\gamma\le\hat w_k \hat w_{opt}\le||\hat w_k||||\hat w_{opt}||\le \sqrt{k}\eta R$

2.4 感知机学习的对偶形式

所谓对偶形式，其实是这样的：由之前的随机梯度下降方法，我们发现感知机根据误分类点修正超平面的方法是根据它的标签 $(x_i,y_i)$ 来达成的，假设修改n次，那么w,b关于 $(x_i,y_i)$ 的增量分别为 $\alpha_iy_ix_I$ 和 $\alpha_iy_i$ ，这里 $\alpha_i=n_i\eta$ ，这样，从学习过程可以发现，经过n次学习以后，w,b可以表示为：
$w=\sum^N_{i=1}\alpha_iy_ix_I \tag {2.17}$