01. 感知机模型 | Colommar Blog

来源：原始 Jupyter Notebook。内容已转换为网页阅读格式；下载原文件。

感知机（perceptron）是一种非常简单的用于二分类的线性模型，对于线性可分的样本，它对应于输入空间中将样本划分为正负两类的划分超平面，感知机模型在 1957 年由 Rosenblatt 提出，是神经网络和支持向量机的基础。

在支持向量机的学习中，我们知道，对于一个线性可分的输入空间，存在多个划分超平面可以将训练样本分开，如下图所示：

这样的划分超平面可以写成线性方程的形式：

w^Tx + b = 0

一旦将空间划分成两个部分之后，就可以通过 $w^Tx + b$ 的符号来进行分类：

f(x) = sign(w^Tx + b)

其中，sign 是符号函数，当 $w^Tx + b \geq 0$ 时，将其归为正类，当 $w^Tx + b < 0$ 时，将其归为负类。这里的 $f(x)$ 函数被称为 感知机（perceptron）模型。

输入空间中的某个点到划分超平面的距离可以写成：

r = \frac{|w^Tx + b|}{\|w\|}

如果某个点 $(x_i, y_i)$ 被误分类，也就是说当 $w^Tx_i + b \geq 0$ 时，将其归为负类（ $y_i = -1$ ），当 $w^Tx_i + b < 0$ 时，将其归为正类（ $y_i = 1$ ），这时我们有：

-y_i(w^Tx_i + b) \geq 0

所以对于误分类的点，它到划分超平面的距离可以写成：

r = \frac{|w^Tx + b|}{\|w\|} = \frac{-y_i(w^Tx_i + b)}{\|w\|}

我们将所有误分类的点到划分超平面的距离累加，得到感知机的损失函数：

loss = -\sum_{x_i \in M} y_i(w^Tx_i + b)

这里我们把 $\frac{1}{\|w\|}$ 省略了，它不影响损失函数的结果，其中 $M$ 表示误分类点的集合，很显然，当没有点被误分类时，损失函数等于 0，感知机算法就是求损失函数最小时的 w、b 参数。

要使感知机的损失函数最小化，通常使用 随机梯度下降法（stochastic gradient descent），首先选取一个超平面 $w_0, b_0$ ，然后用梯度下降法不断的极小化损失函数，在极小化过程中每次随机选取一个误分类点使其梯度下降。

损失函数的梯度如下：

\begin{align} \nabla_w loss &= -\sum_{x_i \in M} y_i x_i \\ \nabla_b loss &= -\sum_{x_i \in M} y_i \end{align}

随机选取一个误分类点 $(x_i, y_i)$ ，对 w, b 的更新公式为：

\begin{align} w &:= w + \eta y_i x_i \\ b &:= b + \eta y_i \end{align}

式中 $\eta$ 是步长，又叫学习率。通过不断的迭代，损失函数不断减小，直到为 0 。

对于一个线性可分的数据集，感知机学习算法是不是一定收敛呢？这就需要引出 Novikoff 定理 了。

根据 Novikoff 定理，感知机算法在训练集上的误分类次数 k 满足不等式：

k \leq (\frac{R}{\gamma})^2

也就是说，误分类次数是有上界的，经过有限次迭代肯定可以找到将训练数据完全正确分开的超平面。

f(x) = sign(\sum_{j=1}^N \alpha_j y_j x_j \cdot x + b)

参考《统计学习方法》中的实例。

感知机学习算法存在多个解，采用不同的初始值或者在迭代过程中改变选取误分类点的顺序，求得的解都会不同。为了得到唯一的超平面，需要对超平面增加约束条件，这就是线性支持向量机的想法。

当训练样本不是线性可分的时候，感知机算法不收敛，迭代结果会发生震荡。