支持向量机笔记

之前我们介绍过PLA算法，对于线性可分的情况，找到一条线，能够区分开正负样本。但是PLA的解具有随机性的特点，我们会得到多组不同的解，那么哪一个才是最好的呢？

我们可以从鲁棒性的角度来考虑，一个好的模型应该对噪声具有很强的容忍性。最右边的线离与它最近的点是最远的，能够容忍较大的测量误差，从鲁棒性的角度来讲是最佳的。

形象点来描述就是我们要找出一条最胖的线，也就是Margin最大，

接下来，我们考虑下如何表示这个Margin，实际上就是求点到超平面的距离

点到平面的距离等价于点与平面内任意一点所组成的向量在平面法向量上的投影。

原来的问题可以表示为：

我们来做一点简化，因为对超平面进行缩放实际上对我们最后的结果不会有任何影响，我们可以做如下变换

我们在解不变的情况下，放松下约束条件

问题可以转化为标准的二次规划问题，

但是直接这样解算法的是与样本的维度相关的，当样本维度很高甚至接近无穷时，这样来解就不太实际了。

我们先利用拉格朗日乘数法将问题转化为无约束问题，

我们可以做对偶转换，

在对偶问题下，求解算法的复杂度与样本数量（等于拉格朗日算子a的数量）有关。

利用偏导等于0进行化简，

化简得，

整理可得，

整个SVM的求解过程我们可以概括为：先根据对偶确定Support Vectors，然后根据Support Vectors确定最佳的分类超平面。

那么对偶问题的计算复杂度真的与样本维度无关吗？

下一篇重点讨论。