支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的 ，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够 推广应用到函数拟合等其他机器学习问题中。   1963年，Vapnik在解决模式识别问题时提出了支持向量方法，这种方法从训练集中选择一 组特征子集，使得对特征子集的划分等价于对整个数据集的划分，这组特征子集就被称为 支持向量(Support Vector，SV)；   1971年，Kimeldorf提出使用线性不等约束重新构 造SV的核空间,解决了一部分线性不可分问题；1990年，Grace、Boser和Vapnik等人开始对SVM进行研究； 1995年，Vapnik正式提出统计学习理论。

SVM涉及的相关概念

  支持向量机和线性分类器(如逻辑回归)都是线性模型。虽然SVM是线性模型，但是它的求解过程要比线性模型困难不少。  

1. 它是一种最大间隔的线性分类器，它只会考虑在decision bound比较近的这些点，而在逻辑回归问题中，即使离决策边界很远，它还是会产生一个loss function。
2. 通过核函数可以做非线性的问题。

  对于分类问题，分开两类数据其实有很多种解法，那哪一种解法是最好的呢？也就是说SVM是从线性可分情况下的最优分类面发展而来，最优分类面就是要求分类线不但能将 两类正确分开，且使分类间隔最大(分类间隔最大能够使得算法在测试数据集上取得较好效果，或者说数据本身存在噪声，较大的分类间隔能够取得较好效果)。  
  SVM考虑寻找一个满足分类要求的超平面,并 且使训练集中的点距离分类面尽可能的远,也 就是寻找一个分类面使它两侧的空白区域 (margin)最大。这与逻辑回归算法不一样，在逻辑回归算法中所有的点都会影响分类边界，而在SVM 算法中不会，它更多考虑的是支持向量。  
  过两类样本中离分类面最近的点且平行于最 优分类面的超平面上H1​，H2​的训练样本就叫 做支持向量。

分类任务

  分类任务就是确定对象属于哪个预定义的目标类。分类任务的输入数据是记录的集合，每条记录也称为实例或样例，用元组(x , y ) 表示，其中 x  是属性的 集合，y 是类标记（也称目标属性）。在回归模型中，目标属性值是连续的； 而在分类模型中，目标属性是离散的。   考虑二分类任务，其目标属性为y ∈ { 0 , 1 } ，而线性回归模型参数的预测值
是实值，于是我们需要将实值z 通过Sigmoid函数转换为0或1。Sigmoid函数定义如下：  
  Logistic回归：目的是从特征中学习出一个0/1分类模型，这个模型是将特征的线性组合作为自变量，由于自变量的取值范围是(− ∞ , + ∞ )。因此使用Sigmoid函数将自变量映射到(0,1)上，映射后的值被认为是属于y = 1 的概率。假设函数为：  
  根据Sigmoid函数的特性，假设：  
  上式表示，已知样本x 和参数θ的情况下，样本$x$属于正样本(y = 1 )和负样本(y = 0 )的条件概率：若$5$则属于正样本，反之属于负样本。当然在实际操作过程中你可以把这个值设置地大一点，使得在测试过程中效果更好。  

分类任务进一步理解

 
  因此Logistic回归就是要学习得到参数θ ，使得正例的特征远远大于0，负例的特征远远小于0，而且要在全部训练数据上达到这个目标。  
 

• 线性可分数据集

  需要注意的是：对于上述问题我们需要数据集是线性可分的，不然不管如何分类都找不到这样一个平面。   线性可分数据集：存在某个超平面$S$能够将数据集的正实例和负实例完全划分 到超平面的两侧，则称为线性可分数据集；否则，线性不可分。  
  上图中的这些数据就是线性可分的，所以可以用一条直线将这两类数据分开，二维中是一条直线，多维中就是一个超平面。  
 

SVM算法

SVM所要解决的问题

  假定给定数据图，圆的为正类，方的为负类，要想通过一个划分超平面（这里是二维，所以是条直线）将不同类别的样本分开。从图中可以看出，能将训练样本分开的划分超平面可能有很多，但是我们应该去选择哪一个呢？   直观上，我们应该选择中间红色的那个，因为它对于 训练样本局部扰动的“容忍”性最好；   比如，训练集外的样本可能比图中的样本更接近两类 的划分超平面，这将使许多划分超平面出现错误，而 红色的超平面受到的影响是最小的，也就是说，这个 划分超平面的分类结果是最鲁棒的，对未知样本的泛 化能力最强。  
  在所有的划分超平面中，有一个平面是最好的，它可以尽可能地让所有的样本点都离该划分 超平面最远，这就是SVM要做的。  

函数间隔

  有三个实例$A、B、C$均在划分超平面的正类一侧，点$A$举例超平面较远，若预测为正类，叫比较确信预测是正确的；点$C$距离超平面较近，若预测为正类就不那么确信了；点$B$介于$A$、$C$之间，预测其为正类的确信度也在$A$、$C$之间。   一般来说，一个点距离超平面的远近可以相对地表示分类预测的确信程度。  

 

 
  另外，直接计算其内积，可以得到：  

 
 

• 对于给定的训练数据集T 和超平面($b$)：

  定义超平面($b$)关于样本点(x i , y i )的几何间隔公式如下，它一般是样本点到超平面的带符号的距离，当样本点被超平面正确分类时，就是样本点到超平面的距离(将每个样本点x i ​带入距离计算公式  
 
  定义超平面($,b$)关于数据集T 的几何间隔为超平面($b$) 关于T 中所有样本点(x i , y i ​)的几何间隔的最小值 γ = min ⁡ { γ i , ( x i , y i ) ∈ T } ，表示为距离超平面距离最小的那个样本。此时相当于能够找到支持向量所对应的样本，通过调整参数w 让其几何间隔最大，就是SVM所要做的事情。   几何间隔与函数间隔的关系为：  
  如果超平面的参数w 和b 成比例的改变（超平面没有变），函数间隔也按此比例改变， 但是几何间隔不变。   支持向量的函数间隔为1，SVM的优化目标为：  
  约束条件表示的是最大化的一定是支持向量。要求解上述问题我们需要一定的凸优化基础，接下来简要介绍一下所需数学知识部分。  

凸优化基础

拉格朗日对偶性 – 原问题

  假设f ( x ) ，c i ( x ) ，h j ( x ) 是定义在R n R^{n}Rn上的连续可微函数，称以下的约束最优化问题 为原问题：  
  对于上述约束化问题首先引入拉格朗日函数 ( 将等式和不等式约束融入到一个目标函数中去，从而只用一个函数表达我们的问题。)：  
  由以上两个式子可以得到：  
  则极小化问题 θ P ( x ) \ 有：  
  与原问题等价，即有相同的解。（因为当趋向无穷时，问题无解，因此必须 满足约束条件）。   广义拉格朗日函数的极小极大问题：
 

拉格朗日对偶性 – 对偶问题

  构建关于α  和 β 的函数：  
  则其极大化问题称为广义拉格朗日函数的极大极小问题  
  将其表示为约束最优化问题，称为原始问题的对偶问题  
 

原问题与对偶问题之间的关系

  弱对偶性：若原始问题与对偶问题都有最优解，则对偶问题最优解与原问题最优解具备以下关系：  
  强对偶性：满足 d ∗ = p∗   强对偶是一个非常好的性质，因为在强对偶成立的情况下，可以通过求解对偶问题来得到 原始问题的解，在 SVM 中就是这样做的。   当然并不是所有的对偶问题都满足强对偶性 ，在 SVM 中是直接假定了强对偶性的成立， 其实只要满足一些条件，强对偶性是成立的，比如说 KKT条件。   KKT条件：对于原始问题及其对偶问题，假设函数f ( x ) 和c i ( x )是凸函数，h j ( x ) 是仿射函数，且不等式约束c i ( x ) 是严格可行的，即存在x ，对所有i 有c i ( x ) < 0 ，则存在x ∗ ，α ∗ ∗，β ∗ ，使x ∗是原始问题的解，α ∗ ，β ∗ 是对偶问题的解的充分必要条件是 x ∗，α ∗ ，β ∗满足下面的Karush-Kuhn-Tucker (KKT)条件：  
 

线性可分支持向量机

线性可分SVM

  设有如下两类样本的训练集：  
  线性可分情况意味着存在超平面，使训练点中的正类和负类样本分别位于该超平面的两侧。  
  如果能确定这样的参数对($w,b$) 的话，就可以构造决策函数来进行识别新样本。  
 

硬间隔最大化

  存在的问题：这样的参数对($w,b$)有许多。  
  解决办法是采用最大间隔原则：即选择使得训练集 $D$ 对于线性函数 $w\cdot x+b$ 的几何间隔取最大值的参数对($w,b$)，并由此构造优化问题。   目标函数：  
  约束条件：  
 
 

基于对偶的线性可分SVM学习算法

  构建拉格朗日对偶函数：
  根据拉格朗日对偶性，原问题的对偶问题是极大极小问题：max ⁡ α min ⁡ w , b L ( w , b , α )即需要先求L ( w , b , α )  对$b$的极小，再求对α 的极大。   (1) 固定α ，让L 关于$b$最小化，分别对$b$求偏导数，令∂ L / ∂ w和∂ L / ∂ b等于零：  
  可以得到：  
  (2) 将结果代入拉格朗日函数中，整理后可得：  
  根据拉格朗日对偶性，原问题的对偶问题是极大极小问题：   即需要先求L ( w , b , α ) 对w,b的极小，再求对α 的极大。   (3) 求m i n w , b L ( w , b , α ) 对α的极大，即是对偶问题：  
  对偶问题：  
  (4) 求解上述问题可得到最优的α ∗  ，进而求得w ∗ ， b ∗ ，最终获得分离超平面和分类决策函数：  
  分类超平面：  
  分类决策函数：  
  以上是推导过程，实际使用过程是这样的：  

1. 构造并求解最优化问题

  求得最优解：  
 

2. 计算w ∗ , b ∗：

 
  选择α ∗ 的一个正分量α j ∗，计算：  
 

3. 求得分离超平面：

4. 获得分类决策函数：

• 我们得到的原问题的对偶问题的目标函数为：

 
  第一项为正则化项，第二项为模型精度。  

• 如果x i x_{i}xi​是支持向量的话，上式中y i ( w x + b ) − 1 = 0  (因为此向量到分类超平面的函数间隔为1)；
• 对于非支持向量来说，函数间隔会大于1，因此会有y i ( w x + b ) − 1 > 0，由于有约束条件α i ≥ 0 ，因此为了满足最大化，在最优解α ∗ 中，必须有α i = 0。
• 结构风险最小化：目标函数第二项为模型精度，第一项为正则化项，有效保证稀疏性，以降低置信风险，因而SVM是基于结构风险最小化的学习方法。

线性不可分支持向量机

线性不可分

• 设有如下两类样本的训练集：

                                   D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) }    线性不可分情况意味着不存在这样的超平面，使训练点中的正类和负类样本能 够完全分别位于该超平面的两侧，即无法将它们完全分开。如果要用超平面来 划分的话，必然有错分的点。                                                                                              w ⋅ x + b = 0           
  现实情况：我们只会线性可分的方法；   处理思路：允许分类误差，并且在目标函数 中引入对分类误差的惩罚。  

软间隔最大化

• 允许支持向量机在一些样本上出错，需要我们将硬间隔最大化改为软间隔最大化，当然，在最大化软间隔的同时，不满足约束的样本应尽可能的少。y i ( w ⋅ x + b ) = 1 软间隔要求是 y i ( w ⋅ x + b ) ≥ 1 。
• 为了解决某些样本不满足约束的情况，对每个样本点(x i , y i​)引入一个松弛变量ξ i ≥ 0 ，使函数间隔加上松弛变量大于等于1，这样约束条件就变为：

• 为了避免ξ i \xi_{i}ξi​取太大的值，需要在目标函数中对他们进行惩罚，其中C > 0 称为惩罚系数，C 值大时，对误分类的惩罚增加，C 值小时对误分类的惩罚减小。

 
  有了上面的思路，可以和线性可分支持向量机一样来考虑线性支持向量机的学习问题，线性不可分的线性支持向量机的学习问题就变为如下凸二次规划问题：

  ​  

• 通过求解以上凸二次规划问题，即软间隔最大化问题，得到分离超平面为：

 
  相应的分类决策函数为：  

基于对偶的学习算法

  构建拉格朗日对偶函数：     α i ≥ 0 ，μ i ≥ 0 ，需要先求L ( w , b , ξ , α , μ ) 对w , b ,的极小，再求对α 的极大。   (1) 分别对w , b , ξ 求偏导数，令∂ L / ∂ w , ∂ L / ∂ b , ∂ L / ∂ ξ 等于零：  
  可以推出：  
  (2) 将结果代入拉格朗日函数中，整理后可得：  
  α i ≥ 0 ，μ i ≥ 0 ，需要先求L ( w , b , ξ , α , μ ) 的极小，再求对α 的极大。   (3) 求m i n w , b , ξ L ( w , b , ξ , α , μ ) 对α的极大，即得对偶问题：  
  对偶问题，凸二次规划问题，有唯一的最优解：   ​   (4) 求解上述问题可得到最优的α ∗ ，进而求得w ∗ ，最终获得分离超平面和分类决策函数：  
  得到分类超平面：  
  得到分类决策函数：  
  以上是推导过程，实际使用过程是这样的：  
 

软间隔支持向量

  软间隔支持向量具有以下性质：  
 

非线性支持向量机

非线性数据

  在现实任务中，我们得到的数据一般都不是线性可分的，这时线性可分支持向 量机就不适用了。非线性数据意味着不存在这样的超平面，使训练点中的正类 和负类样本能够完全分别位于该超平面的两侧。

Kernel核函数方法

  核方法的主要思想： 基于这样一个假设：“在低维空间中不能线性分割的点集，通过转化为高维空间中的点集 时，很有可能变为线性可分的”。   具体来说，在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后通过核 函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优的分离超平面， 从而把平面上本身不好分的非线性数据分开。  
  SVM处理非线性数据的一般方法：   选择一个非线性特征集，并将数据改写成新的表达方式，这等价于应用一个固定的非线性 映射，将数据映射到高维特征空间，在高维特征空间中使用线性分类器。  
  其中，$\varphi ()$ 表示从输入空间到某个高维特征空间的映射。   这意味着线性分类方法求解非线性分类问题一般分为两步：  

• 使用一个变换将原空间的数据映射到新空间。
• 在新空间里使用线性分类学习方法从训练数据中学习分类模型。

• 使用映射函数方法的再思考：

• 两种方法的区别：

 
  现在我们回忆下前面提到的维度爆炸，在前一种方法已经无法计算的情况下，后一种方法却 依旧能处理，甚至无穷维度也没有问题。   我们把这里的计算两个向量在隐式映射过后在空间中的内积的函数叫做核函数，例如，前面 的例子中，核函数为，例如，前面的例子中，核函数为：  
  核函数能够简化映射空间中的内积运算。  

• 核函数的定义：

• 核技巧：

  在核函数$k(x,z)$给定的条件下，可以利用求解线性分类问题的方法求解非线性分类问题的支持向量机；学习是隐式地在特征空间进行，不需要显示地定义特征空间和映射函数，这样的技巧称为核技巧。   使用核技巧，解决了计算的复杂性问题，避开了直接在高维空间中进行计算，，而结果却是等价的。  

• 针对任意一个映射，手工设计出相应的核函数是很困难的，所以我们通常是在 常用的核函数中，按照问题和数据特点，进行选择：

 
  δ ≥ 1 为高斯核的带宽。在实际应用中，采用较多的是高斯核函数，这个核可以将原始空间映射为高维空间（也就是我们前面提到的空间映射）。  
 

• 高斯核函数中参数σ对模型性能的影响。

  如果σ选得过大的话，高次特征上的权重实际上衰减的非常快，所以实际上相当于一个低维的子空间；   性质1. 当σ趋于无穷时，SVM的判别函数为一常函数，其推广能力或对新样本的正确分类能力为零，即把所有样本点判别为同一类。   如果σ 选得过小的话，则可以将任意的数据映射为线性可分的–当然这并不完全是好事，因为随着而来的是非常严重的过拟合问题；   性质 2. 若RBF核中尺度参数σ趋于0，则拉格朗日 乘子向量的所有分量都大于0，即全部样本点都是 支持向量。  
总的来说，通过调控参数σ ，高斯核实际上具有相当高的灵活性，也是使用最广泛的核函数之一。   线性核函数：  
 

核函数的本质

  通常我们遇到的数据都是线性不可分的，我们需要将其映射到高维空间，但是这 可能带来维度灾难；这时候，核函数便是一种很好的解决方法，核函数的价值就 在于它虽然也是将特征进行从低维到高维的映射，但是核函数的巧妙之处在于它 事先在低维上进行计算，而将实质上的分类效果表现在高维上，这样做也就避免 了在高维空间中的复杂运算。  

基于Kernel的SVM：假设现在你是一个农场主，圈养了一批羊，但为了预防狼群 袭击羊群，你需要搭建一个篱笆来把羊和狼分开，但是篱笆应该建在哪儿呢？

基于核函数的非线性支持向量机

最小二乘支持向量机

LSSVM概述

  LSSVM提出的背景  

• 支持向量机是针对小样本问题，基于结构风险最小化，较好地解决了以往机器学习模型中的 过学习、非线性、维数灾难以及局部极小值等问题，具有较好的泛化能力；

• 然而，该方法在大规模训练样本时，存在训练速度慢、稳定性差等缺陷，从而制约了其使用 范围（学习过程中需要求解二次规划问题）；

• 因此，1999年，Suykens和Vandewalle等人在SVM的基础上提出LSSVM（Least Square Support Vector Machine, LSSVM），该算法的计算复杂度大为减少，使得训练速度得到提高。

• 最小二乘支持向量机（LSSVM）是标准支持向量机的一种扩展，该算法将支持 向量机的求解从二次规划问题转化为线性方程组。

• 它与支持向量机的不同之处在于它把不等式约束改成等式约束，并把经验风险 由偏差的一次方改为二次方

  。

  分类问题回顾：   给定训练数据集T = { ( x 1 , y 1 ) , ⋯   , ( x N , y N ) }，其中x i ∈ R n , y i ∈ { − 1 , + 1 } , i = 1 , … , N；   分类支持向量机的目标是构造如下形式的分类器，使得 f ( x ) 能够将样本正确分类  
    回归问题回顾   给定训练数据集T = { ( x 1 , y 1 ) , ⋯   , ( x N , y N ) } ，其中x i ∈ R n , y i ∈ R , i = 1 , … , N ；   回归(Regression)支持向量机的目标是构造如下形式的预测函数，使得$f(x)$能够与样本的实际 函数值近似  
 
 

参考