机器学习算法一：支持向量机（SVM）[上]

虽然目前网络中有大量关于机器学习算法的资料，但独自埋头苦学难免会觉得枯燥无味，所以我们将开展一系列机器学习算法交流学习活动，以加深巩固掌握的算法知识。我们也会定期将学习内容及调用算法的代码整理分享出来，如内容上有不足之处，欢迎给我们留言，一起交流学习。本期我们主要探讨的是支持向量机(SVM)算法。

1.支持向量机简介

支持向量机（Support Vector Machine,SVM）是机器学习中一种常用的监督学习算法，其优势主要表现在适合解决小样本、非线性和高维等分类问题，并具有较强的推广能力，在文本分类、人脸识别和语音模式识别等领域都有广泛的应用。"支持向量"是指那些在间隔区间边缘的训练样本点，这些点在分类过程中起决定性作用。"机"实际上是指一个算法，把算法当成一个机器。

支持向量机常用来解决二分类问题，其学习策略是通过学习一个线性分类面使不同类别的样本在特征空间上的间隔最大化，再转化为一个凸二次规划问题来求解。更形象的理解可以将两个不同类别的样本看作朝不同方向行驶的汽车，我们需要在这些汽车中间建立一块隔离带来将它们分开。显然，如果可以将隔离带的面积建得最大，那就可以正确无歧义的将他们分开，所以支持向量机的目标可以说是在约束条件下最大化两类样本点的间隔。

2．线性SVM

在处理非线性问题时，通常会将非线性问题转化为线性问题来处理。我们先针对线性SVM进行说明，对于两类不同的样本点，其类别可以用y=1或-1来表示，而线性分类面函数可以表示为：

f(x) = (w^T)*X+b = 0

其中w为权重向量系数，b为平面偏移量。通过映射关系，当f(x) = (w^T)*X+b > 0 时，y = 1；当f(x) = (w^T)*X+b < 0时，y = -1。根据训练样本得到这两个参数的值，就可以确定分类面，进而能够对新输入的样本进行分类。那我们如何来求解这两个参数？如下左图所示，每一条线对分开图中的两类样本都有效，但是哪一条是最好的呢？前面说过使两类样本点间隔最大化的分类面才是最好的分类面，故需要先找到最大间隔。

由于函数间隔的可变化性和几何间隔的不变行，样本点（xi,yi）到分割平面(w,b)的函数间隔为：r1 = Yi(w*Xi +b),几何间隔为r2 = Yi(w*Xi +b)/||w||,即函数间隔与几何间隔的关系为r2 = r1/||w||。我们所要求的最大化间隔，即求Max r1/||w||。因为函数间隔的值不会影响最优化问题的解，故可以假设离分离面最近的样本点到分离面的函数间隔r1 = 1,则其他样本点的间隔都不会小于1。同时将目标函数转化为等价形式求最小值，则目标函数和约束条件可以表示为：

3. 凸二次规划问题求解

目标问题为凸二次规划问题，存在全局最优解，将其转化为拉格朗日求极值问题，定义拉格朗日函数为：

则问题转变为：

由于先对求偏导并令其等于0，以消去来简化方程对求解w , b没有帮助，所以需要进行对偶变化。因问题满足KKT条件，故将原问题转化为其对偶问题：

在拉格朗日式子先对w和b求偏导并令其等于0，得到：

将w的表达式带入拉格朗日方程，得到：

问题转化为：

再将 w的表达式带入到支持平面方程中，解得b的值为：

关于的求解，通常会使用序列最小优化SMO算法进行求解，其算法流程为：

最后根据求目标函数对的极大值解出的值，进而导出w和b的解，最终得出分离超平面和分类函数。

当然，要真正的掌握支持向量机的原理需要大家自己动手去推导和应用，下次分享我们将针对非线性SVM及如何调用python中的SVM算法进行探讨。