四种TSVR型学习算法的性能比较
李艳蒙;范丽亚
【摘 要】It is w ell know n that the computational complexity and sparsity of learning algorithms based on support vector regression machines (SVRs) are two main factors for analyzing and treating big data ,especially for high dimensional data .According to the two factors ,scholars did a lot of research work and proposed many improved SVR‐type learning algorithms .Among these improved algorithms , some have the basically same starting point ,just solving methods are slightly different ;some have dis‐tinctly different starting point and then result in different optimization problems ,but the solving meth‐ods are similar .For deep understanding these improved algorithms and being more selective in the appli‐cations ,this paper is devoted to analyze and compare the performance for four more representative TS‐VR‐type algorithms .%我们知道，基于SVR的学习算法的计算复杂性和稀疏性对分析和处理大数据来说是非常重要的两个因素，尤其是对高维数据。为此，学者们做了大量的研究工作并提出了许多改进的SVR型算法。它们当中，有些算法的出发点基本相同，只是求解方法上略有不
同；有些算法有明显不同的出发点，其所构建的最优化模型也不相同，但求解方法上大同小异。本文选择四个较具代表性的TSVR型学习算法，分析和比较它们的性能，以期更加深入的理解这些算法，且在应用中更具有选择性。
【期刊名称】《聊城大学学报（自然科学版）》
【年(卷),期】2016(029)003
【总页数】7页(P1-7)
【关键词】孪生支持向量回归机;最小二乘;边界;参数不敏感
【作 者】李艳蒙;范丽亚
【作者单位】聊城大学 数学科学学院，山东 聊城 252059;聊城大学 数学科学学院，山东 聊城 252059
正则化改进算法【正文语种】中 文
【中图分类】O224
支持向量机(Support Vector Machine, SVM)[1,2]作为数据挖掘和机器学习的一个有力工具, 已广泛应用于各种分类与识别问题中, 如: 粒子识别、人脸识别、文本分类等[3-5]. 支持向量回归机(Support Vector Regression Machine, SVR)[6]是基于SVM发展起来的, 多用于数据的估计、拟合和回归. 经典的SVR的计算复杂性是, 其中是用于学习的数据样本个数. 我们知道, 基于SVR的学习算法的计算复杂性和稀疏性对分析和处理“大数据”来说是非常重要的两个因素, 尤其是对高维数据, 学者们为此做了大量的研究并提出了许多改进的基于SVR的学习算法. 它们当中, 有些算法的出发点基本相同, 只是求解方法上略有不同; 有些算法有明显不同的出发点, 其所构建的最优化模型也不相同, 但求解方法上大同小异. 譬如: 为了降低SVR的计算复杂性, Peng[7]于2010年提出了孪生SVR(Twin SVR, TSVR). 不同于SVR直接学习拟合函数, TSVR是通过求解两个小规模的二次规划问题(Quadratic Programming Problems, QPPs)来学习上界函数和下界函数, 进而得到拟合函数. TSVR的计算复杂性是2O(n3), 明显比SVR快得多. 2010年, Kumar和Gopal[8,9]提出了最小二乘TSVR(Least Squares TSVR, LS-TSVR), 其主要特点是不需要求解两个小规模的QPPs, 而是直接求解两个线性方程组, 这进一步加快TSVR的学习速度, 但同时也损失了拟合精确度. 2012年, Peng[10]又提出了孪生参数不敏感SVR(Twin Parameter Insensitive SVR, TPISVR). 2013年, Shao等人[11]提出了孪生边界SVR(Twin Boundary SVR, TBSVR).
针对诸多改进的TSVR型学习算法, 选择四个较具代表性的算法, 分析和比较它们之间的性能, 以期更加深入的理解这些算法, 且在应用中更具有选择性. 鉴于篇幅有限, 只针对线性学习算法加以讨论, 通过引入核函数和核技巧, 用类似于本文的方法可以比较非线性学习算法的性能.
本节简要回顾线性SVR, 详细内容见文献[6]. 不同于SVM, SVR主要是用于数据的估计、拟合和回归, 它是利用结构风险极小化准则和Vapnik ε-不敏感损失函数来寻回归函数f(x)=wTx+b,其中w∈Rm和b∈R分别是法向量和偏移项. 给出数据集是输入样本, yi∈R是对应的输出值. 记A=[x1,…,xn]T∈Rn×m,y=(y1,…,yn)T∈Rn,e=(1,…,1)T∈Rn. 线性SVR 对应的原始问题为
其中c>0是调节参数,ξ,ξ*∈Rn是松弛向量. 模型(1)的几何解释如图1所示.
为了求解模型(1), 考虑其Lagrange函数
其中α,β,γ,γ*∈Rn，是非负Lagrange乘子向量, 并令可得
进而得问题(1)的Wolfe对偶形式:
通过求解问题(2)可得w*=AT(α*-β*)及
进而构造回归函数f(x)=(w*)Tx+b*.
我们知道, 基于SVR的学习算法的计算复杂性和稀疏性对分析和处理大数据来说是非常重要的两个因素, 尤其是对高维数据. 从模型(1)可以看出SVR考虑了结构风险极小化问题且具有稀疏性, 但没有考虑经验风险极小化问题. 从模型(2)可以看出SVR的计算复杂性为,O((2n)3)=8O(n3) 因此随着样本个数n的增加, SVR的学习速度会大大减慢.
为了降低SVR的计算复杂性, 加快SVR的学习速度, Peng于2010年提出了孪生SVR(Twin SVR, TSVR). 不同于SVR求解一个规模较大的二次规划问题(2), TSVR是通过引入两个Vapnik ε-不敏感损失函数:ε1-和ε2-不敏感损失函数, 来构造两个小规模的QPPs. 通过这两个小规模的QPPs来学习回归函数. 具体说来, TSVR是通过构造如下两个QPPs
来学习下界函数x+b1和上界函数x+b, 其中c1,c2>0是调节参数, ξ,η∈Rn是松弛向量, 进而得到回归函数f(x)=[f1(x)+f2(x)]/2. 从模型(3)和(4)中可以看出, TSVR希望所寻的下界函数的上ε1-带和上界函数的下ε2-带中都尽可能多地包含样本输出值, 这导致了TSVR失去了稀疏性, 且带宽ε1,ε2>0的不同选择还会影响拟合精度. TSVR的几何解释如图2所示.
类似于SVR, 通过求解问题(3)和问题(4)的Wolfe对偶形式
可得最优的上、下界函数和其中α,γ是Lagrange乘子向量且G=[A e],f=y-eε1,h=y+eε2.
从模型(5)和(6)中可以看出, TSVR的计算复杂性为2O(n3), 明显比SVR快得多. 但从模型(3)和(4)中可以看出, TSVR只考虑了经验风险极小化问题, 没考虑结构风险极小化问题, 且失去了SVR所具有的稀疏性.
为了进一步加快TSVR的学习速度, Kumar和Gopal提出了LS-TSVR, 其主要特点是不需要求解Wolfe对偶问题(5)和(6), 而是直接从原始问题出发, 通过求解两个线性方程组得到拟合函数.
LS-TSVR将问题(3)和(4)中的不等式约束改变为等式约束, 把一次惩罚改变为二次惩罚, 得到如下两个QPPs
显然问题(7)和(8)等价于无约束最优化问题
令∂g1/∂g1/∂b1=0, 可得
进而得
记
则有Ju1+c1GT(Gu1-f)=0. 不失一般性, 可设对称非负定阵J+c1GTG是非奇异的(否则将其正则化), 于是有同理可得其中h=y+eε2.
从模型(9)的求解过程中可以看出, LS-TSVR不是求解问题(7)和(8)的Wolfe对偶形式, 而是求解两个线性方程组, 这确实大大加快了TSVR的学习速度, 这从后面的实验中也得以验证. 但LS-TSVR需要求解逆矩阵(J+c1GTG)-1和(J+c2GTG)-1, 当样本的维度m较高时, 又会增加计算时间, 对高维数据来说, 甚至是不可计算的. 此外, 如果逆矩阵不存在, 为了便于求解, 还需将矩阵J+c1GTG和J+c2GTG正则化, 且正则化过程中还要受到参数选择的影响, 因此LS-TSVR的拟合精度不稳定. 从模型(9)和(10)可以看出, LS-TSVR同样没有考虑结构风险极小化问题且失去了稀疏性.
为了进一步提高拟合精度, TBSVR既考虑了经验风险极小化问题, 也考虑了结构风险极小化问题. 具体地说, 就是TBSVR在TSVR的基础上融入了结构风险极小化原则, 从而得到如下两个QPPs
其中c1,c2,c3,c4>0是调节参数. 其直观解释如图3所示.
类似于TSVR, 通过求解问题(11)和(12)的Wolfe对偶形式
可得最优的上、下界函数f2(x)=(w*”和进而得到回归函数:
从模型(13)和(14)中可以看出, TBSVR的计算复杂性与TSVR形同, 均为2O(n3), 且矩阵GTG+c3I和GTG+c4I是对称正定阵, 因此是非奇异阵, 这回避了矩阵奇异性问题.
为了考虑稀疏性, 减少噪声对拟合精度的影响, Peng在TSVR的基础上于2012年又提出了TPISVR. 不同于TSVR希望所寻的上、下界函数的单侧带内尽可能多地包含样本输出值, TPISVR希望直接寻上界函数和下界函数, 而不考虑这两个边界函数的单侧带的情况, 这避免了TSVR因带宽的选择而影响拟合精度的不足, 同时也使得算法具有了稀疏性. TPISVR对应的原始问题为
其中c1,c2,v1,v2>0是调节参数, 其直观解释如图4所示.
从模型(15)和(16)中可以看出, TPISVR寻的上、下界函数并不是紧夹样本输出值, 这对噪声的影响起到了一定的抑制作用, 但同时也会在一定程度上损失拟合精度. 类似于TSVR, 通过求解问题(15)和(16)的Wolfe对偶形式
可得最优上、下界函数和进而得到回归函数
从模型(17)和(18)中可以看出, TPISVR的计算复杂性仍为2O(n3). 为了便于上述四种TSVR型学习算法的性能比较, 将其优劣势列综合列入表1中.
为了检验上述四种TSVR型学习算法的性能, 我们利用UCI数据库中的5个数据集(AM, Autoprice, BostonHousing, breast-cancer-wisconsin 和machine)进行了比较实验. 所有实验均以Matlab 7.0为软件环境, 以Intel p4(2.9 GHz)处理器、1 G内存的PC为硬件平台, 且采用5-折交叉验证法. 我们知道, 算法的学习性能不仅取决于所构建的数学模型, 还受限于模型参数的选择. 为了便于比较上述四种算法的性能, 且尽可能少的受到参数选择的影响, 我们取TSVR, LS-TSVR和TBSVR中的带宽均为, 且模型中的所以其他参数均采用网格搜索法, 搜索范围为, 搜索步长为1. 搜索的最优结果见表2, 其中392×8表示有392个样本, 每个样本含7个特征, 1个输出值.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。