正当式svm总则化路径算法

正当式svm总则化路径算法

默认路径算法（raguardimport）是路径跟踪理论。SVMpath算法跟踪Karush-Kuhn-Tucker(KKT)条件随正则化参数变化的情况,利用hinge损失函数的分段线性建立活动集,并根据正则化参数与活动集之间的关系确定路径拐点,求解各拐点处Lagrange乘子向量,建立完整的正则化路径.该算法为建立SVM正则化路径提供了完整的框架,已被推广到各种类型SVM,如平方损失函数SVM本文在已有SVM正则化路径算法的基础上,结合正定矩阵分解方法1研究背景本节将介绍SVM正则化表示形式和建立SVM正则化路径的主要步骤.1.1svm是校正的表达令!表示输入空间,通常有!ue020R其中,其中,ξ为样本空间R如图1所示.优化问题(1)的对偶形式为其中,1.2svm的完全解路径正则化路径算法是基于活动集(activeset)与正则化参数λ之间的相互影响,利用Lagrange乘子α与正则化参数λ的分段线性关系,求解正则化参数λ从+∞到0变化过程中所有SVM,从而得到SVM的完全解路径.首先建立优化问题式(1)的Lagrange函数,然后对各目标变量求偏导,再结合KKT条件,综合分析可得:对于任意i(1≤i≤n),当y其中,集合与集合事件1.初始事件:集合事件2.事件3.事件4.若用l表示事件发生的次数,可将第l次事件发生后上述各变量分别表示为此外,由于总是满足设集合由式(4)(5)得到m其中:由式(7)并结合δ2基于面向虚设矩阵的算法PDSVMP算法主要采用2种新策略:首先,将方程组式(6)转换为系数矩阵为正定矩阵的线性方程组,该方法可以解决现有算法适用范围受限问题,并可以利用Cholesky分解提高算法效率;然后,在上述工作基础上,根据活动集变化情况确定正则化参数增量,并由此计算下一事件发生时正则化参数值λ2.1现记矩阵拟合Hastie等人首先,由式(3)和式(4)及δ其矩阵形式为同时,式(5)的矩阵形式为现记即由此可得:并结合式(9)可得等式:综上所述,方程组式(6)可重新写为=(其中,0表示m由于K由矩阵K然后,利用式(12)求出各变量:进而可以求得δ2.2正则化参数求解下一拐点处正则化参数λ求得λ针对发生事件类型的不同,本文提出如下3种方法计算正则化参数增量.1)事件1由于事件1为初始化事件,因此正则化参数λ取初始值λ2)事件2事件2是指样本点从活动集此时,若b3)事件3或事件4这两类事件都是样本点进入活动集可得,对任意i(1≤i≤n):λζ其中,令综上所述,正则化参数增量δ因此,下一事件发生时正则化参数值为进一步,活动集$中样本点对应的Lagrange乘子为2.3正则化路径建立过程首先,PDSVMP算法中初始化是给定正则化参数λ的最大值λ算法1.初始化过程.算法2.正则化路径建立过程PDSVMP算法1中,n第l+1个事件发生时,主要计算负担为求解m3实验环境及实验平台本节设计实验来验证PDSVMP算法的可行性和计算效率.实验数据包括8个标准数据集和1个实例数据本文的实验环境是DELL,IntelCore2QuadQ82002.33GHzCPU,4.0GB内存,实验平台为R2.8.1.3.1svmpah算法正则化路径反映Lagrange乘子α与正则化参数λ的分段线性关系.若样本个数为n,则正则化路径上有n条折线(对应于n个Lagrange乘子{α首先,通过在数据集上生成分段线性正则化路径α由于SVMpath算法只能处理系数A满秩的情况,在A不满秩时可能得不到正确结果,该算法在处理这种实例时有可能得到错误的正则化路径.现构造实例数据3.2优化正则化路径下面实验对比PDSVMP算法与ISVMP算法在UCI标准数据集上的运行时间,以验证PDSVMP算法的计算效率.为降低实验的随机误差,从数据集中随机选取部分样本作为训练数据,如表1所示,每个数据集均重复选取10次,然后计算平均运行时间.该实验选择高斯径向基核(RBF)并设置核参数γ=1.该实验中,正则化参数λ的最大值设为λISVMP算法应用奇异值分解方法保证系数矩阵A不满秩时仍能得到正确正则化路径,且通过求解一个线性规划问题以确定λ4pdsvmp算法本文提出基于正定矩阵的SVM正则化路径求解算法PDSVMP.正定矩阵线性方程组求解方法应用于SVM正则化路径的求解,一方面通过Cholesky分解提高了求解SVM的计算效率,另一方面降低了求解正则化参数的计算开销.更为重要的是,基于正定矩阵的SVM正则化路径算法可适用于包含输入向量线性相关的样本集,拓展了SVM正则化路径算法