Perceptron and SVM

感知机perceptron和支持向量机SVM的原理解释。

线性可分与超平面

$D_0$和$D_1$ 是 n 维欧氏空间中的两个点集。如果存在 n 维向量 w 和实数 b,使得所有属于$D_0$的点$x_i$都有$wx_i + b > 0$, 而对于所有属于$D_1$的点$x_j$ 则有$wx_j + b < 0$,则我们称 $D_0$ 和 $D_1$线性可分。将$D_0$和$D_1$完全正确地划分开的$wx + b = 0$ 就成了一个超平面。

perceptron和SVM就是为了求解出这个分割超平面,也就是求解线性可分问题。

Perceptron(感知机)

感知机是一个简单的监督学习的机器学习算法,也是最早的神经网络结构。作为一个二分类的线性分类模型,其输入为实例的特征向量,输出为实例的类别。

感知机的损失函数

感知机的损失函数是根据所有误分类点到超平面$S$的总距离来定的,假设超平面$S$的误分类点集合为$M$:

由于$w$的L2范数$|w|$ 本身就和 $w$有固定的倍数关系,并不会影响这个优化问题的最终求解。最终的损失函数定义为:

感知机的学习算法

原始形式:

感知机学习算法是误分类驱动的,采用随机梯度下降法 stochastic gradient descent。一次随机选取一个误分类点使其梯度下降。

根据上面的损失函数,简单求导一下,对应的梯度为:

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

$\eta (0 < \eta \leq 1)$是步长,也就是学习率。

当一个实例点被误分类,即位于超平面的错误一侧,则调整$w,b$的值,使超平面向该误分类点的一侧移动,以减少该误分类点与超平面的距离,直至超平面越过该分类点使其被分类正确。

感知机的算法是可以证明其收敛性的,有限次数之后能对一个线性可分的数据集合完成分类。


假定$\gamma$ 是超平面margin最大值。$R = \max\limits_{1\leq i \leq N}| \hat{x_i} |$, 也就是点集里面离坐标原点的最大距离。那么这个有限次数k满足

流程如下

输入:训练数据集 $T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$,其中$x_i \in \mathcal{X} = R^n$, $y_i \in \mathcal{Y} = \{+1,-1\}, i=1,2,…,N$;学习率 $\eta (0 < \eta \leq 1)$。

输出:$\mathbf{w},b$ ;感知机模型 $f(x)=sign(\mathbf{w} \cdot x + b)$,其中 $\mathbf{w} = (w_1, w_2, … , w_N)$

1.$\mathbf{w} \leftarrow 0$, $b \leftarrow 0$
2.在训练集中选取数据$(x_i,y_i)$
3.如果 $y_i(\mathbf{w} \cdot x_j + b) \leq 0$

4.转到2不断重复,直到训练集里面没有误分类的点。

感知机算法的对偶形式

对偶形式算是对上面算法的改进,本质上仔细看其实是一样的,有点在于计算量上的技巧性优化,流程如下:

输入:训练数据集 $T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$,其中$x_i \in \mathcal{X} = R^n$, $y_i \in \mathcal{Y} = \{+1,-1\}, i=1,2,…,N$;学习率 $\eta (0 < \eta \leq 1)$。

输出:$\mathbf{w},b$ ;感知机模型 $f(x)=sign(\sum\limits^N_{j=1} w_{j} y_j x_j \cdot x + b)$,其中 $\mathbf{w} = (w_1, w_2, … , w_N)$

1.$\mathbf{w} \leftarrow 0$, $b \leftarrow 0$
2.在训练集中选取数据$(x_i,y_i)$
3.如果 $y_i(\sum\limits_{j=1}^{N} w_j y_j x_j \cdot x_{i} + b) \leq 0$

4.转到2不断重复,直到训练集里面没有误分类的点。

sign函数,符号函数,对于$x \geq 0$, $sign(x)=1$; 对于对于$x < 0$, $sign(x)=-1$;

第三个判断误分类的形式里面是计算两个样本$x_i$和$x_j$的内积,而且这个内积计算的结果在下面的迭代次数中可以重用。如果我们事先用矩阵运算计算出所有的样本之间的内积,即用矩阵存储实例间内积$ G = [x_i, x_j]_{N\times N}$ 那么在算法运行时,仅仅一次的矩阵内积运算比多次的循环计算省时。计算量最大的判断误分类这儿就省下了很多的时间,这也是对偶形式的感知机模型比原始形式优的原因。

参考:感知机(Perceptron)及python实现

SVM(支持向量机)

感知机追求最大程度的正确划分,最小化错误,很容易过拟合;支持向量机追求在大致正确分类的同时(因为有软间隔的概念),最大化margin,所以一定程度上避免了过拟合。同时,margin本身也减少了对训练数据的需求量。

SVM的目的和所要解决的问题:

找到一个超平面使得距离两个类别的最近的样本最远(margin最大),这个超平面也被称为最大间隔超平面。

SVM训练的本质是解决一个受约束的凸二次规划(Quadratic Programing, QP)

假设有一个经过原点的超平面(arbitrary separation plane), 对于它有$\overrightarrow{c} \cdot \overrightarrow{x} = 0$。那么假想有两个这个分割平面的复制。一个往上平移,一个往下平移,用同样的速度,并且只要有一个平面触碰到了点集P中的点,就都停下。

这时候这两个复制出来的平面,一个可以表示为$\overrightarrow{c} \cdot \overrightarrow{x} = \lambda$,那么另一个可以表示为$\overrightarrow{c} \cdot \overrightarrow{x} = -\lambda$,$\lambda$是正数值。

那么对于点集P中的每一个点p:

  • 如果p的label为1,有$\overrightarrow{c} \cdot \overrightarrow{p} \geq \lambda$;
  • 如果p的label为-1,有$\overrightarrow{c} \cdot \overrightarrow{p} \leq -\lambda$;

对上面的两个不等情况,两侧同时除以$\lambda$,能够得到:

  • 如果p的label为1,有$\overrightarrow{w} \cdot \overrightarrow{p} \geq 1$;

  • 如果p的label为-1,有$\overrightarrow{w} \cdot \overrightarrow{p} \leq -1$;

其中

在图中的$\pi_1$平面是:

$\pi_2$平面是:

margin就是$\pi_1$和$\pi_2$之间距离的一半,即:

那么为了最大化margin,我们就要最小化 $|w|$,也就是尽量最小化 $\sum_{i=1}^{d} w_i^2$,同时两个constraints是:

  • 对于点集P中label为1的点:
  • 对于点集P中label为-1的点:

这就是SVM对应的受约束的凸二次规划。

最大化margin的原因:

我们需要证明的是通过训练集合训练出的分类器,在实际测试中的错误率是有界的,也就是 $err_{D}(M)$ 小于等于 $err_{P_{train}}(M)$ 加上一个常量。

首先看VC-Based Generalization Theorem:

对于$\mathbb{R^{d}}$空间中的线性分类器,其VC-Demension是:

那么根据上面的公式,如果需要减少误差,我们要么增加$|P_{train}|$,也就是增加训练集的数据量。要么就是减少$\lambda$,也就是减少VC-Demension,但问题是VC-Demension是随着点集的维度一起的。同时有时候为了线性可分,我们还需要把点集映射到更高维度的空间。所以方法基本就是增加训练集的量。

下面看看Margin-Based Generalization Theorem

针对Margin-Based Generalization Theorem的公式,如果减少误差,我们需要做的除了增大训练集的量。也需要使得$|\overrightarrow{c}|$尽量小。同时我们根据之前的部分可以知道:

这时候SVM为什么想尽办法想要使得margin最大化的目的也就显现出来了。

其他相关概念:

支持向量

样本中距离超平面最近的一些点,这些点叫做支持向量。

软间隔

对于不能够完全线性可分的样本,我们允许部分样本点不满足约束条件, 也就是允许部分样本点出现在margin区域里面。

核函数

对于那些不线性可分的情况,我们需要将在目前维度线性不可分的样本映射到更高维空间中,让样本点在更高维空间线性可分。这就是非线性SVM。

这时候超平面可以表示为

求解非线性SVM的优化问题(关于利用拉格朗日乘数法和强对偶性强化的部分见参考链接)式子中,之前的$x_i \cdot x_j$变成了需要计算$\phi(x_i) \cdot \phi(x_j)$。因为低维空间映射到高维空间后维度可能会很大,将全部样本的点乘全部计算好,计算量太大。

核函数就是达到了$k(x,y) = \phi(x) \cdot \phi(y)$, 使得高维空间的两点的内积等于它们在原始样本空间中通过函数$k(x,y)$。 常见的核函数有,线性核函数,多项式核函数,高斯核函数。

关于这部分的内容我推荐知乎上一个写的很好的回答。关于SVM的概念和SVM的数学推导过程里面都有。

知乎回答

SVM与Perceptron的区别

1.普通的感知机不能产生大间隔(margin),但是SVM可以。
2.加入了L2正则化的带margin的感知机基本就是SVM。

Perceptron对应的优化问题:

SVM(soft margin)对应的优化问题:

感知器是不能产生大间隔的,因为它只以分对为目的,不关心分界面离数据点有多远,从它的目标函数很容易看出来。

SVM和perceptron区别之一是SVM使用了hinge损失函数,而perceptron采用0/1损失函数,分对了就没损失。这个改进使得感知器具备了产生大间隔的潜质,hinge loss不仅要分类正确,而且置信度足够高的时候,损失才为0,对学习有更高的要求。其实这个道理和SVM中的margin是相符合的,不仅要分类正确,还要使得margin最大化。后面部分加上的是L2正则化,避免产生无意义的大函数间隔,而是产生大的几何间隔。

Hinge Loss 在二分类情况下,公式如下:

下面是hinge loss的图像,也叫合页损失函数:

超平面实现最大分割情况并且支持向量与分割平面之间的距离为1,每个$y=1$的样本其$\widehat{y} \geq 1$, 每个$y=-1$的样本其$\widehat{y} \leq -1 $,这些点的Hinge loss为0。如果分割的超平面出现了误分类,则Hinge loss大于0。如果分割超平面距离支持向量的距离小于1,则Hinge loss大于0。Hinge loss 驱动分割超平面作出调整,使得能够在正确分类的基础上,保证了margin。

Hinge loss的分类器预测值 $\widehat{y} \in R$。$|\widehat{y}|$越大,说明样本点离分割超平面越远,即该样本点很容易被分类。所以选择合适的损失函数进行优化的时候,其实没必要关注离超平面很远的样本。为此,我们可以通过对距分离超平面的距离选择一个阀值,来过滤掉这些离超平面很远的样本。这就是Hinge loss的另一个精髓。$L(y) = max(0, 1-y \cdot \widehat{y})$。这里面的1就是选择的的阀值。

参考链接:感知机(perceptron)和支持向量机(svm)是一种东西吗?
如果不是那他们的区别和关系是什么? - DeAlVe的回答 - 知乎