SVM的推导（非常详细）

SVM的推导（非常详细）

参考自（https://www.zhihu.com/search?q=svm%E6%8E%A8%E5%AF%BC&utm_content=search_suggestion&type=content）
还有李航的统计学习。

支持向量机有三个部分的内容，线性可分支持向量机，软间隔支持向量机，核函数。

目标函数的得出

首先SVM是一个线性分类器，SVM的目标就是找到最大间隔超平面。
我们定义任意的超平面函数为：



看上面的图，最中间的那条线就是（这里的w*就是上面的Wt）：（虽然很直观，但是为什么呢？你怎么知道最中间的那个平面就是下面这个表达式呢？其实很简单，因为在这个最中间的平面一边都是大于零的点，另一边都是小于零的点，所以这个平面自然就是下面这个表达式了。）

而我们要求的分类决策函数就是：

这个就是线性可分支持向量机。

所以假设点到平面的距离为r，有下面的公式：

这个我们称为函数间隔，这是我们要求的函数形式，但是不是实际意义上的几何间隔。所以我们将函数间隔和几何间隔进行转化，我们的目标就是要最大化这个间隔。


（这里y的值为1或者是-1，所以上式必然成立。）
上面这个就是几何间隔。所以我们可以轻易得到几何间隔与函数间隔之间的关系：

接下来就有了我们初步的优化函数：

利用上面几何间隔和函数间隔之间的转化公式可有下面的式子：

又因为最小化1/||w||可以转化为求最大化1/2 *||w||，1/2的作用就是为了求导消除计算方便。所以有了下面最终的目标函数：

写了这个一大堆其实完全没必要。。。。。看一下下面这张图，这里我们假设r=1，所以两个平面的距离自然就是下面的2/||w||了。

这里r=1完全是为了计算方便，因为r的取值并不会影响最后的目标函数的优化。

拉格朗日求极值

对于这个优化我们自然能够想到用拉格朗日求极值。

但是再进行真正的求极值时，我们需要考虑一些不等式约束优化的问题。

不等式优化的步骤：（KKT条件的推导）





现在我们的目标函数如下：（这里的α就是上面推导过程中的λ）

由拉格朗日的对偶性,上面问题等价于求：

其中：




我们可以看出来这是一个二次规划问题，问题规模正比于训练样本数，我们常用 SMO(Sequential Minimal Optimization) 算法求解。

序列最小优化(Sequential Minimal Optimiation, SMO)算法

SMO(Sequential Minimal Optimization)，序列最小优化算法，其核心思想非常简单：每次只优化一个参数，其他参数先固定住，仅求当前这个优化参数的极值。我们来看一下 SMO 算法在 SVM 中的应用。

这就是SMO算法的步骤。
根据SMO算法我们可以求得：



至此，基本的线性SVM就已经求完了。下面的软间隔和核函数基本原理跟上面一致。

软间隔最大化

转化为对偶问题：

惩罚参数C的讨论：
对于不同的惩罚参数C，SVM的结果如下图所示：（从左到右分别是C=100,C=1,C=0.01）


前一项可以理解为“结构风险(structural risk)”，用来描述所求模型的某些性质(SVM就是要求间隔最大)；第二项称为“经验风险(empirical risk)”，用来描述模型与训练数据的契合程度(即误差)。而参数C就是用于对二者的折中,即我们一方面要求模型要满足某种性质另一方面又想使模型与训练数据很契合。

非线性SVM——核技巧

前面介绍的都是线性问题，但是我们经常会遇到非线性的问题(例如异或问题)，此时就需要用到核技巧(kernel trick)将线性支持向量机推广到非线性支持向量机。需要注意的是，不仅仅是SVM，很多线性模型都可以用核技巧推广到非线性模型，例如核线性判别分析(KLDA)。

如下图所示，核技巧的基本思路分为两步:使用一个变换将原空间的数据映射到新空间(例如更高维甚至无穷维的空间)；然后在新空间里用线性方法从训练数据中学习得到模型。


我们不禁有个疑问：只是做个内积运算，为什么要有核函数的呢？

这是因为低维空间映射到高维空间后维度可能会很大，如果将全部样本的点乘全部计算好，这样的计算量太大了。

然后在进行内积计算，才能与多项式核函数达到相同的效果。

可见核函数的引入一方面减少了我们计算量，另一方面也减少了我们存储数据的内存使用量。
常见核函数：

优点：
1、有严格的数学理论支持，可解释性强，不依靠统计方法，从而简化了通常的分类和回归问题；
2、能找出对任务至关重要的关键样本（即：支持向量）；
3、采用核技巧之后，可以处理非线性分类/回归任务；
4、最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。

缺点：