机器学习算法 原理、实现与实践 —— 感知机
感知机（perceptron）是二分类的线性分类模型，输入为特征向量，输出为实例的类别，取值+1和-1。感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此，引入了基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。
1. 感知机模型
假设输入空间（特征空间）是$\mathcal{X}\subset R^n$，输出空间是$\mathcal{Y}=\{-1,+1\}$。输入$x\in\mathcal{X}$表示实例的特征向量，对就于输入空间的点；输出$y\in\mathcal{Y}$表示实例的类别。由输入空间到输出空间的映射函数
$$f(x) = sign(w\cdot x+b)$$
称为感知机。其中，$w$和$b$为感知机的模型参数，$w\in R^n$叫作权值或权值向量，$b\in R$叫作偏置。$w\cdot x$表示内积。$sign$是符号函数，即
$$sign(x） = \begin{cases}+1, & x\ge0 \\ -1,& x < 0 \end{cases}$$
感知机模型的假设空间是定义在特征空间中的所有线性分类模型或线性分类器，即函数集合$\{f|f(x) = w\cdot x+b\}$。
感知机有如下几何解释：线性方程
$$w\cdot x+b = 0$$
对应于特征空间$R^n$中的一个超平面S，其他$w$是超平面的法向量，$b$是超平面的截距。这个超平面将特征空间划分为两个部分。位于两部分的点（特征向量）分别被分为正、负两类。因此，超平面S称为分离超平面（separating hyperplane）。
感知机学习的任务可以描述为：由训练数据集（实例的特征向量及类别）
$$T={(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)}$$
其中$x_i\in\mathcal{X}=R^n,\ y_i\in\mathcal{Y}=\{-1,+1\},\ i=1,2,\dots,N$，求得感知机模型，即求得模型参数$w,b$。感知机预测，通过学习到的感知机模型，对于新的输入实例给出其对应的输出类别。
2. 感知机的学习策略
假设训练数据集是线性可分的，感知机学习的目标就是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面。为了找出这样的超平面，即确定感知机的模型模型参数$w,b$，需要确定一个学习策略，即定义（经验）损失函数并将损失函数极小化。
损失函数的一个自然选择是误分类点的总数。但是，这样的损失函数不是参数$w,b$的连续可导函数，不易优化。损失函数的另一个选择是误分类点到超平面S的总距离，这是感知机所采用的。为此，首先写出输入空间$R^n$中任一点$x_0$到超平面S的距离。
$$\frac{1}{||w||}|w\cdot x_i +b|$$
这里，$||w||$是$w$的$L_2$范数。
其次，对于误分类的数据$(x_i,y_i)$来说
$$-y_i(w\cdot x_i +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)$$
忽略前面的系数$1/||w||$，就得到感知机学习的损失函数。
给定训练数据集
$$T={(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)}$$
其中$x_i\in\mathcal{X}=R^n,\ y_i\in\mathcal{Y}=\{-1,+1\},\ i=1,2,\dots,N$。感知机$sign(w\cdot x +b)$学习的损失函数定义为
$$L(w,b) = -\sum_{x_i\in M}y_i(w\cdot x_i + b)$$
其中$M$为误分类点的集合。这个损失函数就是感知机学习的经验风险函数。感知机学习的策略就是在假设空间中选择使损失函数$L(w,b)$最小的模型参数。
3. 感知机学习算法
感知机学习问题转化为求解损失函数最优化问题，最优化的方法是随机梯度下降法。
感知机学习算法是误分类驱动的，具体采用随机梯度下降算法（stochastic gradient descent）。首先，任意选择一个超平面$w_0,b_0$，然后用梯度下降法不断地极小化目标函数。极小化过程中不是一次使$M$中所有误分类点的梯度下降，而是一次随机选择一个误分类点使其梯度下降。
假设误分类点集合$M$是固定的，那么损失函数$L(w,b)$的梯度由
$$\nabla_w L(w,b) = - \sum_{x_i\in M}y_i x_i$$
$$\nabla_bL(w,b) = -\sum_{x_i \in M}y_i$$
给出。
随机选择一个误分类点$(x_i,y_i)$，对$w,b$进行更新：
$$w \gets w+ \eta y_i x_i$$
$$b \gets b+\eta y_i$$
式中$\eta(0<\eta\le 1)$是步长，在机器学习中又称为学习率。这样通过迭代可以期待损失函数$L(w,b)$不断减小，直到为0.
这种学习算法直观上有如下解释:当一个实例点被误分类，即位于分离超平面的错误一侧时，则调整$w,b$的值，使分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面之间的距离，直到超平面越过该误分类点使其被正确分类。
4. 感知机学习算法的收敛性
（Novikoff）定理 设训练数据集为$T={(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)}$，其中$x_i\in\mathcal{X}=R^n,\ y_i\in\mathcal{Y}=\{-1,+1\},\ i=1,2,\dots,N$，则
1）存在满足条件$||\hat{w}_{opt}|| = 1$的超平面$\hat{w}_{opt}\cdot \hat{x} = w_{opt}\cdot x + b_{opt} = 0$将训练数据集完全正确分开；且存在$\gamma>0$，对所有的$i=1,2,\dots,N$
$$y_i(\hat{w}_{opt}\cdot \hat{x}_i = y_i(w_{opt}\cdot x_i + b_{opt}) \ge \gamma$$
2）令$R = \max_{1\le i\le N}||\hat{x}_i||$，则感知机算法在训练数据集上的误分类次数$k$满足不等式
$$k \le \left(\frac{R}{\gamma}\right)^2$$
定理表明，误分类的次数$k$是有上界的，经过有限次搜索可以找到将训练数据完全正确分开的分离超平面。但是，感知机学习算法存在许多解，这些解既依赖于初值的选择，也依赖于迭代过程中误分类点的选择顺序。为了得到唯一的超平面，需要对分离超平面增加约束条件。