支持向量机

支持向量机支持向量机，英文名为supportvectormachine，一般简称SVM，通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划（convexquadraticprogramming）问题的求解,支持向量机的学习算法是求解凸二次规划的最优化算法。其方法包含构建由简到繁的模型：线性可分支持向量机、线性支持向量机和非线性支持向量机。线性可分支持向量机假定一特征空间上的训练数据集{()()()}，其中,{}，，为第i个特征向量，也就是实例，为的类标记，当时，称为正例；当时，称为负例，()称为样本点。再假设训练数据集是线性可分的，即存在某个超平面能够将正例和负例完全正确的分开，不妨设分离超平面方程为，法向量为w、截距为b。一般地，当训练数据集线性可分时，存在无穷多个分离超平面可将两类数据正确分开，线性可分支持向量机利用间隔最大化求最优分离超平面，这是解是唯一的。若最优分离超平面为,则分类决策函数为()()。在上图中，有A、B、C三个点，表示三个实例，设“。”表示正类，“”表示负类，则这三个点全在正类。A距分类超平面较远，若预测该点为正类就比较确信预测是正确的；C距分类超平面较近，若预测该点为负类就不那么确信；B介于AC两者之间，预测为正类的确信度也在A与C之间。故一般来说，点距离分离超平面的远近可以表示分类预测的确信程度。在超平面确定的情况下，||能够相对地表示点x到超平面的远近，而的符号与类标记y的符号是否一致可表示分类是否正确，所以()可以来表示分类的真确性及确信度，我们称之为函数间隔。也就是，样本点()的函数间隔为()，训练样本集T的函数间隔为超平面()关于T中所有样本点()的函数间隔最小值，即，函数间隔可以表示分类预测的正确性及确信度，但是我们成比例地改变w和b时，超平面并没有变而函数间隔却扩大2倍，为此可以对分离超平面的法向量w加些约束，如规范化，‖‖，使得间隔是确定的，这时函数间隔成为几何间隔，此时(‖‖‖‖)，超平面()关于T中所有样本点()的函数间隔最小值，即，这样如果成比例地改变w和b时，几何间隔不变化。支持向量机学习的基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对线性可分的训练数据集而言，线性可分的超平面有无穷多，但是几何间隔最大的只有一个。几何间隔最大意味着以充分大的的确信度对训练数据集进行分类，也就是说，不仅将正负实例分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度把它们分开，这样的超平面应该对未知的新实例有很好的分类预测能力。最大间隔分类超平面这个问题可以表示为下面的的约束最优化问题：s.t(‖‖‖‖)，即我们希望最大化超平面()关于训练数据集的几何间隔，约束条件表示超平面每个训练样本点的几何间隔至少是，考虑几何间隔和函数间隔的关系，可将这个问题改写为wbw^,　maxs.t^bxwyii函数间隔的取值并不影响最优化问题的解，事实上，假设将w和b按比例改变，函数间隔也改变同样的倍数，这一改变对这最优化问题的不等式约束没有影响，对目标函数的优化也没有影响，也就是说，它产生的是一组等价问题，为此我们可以取1^，将其代入，且注意到最大化‖‖和最小化‖‖是等价的，于是得到下面的线性可分支持向量机学习的最优化问题2,w21min　　bwNbxwtsii,,2,1i01y..，　　　这是个凸二次规划问题。在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。支持向量就是使下列约束条件等号成立的点，即()对的正例点，支持向量在超平面𝐻：上，对的负例点，支持向量在超平面𝐻：上，下图在𝐻和𝐻上的点就是支持向量。由图可知，再决定分离超平面时只有支持向量起作用，而其他实例点并不起作用，如果移动支持向量将改变所求的解；但是如果在间隔边界以外移动其他的点，甚至去掉这下点，则解是不变的，由于支持向量在确定分离超平面中起决定作用，所以这种分类模型取名为支持向量机。支持向量的个数一般很少，所以支持向量机由很少的“重要的”训练样本确定。学习的对偶算法首先构建拉格朗日函数，为此，引进拉格朗日乘子（Lagrangemultiplier）𝛼，定义拉格朗日函数：L(𝛼)‖‖∑𝛼()∑𝛼根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：,,minmax,bwLbw　所以，为了得到对偶问题的解，需要先求L(𝛼)对w、b的极小，再求对α的极大。1)求,,min,bwLbw将拉格朗日函数L(𝛼)分别对w、b求偏导并令其为零，可得∑𝛼∑𝛼将其结果代入拉格朗日函数，化简可得L(𝛼)∑∑𝛼𝛼𝑗𝑗𝑗(⋅𝑗)∑𝛼即,,min,bwLbw=∑∑𝛼𝛼𝑗𝑗𝑗(⋅𝑗)∑𝛼2)求,,min,bwLbw对α的极大，即是对偶问题　max∑∑𝛼𝛼𝑗𝑗𝑗(⋅𝑗)∑𝛼.𝑡.∑𝛼𝛼根据KKT条件可得，设𝛼(𝛼，𝛼，，𝛼𝑙)𝑇是上述问题的解，则存在下标j，使得𝛼𝑗，并可按下式求得原始最优化问题的解：∑𝛼𝑗∑𝛼分类决策函数可以写成()[∑𝛼()]这就是说，分类决策函数只依赖于输入x和训练样本输入的内积。此外，和只依赖于训练数据中对应于𝛼的样本()，而其他的样本点对和没有影响，于是我们将训练数据中对应于𝛼的实例点称为支持向量。线性支持向量机线性可分支持向量机对线性不可分训练数据是不适用的，因为此时不等式约束并不成立，为了解决此问题，线性支持向量机产生了。线性不可分数据集中，通常情况下是训练数据中有一些奇异点，若将这些奇异点取出，剩下大部分样本点组成的集合石线性可分的。线性不可分意味着某些样本点()不满足间隔大于等于1的约束条件，为了解决此问题，可以对每个样本点()引入一个松弛变量，使函数间隔加上松弛变量后大于等于1，这样约束条件变为()目标函数变为‖‖𝐶∑C为惩罚参数，一般由问题决定，是调和二者的系数。线性不可分的学习支持向量机的学习问题变成如下的凸二次规划：NiibwCw12,,21min　s.t.()𝜉𝑁𝜉𝐼可以证明，w的解是唯一的，但b的解不唯一，b的解存在于一个区间。线性不可分支持向量机的学习算法，上述原始问题的对偶问题为　max∑∑𝛼𝛼𝑗𝑗𝑗(⋅𝑗)∑𝛼.𝑡.∑𝛼≤𝛼≤C拉格朗日函数为L(ξαμ)‖‖𝐶∑𝜉∑𝛼(()𝜉)∑𝜇𝜉首先求拉格朗日函数ξ的最小值，求偏导令其为零可得∑𝛼∑𝛼C𝛼𝜇将上述结果代入之后得到对偶问题：　max∑∑𝛼𝛼𝑗𝑗𝑗(⋅𝑗)∑𝛼.𝑡.∑𝛼𝛼C𝛼𝜇𝜇根据KKT条件，设𝛼(𝛼，𝛼，，𝛼𝑙)𝑇是上述问题的解，则存在下标j，使得𝛼𝑗𝐶，并可按下式求得原始最优化问题的解：∑𝛼𝑗∑𝛼在线性不可分的情况下，将对偶问题的解𝛼(𝛼，𝛼，，𝛼𝑙)𝑇中对应于𝛼的实例点称为支持向量。如下图所示，分类超平面由实线表示，间隔边界由虚线表示，“。”表示正类，“”表示负类，图中还标出了实例到间隔边界的距离‖‖.此时的支持向量或者在间隔边界上，或者在间隔边界与分类超平面之间，或者在分类超平面误分的一侧。若𝛼𝐶，则𝜉，支持向量恰好落在间隔边界上；若𝛼𝐶，𝜉，分类正确，在间隔边界与分类超平面之间；若𝛼𝐶，𝜉，则在分类超平面上；若𝛼𝐶，𝜉，则在分类超平面误分一侧。非线性支持向量机训练数据集并不都是线性的，有时候分类问题是非线性，这时就需要非线性支持向量机。此问题中的最终目的是在对偶问题的目标函数中，用核函数K(𝑗)Φ()Φ(𝑗)来代替内积𝑗，此时对偶问题的目标函数为：∑∑𝛼𝛼𝑗𝑗𝑗K(𝑗)∑𝛼核函数有称为正定核，其等价条件为K(𝑧)对应的Gram矩阵K[K(𝑗)]是半正定矩阵。常用的核函数有高斯核函数，公式为K(𝑧)ep⌈‖𝑧‖𝜎⌉