简述svm算法的原理 求svm算法的应用实例,要求有计算过程!有程序!
1、支持向量机( SVM )是一种比较好的实现了结构风险最小化思想的方法。它的机器学习策略是结构风险最小化原则
为了最小化期望风险,应同时最小化经验风险和置信范围)
支持向量机方法的基本思想:
( 1
)它是专门针对有限样本情况的学习机器,实现的是结构风险最小化:在对给定的数据逼近的精度与逼近函数的复杂性之间寻求折衷,以期获得最好的推广能力;
( 2
)它最终解决的是一个凸二次规划问题,从理论上说,得到的将是全局最优解,解决了在神经网络方法中无法避免的局部极值问题;
( 3
)它将实际问题通过非线性变换转换到高维的特征空间,在高维空间中构造线性决策函数来实现原空间中的非线性决策函数,巧妙地解决了维数问题,并保证了有较好的推广能力,而且算法复杂度与样本维数无关。
目前, SVM
算法在模式识别、回归估计、概率密度函数估计等方面都有应用,且算法在效率与精度上已经超过传统的学习算法或与之不相上下。
对于经验风险R,可以采用不同的损失函数来描述,如e不敏感函数、Quadratic函数、Huber函数、Laplace函数等。
核函数一般有多项式核、高斯径向基核、指数径向基核、多隐层感知核、傅立叶级数核、样条核、 B
样条核等,虽然一些实验表明在分类中不同的核函数能够产生几乎同样的结果,但在回归中,不同的核函数往往对拟合结果有较大的影响
2、支持向量回归算法(svr)主要是通过升维后,在高维空间中构造线性决策函数来实现线性回归,用e不敏感函数时,其基础主要是 e
不敏感函数和核函数算法。
若将拟合的数学模型表达多维空间的某一曲线,则根据e 不敏感函数所得的结果,就是包括该曲线和训练点的“
e管道”。在所有样本点中,只有分布在“管壁”上的那一部分样本点决定管道的位置。这一部分训练样本称为“支持向量”。为适应训练样本集的非线性,传统的拟合方法通常是在线性方程后面加高阶项。此法诚然有效,但由此增加的可调参数未免增加了过拟合的风险。支持向量回归算法采用核函数解决这一矛盾。用核函数代替线性方程中的线性项可以使原来的线性算法“非线性化”,即能做非线性回归。与此同时,引进核函数达到了“升维”的目的,而增加的可调参数是过拟合依然能控制。
SVM线性分类器
SVM从线性可分情况下的最优分类面发展而来。最优分类面就是要求分类线不但能将两类正确分开(训练错误率为0),且使分类间隔最大。SVM考虑寻找一个满足分类要求的超平面,并且使训练集中的点距离分类面尽可能的远,也就是寻找一个分类面使它两侧的空白区域(margin)最大。
过两类样本中离分类面最近的点且平行于最优分类面的超平面上H1,H2的训练样本就叫做支持向量。
图例:
问题描述:
假定训练数据 :
可以被分为一个超平面:
进行归一化:
此时分类间隔等于:
即使得:最大间隔最大等价于使最小
下面这两张图可以看一下,有个感性的认识。那个好?
看下面这张图:
下面我们要开始优化上面的式子,因为推导要用到拉格朗日定理和KKT条件,所以我们先了解一下相关知识。在求取有约束条件的优化问题时,拉格朗日乘子法(Lagrange Multiplier) 和KKT条件是非常重要的两个求取方法,对于等式约束的优化问题,可以应用拉格朗日乘子法去求取最优值;如果含有不等式约束,可以应用KKT条件去求取。当然,这两个方法求得的结果只是必要条件,只有当是凸函数的情况下,才能保证是充分必要条件。KKT条件是拉格朗日乘子法的泛化。之前学习的时候,只知道直接应用两个方法,但是却不知道为什么拉格朗日乘子法(Lagrange Multiplier) 和KKT条件能够起作用,为什么要这样去求取最优值呢?
拉格朗日乘子法和KKT条件
定义:给定一个最优化问题:
最小化目标函数:
制约条件:
定义拉格朗日函数为:
求偏倒方程
可以求得的值。这个就是神器拉格朗日乘子法。
上面的拉格朗日乘子法还不足以帮我们解决所有的问题,下面引入不等式约束
最小化目标函数:
制约条件变为:
定义拉格朗日函数为:
可以列出方程:
新增加的条件被称为KKT条件
KKT条件详解
对于含有不等式约束的优化问题,如何求取最优值呢?常用的方法是KKT条件,同样地,把所有的不等式约束、等式约束和目标函数全部写为一个式子L(a, b, x)= f(x) + a*g(x)+b*h(x),KKT条件是说最优值必须满足以下条件:
1. L(a, b, x)对x求导为零;
2. h(x) =0;
3. a*g(x) = 0;
求取这三个等式之后就能得到候选最优值。其中第三个式子非常有趣,因为g(x)<=0,如果要满足这个等式,必须a=0或者g(x)=0. 这是SVM的很多重要性质的来源,如支持向量的概念。
二. 为什么拉格朗日乘子法(Lagrange Multiplier) 和KKT条件能够得到最优值?
为什么要这么求能得到最优值?先说拉格朗日乘子法,设想我们的目标函数z = f(x), x是向量, z取不同的值,相当于可以投影在x构成的平面(曲面)上,即成为等高线,如下图,目标函数是f(x, y),这里x是标量,虚线是等高线,现在假设我们的约束g(x)=0,x是向量,在x构成的平面或者曲面上是一条曲线,假设g(x)与等高线相交,交点就是同时满足等式约束条件和目标函数的可行域的值,但肯定不是最优值,因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部,使得新的等高线与目标函数的交点的值更大或者更小,只有到等高线与目标函数的曲线相切的时候,可能取得最优值,如下图所示,即等高线和目标函数的曲线在该点的法向量必须有相同方向,所以最优值必须满足:f(x)的梯度 = a* g(x)的梯度,a是常数,表示左右两边同向。这个等式就是L(a,x)对参数求导的结果
附上出处链接:http://blog.csdn.net/alvine008/article/details/9097105