[toc]

SVM是一类按监督学习方式对数据进行非概率二元分类的广义线性分类器，学习策略是间隔最大化，使最终转化为凸二次规划问题求解

由简至繁有如下几个模型：

  • 线性可分SVM：

    当训练数据线性可分时，通过硬间隔(==hard margin==)最大化可以学习得到一个线性分类器，即硬间隔SVM。

  • 线性SVM：

    当训练数据不能线性可分但是可以近似线性可分时，通过软间隔(soft margin)最大化也可以学习到一个线性分类器，即软间隔SVM。

  • 非线性SVM：

    当训练数据线性不可分时，通过使用核技巧(kernel trick)和软间隔最大化，可以学习到一个非线性SVM。

当输入空间为欧式空间或离散集合、特征空间为希尔伯特空间时，核函数表示将输入从输入空间映射到特征空间得到特征空间之间的内积，可以学习到非线性支持向量机。等价于隐式地在高维的特征空间中学习线性支持向量机

函数间隔与几何间隔

函数间隔： $\widehatγ = y(w T x + b) = yf(x)$,数据集中所有样本点的函数间隔最小值即为数据集的函数间隔

考虑到上述定义中若成比例修改$w$和$b$的值，$f(x)$的值也会改变，但是超平面并没有变化，因此要对$w$加上约束条件

几何间隔：t通过几何距离得出， $γ = \frac{(w^T x + b)}{ ∥w∥} = \frac{f(x)}{ ∥w∥}$,为了得到绝对值再乘上标签$y$,即 $\widetilde γ =\frac{\widehatγ}{ ∥w∥}$ ，就是函数间隔除以 $∥w∥$

因此要找的最大间隔分类器的目标函数可以定义为 $max \widetilde γ$，且根据间隔定义有：

​ $y_i(w^T x_i + b) = \widehatγ_i ≥ \widehatγ, i = 1, …, n$

假设 $\widehatγ = 1$，则目标函数转化成了：

​ $max\frac{1}{∥w∥},s.t.y_i(w^T x_i + b)\geq 1$

深入推导

从原始问题到对偶问题求解

继续变换上述目标函数为：$min\frac{1}{2} ∥w∥^2,s.t.y_i(w^T x_i + b)\geq 1$ $(1)$

由于目标函数是二次的，约束条件是线性的，问题最终被转化为一个凸二次规划问题，可直接使用 $Quadratic\ Programming$优化包求解,同时由于这个问题的特殊结构，还可以通过拉格朗日对偶性（Lagrange Duality） 变换到对偶变量 (dual variable) 的优化问题，即通过求解与原问题等价的对偶问题 （dual problem）得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：对偶问题往往更容易求解；同时可以自然的引入核函数， 进而推广到非线性分类问题。

最大间隔超平面的存在唯一性

  1. 存在性：由于数据集线性可分，由 $(1)$ 知，必定存在可行解，记作$(w^,b^)$，可知超平面存在的情况下，$w$不会为0

  2. 唯一性：若存在多个最优解$(w_1,b_1),(w_2,b_2)$,显然$∥w_1∥=∥w_2∥=c$,分别代入约束函数并左右相加得： $ y_i(\frac{w_1+w_2}{2} x_i + \frac{b_1+b_2}{2})\geq 1$，

    即新的可行 $w =\frac{w_1+w_2}{2},b = \frac{b_1+b_2}{2}$

    已知向量和的模小于等于向量模的和：故 $ c\leq\ ∥w∥\leq \frac{1}{2}(∥w_1∥+∥w_2∥)=c$，所以$w_1=λw_2$，其中$λ=1、-1$，若为-1，$w = 0$,与存在性相悖，故$w_1 = w_2$

    再任意找几个点分别对应两个超平面进行计算可得出，$b_1 = b_2$

支持向量与间隔边界

支持向量：数据集中样本点与分离超平面距离最近的点，是使约束条件等号成立的点

间隔边界：正负支持向量样本点所在的超平面

由此可知决定分离超平面的只有支持向量，如果移动支持向量将改变所求的解，而改变其他点不会有任何影响

拉格朗日对偶性:通过给每一个约束条件加上一个拉格朗日乘子α，定义拉格朗日函数，通过拉格朗日函数将约束条件融合到目标函数里去，从而只用一个函数表达式便能清楚的表达出问题：

$L(w, b, α) = \frac1 2 ∥w∥^2 − ∑^n_{i=1} α_i(y_i(w^T x_i + b) − 1)$

非支持向量机与核函数

核技巧

参考

  1. 支持向量机通俗理论
  2. 凸优化
  3. 拉格朗日对偶性
  4. 对偶变量优化问题