支持向量机算法推导及其分类的算法实现摘要：本文从线性分类问题开始逐步的叙述支持向量机思想的形成，并提供相应的推导过程。
简述核函数的概念，以及kernel在SVM算法中的核心地位。
介绍松弛变量引入的SVM算法原因，提出软间隔线性分类法。
概括SVM分别在一对一和一对多分类问题中应用。
基于SVM在一对多问题中的不足，提出SVM 的改进版本DAG SVM。
Abstract：This article begins with a linear classification problem, Gradually discuss formation of SVM, and their derivation. Description the concept of kernel function, and the core position in SVM algorithm. Describes the reasons for the introduction of slack variables, and propose soft-margin linear classification. Summary the application of SVM in one-to-one and one-to-many linear classification. Based on SVM shortage in one-to-many problems, an improved version which called DAG SVM was put forward.关键字：SVM、线性分类、核函数、松弛变量、DAG SVM1. SVM的简介支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。
支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力。
对于SVM的基本特点，小样本，并不是样本的绝对数量少，而是与问题的复杂度比起来，SVM算法要求的样本数是相对比较少的。
非线性，是指SVM擅长处理样本数据线性不可分的情况，主要通过松弛变量和核函数实现，是SVM 的精髓。
高维模式识别是指样本维数很高，通过SVM建立的分类器却很简洁，只包含落在边界上的支持向量。
2. 线性分类器及其求解线性分类器，是最简单也很有效的分类器形式。
在一个线性分类器中，可以看到SVM 形成的思路,并接触很多SVM 的核心概念。
用一个二维空间里仅有两类样本的分类问题来举例。
如图1所示图1 两类样本分类C1和C2是要区分的两个类别，在二维平面中它们的样本如图1所示。
中间的直线就是一个分类函数，它可以将两类样本完全分开。
一般的，如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性可分的。
很容易看出来，图1中间那条分界线并不是唯一的，旋转一下，只要不把两类数据分错，仍然可以达到分类的效果，稍微平移一下，也可以。
对同一个问题存在多个分类函数的时候，哪一个函数更好呢？必须要先找一个指标来量化“好”的程度，通常使用分类间隔来衡量。
设平面中的直线方程为：(x)wx b g =+ （1） 设i x 是一个有某一对象抽取出的n 维向量，i y 为分类标记，则可以定义点到某一超平面的间隔：(w b)i i y x δ=+（2） 用||||w w 和||||b w 替代（2）式中的w 和b 得： 1|(x )|||||i i g w δ= （3）将（3）式得到的间隔称为几何间隔，几何间隔所表示的正是点到超平面的欧氏距离，以上是单个点到某个超平面的距离定义，同样可以定义一个点的集合（就是一组样本）到某个超平面的距离为此集合中离超平面最近的点的距离。
图2更加直观的展示出了几何间隔的含义。
图2 分割超平面图2中，H 是分类面，H1和H2是平行于H ，且过离H 最近的两类样本的直线，H1与H ，H2与H 之间的距离就是几何间隔。
几何间隔与样本的误分次数间存在关系：22()R δ≤误差分数其中的δ是样本集合到分类面的间隔，max ||x ||,i 1,...,n i R ==，即R 是所有样本中向量长度最长的值。
从上式可以看出，误分次数的上界由几何间隔决定。
因此选择几何间隔来作为评价一个解优劣的指标，几何间隔越大的解，它的误差上界越小。
因此最大化几何间隔成了我们训练阶段的目标。
从（3）式可知，几何间隔与||w||是成反比的，因此最大化几何间隔与最小化||w||等价。
通常不是固定||w||的大小而寻求最大几何间隔，而是固定间隔（例如固定为1），寻找最小的||w||。
此时变成一个最优化问题，若想寻找一个小||w||，就可以用下面的式子表示：min ||||w但实际上对于这个目标，常常使用另一个完全等价的目标函数来代替，如下：21min ||||2w如果直接来解这个求最小值问题，很容易看出当||w||=0的时候就得到了目标函数的最小值。
反映在图2中，就是1H 与2H 两条直线间的距离无限大，这个时候，所有的样本点都位于1H 和2H 中间，而我们原本的意图是，1H 右侧的被分为正类，2H 左侧的被分为负类，位于两类中间的样本则拒绝分类。
这样，所有样本点都进入了无法分类的灰色地带。
造成这种结果的原因是在描述问题的时候只考虑了目标，而没有加入约束条件，于是可以添加约束条件：[()b]1(i 1,2,...,n)i i y w x ⋅+≥=（n 是总的样本数）于是可以将两类分类转化成数学形式，如下：21min ||||2[()b]-10(i 1,2,...,n)i i w y w x ⎧⎪⎨⎪⋅+≥=⎩ （4）在这个问题中，自变量就是w ，而目标函数是w 的二次函数，所有的约束条件都是w 的线性函数，这种规划问题就是二次规划（Quadratic Programming ，QP ），由于它的可行域是一个凸集，因此它是一个凸二次规划。
样本确定了w ，用数学的语言描述，就是w 可以表示为样本的某种组合：1122n n w x x x ααα=++⋯+ （5）式子中的i α是拉格朗日乘子，而i x 是样本点，也是向量，n 就是总样本点的个数。
为了方便描述，以下开始严格区别数字与向量的乘积和向量间的乘积，我会用i i x α表示数字和向量的乘积，而用,i j x x <>表示向量,i j x x 的内积。
因此（1）式严格的形式应该是：(x ),g w x =<>+ （6）w 不仅跟样本点的位置有关，还跟样本的类别有关。
因此用下面这个式子表示w ：121122n n n w x x y x y y ααα=++⋯+ （7）其中的i y 就是第i 个样本的标签，它等于1或者-1。
其实以上式子的拉格朗日乘子12,,,n ααα⋯中，只有很少的一部分不等于0，这部分不等于0的拉格朗日乘子后面所乘的样本点，其实都落在1H 和2H 上，也正是这部分样本唯一的确定了分类函数。
这部分可以确定分类的样本点，就叫做支持向量。
因此原来的g(x)表达式可以写为：1(x),b(),n i i i i g w x y x x bα==<>+=<>+∑， （8）其中，1()n i i i i w y x α==∑上式可以变形为：1(x ),n i i i i g y x x bα==<>+∑ （9）此时消去了上式中的w ，问题从求w 变成了求α。
这样就简化了原问题的求解，以这样的形式描述问题以后，优化问题少了很大一部分不等式约束。
接下来看看 SVM 在线性分类器上所做的重大改进——核函数。
3. SVM 中的核函数根据模式识别理论，低维空间线性不可分的模式通过非线性映射到高维特征空间则可能实现线性可分，但是如果直接采用这种技术在高维空间进行分类或回归，则存在确定非线性映射函数的形式和参数、特征空间维数等问题，而最大的障碍则是在高维特征空间运算时存在的“维数灾难”。
采用核函数技术可以有效地解决这样问题。
如图3所示，当分类问题在低纬空间无法用线性分类方法解决时，可以通过φ将低纬空间的数据映射到高纬特征空间中，从而达到线性可分的目的。
图3 低纬度向高纬度空间映射从低纬度向高纬度转化关键在于寻在一个φ函数，但对目前没有一个系统的方法。
对映射过程推导如下：1212123123222211221122222211121222211222(,),(,)(,,),(,,)(,),(,)2()(,)(,)T T T T T T TTT T TTT T T T T x x x x z z z z z z x x x x x x x x x x x x x x x x x x x x K x x φφ<>=<>=<>=++=+=<>= （10）从上式可以得出，我们只关心高维空间里内积的值，而核函数就是接受低空间的输入，并计算出在高纬空间的内积值。
(,)T K x x ，就是我们要找的核函数。
如图4图4 在映射过程中的核函数于是上式，可以表示为1(x)(,)n i i i i g y K x x bα==+∑。
尽管给的问题是线性不可分的，但凡是要求内积的时候我们就选定的核函数来算。
这样求出来的α再和你选定的核函数一组合，就可以得到线性分类器。
但是任然存在以下两个问题：1．既然有很多的核函数，针对具体问题该怎么选择？2．如果使用核函数向高维空间映射后，问题仍然是线性不可分的，那怎么办？第一个问题：对核函数的选择，现在还缺乏指导原则！各种实验的观察结果的确表明，某些问题用某些核函数效果很好，用另一些就很差，但是一般来讲，径向基核函数是不会出太大偏差的一种，首选。
对第二个问题的解决则引出了SVM 中的另一个概念：松弛变量。
4. SVM 中的松弛变量假设有另一个训练集，只比原先这个训练集多了一个样本，映射到高维空间以后，也就多了一个样本点，但是这个样本的位置是这样的，如图5：图5 新增加了一个样本后分类的结果就是图中黄色那个点，它是方形的，因而它是负类的一个样本，这单独的一个样本，使得原本线性可分的问题变成了线性不可分的。
这样类似的问题（仅有少数点线性不可分）叫做“近似线性可分”的问题。
对于人类思维，在大量的样本基础上，可能会认为图5中的黄点是错误的，是噪声，会自动的剔除掉。