Home > ComputerVision > 原创:SVM与SVR支持向量机原理学习与思考(一)

原创:SVM与SVR支持向量机原理学习与思考(一)

弱弱的看了看老掉牙的支持向量机(Support Vector Machine, SVM)与支持向量回归(Support Vector Regression, SVR),发现知道的太少太弱了,基础知识要好好补一补。

SVM的原理参考
http://en.wikipedia.org/wiki/Support_vector_machine
http://zh.wikipedia.org/wiki/%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA
下标用_表示,上标用^表示

SVM中对k类即多类问题的处理,有几种方法(节选自一本烂书:方瑞明《支持向量机理论及其应用分析》):
(1)     One against all:设计k个SVM两类分类器;
(2)     All against all/one against one: 设计两两k(k-1)/2个SVM两类分类器。
(3)     Error correcting output codes(ECOCs):大约是利用类似Hanming码的方式,去除输出的错误,没有太仔细研究,但这种方法可能将来对我有用。p.s. Hanming编码:用多位编码少位的数据,采取处理避免信道噪声引起的信号错误,采用Hanming矩阵,大致参考(2005)A study on Error Correcting Output Codes.pdf,说了一点点。
(4)     一次性分类:采用一次优化求解解决问题。对于每一类,设计w_i与b_i,约束真实类别对应的w_i x + b_i大于其他类别的w_i x + b_i进行训练,求解目标是所有w_i的范数之和最小,也可以引入 样本数乘以类别数 个松驰变量。
LIBSVM采用的是(2),并且投票的方法,如果两类投票相同,它选择标号小的一类-_-b。

SVR(support vector regression)的主要思想:
(1)     所谓回归(regression),基本上就是拟合,用一个函数拟合x与y的关系。对于SVR来说,x是向量,y是标量,拟合的函数形式为y=W^T*g(x)+b,其中g(x)为核函数对应的特征空间向量。
(2)     SVR认为,只要估计的y在实际的y的两侧一个固定的范围(epsilon)之内,就认为是估计正确,没有任何损失;
(3)     SVR的优化目标,是|W|最小,这样y-x曲线的斜率最小,这个function最flat,这样据说可以增加估计的鲁棒性。
(4)     之后的事情就很自然了,和SVM一样:可以有soft margin,用一个小正数控制。用对偶式来解;
(5)     但有一个不同,控制范围的epsilon的值难于确定,在最小优化目标中加入一项C*
u*epsilon,其中epsilon是一个变量,nu是一个预先给定的正数。

SVM中的增量学习,可以采用的有几种方式:
(1)     基于KKT条件方法,在新的训练样本中选择不符合已训练分类器的KKT(Karush-Kuhn-Tucker)条件的样本与原支持向量组成新的训练集,如此反复。
(2)     Batch-SVM:原支持向量+新训练样本进行训练;
(3)     渐进增量学习方法:这个复杂一点,要求比较多的迭代次数。

关于SVM的一些其他事情:
(1)     去掉训练数据中的非支持向量(包括软间隔问题中的在间隔带外的正确分类样本),优化的结果不变,因为那些是原优化问题中的不起作用约束,同时又有全局最优解;
(2)     硬间隔SVM与二范数软间隔SVM(L2SVM)有唯一解,一范数软间隔SVM(L1SVM)不一定有唯一解。

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: