摘自:
http://www.blogjava.net/zhenandaci/archive/2009/02/14/254630.html
从最一般的定义上说,一个求最小值的问题就是一个优化问题(也叫寻优问题,更文绉绉的叫法是规划——Programming),它同样由两部分组成,目标函数和约束条件,可以用下面的式子表示:
(式1)
约束条件用函数c来表示,就是constrain的意思啦。你可以看出一共有p+q个约束条件,其中p个是不等式约束,q个等式约束。
关于这个式子可以这样来理解:式中的x是自变量,但不限定它的维数必须为1(视乎你解决的问题空间维数,对我们的文本分类来说,那可是成千上万啊)。要求f(x)在哪一点上取得最小值(反倒不太关心这个最小值到底是多少,关键是哪一点),但不是在整个空间里找,而是在约束条件所划定的一个有限的空间里找,这个有限的空间就是优化理论里所说的可行域。注意可行域中的每一个点都要求满足所有p+q个条件,而不是满足其中一条或几条就可以(切记,要满足每个约束),同时可行域边界上的点有一个额外好的特性,它们可以使不等式约束取得等号!而边界内的点不行。
关于可行域还有个概念不得不提,那就是凸集,凸集是指有这么一个点的集合,其中任取两个点连一条直线,这条线上的点仍然在这个集合内部,因此说“凸”是很形象的(一个反例是,二维平面上,一个月牙形的区域就不是凸集,你随便就可以找到两个点违反了刚才的规定)。
回头再来看我们线性分类器问题的描述,可以看出更多的东西。
(式2)
在这个问题中,自变量就是w,而目标函数是w的二次函数,所有的约束条件都是w的线性函数(哎,千万不要把xi当成变量,它代表样本,是已知的),这种规划问题有个很有名气的称呼——二次规划(Quadratic Programming,QP),而且可以更进一步的说,由于它的可行域是一个凸集,因此它是一个凸二次规划。
一下子提了这么多术语,实在不是为了让大家以后能向别人炫耀学识的渊博,这其实是我们继续下去的一个重要前提,因为在动手求一个问题的解之前(好吧,我承认,是动计算机求……),我们必须先问自己:这个问题是不是有解?如果有解,是否能找到?
对于一般意义上的规划问题,两个问题的答案都是不一定,但凸二次规划让人喜欢的地方就在于,它有解(教科书里面为了严谨,常常加限定成分,说它有全局最优解,由于我们想找的本来就是全局最优的解,所以不加也罢),而且可以找到!(当然,依据你使用的算法不同,找到这个解的速度,行话叫收敛速度,会有所不同)
对比(式2)和(式1)还可以发现,我们的线性分类器问题只有不等式约束,因此形式上看似乎比一般意义上的规划问题要简单,但解起来却并非如此。
因为我们实际上并不知道该怎么解一个带约束的优化问题。如果你仔细回忆一下高等数学的知识,会记得我们可以轻松的解一个不带任何约束的优化问题(实际上就是当年背得烂熟的函数求极值嘛,求导再找0点呗,谁不会啊?笑),我们甚至还会解一个只带等式约束的优化问题,也是背得烂熟的,求条件极值,记得么,通过添加拉格朗日乘子,构造拉格朗日函数,来把这个问题转化为无约束的优化问题云云(如果你一时没想通,我提醒一下,构造出的拉格朗日函数就是转化之后的问题形式,它显然没有带任何条件)。
读者问:如果只带等式约束的问题可以转化为无约束的问题而得以求解,那么可不可以把带不等式约束的问题向只带等式约束的问题转化一下而得以求解呢?
聪明,可以,实际上我们也正是这么做的。下一节就来说说如何做这个转化,一旦转化完成,求解对任何学过高等数学的人来说,都是小菜一碟啦。
分享到:
相关推荐
SVM入门(五)线性分类器的求解——问题的描述Part2 SVM入门(六)线性分类器的求解——问题的转化,直观角度 SVM入门(七)为何需要核函数 SVM入门(八)松弛变量。 SVM入门(九)松弛变量(续)。 SVM入门(十)...
简单的SVM线性分类的仿真实验,包括测试数据跟源码,易学
使用SVM对数据进行分类,且进行结果显示,可查阅SVM相关资料,对该代码及其算法进行进一步了解。
SVM的数据分类预测—意大利葡萄酒种类识别的matlab源程序与数据 - SVM prediction data classification - Italian Wine type recognition matlab source code and data
利用支持向量机(SVM)求解分类问题,包含线性分类方法,非线性分类方法,高斯核分类方法等小实例
带你入门常见的机器学习分类算法——逻辑回归、朴素贝叶斯、KNN、SVM、决策树.pdf带你入门常见的机器学习分类算法——逻辑回归、朴素贝叶斯、KNN、SVM、决策树.pdf带你入门常见的机器学习分类算法——逻辑回归、朴素...
带你入门常见的机器学习分类算法——逻辑回归、朴素贝叶斯、KNN、SVM、决策树.docx带你入门常见的机器学习分类算法——逻辑回归、朴素贝叶斯、KNN、SVM、决策树.docx带你入门常见的机器学习分类算法——逻辑回归、...
matlab14 基于SVM的数据分类预测——意大利葡萄酒种类识别
matlab程序,基于SVM的数据分类预测——意大利葡萄酒种类识别,里面一个.m文件,一个.mat数据集,直接可以使用。
采用matlab进行支持向量机svm的线性分类,每一句都有详尽的解释,方便大家学习交流
SVM的参数优化——如何更好的提升分类器的性能.7z本章要解决的问题就是仅仅利用训练集找到分类的最佳参数,不但能够高准确率的预测训练集而且要合理的预测测试集,使得测试集的分类准确率也维持在一个较高水平,即...
线性svm的admm算法,matlab程序。搞学术的小伙伴,研究admm算法的可以看看
Matlab的SVM入门整理文档-SVM入门.rar 首先非常感谢matlab中文论坛的人工智能版主在SVM知识方面做的贡献,《SVM入门》文档就是在论坛上下的,但是有一缺点就是板书不太好看,因此我将该文档调整了一下,看上去舒服...
分类器设计之线性分类器和线性SVM(Matlab代码 具休请参考本人博客: http://blog.csdn.net/ranchlai/article/details/10303031
SVM-非线性分类数据集
线性支持向量机训练文件 MATLAB代码 可运行
线性SVM分类器
这是一款很好用的SVM分类器工具,很适合实验用!
用线性SVM解决非线性问题,基于MATLAB平台的数据分类代码
模式识别 北京大学 本科生课程 课件 (包括贝叶斯模型、最近邻、SVM、线性与非线性分类器、boosting、统计学习、非监督学习等)