L1正则化机器学习问题求解分析

以稀疏学习为主线,从多阶段、多步骤优化思想的角度出发,对当前流行的L1正则化求解算法进行分类,比较基于次梯度的多步骤方法、基于坐标优化的多阶段方法,以及软L1正则化方法的收敛性能、时空复杂度和解的稀疏程度。分析表明,基于机器学习问题特殊结构的学习算法可以获得较好的稀疏性和较快的收敛速度。     

一种求解截断Hinge损失的软阈值坐标下降算法

有效地减少支持向量数目能够提高分类器的鲁棒性和精确性,缩短支持向量机(support vector machine, SVM)的训练和测试时间.在众多稀疏算法中,截断Hinge损失方法可以显著降低支持向量的数目,但却导致了非凸优化问题.一些研究者使用CCCP(concave-convex procedure)方法将非凸问题转化为多阶段凸问题求解,不仅增加了额外计算量,而且只能得到局部最优解.为了弥补上述不足,提出了一种基于CCCP的软阈值坐标下降算法.用坐标下降方法求解CCCP子阶段凸问题,提高计算效率;对偶SVM中引入软阈值投影技巧,能够减少更多的支持向量数目,同时选择合适的正则化参数可消除局部最优解的不良影响,提高分类器的分类精度.仿真数据库、UCI数据库和大规模真实数据库的实验证实了所提算法正确性和有效性.     

基于L1正则化的贝叶斯网络分类器

目前基于节点排序的贝叶斯网络分类器忽略了节点序列中已选变量和类标签之间的信息,导致分类器的准确率很难进一步提高。针对这个问题,提出了一种简单高效的贝叶斯网络分类器的学习算法:L1正则化的贝叶斯网络分类器(L1-BNC)。通过调整Lasso方法中的约束值,充分利用回归残差的信息,结合点序列中已选变量和类标签的信息,形成一条优秀的有序变量拓扑序列(L1正则化路径);基于该序列,利用K2算法生成优良的贝叶斯网络分类器。实验表明,L1-BNC在分类精度上优于已有的贝叶斯网络分类器。L1-BNC也与SVM,KNN和J48分类算法进行了比较,在大部分数据集上,L1-BNC优于这些算法。     

一种求解截断L1正则化项问题的坐标下降算法

L1正则化在稀疏学习的研究中起关键作用,使用截断L1正则化项往往可以获得更好的准确率,但却导致了非凸优化问题.目前,主要采用多阶段凸松弛(multi-stage convex relaxation, MSCR)算法进行求解,由于每一阶段都需要求解一个凸优化问题,计算代价较大.为了弥补上述不足,提出了一种求解截断L1正则化项非凸学习问题的坐标下降算法(Non-convex CD).该算法只需在多阶段凸松弛算法的每一阶段执行单步的坐标下降算法,有效降低了计算复杂性.理论分析表明所提出的算法是收敛的.针对Lasso问题,在大规模真实数据库作了实验,实验结果表明,Non-convex CD在取得和MSCR几乎相同准确率的基础上,求解的CPU时间甚至优于求解凸问题的坐标下降方法.为了进一步说明所提算法的性能,进一步研究了Non-convex CD在图像去模糊化中的应用问题.     

基于L1/2正则化的超分辨率图像重建算法

为提高图像重建质量,研究超分辨率图像重建技术与稀疏表示理论,提出一种基于L1/2正则化的超分辨率图像重建算法.将L1/2正则化理论运用到字典学习中,利用学习得到的字典重建高分辨率图像.实验结果表明,该算法的图像重建效果优于基于L1正则化的超分辨率图像重建算法.     

基于L1范数的全变分正则化超分辨重构算法

针对结构化照明显微成像系统的超分辨图像重构算法存在边界振铃效应、噪声免疫性差的问题,提出了一种基于L1范数的全变分正则化超分辨图像重构算法（简称L1/TV重构算法）。从结构化显微成像模型入手,分析了传统算法的设计原理和局限性;论述了L1/TV重构算法的原理,采用L1范数对重构图像保真度进行约束,并利用全变分正则化有效克服了重构过程的病态性,保护了重构图像边缘。对比研究传统重构算法和L1/TV重构算法的性能。实验结果表明：L1/TV重构算法具有更强的抗噪声干扰能力,重构图像空间分辨率更高。     

基于L1与TV正则化的改进图像重建算法

针对不完全投影数据图像重建中出现伪影和噪点的问题,提出了L1与TV同时进行正则化的图像重建模型。基于该重建模型,通过将Bregman迭代和TV软阈值滤波相结合,进一步提出了一种图像重建算法。该算法首先将投影数据通过优化的Bregman迭代算法进行初步重建,然后使用TV软阈值滤波对改造的全变分模型进行二次重建,最后判断是否满足设定的收敛阈值,若满足则结束重建,输出重建图像,否则重复进行上述两步操作,直至迭代完成。实验采用不添加噪声的Shepp-Logan模型与添加噪声的Abdomen模型来验证算法的有效性,证明了所提出的算法在视觉上均优于ART,LSQR,LSQT-STF,BTV等典型的图像重建算法,同时通过多项评价指标对比表明所提出的算法有明显优势。实验结果表明,所提算法在图像重建中能够有效去除条形伪影并保护图像细节,同时具有良好的抗噪性。     

基于Rescaled Hinge损失函数的多子支持向量机

针对多分类学习模型性能会受异常值影响的问题，提出基于Rescaled Hinge损失函数的多子支持向量机（RHMBSVM）。首先，该方法通过引入有界、非凸的Rescaled Hinge损失函数来构建相应的优化问题；然后，利用共轭函数理论将优化问题作等价变换；最后，使用变量交替策略形成一个迭代算法来求解非凸优化问题，该方法在求解的过程中可自动调节每个样本点的惩罚权重，从而削弱了异常值对K个超平面的影响，增强了鲁棒性。使用5折交叉验证的方法进行数值实验，实验结果表明，在数据集无异常值的情况下，该方法的正确率比多子支持向量机（MBSVM）提升了1.11个百分点，比基于Rescaled Hinge损失函数的鲁棒支持向量机（RSVM-RHHQ）提升了0.74个百分点；在数据集有异常值的情况下，该方法的正确率比MBSVM提升了2.10个百分点，比RSVM-RHHQ提升了1.47个百分点。实验结果证明了所提方法在解决有异常值的多分类问题上的鲁棒性。     

基于Rescaled Hinge损失函数的多子支持向量机

针对多分类学习模型性能会受异常值影响的问题,提出基于Rescaled Hinge损失函数的多子支持向量机（RHMBSVM）。首先,该方法通过引入有界、非凸的Rescaled Hinge损失函数来构建相应的优化问题;然后,利用共轭函数理论将优化问题作等价变换;最后,使用变量交替策略形成一个迭代算法来求解非凸优化问题,该方法在求解的过程中可自动调节每个样本点的惩罚权重,从而削弱了异常值对K个超平面的影响,增强了鲁棒性。使用5折交叉验证的方法进行数值实验,实验结果表明,在数据集无异常值的情况下,该方法的正确率比多子支持向量机（MBSVM）提升了1.11个百分点,比基于Rescaled Hinge损失函数的鲁棒支持向量机（RSVM-RHHQ）提升了0.74个百分点;在数据集有异常值的情况下,该方法的正确率比MBSVM提升了2.10个百分点,比RSVM-RHHQ提升了1.47个百分点。实验结果证明了所提方法在解决有异常值的多分类问题上的鲁棒性。     

一种具有最优收敛速度的正则化境面下降算法

Pegasos算法是求解大规模支持向量机问题的有效方法,在随机梯度下降过程中植入多阶段循环步骤,能使该算法得到最优的收敛速度O(1/T)。COMID算法是由镜面下降算法推广得到的正则化随机形式,可保证正则化项的结构,但对于强凸的优化问题,该算法的收敛速度仅为O(logT/T)。为此,在COMID算法中引入多阶段循环步骤,提出一种求解L1+L2混合正则化项问题的最优正则化镜面下降算法,证明其具有最优的收敛速度O(1/T),以及与COMID算法相同的稀疏性。在大规模数据库上的实验结果验证了理论分析的正确性和所提算法的有效性。     

一种具有O(1/T)收敛速率的稀疏随机算法

随机梯度下降(stochastic gradient descent, SGD)是一种求解大规模优化问题的简单高效方法,近期的研究表明,在求解强凸优化问题时其收敛速率可通过α-suffix平均技巧得到有效的提升.但SGD属于黑箱方法,难以得到正则化优化问题所期望的实际结构效果.另一方面,COMID(composite objective mirror descent)是一种能保证L1正则化结构的稀疏随机算法,但对于强凸优化问题其收敛速率仅为O(logT/T).主要考虑“L1+Hinge”优化问题,首先引入L2强凸项将其转化为强凸优化问题,进而将COMID算法和α-suffix平均技巧结合得到L1MD-α算法.证明了L1MD-α具有O(1/T)的收敛速率,并且获得了比COMID更好的稀疏性.大规模数据库上的实验验证了理论分析的正确性和所提算法的有效性.     

A pruning algorithm with L1/2regularizer for extreme learning machine简

Compared with traditional learning methods such as the back propagation （BP） method, extreme learning machine provides much faster learning speed and needs less human intervention, and thus has been widely used. In this paper we combine the L1/2 regularization method with extreme learning machine to prune extreme learning machine. A variable learning coefficient is employed to prevent too large a learning increment. A numerical experiment demonstrates that a network pruned by L1/2 regularization has fewer hidden nodes but provides better performance than both the original network and the network pruned by L2 regularization.     

清除椒盐噪声的局部L1去噪保边方法

中值滤波在去除椒盐噪声领域应用非常广泛。但是中值滤波去除椒盐噪声时有其固有缺点,比如说中值滤波并不能很好地保持边缘以及图像中的大量细节信息,所以中值滤波在对边缘和细节要求严格的情况下并不能带来很好的处理效果。为此,提出一种去除椒盐噪声并保持边缘的新方法,力图解决中值滤波在去除椒盐噪声时的问题。该方法是基于统计的跳变回归方法的改进型,并将能量函数由L2改为L1 。实验结果证明,这种方法不但能有效地滤除椒盐噪声,而且能够很好地保持边缘。     

基于L1-范数距离的最小二乘对支持向量机

最小二乘对支持向量机(LSTSVM)是一种有效的分类技术。然而,该方法需计算点到平面的平方L2-范数距离,从而易受野值或噪声的影响。为了缓解此问题,提出了一种有效的鲁棒 LSTSVM方法,即基于L1-范数距离的LSTSVM(LSTSVML1D)。该方法由于使 用L1范数作为距离度量,因此不易受到野值或噪声数据的影响。此外,设计了一种有效的迭代算法,旨在求解目标问题,并从理论上证明了其收敛性。在人工数据集和UCI数据集上验证了LSTSVML1D 的有效性。     

L1范数约束正交子空间非负矩阵分解

针对非负矩阵分解（NMF）相对稀疏或局部化描述原数据时导致的稀疏能力和程度比较弱的问题,提出了L1范数约束正交子空间非负矩阵分解方法.通过将L1范数约束引入到正交子空间非负矩阵分解的目标函数中,提升了分解结果的稀疏性.同时给出累乘迭代规则.在UCI、ORL和Yale三个数据库上进行的实验结果表明,该算法在聚类效果以及稀疏表达方面优于其他算法.     

一种基于ADMM的非光滑损失在线优化算法

交替方向乘子法（ADMM）在机器学习问题研究中已有一些高效的实际应用,但为了适应大规模数据的处理和求解非光滑损失凸优化问题,文中提出对原ADMM进行改进,得到了损失函数线性化的ADMM的在线优化算法。该在线算法相较原算法具有操作简单、计算高效等特点。通过详尽的理论分析,文中证明了新在线算法的收敛性,并得到其在一般凸条件下具有目前最优的Regret界以及随机收敛速度。最后在与当今流行在线算法的对比实验中验证了新在线算法的高效可行性。     

高维数据的1-范数支持向量机集成特征选择

特征选择是机器学习和模式识别领域的关键问题之一.随着模式识别与数据挖掘的深入,研究对象越来越复杂,对象的特征维数也越来越高,此时特征选择的稳定性也显得尤为重要.分析了1-范数支持向量机,用该方法对高维数据进行特征选择,并对特征选择的结果进行集成;提出了一种针对高维数据的稳定性度量方法;在基因表达数据上的实验结果表明,集成特征选择可以有效提高算法的稳定性.     

L1+L2正则化逻辑斯蒂模型分类算法

提出一种L1+L2范数正则化逻辑斯蒂模型分类算法。该算法引入L2范数正则化,解决L1正则化逻辑斯蒂算法迭代过程奇异问题,通过引入样本向量的扩展和新的权值向量完成L1范数非平滑问题,最终使用共轭梯度方法求解经过转化的最优化问题。在各种实际数据集上的实验结果表明,该算法优于L2范数、L1范数和Lp范数正则化逻辑斯蒂模型,具有较好的特征选择和分类性能。