基于低秩矩阵估计的机器学习算法分析

发布时间：2017-05-18 07:01

  本文关键词：基于低秩矩阵估计的机器学习算法分析，由笔耕文化传播整理发布。

【摘要】：在例如推荐系统,图像／视频分析等许多机器学习问题中,数据往往是以矩阵的形式进行表达。在这些问题中,矩阵的低秩性质在学习原始数据隐藏结构的过程中有着非常重要的作用。因此,近来针对低秩矩阵算法成为机器学习和相关领域的一个研究热点。低秩近似算法大致上可以被分为两类：(1)恢复数据(很可能是不完整的)中的低秩结构；(2)利用低秩信息提升其他机器学习模型的学习效果。虽然在这两类算法中目前已经有很多相关工作,但是不管从准确性还是效率来看,已有的算法都并不能达到让人满意的效果。在本论文中,我们从算法理论分析到具体的应用对低秩近似算法进行了一个系统的研究,研究内容包括矩阵补全问题,主动学习和基于低秩矩阵正则化的大规模图像分类问题。总的来说,本文的创新点如下：1.为了加速针对大规模矩阵补全问题的奇异值截断式算法(Singular Value Thresholding, SVT),在本论文中我们提出了一种奇异值截断式加速算法(Accelerated Singular Value Thresholding, ASVT)将传统的SVT算法的收敛速度从O(1/N)提升至O(1/N2),其中N是优化过程中的迭代次数。具体而言,通过理论分析我们证明了原始优化问题的最优解可以通过其对偶问题的最优解直接得到。我们在人工数据集,真实距离矩阵数据集和电影推荐数据集上进行一系列的验证,实验结果证明了我们所提出算法的效率和有效性。2.为了更好地解决基于截断式核范数的矩阵补全问题,本论文首先对原始截断式核范数优化问题进行重构。原始优化问题中的多个限制条件会减缓基于乘子的交替方向理论(Alternating Direction Method of Multipliers, ADMM)的收敛速度,并会对解的准确性造成一定的影响。随后,我们对重构后的问题提出了一个带自适应惩罚项的ADMM算法(Alternating Direction Method of Multipliers with Adaptive Penalty, ADMMAP)。在每一次迭代中,我们根据一个迭代机制调整目标函数中的惩罚项大小,从而加速算法收敛速度。我们在人工数据集和真实数据集的实验分析证明了,同已有的矩阵补全算法相比,我们提出的算法具有更好的效果。3.为了更好地在数据集中选择最具代表性的样本(我们称之为锚点),本论文提出在锚点的选择过程中充分考虑数据的局部信息,并设计了一种基于近邻重建的主动学习方法(Active Learning via Neighborhood Reconstruction, ALNR)。传统基于重建的主动学习理论利用所有的锚点对目标数据进行重建。然而,离目标数据越近的锚点对数据重建的作用越大,而离目标数据较远的点对数据重建的作用较小甚至有负面的作用。因此,在我们提出的ALNR算法中,我们仅仅只使用目标数据的近邻锚点对目标数据进行重建。为更好地求解最终的优化问题,我们提出了一种高效的两步迭代机制。我们在人工和真实数据集上的实验效果证明了我们算法比已有的主动学习算法更加准确高效。4.为了更好地在图像分类问题中利用矩阵的低秩信息,本论文考虑当分类器系数空间存在低维结构时的图像分类问题。当前已有的算法往往利用矩阵的核范数来刻画分类器系数矩阵的低秩结构。然而,考虑核范数并不能对矩阵秩算子进行很好地近似,我们提出了一种基于截断式核范数的大规模图像分类算法。为了求解最终非凸非光滑的优化问题,我们设计了一个高效的算法将原始问题首先分解为多个非光滑凸子问题,并进行迭代优化求解。在每一次迭代中,我们将每一个子问题转化为一个无线维空间下的l1范数正则化问题,并使用一种简单高效的加速坐标梯度下降算法进行求解。我们在若干大规模数据图像数据集上进行了测试,实验结果显示同已有的大规模图像分类算法相比,我们提出的算法有效地提升了大规模图像分类系统的准确性。
【关键词】：低秩结构 矩阵补全 核范数 截断式核范数 加速
【学位授予单位】：浙江大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP181
【目录】：

• 摘要5-7
• Abstract7-16
• 1 绪论16-28
• 1.1 研究背景和意义16-20
• 1.1.1 理论研究价值17-18
• 1.1.2 应用价值18-20
• 1.2 相关研究现状20-25
• 1.2.1 基本数学工具的定义20-21
• 1.2.2 基于矩阵分解的缺失信息恢复算法21-22
• 1.2.3 基于最小化矩阵秩问题的矩阵补全算法22-24
• 1.2.4 基于核范数的矩阵补全算法24-25
• 1.3 本文的研究内容和主要贡献25-27
• 1.4 论文的组织结构27-28
• 2 针对矩阵补全的奇异值截断加速算法28-44
• 2.1 研究动机28-29
• 2.2 研究的相关工作及背景知识29-30
• 2.2.1 数学工具29-30
• 2.2.2 基于奇异值截断的矩阵补全算法30
• 2.3 目标函数30-33
• 2.4 优化理论33-37
• 2.5 实验37-43
• 2.5.1 人造数据上的实验结果37-39
• 2.5.2 距离矩阵数据集上的实验结果39-41
• 2.5.3 MovieLens数据集上的实验结果41-43
• 2.6 实验结论43-44
• 3 基于截断式核范数的快速准确矩阵补全理论44-68
• 3.1 研究动机44-46
• 3.2 研究背景46-50
• 3.2.1 截断式核范数正则项46-47
• 3.2.2 基于ADMM的截断式核范数优化算法47-49
• 3.2.3 基于APGL的截断式核范数优化算法49-50
• 3.3 目标函数50-52
• 3.4 优化理论52-56
• 3.4.1 自适应地调整惩罚项系数54-56
• 3.5 实验56-66
• 3.5.1 人造数据集上的实验结果57-58
• 3.5.2 真实图像上的实验结果58-62
• 3.5.3 收敛性分析62-66
• 3.6 结论66-68
• 4 基于局部重建的主动学习方法68-84
• 4.1 研究动机68-69
• 4.2 研究背景69-72
• 4.3 目标函数72-73
• 4.4 优化理论73-78
• 4.4.1 基于块的坐标下降理论的优化机制73-74
• 4.4.2 惩罚项中的几何描述74-76
• 4.4.3 利用邻近梯度理论求解优化问题(4.11)76-78
• 4.5 实验结果78-81
• 4.5.1 人造数据集上的实验结果78-80
• 4.5.2 人脸数据集上的实验结果80
• 4.5.3 参数敏感性分析80-81
• 4.6 结论81-84
• 5 基于截断式核范数正则化的大规模图像分类方法84-98
• 5.1 研究动机84-86
• 5.2 研究背景86-88
• 5.3 目标函数88-89
• 5.4 优化算法89-92
• 5.5 实验92-97
• 5.5.1 数据预处理93
• 5.5.2 对比算法93-95
• 5.5.3 实验结果比较95-96
• 5.5.4 参数敏感性分析96-97
• 5.6 结论97-98
• 6 总结与展望98-102
• 6.1 本文工作总结98-99
• 6.2 工作展望99-102
• 致谢102-104
• 参考文献104-114
• 攻读博士学位期间主要的研究成果114-115

【相似文献】

中国期刊全文数据库 前10条

1 朱峗,吴炜;图像分类中变形决策树的应用[J];计算机工程与应用;2004年21期

2 陈戏墨,徐红兵,李志铭,谢铉洋,李曦,李扬彬;数据挖掘在医学图像分类中的应用[J];现代计算机(专业版);2005年01期

3 冀翠萍;孟祥增;;基于内容的图像分类体系[J];电脑知识与技术(学术交流);2007年07期

4 杨杰;陈晓云;;图像分类方法比较研究[J];微计算机应用;2007年06期

5 杨文潮;姜志坚;;图像分类技术研究[J];福建电脑;2008年08期

6 葛寒娟;邱桃荣;王剑;卢强;李北;刘韬;聂斌;;一种基于相容信息粒原理的图像分类方法[J];广西师范大学学报(自然科学版);2008年03期

7 王军;王员云;;粒计算及其在图像分类中的应用研究[J];计算机工程与科学;2009年03期

8 吴军;王士同;;基于正负模糊规则的相结合的图像分类[J];计算机应用;2011年01期

9 吴军;王士同;赵鑫;;正负模糊规则系统、极限学习机与图像分类[J];中国图象图形学报;2011年08期

10 郝永宽;王威;聂维同;王德强;;图像分类与聚类分析[J];数字技术与应用;2011年12期

中国重要会议论文全文数据库 前10条

1 郑海红;曾平;;一种基于图像分类的逆半调算法[A];’2004计算机应用技术交流会议论文集[C];2004年

2 文振q;欧阳杰;朱为总;;基于语义特征与支持向量机的图像分类[A];中国电子学会第十六届信息论学术年会论文集[C];2009年

3 王海峰;管亮;;基于颜色特征的图像分类技术在油品分析中的应用[A];中国仪器仪表学会第六届青年学术会议论文集[C];2004年

4 陈思坤;吴洪;;基于图分块并利用空间金字塔的医学图像分类[A];第六届和谐人机环境联合学术会议（HHME2010)、第19届全国多媒体学术会议（NCMT2010）、第6届全国人机交互学术会议（CHCI2010）、第5届全国普适计算学术会议（PCC2010）论文集[C];2010年

5 张淑雅;赵晓宇;赵一鸣;李均利;;基于SVM的图像分类[A];第十三届全国图象图形学学术会议论文集[C];2006年

6 李博;韩萍;;基于压缩感知和SVM的极化SAR图像分类[A];第二十七届中国（天津）2013IT、网络、信息技术、电子、仪器仪表创新学术会议论文集[C];2013年

7 朱松豪;胡娟娟;孙伟;;基于非欧空间高阶统计的图像分类方法[A];第25届中国控制与决策会议论文集[C];2013年

8 潘海为;李建中;张炜;;基于像素聚类的脑部医学图像分类[A];第二十届全国数据库学术会议论文集（研究报告篇）[C];2003年

9 吴霜;张一飞;修非;王大玲;鲍玉斌;于戈;;基于兴趣点特征提取的医学图像分类[A];第二十四届中国数据库学术会议论文集（研究报告篇）[C];2007年

10 武进;尹恺;王长明;张家才;;SVDM在蔬菜病害图像分类中的应用[A];图像图形技术与应用进展——第三届图像图形技术与应用学术会议论文集[C];2008年

中国博士学位论文全文数据库 前10条

1 胡尧;基于低秩矩阵估计的机器学习算法分析[D];浙江大学;2015年

2 赵鑫;图像分类中的判别性增强研究[D];中国科学技术大学;2013年

3 杨冰;基于艺术风格的绘画图像分类研究[D];浙江大学;2013年

4 丁建睿;基于多示例学习的浅表器官超声图像分类方法研究[D];哈尔滨工业大学;2012年

5 贾世杰;基于内容的商品图像分类方法研究[D];大连理工大学;2013年

6 李晓旭;基于概率主题模型的图像分类和标注的研究[D];北京邮电大学;2012年

7 王海江;极化SAR图像分类方法研究[D];电子科技大学;2008年

8 韩东峰;图像分类识别中特征及模型的若干问题研究[D];吉林大学;2008年

9 白有茂;基于张量流形学习的图像分类技术研究[D];中国矿业大学（北京）;2013年

10 龙显忠;矩阵分解方法在图像分类中的应用研究[D];上海交通大学;2014年

中国硕士学位论文全文数据库 前10条

1 李函怡;融合主动学习的半监督技术在图像分类中的应用研究[D];西南大学;2015年

2 王亚凤;基于多特征的主动学习方法在图像分类中的应用研究[D];河北工程大学;2015年

3 陈荣安;基于改进的Bag-of-Features模型的图像分类研究[D];兰州大学;2015年

4 钟畏丹;基于HSV和纹理特征的图像分类[D];华中师范大学;2015年

5 焦阳;基于主动学习的多标签图像分类方法研究[D];苏州大学;2015年

6 王腾川;基于主动学习的SAR图像分类方法研究[D];上海交通大学;2015年

7 NGUYEN QUANG KHANH;基于极化SAR目标信息提取与SVM分类[D];哈尔滨工业大学;2015年

8 王朔琛;基于半监督支持向量机的图像分类方法研究[D];陕西师范大学;2015年

9 田云;基于二次分割的多特征图像分类方法研究[D];山西大学;2011年

10 席晓聪;图像分类方法研究[D];山东大学;2013年

  本文关键词：基于低秩矩阵估计的机器学习算法分析，由笔耕文化传播整理发布。

，

本文编号：375345