求解大型线性最小二乘问题的贪婪随机坐标下降法

贪婪随机坐标下降法(GRCD)是求解大型线性最小二乘问题的有效迭代方法之一。本文在GRCD算法中引入松弛因子,构造了一种含参数的贪婪随机坐标下降法。并证明了当线性最小二乘问题的系数矩阵为列满秩时该方法依期望的收敛性。数值实验表明,当选取适当的松弛因子时,该算法在迭代步数和计算时间比GRCD方法更有效。

基于块坐标下降法的有砟轨道大机捣固维修经济决策模型及算法

为了更好地利用检修数据指导轨道维修决策计划,在预防性维修理念下提出1种基于块坐标下降法的有砟轨道大机捣固维修经济决策模型及算法。考虑多种捣固模式下不同的捣固效果和相应成本,以轨道质量年末保持值和维修经济成本为决策目标,结合大机养修效率和现场实际条件,建立大机捣固维修经济决策模型;采用块坐标下降算法,以并行计算为主要思路并通过聚类算法调整捣固区段的连续性,实现最佳捣固模式、捣固时机和捣固区段的高效求解。依托某120 km·h~(-1)、50 km试验区段在某年份的实测数据,验证模型及算法有效性。结果表明:依据模型及算法得出的维修计划,采用09-32型捣固车开展单捣、双捣2种捣固模式后,每年可较实际平推捣固计划分别节省18%和15%的费用,改良型大机捣固质量指数MTQI的年末平均值从实际平推捣固计划的6.5 mm分别降低约0.80和1.35 mm;模型及算法能够快捷有效地制定符合线路实际的大机捣固维修计划,不仅实现了大机作业的连续捣固,还较大幅度提升了捣固维修的经济性。

基于块坐标下降法的神经网络学习算法

针对当前一阶优化算法收敛速度慢,对学习率依赖性强和二阶优化方法复杂度高等问题,利用神经网络固有的可分性,提出递归最小二乘与梯度下降的混合算法(Hybrid Recursive Least-Squares with Stochastic Gradient Descent, HRLSGD),将原本复杂的网络模型分解为更易解决的低维优化问题。实验结果表明,HRLSGD的收敛速度优于主流的一阶优化算法,对于学习率的鲁棒性更高。

一种基于Comid的非光滑损失随机坐标下降方法

坐标下降方法以简洁的操作流程、低廉的计算代价和快速的实际收敛效果,成为处理大规模优化最有效的方法之一.但目前几乎所有的坐标下降方法都由于子问题解析求解的需要而假设损失函数的光滑性.本文在结构学习的框架下,在采用Comid方法求解随机挑选单变量子问题的基础上,提出了一种新的关于非光滑损失的随机坐标下降方法.理论分析表明本文所提出的算法在一般凸条件下可以得到Ο(t-(1/2)/t)的收敛速度,在强凸条件下可以得到Ο(lnt/t)的收敛速度.实验结果表明本文所提出的算法对正则化Hinge损失问题实现了坐标优化预期的效果.

基于分块坐标下降思想的并行无功优化分解协调算法

针对无功优化分解协调模型求解中增广拉格朗日函数的不可分问题,提出了基于分块坐标下降(block coordinatedescent,BCD)思想的并行分解协调计算方法。该方法可实现全网无功优化的分解协调计算,仅需要在相邻分区之间交换边界节点的功率和电压用于协调,解决了大规模电网集中式无功优化存在的计算速度慢和数据传输瓶颈问题;而且各控制中心可自主选择优化算法,实现了自律分散与协调控制的结合。算例结果表明,该算法可以大大减少全网无功优化的计算时间,并且与基于辅助问题原理的分解协调算法相比,其收敛速度更快、计算效率更高。

求解AUC优化问题的对偶坐标下降方法

AUC被广泛作为衡量不平衡数据分类性能的评价标准.与二分类问题不同,AUC问题的损失函数由来自两个不同类别的样本对组成.如何提高其实际收敛速度,是一个值得研究的问题.目前的研究结果表明:使用reservoir sampling技术的在线方法(OAM)表现出很好的AUC性能,但OAM仍存在诸如收敛速度慢、参数选择复杂等缺点.针对AUC优化问题的对偶坐标下降(AUC-DCD)方法进行了系统的研究,给出3种算法,即AUC-SDCD,AUCSDCDperm和AUC-MSGD,其中,AUC-SDCD和AUC-SDCDperm与样本数目有关,AUC-MSGD与样本数目无关.理论分析指出,OAM是AUC-DCD的一种特殊情形.实验结果表明,AUC-DCD在AUC性能和收敛速度两方面均优于OAM.研究结果表明,AUC-DCD是求解AUC优化问题的首选方法.

多层局部块坐标下降法及其驱动的分类重构网络

卷积稀疏编码(Convolutional sparse coding,CSC)已广泛应用于信号或图像处理、重构和分类等任务中,基于深度学习思想的多层卷积稀疏编码(Multi-layer convolutional sparse coding,ML-CSC)模型的多层基追踪(Multi-layer basic pursuit,ML-BP)问题和多层字典学习问题成为研究热点.但基于傅里叶域的交替方向乘子法(Alternating direction multiplier method,ADMM)求解器和基于图像块(Patch)空间域思想的传统基追踪算法不能容易地扩展到多层情况.在切片(Slice)局部处理思想的基础上,本文提出了一种新的多层基追踪算法:多层局部块坐标下降(Multi-layer local block coordinate descent,ML-LoBCoD)算法.在多层迭代软阈值算法(Multi-layer iterative soft threshold algorithm,ML-ISTA)和对应的迭代展开网络ML-ISTA-Net的启发下,提出了对应的迭代展开网络ML-LoBCoD-Net.ML-LoBCoD-Net实现信号的表征学习功能,输出的最深层卷积稀疏编码用于分类.此外,为了获得更好的信号重构,本文提出了一种新的多层切片卷积重构网络(Multi-layer slice convolutional reconstruction network,ML-SCRN),ML-SCRN实现从信号稀疏编码到信号重构.我们对这两个网络分别进行实验验证.然后将ML-LoBCoD-Net和ML-SCRN进行级联得到ML-LoBCoD-SCRN合并网,同时实现图像的分类和重构.与传统基于全连接层对图像进行重建的方法相比,本文提出的ML-LoBCoD-SCRN合并网所需参数少,收敛速度快,重构精度高.本文将ML-ISTA和多层快速迭代软阈值算法(Multilayer fast iterative soft threshold algorithm,ML-FISTA)构建为ML-ISTA-SCRN和ML-FISTA-SCRN进行对比实验,初步证明了所提出的ML-LoBCoD-SCRN分类重构网在MNIST、CIFAR10和CIFAR100数据集上是有效的,分类准确率、损失函数和信号重构结果都优于ML-ISTA-SCRN和ML-FISTA-SCRN.

基于平行坐标下降法的图像修复

以压缩传感和稀疏表示为理论依据,提出了一种基于平行坐标下降法的图像修复模型。该模型用小波变换作为图像的稀疏表示,以稀疏性作为正则化项;同时基于松弛阈值来标记函数实现全局优化,并采用该模型算法得到全局最优解。从峰值信噪比、收敛速度和视觉效果等3个方面验证了算法的有效性。结果表明新的模型无论是在客观还是视觉主观上都有更好的效果,同时算法具有更快的收敛速度。

弱分层交互Lasso罚logistic回归模型和改进坐标下降算法

基于变量交互和分层思想,提出了一种弱分层交互Lasso罚logistic回归模型。首先给出了交互模型定义和弱分层约束条件,然后给出了凸松弛条件和基于坐标下降法的系数求解算法。在4个UCI机器学习数据集和1个日常生活活动识别数据集上进行实验,实验结果证明了变量交互对分类也有贡献,分层对分类也有贡献。分层交互Lasso兼具Lasso和交互Lasso的优点。

坐标下降l_2范数LS-SVM分类算法

研究l2范数正则化最小二乘支持向量机的坐标下降算法实现.在图像处理、人类基因组分析、信息检索、数据管理和数据挖掘中经常会遇到机器学习目标函数要处理的数据无法在内存中处理的场景.最近研究表明大规模线性支持向量机使用坐标下降方法具有较好的分类性能,在此工作基础上,文中扩展坐标下降方法到最小二乘支持向量机上,提出坐标下降l2范数LS-SVM分类算法.该算法把LS-SVM目标函数中模型向量的优化问题简化为特征分量的单目标逐次优化问题.在高维小样本数据集、中等规模数据集和大样本数据集上的实验验证了该算法的有效性,与LS-SVM分类算法相比,在数据内存中无法处理的情况下可作为备用方法.

求解大规模SCAD回归问题的随机坐标下降算法研究

回归方法是重要的数据分析工具。带平滑削边绝对偏离(smoothly clipped absolute deviation, SCAD)正则项的回归问题,以其在处理高维数据中的近似无偏性(见Fan和Li,2001),在大数据分析中得到广泛应用。但在大数据背景下,待求解的SCAD回归问题的数据量往往很大,而且分布在不同地理位置,这使得在SCAD回归问题的求解算法设计中,需要重新考虑计算的内存使用量。常规用于求解SCAD回归问题的优化算法(LQA、LLA、ADMM等)往往需要在每一次迭代中更新全部变量,从而造成计算的内存需求很大,难以适应大数据的求解要求。随机坐标下降方法(stochastic coordinate descent, SCD)以其子问题运算内存需求小(见Nesterov,2012)的优势,在大规模分布式最优化问题中得到了广泛的应用。但目前理论上SCD算法仅能处理带凸惩罚项的回归问题,由于SCAD回归问题中惩罚项的非凸非光滑性,现有的随机坐标下降方法难以处理这一问题。首先对SCAD回归问题模型进行分析,得出SCAD回归模型的损失函数是导数Lipschitz、惩罚函数是semi-convex的,此外根据已有结论,得到SCAD回归问题的稳定点即可保证良好的统计性质。基于这些性质的分析,介绍了一种新的随机坐标下降方法(variable bregman stochastic coordinate descent, VBSCD),这一方法能很好求解带SCAD惩罚项的回归问题,算法的收敛点是SCAD回归模型的稳定点。最后,通过计算实验进一步说明本算法在求解SCAD回归问题的有效性。对不同的变量分组数,算法迭代到稳定点所需的迭代回合数相对稳定。随着变量分块数的增加,单次迭代中计算的内存需求减少。该研究方法可广泛应用于大数据背景下SCAD回归问题的求解当中。

无约束优化的并行坐标下降法

提出了一种求解无约束优化问题的并行坐标下降法,并给出了该并行算法的数值实验结果,进而讨论了该算法的加速倍数及并行效率。计算结果表明该并行算法是行之有效的。

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

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

几类群组变量选择方法及其块坐标下降算法

在复杂数据中变量往往成组出现,考虑了Lasso、SCAD、Bridge及MCP四种不同模型选择的惩罚项,研究了它们在群组变量中的方法及其块坐标下降算法,在Logistic模型的条件下进行模拟,结果表明Composite MCP组惩罚方法在预测能力和变量选择上均优于其他三种群组惩罚方法,并运用到销售网络办公软件公司的广告数据中,结果表示四种方法中Composite MCP方法在广告转化研究中效果是最优的,通过比较,选择出影响广告转化的群组结构及单个变量,为选择投放策略提供合理的依据。

基于坐标下降和偏移映射的运动编辑与重定向

提出了一种基于坐标下降和偏移映射的人体运动编辑与重定向方法,使角色运动适用于虚拟场景。采用加入生理限制的循环坐标下降算法自动求解约束帧目标姿态,在约束帧附近通过构造运动偏移映射曲线的方法对运动进行自动平滑处理。实验结果表明,该方法较为完整的很好的保留了原始运动的特征,且重定向得到的运动较为平滑自然。

多用户检测问题的半定规划坐标下降算法

In this paper, a detection strategy based on a semidefinite relaxation of the CDMA maximum-likelihoodmultiuser detection is investigated. Coordinate descent algorithm is used to strengthen the approximation. The simu-lated bit-error-rate performance demonstrates that this approach provides a good approximation to the maximum-like-lihood multiuser detection.

基于块坐标下降算法的优化哈希数据流频率估计

为了不依赖于随机哈希,并且降低计算复杂度,提出了一种基于块坐标下降算法的优化哈希数据流频率估计方法。该方法利用观察到的流媒体数据前缀来接近最佳哈希元素,并压缩目标频率分布。然后引入了一种高效的块坐标下降算法,从而计算最优的哈希方案。提出的方法能够使用动态规划在线性时间内实现精确的求解。最后在合成数据集和搜索查询数据集上对所提出的方法进行了实验评估,结果证明提出的方法能够有效降低计算复杂度,并且保证了较好的估计精度。

利用坐标下降实现并行稀疏子空间聚类

随着数据规模的不断扩大,稀疏子空间聚类问题面临计算上的巨大挑战。现有稀疏子空间聚类算法如交替方向乘子法(ADMM)往往基于串行实现,难以利用多核处理器提高处理大规模聚类问题的效率。针对这个问题,提出一种基于坐标下降的并行稀疏子空间聚类方法。该方法利用稀疏子空间聚类可以建模为求解一系列的样本自稀疏表达子问题的特点,使用坐标下降方法来求解每个子问题,具有参数少、收敛快的优点;同时结合自稀疏表达子问题独立的特点,在处理器的各个核心上同时求解不同样本对应的子问题,因此可以充分利用计算机资源,减少运行时间开销。在模拟数据和运动分割数据集Hopkins-155上与常用的ADMM算法进行对比实验,结果表明该算法在多核处理器上可以显著提升运行速度且聚类精度与ADMM相当。

贝叶斯模型下基于坐标下降法的水声信道估计

在相关水声信道环境下,为了避免常规最小二乘方法信道估计精度不高的缺陷,对相关水声信道进行统计建模,构建贝叶斯数据模型,在此模型下,结合水声信道稀疏性,提出了采用坐标下降法进行多变量最佳化的稀疏信道估计方法。仿真结果表明,该方法不仅获得了相关水声信道的稀疏估计,而且还提升了估计信道的性能。

基于坐标下降邻域选择的高斯图模型结构并行估计

在许多机器学习问题中,往往需要研究高维数据中各个特征之间的统计相关性.稀疏高斯图模型作为解决这一问题的有效方法之一,广泛应用于数据挖掘、生物信息、金融分析等应用问题中.由于模型参数量是数据维度的平方量级,基于高维数据的稀疏高斯图模型的参数估计一直是统计机器学习研究中的挑战性问题之一.提出了一种新颖的基于坐标下降优化的稀疏高斯图模型并行估计算法,其核心思想是根据高斯图模型结构估计等价于每个变量的稀疏近邻选择这一基本结论,采用坐标下降来求解每个近邻选择子问题.通过将样本矩阵进行分布式存储,在MPI(Message-Passing Interface)框架下实现了这些子问题的并行求解.实验结果表明,该算法具有良好的并行运算性能,在保证结构估计精度的同时,能够大幅度提升运算速度.