Svm（supportVectorMac）又称为支持向量机，是一种二分类的模型。当然如果进行修改之后也是可以用于多类别问题的分类。支持向量机可以分为线性核非线性两大类。其主要思想为找到空间中的一个更够将所有数据样本划开的超平面，并且使得本本集中所有数据到这个超平面的距离最短。
图1图2
既然这样的直线是存在的，那么我们怎样寻找出这样的直线呢？与二维空间类似，超平面的方程也可以写成一下形式：
其中||W||为超平面的范数，常数b类似于直线方程中的截距。
上面的公式可以利用解析几何或高中平面几何知识进行推导，这里不做进一步解释。
1.2.2最大间隔的优化模型
现在我们已经知道了如何去求数据点到超平面的距离，在超平面确定的情况下，我们就能够找出所有支持向量，然后计算出间隔margin。每一个超平面都对应着一个margin，我们的目标就是找出所有margin中最大的那个值对应的超平面。因此用数学语言描述就是确定w、b使得margin最大。这是一个优化问题其目标函数可以写成：
为了后面计算的方便，我们将目标函数等价替换为：
这是一个有约束条件的优化问题，通常我们可以用拉格朗日乘子法来求解。拉格朗日乘子法的介绍可以参考这篇博客。应用拉格朗日乘子法如下：
将(1.7)代入到(1.6)中化简得：
原问题的对偶问题为：
该对偶问题的KKT条件为
到此，似乎问题就能够完美地解决了。但是这里有个假设：数据必须是百分之百可分的。但是实际中的数据几乎都不那么“干净”，或多或少都会存在一些噪点。为此下面我们将引入了松弛变量来解决这种问题。
由上一节的分析我们知道实际中很多样本数据都不能够用一个超平面把数据完全分开。如果数据集中存在噪点的话，那么在求超平的时候就会出现很大问题。从图三中课看出其中一个蓝点偏差太大，如果把它作为支持向量的话所求出来的margin就会比不算入它时要小得多。更糟糕的情况是如果这个蓝点落在了红点之间那么就找不出超平面了。
图3
因此引入一个松弛变量ξ来允许一些数据可以处于分隔面错误的一侧。这时新的约束条件变为:
式中ξi的含义为允许第i个数据点允许偏离的间隔。如果让ξ任意大的话，那么任意的超平面都是符合条件的了。所以在原有目标的基础之上，我们也尽可能的让ξ的总量也尽可能地小。所以新的目标函数变为：
其中的C是用于控制“最大化间隔”和“保证大部分的点的函数间隔都小于1”这两个目标的权重。将上述模型完整的写下来就是：
新的拉格朗日函数变为：
代入原式化简之后得到和原来一样的目标函数：
经过添加松弛变量的方法，我们现在能够解决数据更加混乱的问题。通过修改参数C，我们可以得到不同的结果而C的大小到底取多少比较合适，需要根据实际问题进行调节。
图4
那么这种非线性可分的数据是否就不能用svm算法来求解呢？答案是否定的。事实上，对于低维平面内不可分的数据，放在一个高维空间中去就有可能变得可分。以二维平面的数据为例，我们可以通过找到一个映射将二维平面的点放到三维平面之中。理论上任意的数据样本都能够找到一个合适的映射使得这些在低维空间不能划分的样本到高维空间中之后能够线性可分。我们再来看一下之前的目标函数：
定义一个映射使得将所有映射到更高维空间之后等价于求解上述问题的对偶问题：
通过以上例子，我们可以很明显地看到核函数是怎样运作的。上述问题的对偶问题可以写成如下形式：
那么怎样的函数才可以作为核函数呢？下面的一个定理可以帮助我们判断。
值得注意的是，上述定理中所给出的条件是充分条件而非充要条件。因为有些非正定函数也可以作为核函数。
下面是一些常用的核函数：
表1常用核函数表
核函数名称
核函数表达式
线性核
指数核
多项式核
拉普拉斯核
高斯核
Sigmoid核
根据以上问题的分析，我们已经将原始问题转化为了求的值，即求下面优化模型的解：
而原对偶问题的子问题的目标函数可以表达成：
其中：
为了表述方便，定义一个特征到输出结果的输出函数：
该对偶问题中KKT条件为：
最优解需要满足KKT条件，因此需要满足以上的三个条件都满足。而不满足这三个条件的情况也有三种：
令其两边同时乘y1，可得：
经过转化之后可得：
而b在满足以下条件时需要更新：
且更新后的和如下：
第二节已经对Smo算法进行了充分的说明并进行了推导，现在一切都准备好了。接下来需要做的就是实现这些算法了，这里我参考了《机器学习实战》这本书中的代码，并利用该程序对一个问题进行了求解。由于代码数量过大，因此这里就不再列出，而是放在附录中。有兴趣的朋友可以直接下载，也可以去官网下载源代码。笔者在读这些代码的过程中，也遇到了许多困难，大部分都根据自己的情况进行了注释。
这里我选取的一个数据集为声呐数据集，该问题为需要根据声呐从不同角度返回的声音强度来预测被测物体是岩石还是矿井。数据集中共有208个数据，60个输入变量和1个输出变量。每个数据的前60个元素为不同方向返回的声音强度，最后一个元素为本次用于声呐测试的物体类型。其中标签M表示矿井，标签R为岩石。
所给数据中没有缺失值和异常值，因此不需要对数据集进行清洗。注意到所给数据集的标签为字母类型，而svm算法的标准标签为“-1”和“1”的形式，所以需要对标签进行转化，用“-1”、“1”分别代替M和R。由于该数据集中所给标签相同的数据都放在了一起，因此先对数据顺序进行了打乱。代码如下：
defloadDataSet(fileName):dataMat=[];labelMat=[];data=[]fr=open(fileName)forlineinfr.readlines():line=line.replace(',','\t')#去除逗号line=line.replace('M','-1')#对标签进行替换line=line.replace('R','1')lineArr=line.strip('\n').split('\t')#分割数据data.append([float(lineArr[i])foriinrange(len(lineArr))])random.shuffle(data)#随机打乱列表foriinrange(len(data)):dataMat.append(data[i][0:len(data)-1])labelMat.append(data[i][-1])returndataMat,labelMat
首先测试了一下将所有数据即作为训练集又作为测试集，然后用Smo模型进行训练找到所有的支持向量。最后根据训练好的模型进行求解，最终测试的准确率平均为54%。如果把数据集分成测试集和训练集，发现测试的准确率也在这附近。而根据网上数据统计该数据集测试的准确率最高为84%，一般情况下为百分之六十几。数据集本身是造成测试准确率低的一个原因，但是另外一个更加重要的原因大概是参数的选择问题。如何选取合适的参数是一个值得思考的问题，在接下来的学习过程中我也会注意一下参数选取这个问题。到这里，关于svm的算法就告一段落了。