感知机(perceptron) 是二分类的线性分类模型，输入实例的特征向量，输出实例的类别。

感激机 1957 年由 Rosenblatt 提出，是神经网络与支持向量机的基础。

感知机模型

定义（感知机） 假设输入空间（特征空间）是 $\mathcal X\subseteq \mathbf R^n$ ，输出空间是 $\mathcal=\{+1,-1\}$ 。输入 $x\in\mathcal X$ 表示实例的特征向量，对于输入空间（特征空间）的点；输出 $y\in\mathcal Y$ 表示实例的类别。由输入空间到输出空间的函数 $f(x)=\text{sign}(w\cdot x+b)$ 称为感知机。其中， $w$ 和 $b$ 为感知机模型参数， $w\in\mathbf R^n$ 叫作权值(weight)或权值向量(weight vector)， $b\in\mathbf R$ 叫作偏置(bias)， $w\cdot x$ 表示 $w$ 和 $x$ 的内积。 $\text{sign}$ 是符号函数，即

$$\text{sign}=\left\{\begin{aligned}+1&&x\ge0\\-1&&x\lt0\end{aligned}\right.$$

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

线性方程 $w\cdot x+b=0$ 可以对应于特征空间 $\mathbf R^n$ 中的一个超平面 $S$ ，其中 $w$ 是超平面的法向量， $b$ 是超平面的截距。这个超平面将特征空间划分为两个部分。位于两部分的点（特征向量）分别被分为正、负两类。因此，超平面 $S$ 称为分离超平面(separating hyperplane) 。

感知机学习，由训练数据集（实例的特征向量及类别）

$$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)\}$$

其中， $x_i\in\mathcal X=\mathbf R^n, y_i\in\mathcal Y=\{+1, -1\}, i=1,2,\cdots, N$，求得感知机模型 $f(x)=\text{sign}(w\cdot x+b)$ ，即求得模型参数 $w,b$ 。

感知机预测，通过学习得到的感知机模型，对于新的输入实例给出其对应的输出类别。

感知机学习策略

数据集的线性可分性

定义（数据集的线性可分性） 给定一个数据集

$$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)\}$$

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

感知机学习策略

假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面。

为了找出这样的超平面，即确定感知机模型参数 $w, b$ ，需要确定一个学习策略，即定义（经验）损失函数并将损失函数极小化。

可以将损失函数定为误分类点的总数，但是这样损失函数的参数不是 $w, b$ 的连续可导函数，不易优化。

损失函数的另一个选择是误分类点到超平面 $S$ 的总距离。感知机就是选择这种损失函数。

输入空间 $\mathbf R^n$ 中任一点 $x_0$ 到超平面 $S$ 的距离为

$$\frac1{\|w\|}|w\cdot x_0+b|$$

$|w|=\sqrt{\sum w_i^2}$ 是 $w$ 的 $L_2$ 范数。

对于误分类的数据 $(x_i, y_i)$ 来说，

$$-y_i(w\cdot x_i+b)\gt0$$

因此，误分类点到超平面的距离是

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

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

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

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

给定训练数据集

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

感知机 $\text{sign}(w\cdot x+b)$ 学习的损失函数定义为

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

其中 $M$ 为误分类点的集合。这个损失函数就是感知机学习的经验风险函数。

显然，损失函数 $L(w, b)$ 是非负的。如果没有误分类点，损失函数值是 0. 而且，误分类点越少，误分类点离平面越近，损失函数值就越小。一个特定的样本点的损失函数在误分类时是参数 $w,b$ 的线性函数，在正确分类时是0. 因此，给定训练数据集 $T$ ，损失函数 $L(w,b)$ 是 $w,b$ 的连续可导函数。

感知机学习的策略是在假设空间中选取使损失函数式最小的模型参数 $w,b$ ，即感知机模型。

感知机学习算法

感知机学习问题转化为求解损失函数 $L(w,b)=-\sum\limits_{x_i\in M}y_i(w\cdot x_i+b)$ 的最优化问题。最优化的方法是随机梯度下降法。

本届协议书感知机学习的集体算法，包括原始形式和对偶形式，并证明在训练数据线性可分条件下感知机学习算法的收敛性。

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

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

首先，任意选取一个超平面 $w_0, b_0$，然后用梯度下降法不断地极小化目标函数 $-\sum\limits_{x_i\in M}y_i(w\cdot x_i+b)$ 。

极小化过程中不是一次使 $M$ 中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。

假设误分类点集合 $M$ 是固定的，那么损失函数 $L(w, b)$ 的梯度由

$$\begin{aligned} \nabla_wL(w,b)&=L'_w=-\sum_{x_i\in M}y_ix_i\\ \nabla_bL(w,b)&=L'_b=-\sum_{x_i\in M}y_i \end{aligned}$$

给出。

随机选取一个误分类点 $(x_i, y_i)$ ，对 $w,b$ 进行更新：

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

式中 $0\le\eta\le1$ 是步长，在统计学习中又称为学习率(learning rate) 。这样，通过迭代可以期待损失函数 $L(w,b)$ 不断减小，直到为 0. 纵上所述，得到如下算法：

1. 选取初值 $w_0, b_0$
2. 在训练集中选取数据 $(x_i, y_i)$
3. 如果 $y_i(w\cdot x_i+b)\le 0$，$w\leftarrow w+\eta y_ix_i, b\leftarrow b+\eta y_i$
4. 转至 2 ，直至训练集中没有误分类点。

算法的收敛性

为了便于叙述与推导，记 $\hat w=(w^T, b)^T, \hat x=(x^T, 1)^T$

这样， $\hat w\cdot\hat x=w\cdot x+b$

定理（Novikoff） 设训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$ 是线性可分的，其中 $x_i\in\mathcal X=\mathbf R^n, y_i\in\mathcal Y=\{-1, +1\}, i=1,2,\cdots,N$ ，则

1. 存在满足条件 $|\hat w_{opt}|=1$ 的超平面 $\hat w_{opt}\cdot \hat x=0$ 将训练数据集完全正确分开；且 $\exist\gamma\gt0\space s.t. \space\forall i\in\{1,2,\cdots,N\}, y_i(\hat w_{opt}\cdot\hat x)\ge\gamma$
2. 令 $R=\max\limits_{1\le i\le N}|\hat x_i|$ ，则感知机算法在训练数据集上的误分类次数 $k$ 满足不等式 $k\le\left(\frac Rr\right)^2$

证明：

由于训练级是线性可分的，由数据集的线性可分性的定义知，存在超平面可将训练数据集完全正确分开。取此超平面为 $\hat w_{opt}\cdot\hat x=0$ ，使 $|\hat w_{opt}|=1$ 。由于对有限的 $i=1,2,\cdots,N$ 均有

$$y_i(\hat w_{opt}\cdot\hat x_i)\gt 0$$

所以存在

$$\gamma = \min_i{y_i(\hat w_{opt}\cdot\hat x_i)}$$

使

$$y_i(\hat w_{opt}\cdot\hat x_i)\ge\gamma$$

感知机算法从 $\hat w_0=0$ 开始，如果实例被误分类，则更新权重。令 $\hat w_{k-1}$ 是第 $k$ 个误分类之前的扩充权重向量，则第 $k$ 个误分类实例的条件是 $y_i(\hat w_{k-1}\cdot\hat x_i)\le0$

若 $(x_i, y_i)$ 是被 $\hat w_{k-1}$ 误分类的数据，则 $\hat w$ 的更新是 $\hat w_k=\hat w_{k-1}+\eta y_i\hat x_i$

由于 $y_i(\hat w_{opt}\cdot\hat x_i)\ge\gamma$

可以得到

$$\begin{aligned} \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 y_i\gamma \end{aligned}$$

可由递推关系知

$$\begin{aligned} \hat w_k\cdot\hat w_{opt}&\ge\hat w_0\cdot\hat w_{opt}+k\eta\gamma\\ &=k\eta\gamma \end{aligned}$$

此外，由 $\left\{\begin{aligned} &\hat w_k=\hat w_{k-1}+\eta y_i\hat x\\ &y_i(\hat w_{k-1}\cdot\hat x_i)\le0\\ &R=\max\limits_{1\le i\le N}|\hat x_i| \end{aligned}\right.$ 知

$$\begin{aligned} \|\hat w_k\|^2&=\|\hat w_{k-1}+\eta y_i\hat x\|^2\\ &=\|\hat w_{k-1}\|^2+2\eta y_i\hat w_{k-1}\cdot\hat x_i+\eta^2\|\hat x_i\|^2\\ &\le \|\hat w_{k-1}\|^2+\eta^2\|\hat x_i\|^2\\ &\le \|\hat w_{k-1}\|^2+\eta^2R^2\\ &\le \|\hat w_0\|^2+k\eta^2R^2\\ &\le k\eta^2R^2 \end{aligned}$$

结合

$$\hat w_k\cdot\hat w_{opt}\ge k\eta\gamma\\ \|\hat w_k\|^2\le k\eta^2R^2\\ \|\hat w_{opt}\|=1$$

知

$$k\eta\gamma\le\hat w_k\cdot\hat w_{opt}\le\|\hat w_k\|\|\hat w_{opt}\|\le\sqrt k\eta R\\ \therefore k\le\left(\frac R\gamma\right)^2$$

这说明，误分类的次数 $R$ 是有上界的，经过有限次搜索可以找到将训练数据完全正确分开的分离超平面。也就是说，当训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的。

当训练集线性不可分时，感知机学习算法不收敛，迭代结果会发生震荡。

但是感知机学习算法存在许多解，这些解既一代于初值的选择，也依赖于迭代过程中误分类点的选择顺序。为了得到唯一的超平面，需要对分离超平面增加约束条件。这就是线性支持向量机的想法。

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

感知机学习算法的原始形式与对偶形式与支持向量机学习算法的原始形式和对偶形式相对应。

对偶形式的基本想法是将 $w$ 和 $b$ 表示为实例 $x_i$ 和标记 $y_i$ 的线性组合的形式，通过求解其系数而求得 $w$ 和 $b$ 。

在原始形式中，我们可以假设 $w_0=0, b_0=0$ ，对误分类点 $(x_i, y_i)$ 通过 $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_iy_i$ 。这里 $\alpha=n_i\eta$ ， $n_i$ 是点 $(x_i, y_i)$ 被误分类的次数。

这样最后学习到的 $w, b$ 可以表示为

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

使用对偶形式 $f(x)=\text{sign}\left(\sum_{j=1}^N\alpha_jy_jx_j\cdot x+b\right)$ 可以得到算法：

1. $\alpha\leftarrow0, b\leftarrow0$
2. 在训练集中选取数据 $(x_i, y_i)$
3. 如果 $y_i\left(\sum_{j=1}^N\alpha_jy_jx_j\cdot x_i+b\right)\le0$ ， $\alpha+i\leftarrow\alpha_i+\eta, b\leftarrow b+\eta y_i$
4. 转至 2 直到没有误分类数据

对偶形式中训练实例仅以内积形式出现。为了方便，可以预先将训练集中实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是所谓的 Gram 矩阵（Gram matrix）

$$\mathbf G=[x_i\cdot x_j]_{N\times N}$$

参考资料

李航. 统计学习方法[M]. 第二版. 北京: 清华大学出版社, 2019:3-47.