支持向量机笔记（Support vetctor Machines notes）

    支持向量机是一种二分类算法，CS229的notes中称之为最好的监督学习方法之一（among the best “off-the-shelf” supervised learning algorithm），他的基本模型是定义在特征空间上的间隔最大的线性分类器。本博客将从间隔（Margins）开始，对其基本原理进行推导与整理

(ps: 部分****下Latex公式无法转换用图片表示)

函数与几何间隔（Functional margins & Geometric margins）

    支持向量机的最终目标是对给定的数据集找到一条线性分割线（超平面hyperplane），并转化为凸优化问题求解，为了定义数据点与超平面的间隔，首先引入间隔的概念。

Figure 1

    首先定义函数间隔：

    其中， y取{-1，+1}用于表示对应数据点的实际分类类型，$w^Tx+b$表示在超平面的某一侧的分离程度，正负号代表在当前超平面的某一侧，从而当y取+1$w^Tx+b$也取正值时，间隔值为正，当y取-1$w^Tx+b$取负值时，间隔值也为正，可以看出，这个值的大小反应了对当前数据点的分离程度。（ps: *w 与b的取值大小不会影响超平面但会影响函数间隔的大小）

   而对数据集的函数间隔表示为:

   几何间隔：

Figure 2

    

    w与超平面相垂直，如果A点为图二中AB点距离代表了,B点可以推导为：

$$w^T(x^{(i)}-\gamma^{(i)}\frac{w}{||w||})+b=0$$

    解上式3可以推导几何间隔。

    几何间隔代表数据点与超平面的实际距离，定义为：

$$\gamma^{(i)}=y^{(i)}((\frac{w}{||w||})^Tx^{(i)}+\frac{b}{||w||})$$

$$\gamma=\min_{i=1,...,m}\gamma^{(i)}$$

优化方程与拉格朗日对偶

    初步的优化方程：

    然而，要求解这个优化方程十分困难，它的约束条件中||w||=1保证了函数间隔和几何间隔的一致性，但是具有非凸性，现有的优化技术无法简单求解，所以要对这个问题进行进一步的转化。

    

    此时，我们将优化目标转变成了，我们消除了||w||=1的条件，但是实际上这这个优化目标依然具有非凸性。

    此时，我们进一步分析，在本式中w和b值倍数的变化不会影响优化结果与超平面，我们可以通过改变w和b来限制$\hat\gamma$值从而使：

$$\hat\gamma=1$$

    那么原式优化目标可以转化为1/||w||，同时max1/||w||与min||w||^2效果相同，我们得到了最终可行的优化式子：

    此时，该优化式可以用二次规划（quadratic programming）求解。

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

    现在讨论该优化方程适用该方法的原理。

    首先通过拉格朗日乘子a将上述优化式子转化为：

    拉格朗日法的思路是，通过求maxL(w,b,a)将原优化问题的约束项消除，即:

$$\max L(w,b,a) = \frac{ 1}{ 2}||w||^2$$

    这是因为，当后式不满足约束条件时，即：

$$y^{(i)}(w^Tx+b)-1<0$$

    而a>=0通过增大a值可以将该方程变为无限大，即无解。

    于是我们得到的：

$$p*=\min \max L(w, b, a)$$

    即优化式, p这里指原式解。

    而拉格朗日法另一个好处是，多数时候改变min与max的顺序将极大简化优化的难度，即求解原问题的对偶问题，但前提要满足一定的条件（KKT方程）

    

    我们不直接更具原式推导KKT方程，而是先探讨对偶问题的求解即：

$$d*=\max \min L(w, b, a)$$

    首先要注意，在求minL(w,b,a)时，我们是固定拉格朗日乘子a，优化w,b求解，此时拉格朗日法的优点便能呈现，要求解minL(w,b,a)我们只需要对w和b求偏导：

    对b:

    $$\frac{\partial}{\partial b}L(w,b,a)= \sum_{ i=1}^{ m}a_iy^{ (i)}=0$$

    对w:

    $$\frac{\partial}{\partial w}L(w,b,a) = w - \sum_{ i=1}^{ m}a_iy^{(i)}x^{(i)}=0$$

    则：

    $$w = \sum_{ i=1}^{ m}a_iy^{(i)}x^{(i)}$$

    于是带入原L(w,b,a)可以转化为:

    上面说过，要使对偶问题与原问题等价要满足KKT方程，而在此时上式已经满足KKT方程，则对改优化问题求解即可得到原问题解。

    在得到最优解的a值后我们可以通过上面w与a的关系式求解w，而b则需要通过：

    

支持向量

    当优化完成并求解后，实线即解的超平面，最小间隔的三个点分别在虚线上，而仅有这三个点对应的拉格朗日乘子a是非0项，即该算法的关键，这三个点被称为支持向量。一般来说，支持向量的个数要远小于数据集数量。

• 在一般问题中，出现内积（inner product）部分可以转化为核函数，增加效率
• 核函数是两个映射的积，求解过程中不必直接算出映射。
• 核函数大小反应的是两个映射空间上的相近程度，约相近核函数结果越大
• 核函数的使用需要通过验证（具体方法不在本博客提出）

References

[1] Standford CS229 Lecture Notes of Support Vector Machine