基于压缩感知的多尺度最小二乘支持向量机

王琴　沈远彤

基于压缩感知的多尺度最小二乘支持向量机

王琴1沈远彤2

提出一种基于压缩感知（Compressive sensing，CS）和多分辨分析（Multi-resolution analysis，MRA）的多尺度最小二乘支持向量机（Least squares support vector machine，LS-SVM）.首先将多尺度小波函数作为支持向量核，推导出多尺度最小二乘支持向量机模型，然后基于压缩感知理论，利用最小二乘匹配追踪（Least squares orthogonal matching pursuit，LS-OMP）算法对多尺度最小二乘支持向量机的支持向量进行稀疏化，最后用稀疏的支持向量实现函数回归.实验结果表明，本文方法利用不同尺度小波核逼近信号的不同细节，而且以比较少的支持向量能达到很好的泛化性能，大大降低了运算成本，相比普通最小二乘支持向量机，具有更优越的表现力.

最小二乘支持向量机，压缩感知，多尺度小波核，稀疏化，函数回归

引用格式王琴，沈远彤.基于压缩感知的多尺度最小二乘支持向量机.自动化学报，2016，42（4）:631−640

支持向量机（Support vector machine，SVM）［1］是在统计学习理论发展起来的一种实用方法，是专门针对小样本情况下机器学习问题而建立起来的一套新的理论体系，基于结构风险最小化原则，在模式识别和机器学习领域占有非常重要的地位.最小二乘支持向量机（Least squares support vector machine，LS-SVM）［2］采用误差平方和作为训练集的经验损失，将SVM的二次规划问题转换为求解线性方程组的问题.LS-SVM不仅比标准SVM需要调整的参数少，而且计算更简单.如今LS-SVM已经广泛地应用于隧道的可靠性分析［3］、天然气密度的确定［4］等领域.然而LS-SVM没有体现支持向量的稀疏性，这样会降低标准SVM的泛化能力.最近，Yang等［5］提出一种新颖的LS-SVM算法，把压缩感知（Compressive sensing，CS）理论与LS-SVM中的线性方程结合起来，将核矩阵作为字典，在训练的过程中，对支持向量进行稀疏处理，取得较好的效果.

支持向量机的非线性处理能力是通过“核映射”的方法将输入空间的数据映射到高维空间来实现的.核技巧是支持向量机的重要组成部分，目前已有许多核函数得到普遍使用，并且也表现出良好性能，例如高斯核函数.2004年，Zhang等［6］研究了由Morlet母小波构造的小波核，由于小波基具有良好的时频局部特性，且通过平移伸缩即能生成L2（Rd）上的一组完备基，因此将小波基作为核函数可以使分类支持向量机逼近任意分类面，回归支持向量机逼近任意的目标函数.然而目前的LS-SVM仅仅在单尺度小波空间上对信号进行逼近，没有充分利用小波多分辨的特性，而实际应用中往往碰到的是多尺度信号，因此使用多尺度小波基作为核函数更能体现信号的不同细节.

本文提出了一种基于 CS［7］和多分辨分析（Multi-resolution analysis，MRA）［8］的多尺度LSSVM.首先将小波分解得到的多尺度小波基作为支持向量核函数，得到多尺度LS-SVM模型，然后基于压缩感知理论，在不降低多尺度LS-SVM表现能力的前提下，对输出函数和多尺度小波核矩阵之间形成的关系方程，利用最小二乘正交匹配追踪算法（Least squares orthogonal matching pursuit，LSOMP）对多尺度LS-SVM的支持向量进行稀疏化，最后用稀疏的支持向量对函数进行回归.此方法的特点如下：1）将小波基作为支持向量核函数，能根据曲线不同变化部分调整核尺度参数，体现出小波的稀疏性和多尺度特点，可以比较好地抵御噪声干扰，体现信号的不同细节；2）把小波多分辨分析引入LS-SVM，将不同尺度的小波核函数融合在一起，构成多尺度LS-SVM，具有了很好的理论背景，方法更加灵活；3）多尺度LS-SVM仅通过一次步骤就可以将支持向量稀疏化，大大减少迭代计算成本；4）稀疏化后的多尺度LS-SVM，由于压缩感知的作用，可以将有用信息很好地保留下来；5）在稀疏化的过程中，没有任何参数的调整，降低了运算复杂度.

1　压缩感知理论

CS是一种在保证信息不损失的前提下，信号采集和压缩同时进行的方法，它将信号投影到观测矩阵上，利用这些投影得到的远小于采集信号数据量的观测值重建原始信号，是一种较好的信息获取方法.本文假设是在稀疏字典下的可压缩信号压缩感知使用观测值恢复出原始信号如果矩阵满足受限等距性（Restricted isometry property， RIP），就能从观测值准确地恢复信号从而变成了求解如下最优化问题：

2　多尺度小波理论

假设ϕ（x）∈L2（R），定义如下函数：

令｛ϕj，m（x）|m∈Z｝是Vj的基函数，j，m分别称为尺度因子与平移因子.由｛ϕj，m（x）|m∈Z｝张成的子空间Vj导出L2（R）空间的一个多分辨分析，即如下嵌套式子空间逼近序列｛Vj｝j∈Z：

Wj是Vj在Vj+1中的正交补子空间，可表示如下：

所以，给定J∈Z，在MRA框架下，正交小波分解关系具体表示如下：

其中，函数ψ（x）是小波母函数.所以，∀f（x）∈L2（R）可以分解成如下形式［11］：

3　基于压缩感知的多尺度LS-SVM模型

3.1多尺度LS-SVM回归模型

其中，fr∈Wr，r=1，···，L.然后用如下表达式逼近fr，r=1，···，L.

其中，αri，r=1，···，L，i=1，···，n是拉格朗日算子，kr（·，·）是子空间Wr里的小波核函数.为了简单起见，令多尺度LS-SVM的结构模型如图1所示.

图1　多尺度LS-SVM模型Fig.1　Multi-scale LS-SVM model

在这个模型中，f的每个子空间fr由不同的小波核函数表示，可以通过多尺度的核函数来表现信号中不同细节的变化.如果仅使用固定尺度，则在逼近目标函数的某些细节的时候，其他部分可能会出现过拟合的风险.一般情况下，比较小的L就能处理常见的问题，为方便起见，本文取L=2，对于更多尺度的LS-SVM模型可以用类似的方法推导，在两尺度下可表示为

其中，f1和f2分别用数据和来估计，基于LS-SVM算法，上述问题转化为求如下优化问题：

约束条件为

为了在对偶空间上求解上述优化问题，定义如下的Lagrange泛函：

其中，ai1，ai2为拉格朗日算子.从上式中消去，就能得到如下线性方程组：

3.2基于压缩感知的稀疏两尺度LS-SVM模型

其中，

从式（18）可以看出，将两尺度LS-SVM的支持向量稀疏化相当于使ω 中相应的元素为0.所以，在一定精度范围内，寻找稀疏最小二乘模型可转化为最小化‖ω ‖0，可通过下式计算：

可以很明显看出，式（19）和式（1）一致，就是从观测值重构信号.

其中，nsv是支持向量的个数，n是训练样本的个数.

基于压缩感知的稀疏两尺度LS-SVM算法如下：

步骤4.输出稀疏两尺度LS-SVM模型.

4　实验与分析

本节实验分别采用混合函数、带噪的一维信号、二维信号、非平稳序列信号以及真实机械臂数据.核函数为径向基（Radial basis function，RBF）小波核.每一个实验重复10次，最终取平均结果.在实验中，本文采用归一化均方误差（Normalized mean square error，NMSE）［13］来评估训练误差

其中，~y（t）为估计值，y（t）为实际值，NMSE一般为负值，而且负数绝对值越大，表明逼近效果越好.

4.1混合函数的拟合

本实验选取混合函数［14］如下：

输入数据xi∈［0，10］区间均匀采样生成200个样本，从中随机选取一半作为训练样本，并加入高斯噪声ni～N（0，0.052），测试样本不加噪声.两尺度LS-SVM的惩罚参数γ1，γ2从［20，30，···，200］中选取，小波核参数从［0.2，0.5，···，5］中选取，通过5折交叉验证方法获得最优参数：，图2为两尺度径向基小波核LS-SVM的一次实验结果.

图2　两尺度径向基小波核LS-SVM的实验结果Fig.2　Experimental results of two-scale RBF wavelet kernel LS-SVM

表1为RBF小波核与Morlet小波核、Mexican hat小波核的两尺度LS-SVM比较，表2为RBF小波核函数与RBF核函数、Sinc核函数的两尺度LS-SVM结果比较，表3为RBF小波多尺度核方法与组合RBF核、组合线性核与RBF核方法的比较.从图2可以看出，RBF小波核根据曲线不同变化部分调整核尺度参数，体现出小波的稀疏性和多尺度特点，可以比较好地抵御噪声干扰，体现信号的不同细节；从表2可看出，相比其他非小波核函数，具有更优越的表现力；另外，把小波多分辨分析引入LS-SVM，将不同尺度的小波核函数融合在一起，构成多尺度LS-SVM，具有了很好的理论背景，方法更加灵活，能比合成核方法［14−16］提供更完备的尺度选择；从表3可以看出，本文方法相比其他合成核方法，具有相当或更强的表现力.

表1　不同小波核函数的两尺度LS-SVM NMSE比较Table 1　NMSE comparison of two-scale LS-SVM with different wavelet kernel functions

表2　不同核函数的两尺度LS-SVM NMSE比较Table 2　NMSE comparison of two-scale LS-SVM with different kernel functions

表3　不同多核学习方法NMSE比较Table 3　NMSE comparison of different multi-kernel learning methods

4.2带噪声数据点的回归

本实验中，在式（23）加上高斯噪声 ni～N（0，0.12），从中获取400个样本，随机选取其中的一半作为训练样本，其余作为测试样本.图3为四种算法的误差比较，两尺度LS-SVM的惩罚参数γ1，γ2从［40，60，···，700］中选取，小波核参数从［0.1，0.15，···，1.5］中选取，通过5折交叉验证方法获得最优参数：γ1=460，γ2=200，，标准LS-SVM的最优参数γ=250， σ2=0.1也由交叉验证方法获得.从图3中看出两尺度LS-SVM比标准LS-SVM对带噪声信号的恢复能力要强，稀疏两尺度LS-SVM在有噪声的情况下的回归性能优于稀疏标准LS-SVM的回归性能，稀疏标准LS-SVM在稀疏度大于50%以后的回归能力逐渐下降，而稀疏两尺度LS-SVM在稀疏度大于85%以后回归能力才略有下降.这表明，跟稀疏标准LS-SVM相比，稀疏两尺度LS-SVM不仅可以更好地把信号的有用部分都保留下来，用较少的支持向量来对信号进行回归，而且还可以对信号的不同细节进行比较完整的诠释，特别是在稀疏的过程中，不需要对支持向量中的参数进行再次调整，这也大大降低了两尺度LS-SVM的复杂度.

图3　标准LS-SVM、稀疏LS-SVM、两尺度LS-SVM、稀疏两尺度LS-SVM四算法在不同稀疏度下NMSE比较Fig.3　NMSE comparison of standard LS-SVM，sparse LS-SVM，two-scale LS-SVM，sparse two-scale LS-SVM algorithms under different sparse degrees

为了更直观研究两尺度稀疏LS-SVM性能，取一次实验的结果，将原始数据，加噪声数据，以及标准LS-SVM和两尺度LS-SVM的输出数据进行详细比较，如图4所示.

图4　标准LS-SVM和两尺度LS-SVM的回归结果比较Fig.4　Regression results comparison of standard LS-SVM and two-scale LS-SVM

从图4可以看出，对于带噪声信号，稀疏两尺度LS-SVM在仅用10%的支持向量的时候，就表现出非常稳定的回归性能，而稀疏标准LS-SVM的回归性能与标准LS-SVM相比下降明显，在支持向量为20%的时候，稀疏标准LS-SVM实践效果有所回升，但是相比稀疏两尺度LS-SVM，表现效果过于粗糙，这也就进一步说明，稀疏两尺度LS-SVM具有的多尺度性能可以比较完整的恢复带噪声信号的原始模样，具有较强的抗噪能力，而且需要很少的支持向量就可以达到很好的逼近效果，这样为计算节约了很多成本，大大提高了LS-SVM的泛化性能.

4.3二维函数逼近

二元函数

其中，−10≤x1≤10，−10≤x2≤10，随机选取324个数据点为训练样本，1600个数据点作为测试样本.图5为测试样本曲线图.两尺度LS-SVM的惩罚参数γ1，γ2从［500，1000，···，70000］中选取，小波核参数从［0.2，0.4，···，8］中选取，通过5折交叉验证方法获得最优参数：γ1=2000，，标准LS-SVM最优参数γ=3200，σ2=3.05也由交叉验证方法获得.图6为90%稀疏度两尺度LS-SVM对测试样本的逼近效果.图7为90%稀疏度标准LS-SVM对测试样本的逼近效果.表4给出了稀疏两尺度LS-SVM和稀疏标准LS-SVM在不同稀疏度下NMSE比较的结果.这也说明，稀疏两尺度LS-SVM可以用10%的支持向量就能很好地逼近原测试样本，相比稀疏标准LS-SVM，能用更多的小波尺度，所以能表现出信号的不同细节，即便用较少的支持向量，也完全不降低其表现效果，所以具有更好的泛化性能.

图5　测试样本曲线图Fig.5　Test sample curve

图6　90%稀疏度两尺度LS-SVM逼近效果Fig.6　Approximation result of 90%sparse degree two-scale LS-SVM

图7　90%稀疏度标准LS-SVM逼近效果Fig.7　Approximation result of 90%sparse degree standard LS-SVM

4.4非平稳序列数据的拟合

本实验选取Garchdata 400个非平稳数据点进行拟合，在训练之前，首先对数据进行归一化，在不同稀疏度下比较稀疏两尺度LS-SVM和稀疏标准LS-SVM的回归性能，随机选取200个作为训练样本，其余作为测试样本.两尺度LS-SVM的惩罚参数γ1，γ2从［80，110，···，890］中选取，小波核参数从［0.1，0.2，···，3］中选取，通过5折交叉验证方法获得最优参数：，标准LS-SVM最优参数γ=200， σ2=0.2也由交叉验证方法获得.图8（a）和图8（b）分别表示50%稀疏度两尺度LS-SVM和标准LS-SVM的逼近结果.

从图8中看出，稀疏度两尺度LS-SVM仅用50%的支持向量可以达到很好的实验效果，而稀疏标准LS-SVM的结果的输出数据与原始曲线出现了比较大的偏离.图9给出了两尺度LS-SVM和标准LS-SVM在稀疏度为50%，55%，60%下的NMSE比较，两种方法的NMSE均随着稀疏度的升高而升高，但是在同样的稀疏度下，两尺度LS-SVM总是表现的更好一些.这是因为两尺度LS-SVM更能抓住数据的不同细节，即使去掉一些支持向量，也丝毫不影响它的良好性能，所以稀疏两尺度LS-SVM比稀疏标准LS-SVM具有更好的泛化性能.

4.5真实机械臂数据的估计

本实验对柔性机械臂的逆动力进行辨识［17］，在训练之前，首先对所有的原始数据进行归一化如下：

式中，xij为输入矩阵A的第（i，j）个元素，是 xij的归一化值和分别表示矩阵A第j列的最小值和最大值.

表4　稀疏两尺度LS-SVM和稀疏标准LS-SVM在不同稀疏度下NMSE比较Table 4　NMSE comparison of sparse two-scale LS-SVM and sparse standard LS-SVM algorithms under different sparse degrees

图8　标准LS-SVM和两尺度LS-SVM在50%稀疏度下拟合结果比较Fig.8　Approximation results comparison of standard LS-SVM and two-scale LS-SVM under 50%sparse degree

图9　标准LS-SVM和两尺度LS-SVM在不同稀疏度下NMSE比较Fig.9　NMSE comparison of standard LS-SVM and two-scale LS-SVM under different sparse degrees

此机械臂安装在一个电子发动机上，该系统的输入u（t）为结构的反作用扭矩，相应地输出d（t）为柔性臂的加速度.此数据包含1024对输入-输出样本，如图10所示.

图10　机械臂数据Fig.10　Robot arm data

此逆模型辨识可通过x（t）=（u（t−1），···，u（t−5），d（t−1），···，d（t−4））t和xout（t）=u（t）来学习.该数据集共有1019个形如（x（t），xout（t））的样本点.从样本点中随机选取510个样本点作为训练样本，其余作为测试样本.两尺度LS-SVM的惩罚参数γ1，γ2从［202，402，···，6002］中选取，小波核参数中选取，通过5折交叉验证方法获得最优参数：标准LS-SVM最优参数γ=2500，σ2=0.3也由交叉验证方法获得.图11为四种算法的误差比较，图12（a）和图12（b）分别表示50%稀疏度两尺度LS-SVM和标准LS-SVM对反作用扭矩的辨识结果.

图11　标准LS-SVM、稀疏LS-SVM、两尺度LS-SVM、稀疏两尺度LS-SVM四算法在不同稀疏度下NMSE比较Fig.11　NMSE comparison of standard LS-SVM，sparse LS-SVM，two-scale LS-SVM，sparse two-scale LS-SVM algorithms under different sparse degrees

图12　标准LS-SVM和两尺度LS-SVM在50%稀疏度下的拟合结果比较Fig.12　Approximation results comparison of standard LS-SVM and two-scale LS-SVM under 50%sparse degree

从图12中看出，两尺度LS-SVM在去掉一半支持向量以后丝毫不影响它的逼近效果，而标准LS-SVM在稀疏度大于15%的时候NMSE误差曲线就开始出现明显偏离.在同样的稀疏度下，标准LS-SVM逼近效果明显要次于两尺度LS-SVM.相比标准LS-SVM，两尺度LS-SVM能用更多的小波尺度，既能抓住数据的不同细节，又能在稀疏以后以较少的支持向量达到很好的辨识效果，所以稀疏两尺度LS-SVM比稀疏标准LS-SVM具有更好的泛化性能.

5　总结

本文提出了基于CS和MRA的多尺度LSSVM，首先根据MRA的特性，将多尺度小波基作为LS-SVM的核函数，得到多尺度LS-SVM模型，然后根据CS通过稀疏信号重构原始信号的原理，在多尺度LS-SVM模型的基础上运用LS-OMP贪婪算法，对信号的有用信息进行保留，将支持向量稀疏化，最后得到稀疏多尺度LS-SVM模型.相比普通LS-SVM，本文方法不仅可以用较少的支持向量达到很好的效果，而且可以很好地体现多尺度性能，更全面地提取信号的细节，计算也很简便，更具有现实意义.通过实验也能很好地说明本文方法的优越学习性能.对于多尺度LS-SVM，尺度越多，对信号的逼近细节的能力就越强，然而会有更多参数的调整，比较费时，如何运用比较快速的参数优化算法是继续研究的重点.

References

1 Vapnik V N.The Nature of Statistical Learning Theory. New York:Springer-Verlag，1995.69−83

2 Suykens J A K，Vandewalle J.Least squares support vector machine classifiers.Neural Processing Letters，1999，9（3）: 293−300

3 Zhao H B，Ru Z L，Chang X，Yin S D，Li S J.Reliability analysis of tunnel using least square support vector machine. Tunnelling and Underground Space Technology，2014，41: 14−23

4 Esfahani S，Baselizadeh S，Hemmati-Sarapardeh A.On determination of natural gas density:least square support vector machine modeling approach.Journal of Natural Gas Science and Engineering，2015，22:348−358

5 Yang J，Bouzerdoum A，Phung S L.A training algorithm for sparse LS-SVM using compressive sampling.In:Proceedings of the 2010 IEEE International Conference on Acoustics Speech and Signal Processing.Dallas，TX，USA:IEEE，2010.2054−2057

6 Zhang L，Zhou W D，Jiao L C.Wavelet support vector machine.IEEE Transactions on Systems，Man，and Cybernetics—Part B:Cybernetics，2004，34（1）:34−39

7 Shen Yan-Fei，Li Jin-Tao，Zhu Zhen-Min，Zhang Yong-Dong，Dai Feng.Image reconstruction algorithm of compressed sensing based on nonlocal similarity model.Acta Automatica Sinica，2015，41（2）:261−272（沈燕飞，李锦涛，朱珍民，张勇东，代锋.基于非局部相似模型的压缩感知图像恢复算法.自动化学报，2015，41（2）:261−272）

8 Mallat S G.A Wavelet Tour of Signal Processing.Sam Diego:Academic Press，1998.

9 Zhao J X，Song R F，Zhao J，Zhu W P.New conditions for uniformly recovering sparse signals via orthogonal matching pursuit.Signal Processing，2015，106:106−113

10 Elad M.Sparse and Redundant Representations:From Theory to Applications in Signal and Image Processing.New York:Springer-Verlag，2010.

11 Yang L，Han J Q，Chen D K.Identification of nonlinear systems using multi-scale wavelet support vectors machines.In: Proceedings of the 2007 IEEE International Conference on Control and Automation.Guangzhou，China:IEEE，2007. 1779−1784

12 Yang L X，Yang S Y，Zhang R，Jin H H.Sparse least square support vector machine via coupled compressive pruning. Neurocomputing，2014，131:77−86

13 Schniter P，Potter L C，Ziniel J.Fast Bayesian matching pursuit.In:Proceedings of the 2008 Information Theory and Applications Workshop.San Diego，CA，USA:IEEE，2008.326−333

14 Zhang Y P，Sun J G.Multikernel semiparametric linear programming support vector regression.Expert Systems with Applications，2011，38（3）:1611−1618

15 Zhao Yong-Ping，Sun Jian-Guo.A non-flat function robust regression algorithm using multi-kernel LS-SVM.Information and Control，2008，37（2）:160−165（赵永平，孙建国.一类非平坦函数的多核最小二乘支持向量机的鲁棒回归算法.信息与控制，2008，37（2）:160−165）

16 Cai Y N，Wang H Q，Ye X M，Fan Q G.A multiple-kernel LSSVR method for separable nonlinear system identification.Journal of Control Theory and Applications，2013，11（4）:651−655

17 Balasundaram S，Gupta D，Kapil.Lagrangian support vector regression via unconstrained convex minimization.Neural Networks，2014，51:67−79

王 琴海南医学院信息技术部讲师.主要研究方向为小波分析，人工智能，机器学习.本文通信作者.E-mail:wq-1018@163.com

（WANG QinLecturer in the Department of Information Technology，Hainan Medical University.Her research interest covers wavelet analysis， artificial intelligence，and machine learning.Corresponding author of this paper.）

沈远彤中国地质大学（武汉）数学与物理学院教授.主要研究方向为信号处理，数据挖掘，小波分析.E-mail:whsyt@163.com

（SHEN Yuan-TongProfessor at the School of Mathematics and Physics，China University of Geosciences.His research interest covers signal processing，data mining，and wavelet analysis.）

Multi-scale Least Squares Support Vector Machine Using Compressive Sensing

WANG Qin1SHEN Yuan-Tong2

A multi-scale least squares support vector machine（LS-SVM）based on compressive sensing（CS）and multiresolution analysis（MRA）is proposed.First，a multi-scale LS-SVM model is conducted，in which a support vector kernel with the multi-resolution wavelet function is employed；then inspired by CS theory，sparse support vectors of multi-scale LS-SVM are constructed via least squares orthogonal matching pursuit（LS-OMP）；finally，sparse support vectors are applied to function approximation.Simulation experiments demonstrate that the proposed method can estimate diverse details of signal by means of wavelet kernel with different scales.What is more，it can achieve good generalization performance with fewer support vectors，reducing the operation cost greatly，performing more superiorly compared to ordinary LS-SVM.

Least squares support vector machine（LS-SVM），compressive sensing（CS），multi-resolution wavelet kernel，sparse，function approximation

Manuscript May 15，2015；accepted December 28，2015

10.16383/j.aas.2016.c150296

Wang Qin，Shen Yuan-Tong.Multi-scale least squares support vector machine using compressive sensing. Acta Automatica Sinica，2016，42（4）:631−640

2015-05-15录用日期2015-12-28

国家自然科学基金（11301120）资助

Supported by National Natural Science Foundation of China（11301120）

本文责任编委周志华

Recommended by Associate Editor ZHOU Zhi-Hua

1.海南医学院信息技术部海口5711012.中国地质大学（武汉）数学与物理学院武汉430074

1.Department of Information Technology，Hainan Medical University，Haikou 5711012.School of Mathematics and Physics，China University of Geosciences，Wuhan 430074