基于正则化路径的支持向量机近似模型选择
丁立中;廖士中
【摘 要】模型选择问题是支持向量机的基本问题.基于核矩阵近似计算和正则化路径,提出一个新的支持向量机模型选择方法.首先,发展初步的近似模型选择理论,包括给出核矩阵近似算法KMA-α,证明KMA-α的近似误差界定理,进而得到支持向量机的模型近似误差界.然后,提出近似模型选择算法AMSRP.该算法应用KMA-α计算的核矩阵的低秩近似来提高支持向量机求解的效率,同时应用正则化路径算法来提高惩罚因子C参数调节的效率.最后,通过标准数据集上的对比实验,验证了AMSRP的可行性和计算效率.实验结果显示,AMSRP可在保证测试集准确率的前提下,显著地提高支持向量机模型选择的效率.理论分析与实验结果表明,AMSRP是一合理、高效的模型选择算法.%Model selection is an indispensable step to guarantee the generalization of support vector machines (SVM). The main problem of existing SVM model selection approaches is that a standard SVM needs to be solved with high complexity for each iteration. In this paper, a novel model selection approach for SVM via kernel matrix approximation and regularization path is proposed, based on the observation that approximat
e computation is sufficient for model selection. Firstly, a kernel matrix approximation algorithm KMA-a is presented and its matrix approximation error bound is analyzed. Then, an upper model approximation error bound is derived via the error bound of KMA-a. Under the guarantee of these approximation error bounds, an approximate model selection algorithm AMSRP is proposed. AMSRP applies KMA-a to compute a low-rank approximation of the kernel matrix that can be used to efficiently solve the quadratic programming of SVM, and further utilizes the regularization path algorithm to efficiently tune the penalty factor C. Finally, the feasibility and efficiency of AMSRP is verified on benchmark datasets. Experimental results show that AMSRP can significantly improve the efficiency of model selection for SVM, and meanwhile guarantee the test set accuracy. Theoretical and experimental results demonstrate that AMSRP is a feasible and efficient model selection algorithm.
【期刊名称】《计算机研究与发展》
【年(卷),期】2012(049)006
【总页数】8页(P1248-1255)
【关键词】模型选择;参数调节;支持向量机;矩阵近似计算;正则化路径
【作 者】丁立中;廖士中
【作者单位】天津大学计算机科学与技术学院 天津300072;天津大学计算机科学与技术学院 天津300072
【正文语种】中 文
【中图分类】TP181;TP301
支持向量机（support vector machines，SVM）是一类重要的机器学习方法［1］，该方法在核诱导的特征空间中训练线性学习器，并应用泛化性理论来避免过拟合现象．SVM的学习能力主要依赖于特征空间中的线性学习器和隐式定义特征空间的核函数．当核参数和惩罚因子给定时，线性学习器可通过一个标准的二次规划求得，因而模型（参数）选择对SVM的性能有着决定性的影响．已有的模型选择方法可概括为一个内外双层的优化框架［2］，内层
在超参数（包括核参数和惩罚因子）固定的情况下，通过凸二次优化求解Lagrange乘子，外层基于内层的优化结果通过最小化泛化误差的估计，如交叉验证误差［3－5］或误差界［6－7］，来调节核参数和惩罚因子．
对于软间隔SVM，交叉验证可给出泛化误差的最优估计［3］，但已有交叉验证方法通常格搜索整个参数空间，计算复杂性高［8］．为提高格搜索效率，基因算法［4］、进化计算［5］等被引入交叉验证中．最小化泛化误差的估计界是另一类模型选择方法．常见的误差界有支持向量张成界［6］和半径间隔界［7］等．整体上，两类方法均是设计某种策略来约减超参数搜索空间，进而提高模型选择外层的效率．但搜索方向的确定具有较高的计算代价或有效性难以验证．另一方面，SVM凸二次优化求解的复杂性为O（n3），多核SVM 二阶锥规划求解的复杂性为 O（Nn3．5）［9］，其中n为样本规模，N为候选核矩阵的个数，对于大规模实际问题，如潜在语义索引［10］、网页信息抽取［11］等，若对每个搜索路径上的模型都进行一次SVM训练，计算代价过高．
实际上，对于模型选择而言，没有必要对每个模型都计算其精确结果，所需的仅是一个能够评估模型相对优劣且可快速计算的近似解．基于近似计算对于模型选择的充分性，本文提出
了一个新的支持向量机近似模型选择方法．首先，综合Monte Carlo算法和不完全Cholesky分解［12］，给出核矩阵近似算法KMA－α，该算法先对核矩阵进行 Monte Carlo随机采样，采样后应用具有对称置换的不完全Cholesky分解来计算接近最优的低秩近似．然后，证明了KMA－α的近似误差界定理，并基于该误差界，进一步分析了模型近似误差界．最后，提出了近似模型选择算法AMSRP，该算法应用KMA－α求解核矩阵的一个低秩近似，以生成的近似矩阵输入正则化路径进行优化求解，最终选择具有最小交叉验证近似误差的模型作为算法的输出．标准数据集的实验结果表明，AMSRP在保证测试集准确率的前提下，显著地提高了支持向量机模型选择的效率．
1 背  景
1．1 支持向量机
令X表示输入空间，Y表示输出域，通常有X⊆RRp，二分类问题中Y＝｛－1，1｝，则训练集可表示为S＝（（x1，y1），…，（xn，yn））∈（X×Y）n．
硬间隔SVM是支持向量方法中最基本的模型，针对特征空间中的线性可分数据，寻使分类间隔最大的超平面（w，b）．该过程对应的优化问题为
式（1）的对偶形式为
其中，αi，αj 为Lagrange乘子．
利用核K（x，z）隐式地将数据映射到特征空间，可得式（2）的核化形式：
当特征空间中的数据线性不可分时，引入松弛变量，可得软间隔SVM，其优化形式为
其中，C为惩罚因子，ξi为松弛变量．式（4）的核化对偶形式为
式（5）可进一步表述为
其中，α∈RRn为Lagrange乘子向量，y∈Yn为标签向量，1 为n 维全1 向量，［Q］ij＝yiyjK（xi，xj）．
若优化问题式（6）的解为α＊i，i＝1，…，n，则最终的决策函数为
由上述优化方程可以发现，支持向量机的性能主要依赖于Lagrange乘子和超参数的选择．然而，当超参数给定时，Lagrange乘子可通过求解一个标准的二次规划问题得到，故超参数的
选择对支持向量机的性能起着决定性作用．本文进一步基于正则化路径和核矩阵近似计算给出一个高效的参数选择方法．
1．2 正则化路径
其中，正则化参数λ＝1/C，C为软间隔SVM中的惩罚因子，［1－yif（xi）］＋＝max（0，1－yif（xi））表示Hinge Loss，f（xi）＝wTxi＋b．
式（7）可通过下述优化问题求解：
正则化路径算法［13］是Hastie等人提出的一类高效的SVM正则化参数调节方法，该方法可在相当于一次SVM求解的复杂度内，得到所有的正则化参数及对应的解路径．
已有软间隔SVM的凸优化形式式（4）在正则化框架中可表述为
式（8）的对偶形式为
由原对偶问题的 Karush－Kuhn－Tucker（KKT）条件可得，对于每一个i＝1，…，n：
yif（xi）＝1⇒0≤αi≤1；
yif（xi）＜1⇒αi＝1；
yif（xi）＞1⇒αi＝0．  （10）
基于式（10）可定义如下集合：
E，L，R分别对应Hinge Loss的拐点及其左右两端．正则化路径算法充分利用Lagrange乘子与参数λ的分段线性关系，通过分析集合E，L，R中元素的变化情况来构建整个正则化路径，同时，在核参数给定的情况下，可给出每个正则化参数所对应的SVM的解．算法的详细步骤可参考文献［13］．本文将利用正则化路径算法调节SVM的惩罚因子C．
2 核矩阵近似算法
对于任意给定的矩阵A和正整数k，总是存在一个秩为k的矩阵Ak，使得对于所有的旋转不变范数（如Frobenius范数‖·‖F、谱范数‖·‖2），‖A－Ak‖的值均为最小，这样的Ak被称作最优秩k近似［12］，可通过矩阵A的奇异值分解求得．
若A∈RRn×n为对称半正定矩阵，则A＝UΣUT，其中U 为酉矩阵，Σ＝diag（σ1，…，σn）
正则化线性模型为实对角矩阵且满足σ1≥…≥σn≥0．那么，对于k≤rank（A），，其中，Ui 表示U 的第i列．矩阵奇异值分解的复杂度为O（n3）．

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