第三章 感知机
感知机(perceptron)是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取$+1$和$-1$二值。
感知机对应于输入空间(特征空间)中将实例划分为正负两类的分离超平面，属于判别模型。
感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此，导入基于误分类的损失函数,利用梯度下降法对损失函数进行极小化，求得感知机模型。
感知机学习算法具有简单而易于实现的优点，分为原始形式和对偶形式。
感知机预测是用学习得到的感知机模型对新的输入实例进行分类。
1. 感知机模型
定义2.1（感知机）
定义$2.1$（感知机）：
假设输入空间（特征空间）是$X \subseteq R^n$，输出空间是$Y=\{+1,-1\}$。输入$x\in X$表示实例的特征向量，对应于输入空间（特征空间）的点；输出$y\in Y$表示实例的类别。
由输入空间到输出空间的如下函数：（感知机）
$$ f(x)=sign(w\cdot x + b) \tag {2.1} $$
$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\geq0 \\ -1,x<0 \end{cases} \tag{2.2} $$
感知机是一种线性分类模型,属于判别模型. 感知机模型的假设空间是定义在特征空间中的所有线性分类模型(linear classification model)或线性分类器(linear classifier),即函数集合$\{f|f(x)=w \cdot x+b\}$.
$f(x)=w\cdot x+b$
$y=kx+b$
感知机有如下几何解释:线性方程
$$ w \cdot x + b=0 \tag{2.3} $$
对应于特征空间$R^n$中的一个超平面S,其中$w$ 是超平面的法向量,$b$ 是超平面的截距.
这个超平面将特征空间划分为两个部分.位于两部分的点(特征向量)分别被分为正、负两类. 因此, 超平面S称为分离超平面(separating hyperplane).
简答推导$$ w=(w_1,w_2);x=(x^{(1)},x^{(2)});\\ w \cdot x+b=0 \rightarrow w_1x^{(1)}+w_2x^{(2)}+b=0\\ 得：x^{(2)}=-\frac{w_1}{w_2}x_1-\frac{b}{w_2}\\ A点(0,-b/w_2)\\ B点(-b/w_1,0)\\ 已设定w向上(指向\:0)为正方形。所以w_1,w_2>0。得到-b>0,\\ 所以\: OC=\frac{-B}{\lVert w\rVert_2},d=\frac{\lvert b \rvert}{\sqrt{w_1^2+w_2^2}}=-\frac{b}{\lVert w \rVert_2} $$
感知机学习，由训练数据集（实例的特征向量及类别）
$$ 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$，求得感知机模型$(2.1)$，即求得模型参数$w,b$。
感知机预测，通过学习得到的感知机模型，对于新的输入实例给出其对应的输出类别。
2. 感知机的学习策略
数据集的线性可分性
定义2.2（数据集的线性可分性）
定义$2.2$（数据集的线性可分性）：给定一个数据集
$$ 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_i+b<0$，则称数据集T为线性可分数据集（linearly separable data set）；否则，称数据集T线性不可分。
感知机学习策略
假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确的分离超平面。为了找出这样的超平面，即确定感知机模型参数$w, b$，需要确定一个学习策略，即定义（经验）损失函数并将损失函数极小化。
损失函数的一个自然选择是误分类点的总数。但是，这样的损失函数不是参数$w，b$的连续可导函数，不易优化。损失函数的另一个选择是误分类点到超平面S的总距离，这是感知机所采用的。
为此，首先写出输入空间$R^n$中任一点$x_0$到超平面S的距离:
$$ \frac{1}{\lVert w \rVert} \lvert w \bullet x_0 + b\rvert $$
这里，[bsmark]$\lVert w \rVert$是$w$的$L_2$范数[/bsmark]。
其次，对于误分类的数据$(x_i,y_i)$来说
$$ -y_i(w\bullet x_i+b)>0 $$
且$y_i=\pm 1$。其实$-y_i(w\bullet x_i+b)=\lvert w\bullet x_i+b\rvert$成立。因为当$w\bullet x_i+b>0$时，$y_i=\pm 1$。因此，误分类点$x_i$到超平面S的距离是
$$ -\frac{1}{\lVert w \rVert}y_i(w\bullet x_i+b) $$
这样，假设超平面S的误分类点集合为M，那么所有误分类点到超平面S的总距离为
$$ -\frac{1}{\Vert w \rVert}\sum_{x_i\in M}y_i(w\bullet x_i+b) $$
不考虑$\frac{1}{\lVert w\rVert}$，就得到感知机学习的损失函数$^①$。
给定训练数据集
$$ 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) \tag{2.4} $$
其中M为误分类点的集合。这个损失函数就是感知机学习的经验风险函数。
显然，损失函数$L(w,b)$是非负的。如果没有误分类点，损失函数值是0。而且，误分类点越少，误分类点离超平面越近，损失函数值就越小。一个特定的样本点的损失函数：在误分类时是参数$(w,b)$的线性函数，在正确分类时是0。因此，给定训练数据集T，损失函数$L(w,b)$是$w,b$的连续可导函数。
感知机学习的策略是在假设空间中选取使损失函数式$(2.4)$最小的模型参数$w,b$，即感知机模型。
假设空间：
$$ \begin{cases} w\bullet x+b=0\\ w_1,b_1\\ w_2,b_2\\ ...\\ w_n,b_n \end{cases} $$
范数||x||
[bsmark]$\lVert x \rVert$默认为x得2范数[/bsmark]
$$ \begin{aligned} \lVert x \rVert _n &= \sqrt[n]{(|x_1|^2+|x_2|^2+...+|x_n|^2)} \qquad n\geq1 \\ \lVert x\rVert_\infty &=\mathop{max}\limits_{1\leq i\leq n}|x_i| \qquad 取向量的最大值。\\ \end{aligned} $$
- 0范数：向量中非零元素的个数。
- 1范数： 为绝对值之和。
- 2范数： 通常意义上的模。
- 无穷范数：取向量的最大值。
3. 感知机学习算法—原始形式
感知机学习问题转化为求解损失函数$(2.4)$的最优化问题，最优化的方法是随机梯度下降法。
感知机学习算法的原始形式
感知机学习算法是对以下最优化问题的算法。给定一个训练数据集
$$ T=\{(x_1,y_2),(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$，使其为一下损失函数极小化问题的解
$$ \mathop{min}\limits_{w,b}L(w,b)=-\sum_{x_i\in M}y_i(w\bullet x_i+b) \tag{2.5} $$
其中M为误分类点的集合。
感知机学习算法是误分类驱动的，具体采用随机梯度下降法(stochastic gradient descent)。 首先，任意选取一个超平面$(w_0,b_0)$， 然后用梯度下降法不断地极小化目标函数$(2.5)$。极小化过程中不是一次使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 \tag{2.6} $$
$$ b \longleftarrow b+\eta y_i \tag{2.7} $$
式中$\eta(0< \eta \leq 1)$是步长，在统计学习中又称为学习率(learning rate)。这样，通过迭代可以期待损失函数$L(w,b)$不断减小，直到为0。综上所述，得到如下算法：
算法2.1 （感知机算法的原始形式）
算法2.1 （感知机算法的原始形式）
输入：训练数据集$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\leq1);$
输出：$w,b$;感知机模型$f(x)=sign(w\bullet x+b)$
- 选取初值$w_0,b_0$；
- 在训练集中选取数据$(x_i,y_i)$；
如果$y_i(w\bullet x_i+b) \leq 0$
$$ w_{n+1} \longleftarrow w_n+\eta y_ix_i\\ b_{n+1}\longleftarrow b_n+\eta y_i $$
- 转至 2，直至训练集没有误分类点。
这种算法直观上有如下解释：当一个实例点被误分类，即位于分离超平面的错误一侧时，则调整$w,b$的值，使分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面间的距离，直至超平面越过该误分类点使其被正确分类。
算法2.1是感知机学习的基本算法，对应于后面的对偶形式，称为原始形式。感知机学习算法简单且易于实现。
4. 感知机学习算法—原始形式算法的收敛性
现在证明，对于线性可分数据集感知机学习算法原始形式收敛，即经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型。
为了便于叙述与推导，将偏置[bsmark]$b$[/bsmark]并入权重向量[bsmark]$w$[/bsmark]，记作[bsmark]$\hat{w}=(w^T,b)^T$[/bsmark]，同样将输入向量加以扩充，加进常数[bsmark]1[/bsmark]，记作[bsmark]$\hat{x}=(x^T,1)^T$[/bsmark]。这样，[bsmark]$\hat{x}\in R^{n+1},\hat{w}\in R^{n+1}$[/bsmark]。显然，[bsmark]$\hat{w}\bullet \hat{x}=w\bullet x+b$[/bsmark]。
定理2.1（Novikoff）
定理2.1 (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$，则
[bsmark]$w_{opt} b_{opt}$精确解[/bsmark]
- 存在满足条件$\lVert \hat{w}_{opt}\rVert \bullet \hat{x}=w_{opt}\bullet x+b_{opt}=0$将训练数据集完全正确分开；且存在$\gamma >0$，对所有$i=1,2,...,N$
$$ y_i(\hat{w}_{opt}\bullet\hat{x}_i)=y_i(w_{opt}\bullet x_i+b_{opt}) \geq \gamma \tag{2.8} $$
- 令$R=\mathop{max}\limits_{l\leq i\leq N} \lVert\hat{x}_i\rVert$，则感知机算法$2.1$在训练数据集上的误分类次数$k$满足不等式
$$ k \leq(\frac{R}{\gamma})^2 \tag{2.9} $$
证明 $1.$ 由于训练数据集是线性可分的, 按照定义$2.2$，存在超平面可将训练数据集完全正确分开，取次超平面为$\hat{w}_{opt}\bullet \hat{x}=w_{opt}\bullet x+b_{opt}=0,使\lVert \hat{w}_{opt}\rVert =1$。由于对有限的$i=1,2,...,N$，均有
$$ y_i(\hat{w}_{opt}\bullet \hat{x}_i)=y_i(w_{opt}\bullet x_i+b_{opt})>0 $$
所以存在
$$ \gamma = \mathop{min}\limits_{i}\{y_i(w_{opt}\bullet x_i+b_{opt}) \} $$
使
$$ y_i(\hat{w}_{opt}\bullet \hat{x}_i)=y_i(w_{opt}\bullet x_i+b_{opt})\geq \gamma $$
证明$2.$ 感知机算法从$\hat{w}_0=0$开始，如果实例被误分类，则更新权重。令$\hat{w}_{k-1}$使第k个误分类实例之前的扩充权重向量，即
$$ \hat{w}_{k-1}=(w^T_{k-1},b_{k-1})T $$
则第k个误分类实例的条件是
$$ y_i(\hat{w}_{k-1}\bullet \hat{x}_i)=y_i(w_{k-1}\bullet x_i+b_{k-1}) \leq0 \tag{2.10} $$
若$(x_i,y_i)$是被$\hat{w}_{k-1}=(w^T_{k-1},b_{k-1})^T$误分类的数据，则$w$和$b$的更新是
$$ w_k \longleftarrow w_{k-1}+\eta y_ix_i\\ b_k \longleftarrow b_{k-1}+\eta y_i $$
即
$$ \hat{w}_k=\hat{w}_{k-1}+\eta y_i\hat{x}_i \tag{2.11} $$
下面推导两个不等式$(2.12)$及$(2.13)$：
$$ \hat{w}_k\bullet \hat{w}_{opt} \geq k\eta \gamma \tag{2.12} $$
由式$(2.11)$及式$(2.8)$得：
$$ \begin{aligned} \hat{w}_k\bullet\hat{w}_{opt} & = \hat{w}_{k-1}\bullet\hat{w}_{opt}+\eta y_i\hat{w}_{opt}\bullet\hat{x}_i\\ & \geq \hat{w}_{k-1}\bullet\hat{w}_{opt}+\eta \gamma \end{aligned} $$
由此递推即得不等式$(2.12)$
$$ \hat{w}_k\bullet\hat{w}_{opt}\geq\hat{w}_{k-1}\bullet\hat{w}_{opt}+\eta\gamma\geq\hat{w}_{k-2}\bullet\hat{w}_{opt}+2\eta\gamma\geq...\geq k\eta\gamma $$
$$ \lVert\hat{w}_k\rVert^2\leq k\eta^2\gamma^2\tag{2.13} $$
由式$(2.11)$及式$(2.10)$得
$$ \begin{aligned} \lVert\hat{w}_k\rVert^2 &=\lVert\hat{w}_{k-1}\rVert^2+2\eta y_i\hat{w}_{k-1\bullet\hat{x}_i}+\eta^2\lVert\hat{x}_i\rVert^2\\ &\leq \lVert\hat{w}_{k-1}\rVert^2+\eta^2\lVert\hat{x}_i\rVert^2\\ &\leq\lVert\hat{w}_{k-1}\rVert^2+\eta^2R^2\\ &\leq\lVert\hat{w}_{k-2}\rVert^2+2\eta^2R^2\leq\dots\\ &\leq k\eta^2R^2 \end{aligned} $$
$$ R=\max\lVert \hat{x}_i\rVert \\是误分类点，所以\quad 2\eta y_i\hat{w}_{k-1}\bullet\hat{x}_i\quad中 \hat{w}_{k-1}\bullet\hat{x}_i是一个正数\\ y_i是一个负数，所以整个是一个负数，可以看(2.10)，所以去掉以后左式小于等于右式 $$
结合不等式$(2.12)$及式$(2.13)$即得
$$ \begin{aligned} &k\eta\gamma\leq\hat{w}_k\bullet\hat{w}_{opt}\leq\lVert\hat{w}_k\rVert\:\lVert\hat{w}_{opt}\Vert\leq\sqrt{k}\,\eta R\\ &k^2\eta^2\leq kR^2 \end{aligned} $$
于是
$$ k\leq(\frac{R}{\gamma})^2 $$
定理表明，误分类的次数$k$是有上界的，经过有限次搜索可以找到将训练数据完全正确分开的分离超平面。
也就是说，当训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的。但是例2.1说明，感知机学习算法存在许多解，这些解既依赖于初值的选择，也依赖于迭代过程中误分类点的选择顺序。
为了得到唯一的超平面，需要对分离超平面增加约束条件。这就是第7章将要讲述的线性支持向量机的想法。
当训练集线性不可分时，感知机学习算法不收敛，迭代结果会发生震荡。
5. 感知机学习算法—对偶形式
现在考虑感知机学习算法的对偶形式。感知机学习算法的原始形式和对偶形式与第7章中支持向量机学习算法的原始形式和对偶形式相对应。
对偶形式的基本想法是，将$w$和$b$表示为实例$x_i$和标记$y_i$的线性组合的形式，通过求解其系数而求得$w$和$b$。
不失一般性，在$算法 2.1$中可假设初始值$w_o,b_o$均为0。对误分类点$(x_i,y_i)$通过
$$ \begin{aligned} w &\longleftarrow w+\eta y_ix_i\\ b &\longleftarrow b+\eta y_i \end{aligned} $$
逐步修改$w,b,$设修改$n$次，则$w,b$关于$(x_i,y_i)$的增量分别是$\alpha_iy_ix_i$和$\alpha_iy_i$，这里$\alpha_i=n_i\eta$。这样，从学习过程不难看出，最后学习到的$w,b$可以分别表示为
$$ w=\sum^N_{i=1}\alpha_iy_ix_i\tag{2.14} $$
$$ b=\sum^N_{i=1}\alpha_iy_i\tag{2.15} $$
这里，$\alpha_i\geq0,i=1,2,...,N$，当$\eta=1$时，表示第$i$个实例点由于误分而进行更新的次数。
实例点更新次数越多，意味着它距离分离超平面越近，也就越难正确分类。这样的实例对学习结果影响最大。
下面对照原始形式来叙述感知机学习算法的对偶形式。
算法2.2（感知机学习算法的对偶形式）
算法2.2（感知机学习算法的对偶形式）
输入：线性可分的数据集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N) \}$，其中$x_i\in R^n,y_i\in \{-1,+1\},i=1,2,...,N;$学习率$\eta(0<\eta\leq1);$
输出：$\alpha,b;$感知机模型$f(x)=sign(\sum^N_{j=1}\alpha_jy_jx_j\bullet x+b)$，其中$\alpha=(\alpha_1,\alpha_2,...,\alpha_N)^T$
- $\alpha\leftarrow0,b\leftarrow0$；
- 在训练集中选取数据$(x_i,y_i)$；
如果$y_i(\sum^N_{j=1}\alpha_jy_jx_j\bullet x_i+b)\leq0$，
$$ \begin{aligned} \alpha_i&\longleftarrow \alpha_i+\eta\\ b&\longleftarrow b+\eta y_i \end{aligned} $$
- 转至$2.$直到没有误分类数据。
对偶形式中训练实例仅以内积的形式出现。为了方便，可以预先将训练集中实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是所谓的Gram矩阵(Gram matrix)
$$ G=[x_i\bullet x_j]_{N\times N} $$