支持向量机原理

支持向量机概念

线性分类器

首先介绍一下线性分类器的概念,C1和C2是要区分的两个类别,在二维平面中它们的样本如上图所示。中间的直线就是一个分类函数,它可以将两类样本完全分开。一般的,如果一个线性函数能够将样本完全正确的分开,就称这些数据是线性可分的,否则称为非线性可分的

线性函数是关于自变量的一次函数,在一维空间里就是一个点,在二维空间里就是一条直线,三维空间里就是一个平面,如果不关注空间的维数,线性函数还有一个统一的名称——超平面(Hyper Plane),记作:

g(x) = wx + b

定义分类函数f(x),若点(x,y)在分类平面上方,即y > wx+b 则记f(x)=1 ; 若y < wx + b 记 f(x) = -1。(不分为0-1是因为数学处理方便的需要)

一般而言,一个点距离超平面的远近可以表示分类的可信程度。以样本点距分类平面间隔最大为目标的的线性分类器称作最大间隔分类器(Maxmium Margin Classifier)

支持向量机(Support Vector Machine, SVM)

如图,在最优分类平面上下作两个平行等间距的超平面AB,使得超平面A或B过样本点且AB之间没有样本点。

可以直观的看出在A和B上的样本"支撑"起了AB的间隔,也就是分类的可信程度。因为样本点由向量表示,把这些AB上样本点对应的向量称作支持向量(Support Vector)

引出样本(x,y) 到分类间隔距离的函数间隔(functional margin):

在此基础上定义几何间隔(geometrical margin):

其中,|| w|| 代表P范数,不关心具体的P值。几何间隔实际上是归一化之后的点到分类平面的距离。

这样处理的优势在于对于坐标系的等比例放缩会使函数间隔变化而不会使几何间隔变化。

定义样本组中所有样本点到分类平面几何间隔中的最小值为样本组到平面的间隔:

为使分类的把握最大,定义目标函数:

通过求解这个优化问题,可以找到最优的分类平面。

** 凸集 ** 是指一个点的集合,其中任取两个点连一条直线,这条线上的点仍然在这个集合内部。因为求解最优分类平面的优化问题可行域为一个凸集,所以这个问题为一个** 凸优化问题 **。

不等式约束下的拉格朗日乘数法

先提一下拉格朗日乘数法:拉格朗日乘数法是在在φ(x,y,...)=0的条件下求f(x,y,...)极值的数学方法。

构造函数:

其中,λ为常数称为拉格朗日乘子。方程组:

的解是f(x,y,...)有极值的必要条件。

下面将拉格朗日乘数法由等式约束推广到不等式约束:

为了便于求解,通过等比例放缩将函数间隔变为1,那么原目标函数变为:

(1)

为保证训练数据分类正确且支持向量函数间隔为1,引入约束条件:

(2)

原优化问题变为(2)约束下求(1)的最优解问题。构造函数:

令:

此目标函数表示通过调整a使得F有极大值。

在条件(2)不满足时,一定可以通过令a为正无穷使得C(w)达到正无穷。

这样原优化问题转化为:

放松约束

训练数据集中少量的样本点可能使得线性可分问题变为线性不可分问题, 很可能导致问题解决难度急剧增大。这些异常的样本点可能很是噪声,为此放松模型的约束从而使得模型允许少数异常样本的存在。

原模型:

引入松弛变量和惩罚函数,改进模型:

直观地说,松弛变量表示允许异常样本点偏离的距离,惩罚因子(cost)表示所能容忍的异常样本点造成的损失。

SMO优化算法

SMO(Sequential Minimal Optimization)优化算法是求解SVM的重要工具

因为存在约束:

使得当其它变量固定时也被固定,所以一次选取两个参数进行优化。

SMO在每次循环中选择两个a进行优化,SMO算法的流程大致如下:

创建一个a向量并初始化为0向量
进行指定次数的迭代 {
    令a[i]遍历数据集中的向量 {
        使用KKT条件判断a[i]是否可以优化 {
        随机选择另外一个向量a[j]
            同时优化两个向量(a[i]+a[j]不变)
            若a[i],a[j]均不能被优化则跳出内循环
        }
    }
若所有变量都没有优化则增加迭代次数

这个算法...相...当...难...实...现,这里引用一下* Machine Learning in Action * 中的示例:

随机选取a[j]以及保证a取值范围的工具函数:

def RandJ(i,m):
    j=i
    while (j==i):
        j = int(random.uniform(0,m))
    return j

def adjustAlpha(alpha, upper, lower):
    if alpha > upper:
        alpha = upper
    if lower > alpha:
        alpha = lower
    return alpha

简单SMO实现:

def smoSimple(dataMatIn, classLabels, C, toler, maxIter):
    dataMatrix = mat(dataMatIn); labelMat = mat(classLabels).transpose()
    b = 0; m,n = shape(dataMatrix)
    alphas = mat(zeros((m,1)))
    iter = 0
    while (iter < maxIter):
        alphaPairsChanged = 0
        for i in range(m):
            fXi = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + b
            Ei = fXi - float(labelMat[i])
            #if checks if an example violates KKT conditions
            if ((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei > toler) and (alphas[i] > 0)):
                # random select a[j]
                j = RandJ(i,m)
                fXj = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[j,:].T)) + b
                Ej = fXj - float(labelMat[j])
                # maintain a between 0 and C
                alphaIold = alphas[i].copy();
                alphaJold = alphas[j].copy();
                if (labelMat[i] != labelMat[j]):
                    L = max(0, alphas[j] - alphas[i])
                    H = min(C, C + alphas[j] - alphas[i])
                else:
                    L = max(0, alphas[j] + alphas[i] - C)
                    H = min(C, alphas[j] + alphas[i])
                if L==H: print "L==H"; continue
                eta = 2.0 * dataMatrix[i,:]*dataMatrix[j,:].T - dataMatrix[i,:]*dataMatrix[i,:].T - dataMatrix[j,:]*dataMatrix[j,:].T
                if eta >= 0: print "eta>=0"; continue
                alphas[j] -= labelMat[j]*(Ei - Ej)/eta
                alphas[j] = adjustAlpha(alphas[j],H,L)
                if (abs(alphas[j] - alphaJold) < 0.00001):
                    print "j not moving enough";
                    continue
                alphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j])
                #update i by the same amount as j, the update is in the oppostie direction
                b1 = b - Ei- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[i,:].T - labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[i,:]*dataMatrix[j,:].T
                b2 = b - Ej- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[j,:].T - labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[j,:]*dataMatrix[j,:].T
                if (0 < alphas[i]) and (C > alphas[i]): b = b1
                elif (0 < alphas[j]) and (C > alphas[j]): b = b2
                else: b = (b1 + b2)/2.0
                alphaPairsChanged += 1
                print "iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged)
        if (alphaPairsChanged == 0): iter += 1
        else: iter = 0
        print "iteration number: %d" % iter
    return b,alphas 

函数的5个输入分别为:数据集,标签,边界C,容错和最大迭代次数。

上述实现采用随机方法选择优化对象,SMO算法可以使用启发式算法进行选择对象以提升效率。

因为实现过于复杂(其实是草民也不懂),故不再说明,详见* 机器学习实战 *。

核函数与多核学习算法

通过升高维度解决线性不可分问题

例如在一维空间上的一段线段,我们无法在一维向量空间中找到分类平面将它与其它部分分开,那么称这类问题为线性不可分问题。

在二维空间中的二次曲线可以解决这个问题,但它不是线性分类函数。因此,定义向量:

并定义关于X 的线性函数y = w*x + b 作为分类函数。由此,一维空间的线性不可分问题转化为二维空间上的线性可分问题。

核函数

为便于描述,将x映射到向量X的映射称为H(x)。

通过各种变换得到的线性分类器:

由上式可知,对于新的样本点只需计算它与训练样本点(只需计算支持向量)的内积 即可。

将非线性问题映射到高维的方法会极大增大计算量,即** 维度灾难 **。

核函数是在低维下(通过x)计算高纬向量(由映射H得到的X)内积的方法。即核函数K(X,Y)满足:

核函数不是唯一的,只要对于给定的H(x) 满足上述定义式即可。Mercer定理指出核函数适应与某一映射H(x) 的条件。

示例:

令核函数:

则有:

常用的核函数有:

  • 多项式核函数
  • 高斯核函数(径向基核函数,Radial Basis Function,RBF)

通过调控参数σ,高斯核函数具有相当的灵活性,是使用最广泛的核函数之一。

核函数不是SVM的特有的,两者是相互正交的概念。核函数作为一种数学工具有着广泛的应用。

Mercer定理

对于m个训练样本,两两由核函数K求内积可得到m阶方阵,称为核矩阵(Kernel Matrix)。

因为:

所以方阵为对称方阵。 对于任意向量Z 有:

可知核矩阵K 为半正定矩阵。由Mercer定理可知,只要核矩阵为对称半正定矩阵那么对应的核函数是有效的。

多核学习算法(MKL)

在实际应用中特征向量可能是异构的,与其对应的最佳核函数未必相同。传统的单核SVM需要根据经验或实验来确定核函数。

多核学习算法(Multiple Kernel Learning,MKL)本质上是定义M个基核函数(Base Kernel Function),并使用基函数的加权线性组合作为作为SVM的核函数。

通过优化算法自动学习权重,避免了人工选择核函数的弊端。

多核线性组合最经典的是simpleMKL,也常被作为MKL的具体实现,应用在了计算机各领域。

为了使MKL应用地更广后来又提出了GMKL(G即Generalized),最优化方法采用是PGD(Projected Gradient Descend) 。

为了改进收敛效果,Vishwanathan又提出SPG-GMKL(Spectral Projected Gradient),同时提出了多核的product组合。SPG-GMKL也被后来者视作state-of-art。MKL的经典实现有SimpleMKL,Shogun,SPG-GMKL,SMO-MKL。

SVM工具

经历手写SVM的惨烈教训(还是太年轻)之后,我决定使用工具箱/第三方库

Matlab

Matlab丰富的工具箱提供了各种方便。

Statistic Tools工具箱提供了svmtrain和svmclassify函数进行SVM分类。

traindata = [0 1; -1 0; 2 2; 3 3; -2 -1;-4.5 -4; 2 -1; -1 -3];
group = [1 1 -1 -1 1 1 -1 -1]‘;
testdata = [5 2;3 1;-4 -3];
svm_struct = svmtrain(traindata,group);
Group = svmclassify(svm_struct,testdata);

svmtrain接受traindata和group两个参数,traindata以一行表示一个样本,group是与traindata中样本对应的分类结果,用1和-1表示。

svmtrain返回一个存储了训练好的svm所需的参数的结构体svm_struct。

svmclassify接受svm_struct和以一行表示一个样本的testdata,并以1和-1列向量的形式返回分类结果。

时间: 06-05

支持向量机原理的相关文章

SVM -支持向量机原理详解与实践之四

SVM -支持向量机原理详解与实践之四 SVM原理分析 SMO算法分析 SMO即Sequential minmal optimization, 是最快的二次规划的优化算法,特使对线性SVM和稀疏数据性能更优.在正式介绍SMO算法之前,首先要了解坐标上升法. 坐标上升法(Coordinate ascent) 坐标上升法(Coordinate Ascent)简单点说就是它每次通过更新函数中的一维,通过多次的迭代以达到优化函数的目的. 坐标上升法原理讲解 为了更加通用的表示算法的求解过程,我们将算法表

SVM -支持向量机原理详解与实践之二

SVM -支持向量机原理详解与实践之二 SVM原理分析 以下内容接上篇. 拉格朗日对偶性(Largrange duality)深入分析 前面提到了支持向量机的凸优化问题中拉格朗日对偶性的重要性. 因为通过应用拉格朗日对偶性我们可以寻找到最优超平面的二次最优化, 所以以下可以将寻找最优超平面二次最优化(原问题),总结为以下几个步骤: 在原始权重空间的带约束的优化问题.(注意带约束) 对优化问题建立拉格朗日函数 推导出机器的最优化条件 最后就是在对偶空间解决带拉格朗日乘子的优化问题. 注:以上这个四

SVM -支持向量机原理详解与实践之三

SVM -支持向量机原理详解与实践之三 什么是核 什么是核,核其实就是一种特殊的函数,更确切的说是核技巧(Kernel trick),清楚的明白这一点很重要. 为什么说是核技巧呢?回顾到我们的对偶问题:     映射到特征空间后约束条件不变,则为:     在原始特征空间中主要是求,也就是和的内积(Inner Product),也称数量积(Scalar Product)或是点积(Dot Product),映射到特征空间后就变成了求,也就是和的映射到特征空间之后的内积,就如我前面所提到的在原始空间

支持向量机原理(四)SMO算法原理

支持向量机原理(一) 线性支持向量机 支持向量机原理(二) 线性支持向量机的软间隔最大化模型 支持向量机原理(三)线性不可分支持向量机与核函数 支持向量机原理(四)SMO算法原理 支持向量机原理(五)线性支持回归(待填坑) 在SVM的前三篇里,我们优化的目标函数最终都是一个关于\alpha向量的函数.而怎么极小化这个函数,求出对应的\alpha向量,进而求出分离超平面我们没有讲.本篇就对优化这个关于\alpha向量的函数的SMO算法做一个总结. 1. 回顾SVM优化目标函数 我们首先回顾下我们的

SVM-支持向量机原理详解与实践之一

目录(?)[+] 前言 SVM机器学习与深度学习 人工智能领域 机器学习与深度学习 SVM简介 SVM原理分析 快速理解SVM原理 线性可分和线性不可分 函数间隔和几何间隔 超平面分析与几何间隔详解 二次最优化 SVM-支持向量机原理详解与实践 前言 去年由于工作项目的需要实际运用到了SVM和ANN算法,也就是支持向量机和人工神经网络算法,主要是实现项目中的实时采集图片(工业高速摄像头采集)的图像识别的这一部分功能,虽然几经波折,但是还好最终还算顺利完成了项目的任务,忙碌一年,趁着放假有时间好好

支持向量机(SVM)算法

支持向量机(support vector machine)是一种分类算法,通过寻求结构化风险最小来提高学习机泛化能力,实现经验风险和置信范围的最小化,从而达到在统计样本量较少的情况下,亦能获得良好统计规律的目的.通俗来讲,它是一种二类分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,即支持向量机的学习策略便是间隔最大化,最终可转化为一个凸二次规划问题的求解. 具体原理: 1. 在n维空间中找到一个分类超平面,将空间上的点分类.如下图是线性分类的例子. 2. 一般而言,一个点距离超平面的

SVM支持向量机-拉格朗日,对偶算法的初解

许多地方得SVM讲得都很晦涩,不容易理解,最近看到一篇不错的博文写得很好,同时加上自己的理解,重新梳理一下知识要点 http://blog.csdn.net/zouxy09/article/details/17291543 一.引入 SVM是个分类器.我们知道,分类的目的是学会一个分类函数或分类模型(或者叫做分类器),该模型能把数据库中的数据项映射到给定类别中的某一个,从而可以用于预测未知类别. 对于用于分类的支持向量机,它是个二分类的分类模型.也就是说,给定一个包含正例和反例(正样本点和负样本

svm支持向量机系列(1) -- 线性支持向量机

1.主要内容 沿着之前学些机器学习基石课程中学习到的工具进行分析,该工具主要就是vc维,沿着特征转换这一目标进行探讨: (1).当数据的特征的数量很大时,如何进行特征转换?支撑向量机 (2).能不能找到具有预测性的特征然后联合起来? (3).如何发现隐藏的具有预测意义的特征?原先的神经网络到现在的深度学习技术. 这节课主要讲述svm的由来,背后的原理,最佳化的求解问题. 2.线性支持向量机的由来 (1).从线性分类器说起到svm问题的提出 如果数据线性可分,那么必然可以找到一条线对齐进行分类,计

主成分分析(PCA)原理总结

主成分分析(Principal components analysis,以下简称PCA)是最重要的降维方法之一.在数据压缩消除冗余和数据噪音消除等领域都有广泛的应用.一般我们提到降维最容易想到的算法就是PCA,下面我们就对PCA的原理做一个总结. 1. PCA的思想 PCA顾名思义,就是找出数据里最主要的方面,用数据里最主要的方面来代替原始数据.具体的,假如我们的数据集是n维的,共有m个数据$(x^{(1)},x^{(2)},...,x^{(m)})$.我们希望将这m个数据的维度从n维降到n'维