svm超详细推导

   支持向量机是一种二分类模型，他的基本想法就是基于训练集和样本空间中找到一个最好的划分超平面，将两类样本分割开来，首先你就要知道什么样的划分发才能称为“最”好划分

  看上图，二维平面上有两类样本，一类是用‘+’表示，另一类用‘-’表示，那么中间那几条划分线每条都能将两类样本分割开来，但我们我们一眼就注意到中间那条加粗的划分超平面，似乎他是最好的，因为两类的样本点都离他挺远的，专业点说就是该划分超平面对训练样本局部扰动的‘容忍’性最好。好，这还只是个二维平面，我们可以通过可视化大概寻找这样一个超平面，但如果三维，四维，五维呢，我们必须用我们擅长的数学去描述它，推导它。        

        在样本空间中，划分超平面可用表示，记为（w,b）,样本点（xi,yi）到划分超平面的函数间隔为，几何间隔为：

     若，可知函数间隔和几何间隔相等，若超平面参数w，b成比例的改变（超平面没有变），则函数间隔也是成比例的改变，而几何间隔不变。

   支持向量机的基本想法就是求解能够正确划分训练数据集并且几何间隔最大的分离超平面，表达为数学公式即为：发    

       其实函数间隔的取值并不影响最优化问题的解，假设将w和b成倍的改变为aw，ab，那么函数间隔也会相应变成a，函数间隔的对上面最优化问题的不等式没有影响，也对目标函数没有影响，因此为简便，取，而且我们注意到最大化等价于最小化（为啥取平方呢，因为后面好求导），便可得到下面支持线性可分（线性不可分的情况后面会提到）的支持向量机的最优化问题

这是一个凸二次优化的问题，可以直接求解，但是为了简便呢，我们要应用拉格朗日对偶性，求解他的对偶问题

    其实求解对偶问题相比于原问题有一下几点好处(1).对偶问题更容易求解，因为不用求w了 (2)我们可以自然引入核函数，这样可以推广到线性不可分分类问题上

   建立拉格朗日函数，引进拉格朗日乘子，定义拉格朗日函数：

根据原始问题的对偶性，原始问题的对偶性是极大极小问题，即

首先我们来求最小，零L(w,b,a)分别对w和b求导为零可得

将其代入对偶问题，可得

解出alpha之后，那么w，b也相应得到啦

接下来，我们看看很有意思的上式不等式约束的kkt条件（不懂请百度）带给我们的信息

咦，对于任意训练样本，总有或者，也就是说最终与模型有关的的样本点都位于最大间隔的边界上，我们称之为支持向量，其余的样本点与模型无关

在前面的讨论中，我们都是聊的线性可分的情况，那么大多数情况下都线性不可分怎么办，比如这样（如左）

山人自有妙计，我们可以将样本先映射到高维特征空间，然后就可以继续分割了（如右）

前面我们说到了对偶问题是

公式中涉及到计算，xi，xj是映射到特征空间之后的内积，由于特征维数可能会很高，甚至是无穷多维，直接计算很困难，所以我们引入了核函数

这样我们就可以不用麻烦的计算内积了