CAU数据挖掘 支持向量机

SVM大致思想

线性分类问题

在一群点中用线性函数分类：

但也有线性不可分问题：

线性不可分问题：

最大间隔法

两个平行超平面间隔距离最大

软间隔

部分难以区分的点忽略

升维

通过升维将非线性变为线性

计算统计理论基础

学习过程的一致性

期望风险泛函：定义最优函数在真实数据分布中的期望风险
经验风险泛函：在有限的数据集上最优函数的期望风险。
由于真实分布未知，机器学习传统都是用最小化经验风险来替代最小化期望风险的目标
学习理论的关键定理的解读：如果一个模型方法在最坏情况下仍能表现良好， 则对它的推广能力才有信心。
函数集的容量

函数容量与VC维

容量（ capacity） ： 函数集在一组样本集上可能实现的分类方案数目。
例如：二分类问题中有n个样本，则有2**n种分类方案
生长函数：容量对数在所有可能样本集上的上界。
要达成学习过程一致性，函数集的一致性的能力不会跟随样本数无限增长
VC维：用函数集中的函数所能够打散的最大样本集的样本数目。
期望风险上限


推广能力： 不取决于经验风险最小能有多小， 而在于期望风险与经验风险有多大差距， 差距越小则推广能力越好。
特定的问题样本数是固定的： VC 维越高→函数集复杂性越高→置信范围就越大→推广能力就可能越差。
结构风险最小化原则SRM：


在小样本中应该遵循结构风险最小化原则SRM

理论中svm的优势

为什么要选择最大间隔

为什么要使用核函数升维

不适定问题与正则化方法

SVM中用到的最优化技巧

以二维为例子：

通过化简得到下面式子，确定最优化的目标函数

由最终式子可知，我们的最终目标是求尽量小的w。
接下来求约束条件：
在两线段两端的点被分类为1和-1
由此得到下面的约束条件

为了方便求解，目标函数做了一定处理。
接下来对不等式约束条件做一定处理变为等式：


这里得出${\lambda }_i$ $\ge$ 0。
因为：可以将${\lambda }_i$看成一个惩罚系数

当${\lambda }_i$为正数时，没有满足约束条件会加大原式，作为惩罚，而为负数时则变成了鼓励参数
从几何角度考虑这个问题：

从图中得出有用的约束条件${\lambda }_i$必定为正数，作用是保持约束梯度矢量和与目标梯度方向大小一致。
在这里进一步说明拉格朗日对偶问题：

从求导式子中可以看出，拉格朗日常数法的最终目的是得出一系列常数使目标函数梯度与约束条件梯度相等。

直观的从上图中来理解，最优点一定满足这样一个性质，最优点对于所有过这一点的约束条件上的梯度的可以用${\lambda }_i$作为参数矢量相加等于目标函数的梯度，而其他点（非最优点）没有这个性质。因此可以使用这种方法来寻找最优点，这也是拉格朗日常数法的原理。
而${\lambda }_i$=0则是说明对应的约束条件对于该最优化问题是无效的，即松弛的约束条件。

拉格朗日对偶问题

为方便理解，我们首先要将原问题变一下形。

我们将这个等价问题中的min与max交换一下即可得到等价命题：

将对偶函数的最小值部分变为约束条件得到下图：

这时我们将对偶问题展开：

g($\lambda$, v)是一个仿射集也会是一个凹凸函数，对他求最大值则是对一个凹函数求最大值，约束条件为半空间$\lambda$，v $\ge$ 0，则这总是一个凸优化问题。

强对偶与弱对偶

虽然对偶问题是一个凸优化问题，但原问题只有在与对偶问题强对偶的情况下才能转换为对偶问题


注意A(x)和I($\lambda$, v)都是L(x,$\lambda$, v)的衍生函数，均由L(x,$\lambda$, v)唯一确定。
由上述推断出原问题与对偶问题不总是等价的。

下面通过图形的方式直观说明，为了方便可视化进行如下变换

接下来进行可视化

解析：原问题求$G_1$在t轴的最低点，对偶问题的值为一跳直线的截距，且斜率为负数。先取最小值决定了直线只能紧贴取值域的下端，而这些下端中相对取值最大的则真好如图所示，当对偶问题求最大$\lambda$时必定过$G_1$最低点。
当可行域的范围是一个凸集时，则会成为一个强对偶问题。
在下列两种情况中都是强对偶问题


强对偶的充分条件
凸优化问题并要满足Slash条件

图示如下：

强对偶的必要条件

同时在凸问题中KKT可以推出最优解

回到SVM问题中

在原拉格朗日常数法中已经获得了原问题可行解和梯度为0条件

1，2为原问题可行解，3为梯度为0条件
通过上述描述，用3，4推出互补松弛条件和最后一个对偶可行性。
补松弛条件：

对偶可行性：

由此所有KKT条件集齐：

由于SVM为凸问题，我们已经得到求取最优点的方法。

SVM中使用拉格朗日对偶

原因：为了方便使用核技巧和提升求解效率。
首先根据上述直接给出SVM的对偶问题：

接下来证明​Slater条件成立
以硬间隔问题为例：因为数据线性可分，总有($\omega$， b)使得一条直线将所有点分为两类，即满足所有不等式约束，Slater条件自动满足。
软间隔只是允许一定的误差，原理相同。
由此证明SVM是强对偶问题。
接下来将KKT条件代入对偶问题

然后简化求解

通过对偶问题后约束仅有$\lambda$，并且可以使用核技巧。

核技巧

当处理非线性可分问题时，需要升维。
我们很容易想到方法一：

但方法一可以更容易的写成方法二：
上述核函数可以通过修改参数确定维度
那么有没有什么核函数可以转换成无穷维呢？
高斯核函数可以通过无穷级数变为无穷维