机器学习-SVM支持向量机

2021-02-07 本文已影响0人升不上三段的大鱼

一、简介

支持向量机(Support Vector Machine， SVM) 是一种分类器，它会产生一个二值的决策结果。支持向量机的泛化错误率较低，具有良好的学习能力，并且学到的结果有推广性。

假设我们有一个样本集，包括两个线性可分的类别，我们需要计算一个线性的决策边界来将这两组样本分类，并且需要有很好的泛化能力。在两个类别之间可能存在很多个决策边界，都能将两个类别线性分开，但是为了提高泛化能力，我们需要找到一个超平面来分隔两类，并且让距离最近的不同类的样本点距离超平面最远，这个划分超平面的分类泛化能力是最强的。

假设我们的超平面可以由一个线性的方程来描述： $f(x) = w^Tx +b$ ，对于平面上的两个点，满足 $f(x_1)=f(x_2), w^T(x_1-x_2)=0$ ，平面的方向坐标为 $n=\frac{w}{||w||_2}$

样本空间中的任意一点到这个超平面的距离是 $r =\frac{f(x)}{||\nabla f(x)||_2}$

假设在超平面的两边间隔（margin）的两个点 $x_1$ ， $x_2$ 分别满足 $f(x_1) = +1, f(x_2)=-1$ ，那么得到两个点之间的距离为 $w^T(x_1-x_2)=2$ $\frac{w^T}{||w||_2}(x_1-x_2)=\frac{2}{||w||}$

支持向量与间隔

约束条件：间隔应该隔开两个类
$w^Tx_i+b \leq -1, if \quad y_i=-1$ $w^Tx_i+b \geq +1, if \quad y_i=+1$
写在一起就是 $y_i \cdot (w^Tx_i+b)\geq1$

为了使泛化能力最好，需要找到具有最大间隔（maximum margin）的超平面，对应的目标函数以及约束就是
$maximize \quad \frac{1}{||w||_2}$ $s. t. \quad \forall i: y_i \cdot(w^Tx_i +b)\geq1$
这个优化问题就相当于： $minimize \quad \frac{1}{2}||w||_2^2$ $s. t. \quad \forall i: y_i \cdot(w^Tx_i +b)-1\geq0$
这种形式要求所有样本都要满足约束，也就是两个类是线性可分的，被称为硬间隔问题。

对于非线性可分的类，可以加入松弛变量，这被称为软间隔问题，允许某些样本不满足约束优化问题就是 $minimize \quad \frac{1}{2}||w||_2^2+\mu\sum_i \xi_i$ $s. t. \quad \forall i: -(y_i \cdot(w^Tx_i +b)-1 + \xi_i)\leq0$ $\forall i: -\xi_i \leq0$

二、优化中的对偶问题

先来说优化中的原问题（primal problem）:
$minimize \quad f_0(x)$ $s. t. \quad f_i(x)\leq0, i=1,2, \cdots,m$ $\quad h_i(x)=0, i=1,2, \cdots,p$
这里的 $f_0(x)$ 不一定是凸的。

上述问题的Lagrangian定义为： $L(x, \lambda, v)=f_0(x)+\sum_{i=i}^m \lambda_i f_i(x)+\sum_{i=1}^p\nu_ih_i(x)$
其中 $\lambda, \nu$ 被称为拉格朗日乘子，或者对偶变量。

Lagrange dual function被定义为Lagrangian在 $x$ 的极小值，可以看作是Lagrangian的下界：
$g(\lambda, \nu)=inf_{x}L(x, \lambda, \nu)$
Lagrange dual function是凸的，尽管原问题可能是非凸的。
设 $p^*$ 是优化问题的最优值，对于 $\lambda \geq 0$ 和任意 $\nu$ ，以下关系都存在： $g(\lambda,\nu)\leq p^*$

假设 $\tilde{x}$ 是优化问题的一个可行点，如果 $\lambda \geq0$ ，那么由约束条件可以得到： $\sum_{i=1}^m\lambda_i f_i(\tilde{x})+\sum_{i=1}^p\nu_i h_i(\tilde{x}) \leq0$

因此可以得到： $L(\tilde{x}, \lambda, v)=f_0(\tilde{x})+\sum_{i=i}^m \lambda_i f_i(\tilde{x})+\sum_{i=1}^p\nu_ih_i(\tilde{x}) \leq f_0(\tilde{x})$

由dual function的定义可以得到： $g(\lambda, \nu)=inf_x L(x, \lambda, \nu) \leq L(\\tilde{x}, \lambda, \nu) \leq f_0(\tilde{x})$
这个不等式对于每个可行点都适用，因此，dual function同样也小于或等于最优解 $p^*$ ： $g(\lambda,\nu)\leq p^*$ .

拉格朗日对偶问题是，找到原问题的最优下界，优化问题写出来就是： $maximize \quad g(\lambda, \nu)$ $s.t. \lambda \geq 0$

如果记原问题的最优值为 $p^*$ ，对偶问题的最优值为 $d^*$ ，那么他们之间的差 $p^*-d^*$ 就是duality gap。如果 $p^*=d^*$ ，我们称之为strong duality，如果 $p^*>d^*$ ，就是weak duality。

Slater条件：给定一个凸优化问题，如果存在严格满足约束条件的点 $x$ ，这里的“严格”是指 “小于或等于号”要严格取到“小于号”： $f_i(x)<0, i=1,2, \cdots,m$ $\quad h_i(x)=0, i=1,2, \cdots,p$ , 那么存在strong duality。

KKT (Karush-Kuhn-Tucker) 条件：

原问题的约束： $f_i(x)<0, i=1,2, \cdots,m$ $h_i(x)=0, i=1,2, \cdots,p$ ,
对偶约束： $\lambda \geq 0$
complementary slackness: $\lambda_i f_i(x)=0$
Lagrangian L的梯度为0： $\nabla L(x, \lambda, v)=\nabla f_0(x)+\sum_{i=i}^m \lambda_i \nabla f_i(x)+\sum_{i=1}^p\nu_i \nabla h_i(x) =0$

如果一个问题满足strong duality并且有最优值，那就满足KKT条件。

最后，

对于具有strong duality且具有可微的目标和约束方程的优化问题，任何一对原始最优和对偶最优都一定满足KKT条件。
对于具有可微的目标和约束函数的凸优化问题，满足KKT条件的任何点都是原始和对偶的最优，并且duality gap为0。
如果具有可微的目标和约束函数的凸优化问题满足Slater条件，那么KKT条件为最优提供了必要条件。

三、支持向量与核函数

对于上面出现过的硬间隔问题计算它们的拉格朗日函数:
$L_D=\frac{1}{2}w^Tw-\sum_i \lambda_i(y_i \cdot (w^Tx_i+b)-1)$ $=\frac{1}{2}w^Tw-(\sum_i\lambda_iy_i \cdot x_i)^Tw-\sum_i\lambda_i y_i b+\sum_i \lambda_i$
令上面式中 $L_D$ 对 $w,b$ 的偏导为零，可以得到 $w = \sum_i \lambda_i y_i \cdot x_i$
$L_D= -\frac{1}{2}\sum_i\sum_j \lambda_i \lambda_j y_i y_j \cdot x_i^T x_j+\sum_i \lambda_i$
因此得到这个优化问题的拉格朗日对偶问题
$max \quad -\frac{1}{2}\sum_i\sum_j \lambda_i \lambda_j y_i y_j \cdot x_i^T x_j+\sum_i \lambda_i$ $s.t. \lambda \geq 0, \sum_i \lambda_iyi=0$

KKT条件中的 complementary slackness， $\lambda_i f_i(x)=0$ ，对于硬间隔的SVM来说就是： $\forall i: \lambda_i(y_i \cdot(w^Tx_i+b)-1)=0$
这个等式说明了，当 $\lambda_i >0$ 时， $y_i \cdot(w^Tx_i+b)=1$ , 所有 $\lambda_i >0$ 的 $x_i$ 都是边界平面上的元素，它们被称为支持向量。

由 $w = \sum_i \lambda_i y_i \cdot x_i$ 可以得到，决策边界的法向量时支持向量的线性集合。把这个式子重新带入决策方程，可以得到 $f(x) = \sum_i \lambda_i y_i \cdot x_i^Tx_i +b$ ，特征向量以内积的形式出现。

在现实生活中，样本空间也许并不存在一个能正确划分两种样本的超平面，对于这样的问题可以将样本映射到一个更高维的特征空间内。求解需要计算样本映射到高维特征空间之后的内积，这通常都是很难计算的。

而核函数的作用是 $x_i$ 与 $x_j$ 在特征空间的内积等于它们在原始样本空间中通过核函数计算的结果。因此可以使用核函数来代替内积，从而达到向高维空间映射的作用。

常见的核函数有：

核函数

对于求解决策方程，常用的算法是序列最小优化SMO算法，SMO算法的目标是求出一系列alpha和b，一旦求出了这些alpha，就很容易计算出权重向量w并得到分隔超平面。
SMO算法的工作原理是：每次循环中选择两个alpha进行优化处理。一旦找到一对合适的alpha，那么就增大其中一个同时减小另一个。这里所谓的“合适”就是指两个alpha必须要符合一定的条件，条件之一就是这两个alpha必须要在间隔边界之外，而其第二个条件则是这两个alpha还没有进行过区间化处理或者不在边界上。

参考：
https://blog.pluskid.org/?p=702
机器学习-周志华
机器学习实战

机器学习-SVM支持向量机

一、简介

二、优化中的对偶问题

三、支持向量与核函数

猜你喜欢

热点阅读