支持向量机

缩写：SVM（Support Vector Machine）

定义：最大化间隔的线性分类器

SVM 是从线性可分情况下的最优分类面发展而来的，其基本思想可用下图说明。图中的黑色点和白色点代表两类样本，现在需要用一条直线将这两类样本分隔开，这条线用W•x-b 表示。假设当W•x-b =1时直线已经穿过了黑色点，W•x-b =-1时直线穿过了白色点，那么这两条线之间的所有直线，都可将这两类样本分开。而所谓的最优分类面，就是要求分类面不但能将两类正确分开，而且使分类间隔最大。如图中的实线W•x-b =0所示。推广到高维空间，最优分类线就变为最优分类面。

这两个位于边缘上的平行的分类面之间的距离可表示为。由于数据点有两类，每个样本可用y= 1（黑色点）或-1（白色点）来表示。那么，所有点都在平面之外可以表示为约束条件。所以这种线性可分的SVM模型就转化成了一个约束极值问题

上方称为目标函数，下方称为约束条件。确定了线性可分SVM模型后，通过求解该模型就可以得到两个平行超平面的方程，我们取两个平行超平面的中间平面作为判别函数。

而对于线性不可分模型，也就是上图中的白色点中有少许黑色点，这时我们容许分类错误出现，目标函数变为。在限制条件中本来要求任意的点都要在两个平行超平面之外，现在如果一个点不能被准确分开，它偏离平行超平面的距离就会被记录为最后的目标函数上修改成平行超平面的距离加上误差的和，参数C用于调节两者权重。线性不可分SVM又称为软间隔SVM（soft margin）。

对于这种约束问题，常使用拉格朗日乘子法，将约束与目标函数组合，将目标函数变为

而在求解时，由于λ是有约束的，需要先最小化w，再最大化λ。在求解此式时，通常转换为其对偶问题求解，也就是此转化方式这里不加赘述（SVM满足KKT条件，满足此条件的原问题和对偶问题等价）。由对偶问题转换为λ的函数后，可进一步迭代求解其极值。

参考文献

[1] Cortes C, Vapnik V. Support-vector networks[J]. Machine learning, 1995, 20(3): 273-297.
[2] Cristianini N, Shawe-Taylor J. An introduction to support vector machines and other kernel-based learning methods[M]. Cambridge university press, 2000.
[3] Karush W. Minima of functions of several variables with inequalities as side constraints, 1939
Gale D, Kuhn H W, Tucker A W. Linear programming and the theory of games, 1951

参阅：核方法，有监督学习，线性分类器，拉格朗日乘子法，对偶问题，SMO算法

　

本文为原创内容，所有权归本网站所有，禁止转载。违反上述声明者，将追究其相关法律责任

- END -