机器学习第二发：支持向量机

随着2016年3月份谷歌带领alphaGo 4:1 打败李世石，其中使用的深度学习技术也社会引起了强烈的反响。实则深度学习是在人工智能领域机器学习算法的一种，是一种深层的神经网络算法。借此，三棵树将推出系列讲机器学习的文章，之前已经发过机器学习第一发：逻辑回归。

今天我们将来介绍支持向量机算法。

支持向量机(Support Vector Machine，SVM)，是Corinna Cortes和Vapnik等于1995年第一提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法不仅可以对线性可分的样本进行分类，而且可以对线性不可分的样本进行分类。此外计算速度快，空间成本低，在工业界也有广泛的应用。

SVM 是基于结构风险最小化的机器学习方法，通过在特征空间中构建最优分类超平面， 将不同类别样本分开。如图 所示，其中H1和H2为分类超平面，H1和H2上的点为支持向量。

设训练样本集合为D={x,y}，对应的类别标签为y={-1,1}，设超平面处的方程为：

使得所有样本满足：

即满足限制条件

其中超平面之间的距离为
要最大化，超平面H1和H2之间的距离，同时要满足上面的限制条件，用数学可以表明为

等价于解决

这是一个凸二次规划（convex quadratic programming）问题，求解上述问题，应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解。这样做的优点：一是对偶问题往往更容易求解；二是自然引入核函数，进而推广到非线性分类问题。那么构建拉格朗日函数如下：

根据拉格朗日对偶性，原始问题是极大极小问题。可以转化为求解凸二次规划问题，最常用的是使用序列最小最优化(sequential minimal optimization, SMO)算法进行求解 (Platt, 1999)。

针对线性不可分问题，可以借助核技巧来实现，所谓的核技巧就是借助核函数将在低维不可分的数据映射到高维可分的空间中，在使用线性可分的支持向量机进行解决。

LIBSVM(
http://wwwcsientuedutw/~cjlin/libsvm)工具包可以实现SVM分类器的构建及测试，该工具包是由台湾大学林智仁教授等人开发设计的一个简单易用的基于SVM 算法的软件包，并得到广泛的使用。

机器学习第一发：逻辑回归