简述SVM

概述

SVM，即支持向量机（Support Vector Machine），是一种常见的监督学习算法，用于分类和回归问题。它是一种基于统计学习理论和结构风险最小化原则的机器学习方法。

SVM的主要思想是在特征空间中找到一个最优的超平面，将不同类别的样本点分隔开来。这个超平面可以被视为一个决策边界，用于对新的样本进行分类。SVM的目标是找到具有最大间隔(下图中margin的一半)的超平面，以实现更好的泛化性能。

超平面公式怎么推导

假设x0为超平面上的一点,w为超平面的法向量,对于超平面上任意的一点x都存在

w·(x-x0) = w·x - w·x0 = 0

令-w·x0 = b,则变为

w·x + b = 0

函数距离和几何距离

在超平面w·x + b = 0确定的情况下,|w·x + b|可以相对地表示点x距离超平面的远近,对于二分类问题,如果w·x + b > 0,则x的类别被判定为1,否则判定为-1。如果y(w·x + b) > 0,则x的分类正确,并且y(w·x + b)的值越大,分类结果的确信度越大。

所以样本点(xi,yi)与超平面(w,b)之间的函数距离定义为d = yi(w·xi + b)

但是该定义存在问题,即w和b同时缩放k倍后,超平面没有变化(比如w·x + b = 0和2w·x + 2b = 0是同一个超平面),但是函数距离却变化了,于是我们需要求几何距离。

几何距离可以通过面与面的距离公式来算,因为离超平面最近的样本点其实可以看作是处在一个和超平面平行的面上,所以我们要求的其实是面w·x + b = 1和面w·x + b = 0的距离,由距离公式可得d = 1/||w||。

于是我们得到

$\left\{\begin{matrix}max \frac{1}{||w||} & \\s.t. y_{i}(w^{T}x_{i} + b) - 1 >= 0,i = 1,2,...,n & \end{matrix}\right.$

拉格朗日乘子法

再进行下一步之前,我们先来了解一下拉格朗日乘子法。

拉格朗日乘子法是一种在最优化的问题中寻找多元函数在其变量受到一个或多个条件的约束时的求局部极值的方法。这种方法可以将一个有n个变量和k个约束条件的最优化问题转换为一个解有n + k个变量的方程组的解的问题。

举个例子:求双曲线xy = 3上离原点最近的点。

首先根据问题得出min f(x,y) = x^2 + y^2 s.t. xy = 3

如下图

可以看出,xy = 3和f(x,y) = x^2 + y^2的曲线簇的切点,就是我们要求的距离原点最近的点。

又有如果两个曲线相切,那么它们的切线相同,即法向量是相互平行的,于是由▽f//▽g可得▽f = λ*▽g。

这时,就将原有的约束优化问题转化为了一种对偶的无约束优化问题

原问题：

对偶问题：

min f(x,y) = x2 + y2

s.t. xy = 3

由▽f = λ*▽g得：

fx = λ*gx (1)

xy = 3

约束优化问题

无约束方程组问题

接着对上面的(1)式分别对x和y求偏导,得到2x = λ*y, 2y = λ*x, xy = 3

通过求解方程得λ = ±2,当λ = 2时,x = sqrt(3),y = sqrt(3)或者x = sqrt(3),y = sqrt(3);当λ = -2时无解。

从等式约束到非等式约束

现在回到之前的问题,我们发现,在上面的例子中,约束条件是一个等式,而在我们的问题中约束条件s.t. yi(w·xi + b) - 1 >= 0,i=1,2,...,n是一个不等式,那么非等式约束又该怎么处理呢?

下图展示了拉格朗日乘子法的几何含义:红色曲线表示等式约束g(x) = 0,红色曲线围成的曲面内表示非等式约束g(x) <= 0

非等式约束g(x) <= 0的情形中,最优点x要么出现在边界g(x) = 0上,要么出现在区域g(x) < 0中,

对于g(x) < 0的情况,因为▽f(x)方向向里,因此约束条件g(x) <= 0不起作用,我们只需要通过条件▽f(x) = 0求得可能的极值即可

对于g(x) = 0的情况,类似于之前提到的等式约束,但是▽f(x)的方向和▽g(x)的方向必须相反,即存在常数λ > 0使得▽f(x) + λ*▽g(x) = 0

当最优值落在g(x) < 0区域时,约束条件g(x) <= 0不起作用,因此我们令约束条件的乘子λ = 0,当最优值落在g(x) = 0边界上时,λg(x)自然等于0。综合这两种情况,可以推出λg(x) = 0。

因此,拉格朗日乘子法可以写成如下的等价形式,括号中的条件也叫做KKT条件。

L(x,λ) = f(x) + λ*g(x)

$\left\{\begin{matrix}g(x) <= 0 \\ \lambda >= 0 \\ \lambda *g(x) = 0 \end{matrix}\right.$

从原函数到对偶问题

接着考虑之前得到的目标函数

$\left\{\begin{matrix}max \frac{1}{||w||} & \\s.t. y_{i}(w^{T}x_{i} + b) - 1 >= 0,i = 1,2,...,n & \end{matrix}\right.$

由于求 $\frac{1}{||w||}$ 的最大值相当于求 $\frac{1}{2}\left \| w \right \|^{2}$ 的最小值,所以上述目标函数等价于

$\left\{\begin{matrix}min \frac{1}{2}\left \| w \right \|^{2} & \\s.t. y_{i}(w^{T}x_{i} + b) - 1 >= 0,i = 1,2,...,n & \end{matrix}\right.$

因为现在的目标函数是二次的,约束条件是线性的,所以它是一个凸二次规划问题(之所以等价于 $\frac{1}{2}\left \| w \right \|^{2}$ 而不是等价于 $\left \| w \right \|$ 就是为了将它转化为一个凸二次规划问题)

此外,由于这个问题的特殊结构,还可以通过拉格朗日对偶性变换到对偶变量的优化问题,即通过求解与原问题等价的对偶问题得到原始问题的最优解,这就是线性可分条件下支持向量机的对偶算法,这样做的优点在于:一者对偶问题往往更容易求解;二者可以自然的引入核函数,进而推广到非线性分类问题。

那什么是拉格朗日对偶性呢?简单来讲,通过给每一个约束条件加上一个拉格朗日乘子α,定义拉格朗日函数如下

然后令

容易验证,当某个约束条件不满足时,例如 $y_{i}(w^{T}x_{i} + b) < 1$ ,那么显然有 $\theta (x) = \infty$ (只要令 $\alpha _{i} = \infty$ 即可)。而当所有约束条件都满足时,则最优值为 $\theta (x) = \frac{1}{2}\left \| w \right \|^{2}$ ,亦即最初要最小化的量。

因此,在要求约束条件得到满足的情况下最小化 $\frac{1}{2}\left \| w \right \|^{2}$ ,实际上等价于直接最小化 $\theta (x)$ (当然,这里也有约束条件，就是≥0,i=1,…,n),因为如果约束条件没有得到满足, $\theta (x)$ 会等于无穷大,自然不会是我们所要求的最小值。

具体写出来,目标函数变成了：

这里用 $p^{*}$ 表示这个问题的最优值,且和最初的问题是等价的。如果直接求解,那么一上来便得面对w和b两个参数,而 $\alpha _{i}$ 又是不等式约束,这个求解过程不好做。不妨把最小和最大的位置交换一下,变成：

交换以后的新问题是原始问题的对偶问题，这个新问题的最优值用 $d^{*}$ 来表示。而且有 $d^{*}$ ≤ $p^{*}$ ，在满足某些条件的情况下(这个条件指的是强对偶,Slater条件是强对偶的充分条件),这两者相等,即 $d^{*}$ = $p^{*}$ ,这个时候就可以通过求解对偶问题来间接地求解原始问题。

换言之,之所以从minmax的原始问题 $p^{*}$ ,转化为maxmin的对偶问题 $d^{*}$ ,一者因为 $d^{*}$ 是 $p^{*}$ 的近似解,二者,转化为对偶问题后,更容易求解。

所谓Slater 条件,即指:凸优化问题,如果存在一个点x,使得所有等式约束都成立,并且所有不等式约束都严格成立(即取严格不等号，而非等号),则满足Slater 条件。对于此处,Slater条件成立,所以 $d^{*}$ ≤ $p^{*}$ 可以取等号,即 $d^{*}$ = $p^{*}$ ,所以我们对对偶问题的求解等价于对原问题的求解。

下面可以先求L 对w、b的极小,再求L 对的极大。