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

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

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

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

一种非光滑损失坐标下降算法

针对非光滑损失问题提出一种新的坐标下降算法,采用排序搜索的方式求解子问题解析解。分析了算法的时间复杂度,并给出了三种提高收敛速度的实用技巧。实验表明算法对正则化Hinge损失问题具有良好的性能,达到了预期的效果。     

L1/2正则化Logistic回归

提出一种L1/2正则化Logistic回归模型,并针对此模型构造有效的求解算法.文中模型基于L1/2正则化理论建立,有效改善传统模型存在的变量选择与计算过拟合问题.文中算法基于"坐标下降"思想构造,快速有效.在一系列人工和实际数据集上的实验表明,文中算法在分类问题中具有良好的变量选择能力和预测能力,优于传统Logistic回归和L1正则化Logistic回归.     

基于次梯度的L1正则化Hinge损失问题求解研究

Hinge损失函数是支持向量机(support vector machines, SVM)成功的关键,L1正则化在稀疏学习的研究中起关键作用.鉴于两者均是不可导函数,高阶梯度信息无法使用.利用随机次梯度方法系统研究L1正则化项的Hinge损失大规模数据问题求解.首先描述了直接次梯度方法和投影次梯度方法的随机算法形式,并对算法的收敛性和收敛速度进行了理论分析.大规模真实数据集上的实验表明,投影次梯度方法对于处理大规模稀疏数据具有更快的收敛速度和更好的稀疏性.实验进一步阐明了投影阈值对算法稀疏度的影响.     

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

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

稀疏学习优化问题的求解综述

机器学习正面临着数据规模日益扩大的严峻挑战,如何处理大规模甚至超大规模数据问题,是当前统计学习亟需解决的关键性科学问题.大规模机器学习问题的训练样本集合往往具有冗余和稀疏的特点,机器学习优化问题中的正则化项和损失函数也蕴含着特殊的结构含义,直接使用整个目标函数梯度的批处理黑箱方法不仅难以处理大规模问题,而且无法满足机器学习对结构的要求.目前,依靠机器学习自身特点驱动而迅速发展起来的坐标优化、在线和随机优化方法成为解决大规模问题的有效手段.针对L1 正则化问题,介绍了这些大规模算法的一些研究进展.     

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

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

L1范数正则化SVM聚类算法

提出L1范数正则化支持向量机(SVM)聚类算法。该算法能够同时实现聚类和特征选择功能。给出L1范数正则化SVM聚类原问题和对偶问题形式,采用类似迭代坐标下降的方法求解困难的混合整数规划问题。在多组数据集上的实验结果表明,L1范数正则化SVM聚类算法聚类准确率与L2范数正则化SVM聚类算法相近,而且能够实现特征选择。     

Relaxed sparse eigenvalue conditions for sparse estimation via non-convex regularized regression

Non-convex regularizers usually improve the performance of sparse estimation in practice. To prove this fact, we study the conditions of sparse estimations for the sharp concave regularizers which are a general family of non-convex regularizers including many existing regularizers. For the global solutions of the regularized regression, our sparse eigenvalue based conditions are weaker than that of L1-regularization for parameter estimation and sparseness estimation. For the approximate global and approximate stationary (AGAS) solutions, almost the same conditions are also enough. We show that the desired AGAS solutions can be obtained by coordinate descent (CD) based methods. Finally, we perform some experiments to show the performance of CD methods on giving AGAS solutions and the degree of weakness of the estimation conditions required by the sharp concave regularizers.     

无约束图像分割模型的快速数值算法

针对无约束图像分割模型的实现问题,提出一种基于分块协调下降方法的快速数值算法.该算法将模型的对偶问题转化为一组约束一元或二元二次极值问题,不仅避免了原问题求解时局部不可微性和高非线性性等难点,使得求解过程简单并易于实现:而且与现有的基于梯度下降的算法相比,具有无条件全局收敛性并显著地提高了收敛速度.仿真实验结果表明了所提出算法的有效性和在分割效率上的优越性.     

含有L1数据保真项的非凸优化脉冲噪声去除模型

随着数字图像处理技术的高速发展,图像恢复被广泛应用于医学领域、军事领域、公共防卫领域及农业气象领域.本文综合TVL1、ROF、STVL1（Squares TVL1）、SHI模型,提出了非凸非光滑关于脉冲噪声去除模型,并使用变量分离技术的ADMM算法对模型进行求解,通常情况下,基于梯度的方法不适合非光滑优化,半二次（half-quadratic）和重权最小二乘算法（IRLS）在零点不可微分情况下不能应用到非光滑函数上,Graduated NonConvexity （GNC） algorithms跟踪非光滑和非凸的最小值沿着一系列近似的非光滑能量函数的势能,需要考虑其计算时间.为了处理模型的非凸非光滑项,本文应用多阶凸松弛方法对模型的子问题进行求解,虽然该方法仅导致原始非凸问题的局部最优解,但该局部解是对初始凸松弛的全局解的改进.此外,因为每个阶段都是凸优化问题,所以该方法在计算上是高效的.利用遗传算法对模型参数进行选择,通过在不同图片及不同噪声上的大量实验表明,该模型的鲁棒性、运行时间和ISNR、PSNR都优于其他三个模型.并且该模型能够保持图像的局部信息具有更好的可视化质量.     

基于正则化约束的遥感图像多尺度去模糊

目的遥感成像过程中的图像降质严重影响了高分辨率成像与高精度探测,为了改善遥感图像质量,提出了基于正则化约束的遥感图像多尺度去模糊方法。方法首先利用双边滤波器和冲击滤波对遥感图像进行预处理,然后结合遥感图像模糊核的稀疏特性,使用正则化方法迭代求解模糊核最优解,最后利用基于梯度稀疏的非盲反卷积方法得到去模糊结果。此外,针对图像模糊程度较严重的情况,分析了尺度信息对去模糊结果的影响,提出了多尺度迭代优化方法。结果采用本文方法对大量遥感图像进行去模糊,实验结果表明该方法能有效地去除遥感成像产生的模糊,在保持图像边缘和细节的同时,可有效抑制振铃效应。相比其他方法,本文方法恢复图像的边缘强度平均提高28.7%,对比度平均提高17.6%。结论提出一种正则化约束的遥感图像多尺度去模糊方法,主观视觉感受和客观评价指标都表明该方法可以有效提升遥感图像质量。     

基于Abdou算子的空间自适应图像去模糊算法

在数字图像去模糊的正则化求解过程中,为了更好地保持图像的边缘和纹理,抑制振铃效应,需要结合图像不同空间位置的信息,自适应地调节正则化参数。通过引入Abdou算子计算图像中每个像素的梯度幅值,并考虑人类的视觉系统特性,构造出空间域上的加权矩阵s,从而对正则化参数自适应加权,并采用共轭梯度法进行去模糊求解。与Lagendijk提出的基于局部方差构造加权矩阵的复杂计算不同,基于Abdou算子求解的方法简单可行,去模糊效果良好。     

模糊图像盲复原的鲁棒自适应滤波算法

运动模糊图像盲复原是图像处理中的关键问题之一.由于模糊信息估计的复杂性以及图像噪声的影响, 现有算法往往难以做到高质量的图像复原.为改善模糊信息估计的效果, 提出一种基于自适应线性滤波的改进算法.首先在原有模糊信息估计过程中引入自适应动态线性滤波以抑制噪声影响, 达到改善模糊信息估计结果的目的, 同时可以起到调整优化目标的作用, 使原问题变得较容易求解, 从而获得高质量的模糊信息估计;在此基础上提出了改进的重定权值split Bregman迭代法, 用于获得模糊信息后求解原始图像的过程中, 进一步改善模糊图像复原的效果.实验结果表明, 与3种现有的模糊图像盲复原算法相比, 该算法能更准确地估计模糊信息, 对多数图像复原任务具有更好的鲁棒性, 能有效地用于运动模糊图像复原任务.     

Coordinate descent with arbitrary sampling I: algorithms and complexity†

We study the problem of minimizing the sum of a smooth convex function and a convex block-separable regularizer and propose a new randomized coordinate descent method, which we call ALPHA. Our method at every iteration updates a random subset of coordinates, following an arbitrary distribution. No coordinate descent methods capable to handle an arbitrary sampling have been studied in the literature before for this problem. ALPHA is a very flexible algorithm: in special cases, it reduces to deterministic and randomized methods such as gradient descent, coordinate descent, parallel coordinate descent and distributed coordinate descent—both in nonaccelerated and accelerated variants. The variants with arbitrary (or importance) sampling are new. We provide a complexity analysis of ALPHA, from which we deduce as a direct corollary complexity bounds for its many variants, all matching or improving best known bounds.