已修改
统计学习方法 支持向量机
支持向量机（support vector machines,SVM）是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；支持向量机还包括核技巧，这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划（convex quadratic programming）的问题，也等价于正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。
支持向量机学习方法包括构建由简至繁的模型：线性可分支持向量机（linear support vector machine in linearly separable case），线性支持向量机（linear support vector machine）及非线性支持向量机（non-linear support vector machine）。简单的模型是复杂模型的基础，也是复杂模型的特殊情况。当训练数据线性可分时，通过硬间隔最大化（hard margin maximization），学习一个线性的分类器，即线性可分支持向量机，又称为硬间隔支持向量机；当训练数据近似线性可分时，通过软间隔最大化（soft margin maximization），也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；当训练数据线性不可分时，通过使用核技巧（kernel trick）及软间隔最大化，学习非线性支持向量机。
当输入空间为欧式空间或离散集合、特征空间为希尔贝特空间时，核函数（kernel function）表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机。这样的方法称为核技巧。核方法（kernel method）是比支持向量机更为一般的机器学习方法。
线性可分支持向量机与硬间隔最大化
线性可分支持向量机
考虑一个二类分类问题。假设输入空间与特征空间为两个不同的空间。输入空间为欧式空间或离散集合，特征空间为欧式空间或希尔伯特空间，线性可分支持向量机、线性支持向量机假设这两个空间的元素一一对应，并将输入空间的输入映射为特征空间中的特征向量。非线性支持向量机利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量。支持向量机的学习是在特征空间进行的。
定义（线性可分支持向量机）
给定线性可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为
函数间隔和几何间隔
函数间隔不是距离，注意上句话中所说的“能够相对地表示”。
定义（函数间隔）
对于给定的训练数据集T和超平面（w,b），定义超平
函数间隔可以表示分类预测的正确性及确信度。但是选择分离超平面时，只有函数间隔还不够。因为只要成比例改变w和b，如改为2w和2b，超平面并没有改变，但函数间隔却成为原来的2倍，所以应该对分离超平面的法向量w加以约束，如规范化||w||=1,使得间隔是确定的。这时函数间隔成为几何间隔。
定义（几何间隔）
对于给定的训练数据集T和超平面（w,b）,定义超平
间隔最大化
支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面.对线性可分的训练数据集而言,线性可分分离超平面有无穷多个(等价于感知机),但是几何间隔最大的分离超平面是唯一的.这里的间隔最大化又称为硬间隔最大化(与将要讨论的训练数据集近似线性可分时的软间隔最大化相对应).
间隔最大化的直观解释是;对训练数据集找到几何间隔最大的超平面意味着
以充分大的确信度对训练数据进行分类.也就是说,不仅将正负实例点分开,而 且对最难分的实例点(离超平面最近的点)也有足够大的确信度将它们分开.这
样的超平面应该对未知的新实例有很好的分类预测能力。
最大间隔分离超平面
考虑如何求得一个几何间隔最大的分离超平面,即最大间隔分离超平面.具体地,这个问题可以表示为下面的约束最优化问题:
函数间隔yhat的取值并不影响最优化问题的解。事实上，假设将w和b按比例改变为λw和λb,这时函数间隔称为λyhat。函数间隔的这一改变对上面最优化问题的不等式约束没有影响，对目标函数的优化也没有影响，也就是说，它产生一
这是一个凸二次规划(convex quadratic programming)问题。
仿射函数，即最高次数为1的多项式函数。常数项为零的仿射函数称为线性函数。
线性可分支持向量机学习——最大间隔法
最大间隔分离超平面的存在唯一性
线性可分训练集的最大间隔分离超平面是存在且唯一的。
定理（最大间隔分离超平面的存在唯一性）
若训练数据集T线性可分，则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。
支持向量和间隔边界
在线性可分情况下,训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量( support vector).支持向量是使约束条件式(7.14)等号成立的点,即
在决定分离超平面时只有支持向量起作用,而其他实例点并不起作用.如果移动支持向量将改变所求的解;但是如果在间隔边界以外移动其他实例点,甚至去掉这些点,则解是不会改变的.由于支持向量在确定分离超平面中起着决定性作用,所以将这种分类模型称为支持向量机.支持向量的个数一般很少,所以支持向量机由很少的“重要的”训练样本确定.
例
学习的对偶算法
为了求解线性可分支持向量机的最优化问题(7.13,7.14)，将它作为原始最优化问题,应用拉格朗日对偶性,通过求解对偶问题(dual problem)得到原始问题( primal problem)的最优解,这就是线性可分支持向量机的对偶算法( dual algorithm).这样做的优点,一是对偶问题往往更容易求解;二是自然引入核函数,进而推广到非线性分类问题。
首先构建拉格朗日函数( Lagrange function).为此,对每一个不等式约束(7.14)引进拉格朗日乘子( Lagrange multiplier )αi≥0,i=1,2,…,N,定义拉格朗日函数:
定理
这种算法称为线性可分支持向量机的对偶学习算法，是线性可分支持向量机学习的基本算法。
算法（线性可分支持向量机学习算法）
支持向量
例
对于线性可分问题,上述线性可分支持向量机的学习(硬间隔最大化)算法是完美的,但是,训练数据集线性可分是理想的情形.在现实问题中,训练数据集往往是线性不可分的,即在样本中出现噪声或特异点.此时,有更一般的学习算法。
线性支持向量机与软间隔最大化
线性支持向量机
线性可分问题的支持向量机学习方法,对线性不可分训练数据是不适用的,因为这时上述方法中的不等式约束并不能都成立.怎么才能将它扩展到线性不可分问题呢?这就需要修改硬间隔最大化,使其成为软间隔最大化.
有了上面的思路,可以和训练数据集线性可分时一样来考虑训练数据集线性不可分时的线性支持向量机学习问题相应于硬间隔最大化,它称为软间隔最大化。
定义（线性支持向量机）
学习的对偶算法
可以通过求解对偶问题而得到原始问题的解，进而确定分离超平面和决策函数.为此，就可以定理的形式叙述原始问题的最优解和对偶问题的最优解的关系.
定理
算法（线性支持向量机学习算法）
符合条件的样本点上的平均值。
支持向量
合页损失函数
目标函数的第一项是经验损失或经验风险，函数
定理
序列最小最优化算法
支持向量机的学习问题可以形式化为求解凸二次规划问题，这样的图二次规划问题具有全局最优解，且有许多最优化算法可以用于这一问题的求解。但当训练样本容量很大时，这些算法往往变得非常低效，以致于无法使用。序列最小最优化算法就是一种快速实现算法。
SMO算法是一种启发式算法，其基本思路是:如果所有变量的解都满足此最优化问题的KKT条件(Karush-Kuhn-Tucker conditions),那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件.否则， 选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题，这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因为这会使得原始二次规划问题的目标函数值变得更小.重要的是，这时子问题可以通过解析方法求解，这样就可以大大提高整个算法的计算速度.子问题有两个变量，一个是违反KKT条件最严重的那一个，另一个由约束条件自动确定.如此，SMO算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的.
整个SMO算法包括两个部分:求解两个变量二次规划的解析方法和选择变量的启发式方法.
两个变量二次规划的求解方法
不失一般性，假设选择的两个变量是α1，α2，其他变量αi（i=3，4，…，N）是固定的。于是SMO的最优化问题（7.98~7.100）的子问题可以写成：
为了求解两个变量的二次规划问题(7.101)-(7.103)，首先分析约束条件，然后在此约束条件下求极小。
不等式约束(7.103)使得(a,a2)在盒子[0,C]x[0,C]内，等式约束(7.102)使(α1，α2)在平行于盒子[0,C]x[0,C]的对角线的直线上.因此要求的是目标函数在一条平行于对角线的线段.上的最优值.这使得两个变量的最优化问题成为实质上的单变量的最优化问题，不妨考患为变量α2的最优化问题.
定理
变量的选择方法
SMO算法在每个子问题中选择两个变量优化，其中至少一个变量是违反KKT条件的。
第一个变量的选择
第二个变量的选择
计算阈值b和差值Ei
SMO算法
非线性支持向量机与核函数
对解线性分类问题，线性分类支持向量机是一种非常有效的方法。但是，有时分类问题是非线性的，这时可以使用非线性支持向量机，其主要特点是利用核技巧(kernel trick)。核技巧不仅应用于支持向量机，而且应用于其他统计学习问题。
核技巧
非线性分类问题
非线性分类问题是指通过利用非线性模型才能很好地进行分类的问题.先看
一个例子:如7.7 左图，是一个分类问题，图中“。”表示正实例点，“x”表示负
实例点. 由图可，见， 无法用直线(线性模型)将正负实例正确分开，但可以用一条椭圆曲线(非线性模型)将它们正确分开.
非线性问题往往不好求解，所以希望能用解线性分类问题的方法解决这个问题.所采取的方法是进行一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题、对图7.7所示的例子， 通过变换，将左图中椭圆变换成右图中的直线,将非线性分类问题变换为线性分类问题.
用线性分类方法求解非线性分类问题分为两步: 首先使用一个变换将原空间的数据映射到新空间;然后在新空间里用线性分类学习方法从训练数据中学习分类模型. 核技巧就属于这样的方法.
核函数的定义
核技巧在支持向量机中的应用
正定核
定理（正定核的充要条件）
定理给出了正定核的充要条件，因此可以作为正定核，即核函数的另一定义。
定义（正定核的等价定义）
常用核函数
多项式核函数
高斯核函数
字符串核函数
核函数不仅可以定义在欧氏空间上，还可以定义在离散数据的集合上.比如，字符串核是定义在字符串集合上的核函数.字符串核函数在文本分类信息检索、生物信息学等方面都有应用.
字符串核函数k,(s,t)给出了字符串s和t中长度等于n的所有子串组成的特征向量的余弦相似度(cosine similarity).直观上，两个字符串相同的子串越多， 它们就越相似，字符串核函数的值就越大.字符串核函数可以由动态规划快速地计算.
非线性支持向量机
利用核技巧，可以将线性分类的学习方法应用到非线性分类问题中去.将线性支持向量机扩展到非线性支持向量机，只需将线性支持向量机对偶形式中的内积换成核函数.
定义 非线性支持向量机
从非线性分类训练集，通过核函数与软间隔最大化，或凸二次规划(7.95~7.97)，学习得到的分类决策函数
算法 非线性支持向量机学习算法
博客
决策面方程
在二维空间下一条直线的方程为y=ax+b
现在我们做一个小小的改变，让原来的x轴变成x1,y轴变成x2
x2=ax1+b
移项得：ax1-x2+b=0
将公式向量化得：
进一步向量化，用w列向量和标量r进一步向量化。
其中向量w和x分别为：
这里w1=a,w2=-1。最初的直线方程a和b的几何意义，a表示直线的斜率，b表示截距，向量化后的直线的w和r的几何意义为
向量w和直线的关系为垂直的，标量r的作用也没有变，依然决定了直线的截距。
将其推广到n维空间，就变成了超平面方程，公式没变，依然是：
不同在于：
“分类间隔”方程
间隔的大小实际上就是支持向量对应的样本点到决策面的距离的二倍。d的求法如下：
点到直线的距离距离公式：
公式中的直线方程为Ax0+By0+C=0，点P的坐标为(x0,y0)。
将直线方程扩展到多维，求得我们现在的超平面方程，对公式进行如下变形：
这个d就是”分类间隔”。其中||w||表示w的二范数，求所有元素的平方和，然后再开方。
核函数与超平面
线性
1.我们的最优化问题是：
我们要求解的是最小化问题，所以一个直观的想法是如果我能够构造一个函数，使得该函数在可行解区域内与原目标函数完全一致，而在可行解区域外的数值非常大，甚至是无穷大，那么这个没有约束条件的新目标函数的优化问题就与原来有约束条件的原始目标函数的优化问题是等价的问题。这就是使用拉格朗日方程的目的，它将约束条件放到目标函数中，从而将有约束优化问题转换为无约束优化问题。
2.将有约束的原始目标函数转换为无约束的新构造的拉格朗日目标函数
其中αi是拉格朗日乘子，αi大于等于0，是我们构造新目标函数时引入的系数变量(我们自己设置)。现在我们令：
当样本点不满足约束条件时，即在可行解区域外：
此时，我们将αi设置为正无穷，此时θ(w)显然也是正无穷。
当样本点满足约束条件时，即在可行解区域内：
此时，显然θ(w)为原目标函数本身。我们将上述两种情况结合一下，就得到了新的目标函数：
此时，再看我们的初衷，就是为了建立一个在可行解区域内与原目标函数相同，在可行解区域外函数值趋近于无穷大的新函数，现在我们做到了。
现在，我们的问题变成了求新目标函数的最小值，即：
这里用p*表示这个问题的最优值，且和最初的问题是等价的。
3.将不易求解的优化问题转化为易求解的优化
我们看一下我们的新目标函数，先求最大值，再求最小值。这样的话，我们首先就要面对带有需要求解的参数w和b的方程，而αi又是不等式约束，这个求解过程不好做。所以，我们需要使用拉格朗日函数对偶性，将最小和最大的位置交换一下，这样就变成了：
交换以后的新问题是原始问题的对偶问题，这个新问题的最优值用d来表示。而且d<=p*。我们关心的是d=p的时候，这才是我们要的解。需要什么条件才能让d=p呢？首先必须满足这个优化问题是凸优化问题。其次，需要满足KKT条件。
求取最小值的目标函数为凸函数的一类优化问题。目标函数是凸函数我们已经知道，这个优化问题又是求最小值。所以我们的最优化问题就是凸优化问题。
而且KKT条件也满足了。
求解这个对偶学习问题，可以分为三个步骤：首先要让L(w,b,α)关于w和b最小化，然后求对α的极大，最后利用SMO算法求解对偶问题中的拉格朗日乘子。
4.让L(w,b,α)关于w和b最小化
根据上述推导已知：
首先固定α，要让L(w,b,α)关于w和b最小化，我们分别对w和b偏导数，令其等于0，即：
将上述结果带回L(w,b,α)得到：
从上面的最后一个式子，我们可以看出，此时的L(w,b,α)函数只含有一个变量，即αi。
5.对α求极大
现在我们的优化问题变成了如上的形式。对于这个问题，我们有更高效的优化算法，即序列最小优化（SMO）算法。我们通过这个优化算法能得到α，再根据α，我们就可以求解出w和b，进而求得我们最初的目的：找到超平面，即”决策平面”。
6.使用SMO算法
步骤一：计算误差
步骤二：计算上下界L和H：
步骤三：计算η：
步骤四：更新αj
步骤五：根据取值范围修剪αj：
步骤六：更新αi：
步骤七：更新b1和b2：
步骤八：根据b1和b2更新b：
非线性
对于非线性的情况，SVM的处理方式就是选择一个核函数。简而言之：在线性不可分的情况下，SVM通过某种事先选择的非线性映射（核函数）将输入变量映到一个高维特征空间，将其变成在高维空间线性可分，在这个高维空间中构造最优分类超平面。
线性可分的情况下，可知最终的超平面方程为：
将上述公式用内积来表示：
对于线性不可分，我们使用一个非线性映射，将数据映射到特征空间，在特征空间中使用线性学习器，分类函数变形如下：
其中ϕ从输入空间(X)到某个特征空间(F)的映射，这意味着建立非线性学习器分为两步：首先使用一个非线性映射将数据变换到一个特征空间F；然后在特征空间使用线性学习器分类。
如果有一种方法可以在特征空间中直接计算内积 <ϕ(xi),ϕ(x)>，就像在原始输入点的函数中一样，就有可能将两个步骤融合到一起建立一个分线性的学习器，这样直接计算的方法称为核函数方法。
这种将内积替换成核函数的方式被称为核技巧(kernel trick)。
如：
假设已知映射函数为：
对于两个向量a1=(x1,x2)和a2=(y1,y2)有
如果我们不进行映射计算，直接运算下面的公式：
这两个公式的计算结果是相同的。区别在于：一个是根据映射函数，映射到高维空间中，然后再根据内积的公式进行计算，计算量大；另一个则直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果，计算量小。
核函数就是：
实践
SVM-simple
简化版的SMO算法，第二个α的选择是随机的。
https://github.com/zdkswd/MLcode/blob/master/%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0/svm/svm-simple.py
完整SMO算法
完整的SMO算法可以启发式选择第二个α值。
在实现SMO算法的时候，先计算η，再更新αj。为了加快第二个αj乘子的迭代速度，需要让直线的斜率增大，对于αj的更新公式，其中η值没有什么文章可做，于是只能令:max|Ei-Ej|。
因此，优化方法为：
- 最外层循环，首先在样本中选择违反KKT条件的一个乘子作为最外层循环，然后用”启发式选择”选择另外一个乘子并进行这两个乘子的优化。
- 在非边界乘子中寻找使得 |Ei - Ej| 最大的样本
3.如果没有找到，则从整个样本中随机选择一个样本
完整版SMO算法覆盖整个数据集进行计算，而简化版SMO算法是随机选择的。可以看出，完整版SMO算法选出的支持向量样点更多，更接近理想的分隔超平面。
对比两种算法的运算时间，结果是完整版SMO算法的速度比简化版SMO算法的速度快6倍左右。
https://github.com/zdkswd/MLcode/blob/master/%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0/svm/svm-smo.py
非线性SVM
https://github.com/zdkswd/MLcode/blob/master/%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0/svm/svmMLiA.py
高斯核函数
从图像中我们可以看出，离中心点越近，函数值就越接近于1。
因此以任意一种颜色的同心圆作为决策边界，我们都可以完成对数据集的简单非线性划分。那么问题来了，如何映射到高维空间上去呢？——————高斯核函数！
sklearn.svm.SVC
参数说明：
C:惩罚项，float类型，可选参数，默认为1.0，C越大，即对分错样本的惩罚程度越大，因此在训练样本中准确率越高，但是泛化能力降低，也就是对测试数据的分类准确率降低。相反，减小C的话，容许训练样本中有一些误分类错误样本，泛化能力强。对于训练样本带有噪声的情况，一般采用后者，把训练样本集中错误分类的样本作为噪声。
kernel：核函数类型，str类型，默认为’rbf’。可选参数为：’linear’：线性核函数，’poly’：多项式核函数，’rbf’：径像核函数/高斯核，’sigmod’：sigmod核函数，’precomputed’：核矩阵，precomputed表示自己提前计算好核函数矩阵，这时候算法内部就不再用核函数去计算核矩阵，而是直接用你给的核矩阵，核矩阵需要为n*n的。
degree：多项式核函数的阶数，int类型，可选参数，默认为3。这个参数只对多项式核函数有用，是指多项式核函数的阶数n，如果给的核函数参数是其他核函数，则会自动忽略该参数。
gamma：核函数系数，float类型，可选参数，默认为auto。只对’rbf’ ,’poly’ ,’sigmod’有效。如果gamma为auto，代表其值为样本特征数的倒数，即1/n_features。
coef0：核函数中的独立项，float类型，可选参数，默认为0.0。只有对’poly’ 和,’sigmod’核函数有用，是指其中的参数c。
probability：是否启用概率估计，bool类型，可选参数，默认为False，这必须在调用fit()之前启用，并且会fit()方法速度变慢。
shrinking：是否采用启发式收缩方式，bool类型，可选参数，默认为True。
tol：svm停止训练的误差精度，float类型，可选参数，默认为1e^-3。
cache_size：内存大小，float类型，可选参数，默认为200。指定训练所需要的内存，以MB为单位，默认为200MB。
class_weight：类别权重，dict类型或str类型，可选参数，默认为None。给每个类别分别设置不同的惩罚参数C，如果没有给，则会给所有类别都给C=1，即前面参数指出的参数C。如果给定参数’balance’，则使用y的值自动调整与输入数据中的类频率成反比的权重。
verbose：是否启用详细输出，bool类型，默认为False，此设置利用libsvm中的每个进程运行时设置，如果启用，可能无法在多线程上下文中正常工作。一般情况都设为False，不用管它。
max_iter：最大迭代次数，int类型，默认为-1，表示不限制。
decision_function_shape：决策函数类型，可选参数’ovo’和’ovr’，默认为’ovr’。’ovo’表示one vs one，’ovr’表示one vs rest。
random_state：数据洗牌时的种子值，int类型，可选参数，默认为None。伪随机数发生器的种子,在混洗数据时用于概率估计。