论文部分内容阅读
现实中,很多物理量都具有“非负”特性,例如:灰度图像像素值、文章中单词出现的频数、用户体验的得分等。在分析处理这类数据时,为了增强结果的可解释性,往往需要其满足“非负性”约束。非负矩阵分解、非负张量分解和非负二次规划是三种常用的非负数据处理工具。非负矩阵分解是满足被分解矩阵和分解后的因子矩阵中所有元素均为非负数的矩阵分解方法。由于非负约束的存在,非负矩阵分解只允许加性的线性组合,这使得其分解结果是基于部分表示的,符合人们“由局部构成整体”的认知方式,具有较强的可解释性。非负矩阵分解已成为处理高维、大规模非负数据的一种重要方法,被广泛应用于模式识别、机器学习和信号分离等诸多领域中。作为矩阵的高阶推广,张量结构被越来越多的研究领域用于数据表示。非负张量分解是非负矩阵分解在高阶张量上的推广,其继承了非负矩阵分解的上述特征,是分析非负张量数据的一种有效方法。非负二次规划是一类经典的凸优化问题。许多非负数据处理问题都可以表示成非负二次规划问题或者和非负二次规划问题相关,例如:图像去噪、非负矩阵分解、贝叶斯网络密度估计等。目前,非负矩阵分解、非负张量分解和非负二次规划在算法以及应用方面的研究已经取得了很多成果,但仍然存在一些问题有待解决,例如:大部分非负矩阵分解算法都采用交替更新的优化方式,但这种方式对算法初始值较为敏感,容易导致算法收敛速度较慢;对称非负张量分解是一种重要的多维概率聚类方法,但目前相关的算法很少且普遍收敛速度较慢;许多非负二次规划算法在保证实现简便性时难以兼顾算法的收敛速度。因此,关于非负矩阵分解、非负张量分解和非负二次规划快速算法的研究具有重要的意义。围绕该问题,本文进行了以下几个方面的研究工作:(1)提出了两个快速的非负矩阵分解算法。本文首先提出了一个基于Procrustes旋转的非负矩阵分解算法,该算法可以同时更新所有的因子矩阵。实验结果表明当数据的噪声比较小或者非负矩阵分解的秩比较低的时候,该算法不仅收敛速度快而且重构误差小。接着,本文进一步提出了一个混合的非负矩阵分解算法,该算法结合了上述算法与Zhou等人的非负矩阵分解算法,实现两者间的优势互补。实验结果表明混合的非负矩阵分解算法不仅收敛速度快而且能很好地对抗噪声的影响。(2)提出了一个基于外推法的快速对称非负矩阵分解算法。在充分研究He等人的乘性更新算法之后,本文采用外推法改善其收敛速度,并利用重启技巧保证目标函数在迭代过程中单调下降。实验结果显示改善后的算法比原来的算法在速度方面提升了 4倍以上。(3)将上述混合的非负矩阵分解算法推广到非负Tucker分解(非负张量分解中的一类),得到一个新的非负Tucker分解算法。本文在多个真实数据集上进行实验,实验结果表明相比于使用相同求解框架的其他算法,新的算法运行时间更少。(4)针对三阶的对称非负张量分解问题提出了两个乘性更新算法。本文首先利用辅助函数得到三阶对称非负张量分解问题的一个乘性更新算法,并证明当给定的张量满足一定条件时,该算法收敛到对称非负张量分解问题的一个稳定点。在此基础上,本文提出了一个混合的乘性更新算法,该算法结合了两个不同的乘性更新规则。实验结果显示相比于最近的对称非负张量分解算法,新提出的两个乘性更新算法在收敛速度方面都有所提升,特别是混合的乘性更新算法。(5)提出了一个新的非负二次规划算法,该算法不仅实现简单而且收敛快速。本文首先利用辅助函数和牛顿法得到一个非负二次规划算法,然后使用外推法改善其收敛速度。本文将新提出的算法应用于支持向量机模型训练中。实验结果显示新算法相比于 M3(Multiplicative Margin Maximization)算法和 SMO(Sequential Minimal Optimization)算法收敛速度更快。