支持向量机：感知机

发表: 2017-06-03 浏览: 2427

算法 Python 机器学习

（这里是本章会用到的 Jupyter Notebook 地址）

感知机是个相当简单的模型，但它既可以发展成支持向量机（通过简单地修改一下损失函数）、又可以发展成神经网络（通过简单地堆叠），所以它也拥有一定的地位

为方便，我们统一讨论二分类问题，并将两个类别的样本分别称为正、负样本

感知机能做什么？

感知机能（且一定能）将线性可分的数据集分开。什么叫线性可分？在二维平面上、线性可分意味着能用一条线将正负样本分开，在三维空间中、线性可分意味着能用一个平面将正负样本分开。可以用两张图来直观感受一下线性可分（上图）和线性不可分（下图）的概念：

那么一个感知机将会如何分开线性可分的数据集呢？下面这两张动图或许能够给观众老爷们一些直观感受：

看上去挺捉急的，不过我们可以放心的是：只要数据集线性可分，那么感知机就一定能“荡”到一个能分开数据集的地方（文末会附上证明）

那么反过来，如果数据集线性不可分，那么感知机将如何表现？相信聪明的观众老爷们已经猜到了：它将会一直“荡来荡去”（最后停了是因为到了迭代上限）：

如何搭建感知机模型？

为了搭建感知机模型，我们需要知道高维数据的线性可分是指什么。为此我们需要定义“超平面”的概念：

$\Pi:w\cdot x+b=0$

其中 $w$ 、 $x$ 都是 $n$ 维向量， $\Pi$ 则是 $\mathbb{R}^n$ 中的超平面。对于二维平面来说 $n=2$ ，上式就可以化为：

$w_1x_1+w_2x_2+b=0$

此即直线方程。有了 $\mathbb{R}^n$ 中超平面的定义后，线性可分的概念也就清晰了：对于一个数据集 $D=\left\{ (x_1,y_1),...,(x_N,y_N) \right\}$ （ $x_i$ 为输入， $y_i$ 为标签），如果存在一个超平面 $\Pi$ ，能够将 $D$ 中正负样本（对于某个样本 $(x_i,y_i)$ ，若 $y_i=1$ 则称其为正样本，若 $y_i=-1$ 则称其为负样本，且标签 $y_i$ 只能取正负 1 这两个值）分开，那么就称 $D$ 是线性可分的。否则，就称 $D$ 是线性不可分的

对于感知机模型来说，以上的这些信息就足够了。事实上，感知机模型只有 $w$ 和 $b$ 这两个参数，我们要做的就是根据样本的信息来逐步更新 $w$ 和 $b$ 、从而使得对应的超平面 $\Pi$ 能够分开 $D$

如何训练感知机模型？

上一节已经说过，感知机模型只有 $w$ 和 $b$ 这两个参数，其中 $w$ 是一个 $n$ 维向量（ $w\in\mathbb{R}^n$ ）、 $b$ 则是一个标量（ $b\in\mathbb{R}$ ）。为了保证收敛性，我们需要将 $w$ 初始化为零向量、将 $b$ 初始化为 0：

class Perceptron:

    def __init__(self):

        self._w = self._b = None

      

    def fit(self, x, y, lr=0.01, epoch=1000):

        # 将输入的 x、y 转为 numpy 数组

        x, y = np.asarray(x, np.float32), np.asarray(y, np.float32)

        self._w = np.zeros(x.shape[1])

        self._b = 0.

上面这个 fit 函数中有个 lr 和 epoch，它们分别代表了梯度下降法中的学习速率和迭代上限
（p.s. 由后文的推导我们可以证明，对感知机模型来说、其实学习速率不会影响收敛性【但可能会影响收敛速度】）

梯度下降法我们都比较熟悉了。简单来说，梯度下降法包含如下两步：

求损失函数的梯度（求导）
梯度是函数值增长最快的方向 $\rightarrow$ 我们想要最小化损失函数 $\rightarrow$ 我们想让函数值减少得最快 $\rightarrow$ 将参数沿着梯度的反方向走一步

（这也是为何梯度下降法有时被称为最速下降法的原因。梯度下降法被普遍应用于神经网络、卷积神经网络等各种网络中，如有兴趣、可以参见这篇文章）

那么对于感知机模型来说，损失函数是什么呢？注意到我们感知机对应的超平面为 $\Pi:w\cdot x+b=0$ 而我们的样本为正负样本，一个自然的想法就是：

$(x,y)$ 是正样本 $\Leftrightarrow w\cdot x+b>0$
$(x,y)$ 是负样本 $\Leftrightarrow w\cdot x+b<0$

（从几何直观来说，上述定义等价为“ $(x,1)$ 在 $\Pi$ 的上方”、“ $(x,-1)$ 在 $\Pi$ 的下方”）

注意我们前文提到过

$(x,y)$ 是正样本 $\Leftrightarrow y=1$
$(x,y)$ 是负样本 $\Leftrightarrow y=-1$

那么一个朴素的损失函数 $L(x,y)$ 就比较容易写出来了：

若 $w\cdot x+b>0$ ，则 $L(x,1)=0,L(x,-1)=w\cdot x+b$
若 $w\cdot x+b<0$ ，则 $L(x,1)=-w\cdot x+b,L(x,-1)=0$

综上所述、就有：

损失函数可写为 $L(x,y)=\max{\left(-y(w\cdot x+b),0\right)}$
$(x,y)$ 被正确分类 $\Leftrightarrow y(w\cdot x+b)>0$

从而易知只有错分类的点才会给 $L(x,y)$ 贡献梯度（因为正确分类的点及其“周围”的 $L(x,y)$ 的值为常数 0，从而梯度为 0）。所以训练感知机时，我们只需挑选使得损失函数 $L(x,y)$ 最大的一个样本 $(x_i,y_i)$ 、用它来计算梯度、然后梯度下降即可（注意如果 $(x_i,y_i)$ 是被正确分类的话，说明所有样本都已被正确分类，所以此时应该停止模型的训练【事实上也训练不动了……】）

由于 $L(x,y)$ 的形式简洁，所以其求导是平凡的（注意对错分类样本 $(x_i,y_i)$ 而言， $L(x,y)=-y_i(w\cdot x_i+b)=-y_ix_i\cdot w-y_ib$ ）：

$\frac{\partial L}{\partial w}(x_i,y_i) = -y_ix_i$ $\frac{\partial L}{\partial b}(x_i,y_i)=-y_i$

体现在代码上即为：

for _ in range(epoch):

    # 计算 w·x+b

    y_pred = x.dot(self._w) + self._b

    # 选出使得损失函数最大的样本

    idx = np.argmax(np.maximum(0, -y_pred * y))

    # 若该样本被正确分类，则结束训练

    if y[idx] * y_pred[idx] > 0:

        break

    # 否则，让参数沿着负梯度方向走一步

    delta = lr * y[idx]

    self._w += delta * x[idx]

    self._b += delta

至此，感知机模型就大致介绍完了，剩下的则是一些纯数学的东西，大体上不看也是没问题的（趴

相关数学理论

从数学的角度来说，线性可分性还有一个比较直观的等价定义：正负样本点集的凸包彼此不交。所谓凸包的定义如下：若集合 $S\subset\mathbb{R}^n$ 由 $N$ 个点组成：

$S={x_1,...,x_N}\ \ (x_i\in\mathbb{R}^n,\forall i=1,...,N)$

那么 $S$ 的凸包 $\text{conv}(S)$ 即为：

$\text{conv}(S)=\left\{ x=\sum_{i=1}^N\lambda_ix_i|\sum_{i=1}^N\lambda_i=1,\lambda_i\ge0\ (i=1,...,N) \right\}$

比如，上文给出过的两个二维数据集的凸包将如下图所示：

左图正负样本点集的凸包不交、所以数据集线性可分，右图的橙色区域即为正负样本点集凸包的相交处、所以数据集线性不可分

该等价性的证明可以用反证法得出：

1）线性可分 $\Rightarrow$ 凸包不交：线性可分意味着存在 $w^*$ 和 $b^*$ ，使得 $y(w^*\cdot x+b^*)>0$ 对任意 $(x,y)\in D$ 成立。如果凸包相交的话，就意味着存在某个样本 $(x^*,y^*)$ 、使得 $x^*$ 既是正样本输入数据的线性组合、又是负样本输入数据的线性组合：

$x^*=\sum_{y_i=1}{\lambda_ix_i}=\sum_{y_i=-1}{\mu_ix_i}$

从而

$y^*(w^*\cdot x^*+b^*)=y^*\left(w^*\cdot\sum_{y_i=1}{\lambda_ix_i+b^*}\right)=y^*\left(w^*\cdot\sum_{y_i=-1}{\mu_ix_i+b^*}\right)>0$ （式 1）

注意到

$y_i=1$ 时， $w^*\cdot x_i+b^*>0$
$y_i=-1$ 时， $w^*\cdot x_i+b^*<0$

所以（注意由凸包的定义我们有 $\sum_i\lambda_i=\sum_i\mu_i=1$ 且 $\lambda_i\ge0,\mu_i\ge0$ ）

$w^*\cdot\sum_{y_i=1}{\lambda_ix_i+b^*}=\sum_{y_i=1}{\lambda_i\left(w^*\cdot x_i+b^*\right)}>0$

$w^*\cdot\sum_{y_i=-1}{\mu_ix_i+b^*}=\sum_{y_i=-1}{\mu_i\left(w^*\cdot x_i+b^*\right)}<0$

这与式 1 矛盾

2）凸包不交 $\Rightarrow$ 线性可分：严谨证明需要用到一些奇怪的东西，这里就只提供一个（非常）不严谨的直观说明（欢迎观众老爷们提供更好的证明，现在这个说明我看上去觉得很像是错的）（喂）：在正样本点集凸包的边界上取一个离负样本点集凸包“最近”的点 $x^{*(1)}$ 并假设负样本点集凸包边界上离 $x^{*(1)}$ “最近”的点为 $x^{*(2)}$ 。过 $x^{*(1)}$ 画一个超平面 $\Pi:w^*\cdot x+b^*=0$ 、使得 $\Pi$ 与 $x^{*(1)}$ 、 $x^{*(2)}$ 的连线垂直。由凸包的几何性质可知此时（除了 $x^{*(1)}$ 外）正样本点集都被分到了 $\Pi$ 的同一侧、且 $x^{*(2)}$ 是离 $\Pi$ “最近”的点，这样只需把 $\Pi$ 稍微往负样本点集那边挪一点（什么鬼！）就行了

然后是前文遗留下来的、感知机模型收敛性的证明。我们知道感知机对应的超平面为：

$\Pi:w\cdot x+b=0$

将其展开的话、就是

$\Pi:w_1x_1+...+w_nx_n+b=0$

所以我们可以将其改写为

$\Pi:\hat w\cdot \hat x=0$

其中

$\hat w=(w_1,...,w_n,b),\hat x=(x_1,...,x_n,1)$

如果数据集线性可分的话，就意味着存在 $\hat w^*$ 、使得对任意 $(x,y)\in D$ 、都有 $y(\hat w^*\cdot \hat x)>0$ ；注意到 $\hat w^*$ 的 scale 不影响超平面、所以我们不妨假设 $\|w^*\|=1$ 。同时由于数据集 $D$ 中的样本是有限的，所以这又意味着 $\exists\gamma,\Delta$ 、使得总有 $y(\hat w^*\cdot\hat x^*)\ge\gamma,\|x_i\|^2\le\Delta$

现在我们初始化 $\hat w$ 为 0 向量（ $\hat w_0 = \bold{0}$ ），并开始感知机模型的训练（假设现在是第 $k$ 步）：

1）假设 $\Pi_k:\hat w_k\cdot\hat x=0$ 已经将所有样本正确分类，则已证毕

2）否则，取被 $\Pi_k$ 误分类的样本 $(x_i,y_i)$ ，进行参数的更新： $\hat w_{k+1}=\hat w_k+\eta y_i\cdot\hat x_i$ 。由此易知（注意 $\hat w_0 = \bold{0}$ ）：

$\begin{align} \hat w^*\cdot \hat w_{k+1}&=\hat w^*\cdot \hat w_k+\eta y_i(\hat w^*\cdot \hat x_i)\ge\hat w^*\cdot \hat w_k+\eta\gamma \\ &\ge...\ge\hat w^*\cdot \hat w_0+(k+1)\eta\gamma=(k+1)\eta\gamma \end{align}$

且

$\|\hat w^*\|^2\cdot\|\hat w_{k+1}\|^2=\|\hat w_{k+1}\|^2=\|\hat w_k\|^2+2\eta y_i(\hat w_k\cdot\hat x_i)+\eta^2y_i^2(\hat x_i\cdot\hat x_i)$ （式 2）

注意 $(x_i,y_i)$ 是被误分类的、且 $y_i$ 只能取正负 1，所以 $y_i(\hat w_k\cdot\hat x_i)\le0$ 、 $y_i^2=1$ ，从而由式 2 可以推出：

从而

$\begin{align} &\left[(k+1)\eta\gamma\right]^2\le(\hat w^*\cdot\hat w_{k+1})^2\le\|\hat w^*\|^2\cdot\|\hat w_{k+1}\|^2\le(k+1)\eta^2\Delta \\ &\Rightarrow k+1\le\frac\Delta{\gamma^2} \end{align}$

亦即训练步数 $k$ 是有上界的，这意味着收敛性。而且 $\frac\Delta{\gamma^2}$ 中不含学习速率 $\eta$ ，这说明对感知机模型来说、学习速率不会影响收敛性

最后简单介绍一个非常重要的概念：拉格朗日对偶性（Lagrange Duality）。我们在前三小节介绍的感知机算法，其实可以称为“感知机的原始算法”；而利用拉格朗日对偶性，我们可以得到感知机算法的对偶形式。鉴于拉格朗日对偶性的原始形式太过纯数学，所以我打算结合具体的算法来介绍、而不打算叙述其原始形式，感兴趣的观众老爷可以参见这里

在有约束的最优化问题中，为了便于求解、我们常常会利用它来将比较原始问题转化为更好解决的对偶问题。对于特定的问题，原始算法的对偶形式也常常会有一些共性存在。比如对于感知机和后文会介绍的支持向量机来说，它们的对偶算法都会将模型的参数表示为样本点的某种线性组合、并把问题转化为求解线性组合中的各个系数

虽说感知机算法的原始形式已经非常简单，但是通过将它转化为对偶形式、我们可以比较清晰地感受到转化的过程，这有助于理解和记忆后文介绍的、较为复杂的支持向量机的对偶形式

考虑到原始算法的核心步骤为：

$w\leftarrow w+\eta y_ix_i$

$b\leftarrow b+\eta y_i$

其中 $(x_i,y_i)\in E$ 、 $E$ 是当前被误分类的样本点的集合；可以看见、参数的更新是完全基于样本点的。考虑到我们要将参数 $w$ 和 $b$ 表示为样本点的线性组合，一个自然的想法就是记录下在核心步骤中、各个样本点分别被利用了多少次、然后利用这个次数来将 $w$ 和 $b$ 表示出来。比如说，若设样本点 $(x_i,y_i)$ 一共在上述核心步骤中被利用了 $n_i$ 次、那么就有（假设初始化参数时 $w=(0,...,0)^T\in \mathbb{R}^n,b=0$ ）：