ch9 支持向量机

总览

• 拉格朗日乘子法
• VC维、结构化风险最小化
• SVM基本型
• SVM软间隔
• SVM核函数

拉格朗日乘子法

根据凸规划最优条件可知，最优解时目标函数正交于约束平面，即：

$$\mathrm{\nabla }f(x^{\star },y^{\star })=\lambda \mathrm{\nabla }g(x^{\star },y^{\star })$$

拉格朗日函数：

$$L(x;\lambda )=f(x)+\lambda g(x)$$

对x求导取0，可得：

$$\mathrm{\nabla }f(x)+\lambda \mathrm{\nabla }g(x)=0$$

对$\lambda$求导取0，可得：

$$g(x)=0$$

对于约束优化问题： 使用拉格朗日乘子法即可转化为无约束优化问题。

如果约束条件不止一个，则：

$$L(x;\mathrm{\Lambda })=f(x)+\sum _{i=1}^m{\lambda }_i{g}_i(x)$$

考虑不等式约束：

以$g(x)\le 0$为例，当$g(x)=0$时类似于等式约束，但是此时的$\mathrm{\nabla }f(x)$与$\mathrm{\nabla }g(x)$必须方向相反，也就是$\lambda >0$。当$g(x)<0$时，约束不起作用，此时等价于$\lambda =0$，然后直接对拉格朗日函数求导取0。总结为KTT条件：

转化为对偶问题

拉格朗日对偶函数给出了主问题的最优值的下界。是主问题的对偶问题，其中$\lambda$和$\mu$称为“对偶变量”(dual variable)。无论主问题的凸性如何，对偶问题始终是凸优化问题。若主问题时凸优化问题，那么强对偶性成立，对偶问题解决了原问题也就解决了。

对偶问题只能得出主问题最优解的下界，不一定是其最优解，但是我们可以根据其值来逼近最优解；如果强对偶性成立，那么对偶问题的解就是主问题的一个最优解。

将拉格朗日函数对x求偏导并令导数为0，即可得到x关于$\lambda ,\mu$的表达式，将x代入就得到了对偶函数的表达式。

VC维、结构化风险最小化

期望风险：

$$R(\alpha )=\int \frac{1}{2}|y-f(x,a)|dP(x,y)$$

经验风险：

$$R_{emp}(\alpha )=\frac{1}{2l}\sum _{i=1}^l|y-f(x,a)|$$

结构化风险最小化

目标：同时学习用于分类正确的“结构”和正确的“规则”。

总风险 = 经验风险 + 由于学习机器结构导致的风险

VC维

对一个指示函数集，如果存在l个样本，能够被函数集中的函数按所有可能的$2^l$种形式分开，则称函数集能够把l个样本打散。函数集的VC维就是它能打散的最大样本数目l。

VC维反映了函数集的学习能力，VC维越大则学习机器越复杂（容量越大），学习能力越强。VC维度与参数数量没有直接关系。

期望风险和经验风险的关系： h是VC维数，I是样本数目

结构风险最小化想最小化边界值，传统方法只能最小化经验风险。

结构风险最小化原理的基本想法：如果我们要求风险最小，就需要使得不等式中两项相互权衡，共同趋于极小。另外，在获得的学习模型经验风险最小的同时希望学习模型的泛化能力尽可能大，这样就需要h值尽可能小，即置信风险最小。

如果固定训练样本数目的大小，则控制风险R(α)的参量有: Remp(α)和h。经验风险$R_{emp}(\alpha )$依赖于学习机器所选定的函数$f(\alpha ,x)$，我们可以通过控制α来控制经验风险。VC维h依赖于学习机器所工作的函数集合。为了获得对h的控制，可以将函数集合结构化，建立h与各函数子结构之间的关系，通过控制对函数结构的选择来达到控制VC维h的目的。

SVM基本型

对于$D=\{(x_1,y_1),(x_2,y_2),\dots ,(x_m,y_m)\}$，其中$x_i\in R^n,y_i\in \{-1,+1\}$。

首先划分超平面：

$$w^{T}x+b=0$$

使用超平面将训练样本正确划分：

$$\begin{gathered} y_i(w^T{x}_i+b)\ge +1,y_i=+1 \\ {y}_i(w^T{x}_i+b)\le -1,y_i=-1 \end{gathered}$$

可以转化为：

$$y_i(w^T{x}_i+b)\ge 1$$

空间任意点到超平面的距离为：

$$r=\frac{|w^{T}x+b|}{||w||}$$

支持向量x到超平面的距离为：

$$r=\frac{1}{||w||}$$

间隔为：

$$\gamma =\frac{2}{||w||}$$

最大间隔问题可以表示并转化为：

$$\underset{w,b}{max}\frac{2}{||w||}\to min\frac{1}{2}||w|{|}^2$$

同时需要满足约束条件：

具有最大间隔的线性判别函数是最好的，直观上对于离群点有鲁棒性，因此具有很强的泛化能力。 即使每条线都能正确的划分样本点，也有相同的VC维，但是并不是每一个都可以的，面对他们从没见过的图像时泛化能力差异很大。

间隔和VC维的关系： 对于上述问题，间隔为0的时候，VC维为3（空间维度+1）；间隔大于$\frac{\sqrt{3}}{2}R$时，VC维小于3。VC维和空间维度有如下不等式关系：

$$h\le min((\frac{R}{r}{)}^2,d)+1\le d+1$$

拉格朗日法

由于前文通过转化的手法得到了需要满足的条件和目标函数，可以通过拉格朗日乘子法求解问题。将原问题转化为其对偶问题：

SMO序列最小优化算法

固定其他参数，仅仅优化两个参数。过程十分高效。

SVM软间隔

引入松弛变量${\xi }_i\ge 0$，将约束条件改为： 此时的拉格朗日函数为： 然后解对偶问题，是个二次规划。（能考这个我吃）

非线性SVM

其中的： 称之为替代损失。

SVM核函数

若原始空间是有限维，即属性有限，那么一定存在一个高维特征空间使样本可分。原始输入空间可以被映射到某个更高维的特征空间，在该特征空间中训练集是可分的。

核函数是否一定存在呢？： 一个对称函数是半正定的，就可以作为核函数。对于一个核函数，总能找到对应的$\varphi$函数。

核函数的选择：

1. 核函数的选择对支持向量机的性能至关重要
2. 一些常见的核函数如下
3. 核函数的函数组合也是核函数
4. 核函数选择是支持向量机中最大的变数

与NN的对比

	神经网络	支持向量机
映射器	隐藏层映射到低维空间	核映射到非常高维的空间
搜索空间	多个局部最小值	一个唯一的最小值
训练	昂贵	极其高效
分类	极其高效	极其高效
参数	需要隐藏单元和层数	需要选择核和成本这两个参数
场景	在典型领域中有很好的准确性	在典型领域中有很好的准确性
其他...		极其稳健