支持向量机

支持向量机（SVM）什么是支持向量机？图A给出了一个线性可分数据集（可以在图中画一条直线将两组数据点分开）图B、C、D分别给出了一条分隔的直线，那么其中哪一条最好？是不是有寻找最佳拟合直线的感觉？支持向量机（SVM）就可以用来寻找此线性可分情形下的最优分类面。（有人说SVM是最好的现成的分类器）什么是支持向量机？支持向量机（SupportVectorMachine）是一种非常流行的监督学习算法，简称为SVM。该算法可以针对线性和非线性的数据。它利用一种非线性转换，将原始训练数据映射到高维空间上。在新的高维空间中，它搜索线性最优分类超平面。或者说是搜索一两个不同类型之间分离的决策边界。通过非线性映射将数据映射到一个足够高的维度上，来自两个不同类的数据总可以被一个超平面所分离。SVM使用支持向量(基本训练元组)和边缘(由支持向量定义)来发现超平面。右图中，将红蓝两类数据分隔开的直线称为分隔超平面，在更高维数据集中，将数据分隔开的对象称为超平面，也就是分类的决策边界。右图中圆圈标记的数据点，也就是距离分隔超平面最近的那些点，称为支持向量（supportvector）。支持向量机（SVM）支持向量机理论：SVM是从线性可分情况下的最优分类面发展而来。最优分类面就是要求不但能将两类正确分开，而且使得分类间隔最大。SVM考虑寻找一个满足分类要求的超平面，并且使得训练集中的点距离分类面尽可能的远，也就是寻找一个分类面使它两侧的空白区域（margin）最大。过两类样本中离分类面最近的点且平行于最优分类面的超平面上的训练样本就叫做支持向量（supportvector）。目前，支持向量机已在人脸识别、文字识别、图像处理和时间序列预测等领域获得了比较广泛的应用。两分类问题线性分割情形第1类第2类许多决策边界可以分割这些数据点出为两类我们选取哪一个?坏的决策边界的例子第1类第2类第1类第2类好的决策边界:间隔最大MaximumMarginal决策边界离两类数据应尽可能远最大化间隔m第1类第2类m1、数学模型描述：设{𝑥1,…,𝑥𝑛}为数据集,𝑦𝑖∈{1,−1}为𝑥𝑖的类标记，则所求的分类面表达式为：𝑔𝑥=𝑤,𝑥+𝑏=𝑤𝑇𝑥𝑖+𝑏要求决策边界正确地分类所有的点，即：于是得到一个带有约束的优化问题：优化目标：约束条件：2、支持向量机求解：通过引入拉格朗日函数将上述最优化问题转化为其对偶问题，则可以得到这是一个二次规划(QP)问题：𝒂𝒊的全局最大值总可以求得W的计算3、解的性质许多的𝒂𝒊为零w只是少数数据的线性组合具有非零ai的xi称为支持向量(SV)决策边界仅由SV确定设tj(j=1,...,s)为支持向量的指标,于是为了检测一个新数据z计算如果WTZ+b0,则z属于第一类;否则,属于第二类。a6=1.44、几何解释第1类第2类a1=0.8a2=0a3=0a4=0a5=0a7=0a8=0.6a9=0a10=0例题：下图给出一个三个数据点的数据集，其中正例点是𝑥1=(3,3)𝑇,𝑥2=(4,3)𝑇负例点是𝑥3=(1,1)𝑇，试求最大间隔分离超平面。线性不可分的情形两分类问题关键思想:为了解决非线性分割问题,将xi变换到一个高维空间。输入空间:xi所在的空间特征空间:变换后f(xi)的空间如何变换?利用一个适当的变换f,使分类变得容易些。特征空间中的线性算子等价于输入空间中的非线性算子。左图是一个典型的线性不可分情形，但是当我们把这两个类似于椭圆形的点映射到一个高维空间后，映射函数为：用这个函数可以将上图的平面中的点映射到一个三维空间（z1,z2,z3)，并且对映射后的坐标加以旋转之后就可以得到一个线性可分的点集了。在左图中，SVM是如何对这种数据进行分类的呢？通过引入新的变量信息：𝑥2+𝑦2=𝑧我们对x和z构建散点图：变量z恒大于零。原始图中，红圈数据分布在原点附近它们的z值比较小；而星星数据则远离原点区域，它们具有较大的z值。变换可能出现的问题难以得到一个好的分类且计算开销大SVM同时解决这两个问题最小化||w||2能得到好的分类利用核函数技巧(kerneltrick)可以进行有效的计算f()f()f()f()f()f()f()f()f(·)f()f()f()f()f()f()f()f()f()特征空间输入空间什么是核函数？核函数定义：核函数是一个对称函数，对所有的x,y∈X，满足：这里f(•)是X到內积空间F的映射。核函数举例d阶多项式核：具有宽度s的径向基函数核：相当接近于径向基函数神经网络具有参数kandq的Sigmoid核核函数技巧(kerneltrick)核函数K与映射f(.)之间的关系是作为核函数技巧这是已知的在应用中,我们指定K,从而间接地确定f(•)以代替选取f(•)。直观地,K(x,y)表示我们对数据x和y之间相似性的一种描述，且来自我们的先验知识。为了f(•)存在，K(x,y)需要满足Mercer条件。变换举例定义核函数𝑲(𝒙,𝒚)如下考虑下列变换内积可由K计算,不必通过映射f(•)计算非线性SVM算法将所有的内积改为核函数训练算法:线性的非线性的例题设有5个1维数据点:𝑥1=1,𝑥2=2,𝑥3=4,𝑥4=5,𝑥5=6,其中1,2,6为第1类,而4,5为第2类𝑦1=1,𝑦2=1,𝑦3=−1,𝑦4=−1,𝑦5=1。利用2阶多项式核𝐾(𝑥,𝑦)=(𝑥𝑦+1)2𝐶取为100先求𝒂𝒊(𝑖=1,…,5)∶利用QP求解,得到𝑎1=0,𝑎2=2.5,𝑎3=0,𝑎4=7.333,𝑎5=4.833注意到确实满足约束条件支持向量为{𝑥2=2,𝑥4=5,𝑥5=6}描述函数为确定b当x2,x4,x5位于上时,𝑓(2)=1,𝑓(5)=−1,𝑓(6)=1,由此解得b=9描述函数的值12456第2类第1类第1类支持向量机应用：人脸识别一个正常人脸，经过预处理之后，得到右图。对于一幅M×M大小的人脸图像,𝑝𝑖𝑗表示对应于图的第i行和第j列的灰度值,这样人脸图像X可以用向量表示为一个矩阵：对于一个图像集合{𝑥1,𝑥2…𝑥𝑁},设向量𝑥𝑖∈𝑅𝑚(𝑚=𝑀×𝑀)为c类(以区别不同的人脸)人脸图像{1,2…c}中的一类,通过变换，将其从原来的m维空间映射到n(nm)维特征空间以达到降低维数的目的，再利用PCA技术得到此空间的特征矩阵。SVM：首先都是将经过预处理的人脸图像投影到经过变换得到的原有的人脸图像特征子空间中。比如系统中特征子空间维数是64。因此一个人脸图像可用特征空间中的一个64维的向量表示,这样的数据即为人脸特征数据.在训练过程中先对不同人脸的特征数据标为不同的标号，如0、1、2…,同一人脸则标以同样的标号。利用支持向量机得到分类函数，从而对人脸特征数据分类标号，最后测试其属于哪一类（一般选择距离测试分类结果最近的5个作为候选分类）人脸识别系统框架图总结支持向量机优缺点：优点：SVM理论避开高维空间的复杂性，直接用內积函数即核函数，来解决决策问题。同时SVM是基于小样本统计理论的基础上的，符合机器学习的目的并且比神经网络具有更好的泛化推广能力。缺点：对参数调节和核函数的选择敏感。支持向量机的应用：支持向量机已在人脸识别、文字识别、图像处理和时间序列预测等领域获得了比较广泛的应用。研究热点：对支持向量机中算法的优化，包括解决SVM中二次规划求解问题如何更好的构造基于SVM的多类分类器如何提高SVM的归纳能力和分类速度如何根据实际问题确定核函数