论文部分内容阅读
在许多数据处理分析与应用领域,比如高维数据的线性降维、计算机视觉领域中的三维场景重建、运动轨迹的分割,以及个性化商品推荐等,其核心问题都归结为矩阵低秩逼近问题的求解。在过去的几年里,针对具体的应用,出现了很多低秩矩阵分解模型。由于实际应用中数据矩阵元素的大量缺损等因素,矩阵低秩逼近呈现很大的不适定性。因而,如何采取正则化来避免实际问题的不适定性并提供有效的数值算法,这是一个具有挑战性的课题。此外,为了更好地利用数据信息,提高矩阵分解后的应用效果,采用合适的、有针对性的正则化方法,也是增强矩阵分解的实用性一个重要的手段。在协同过滤问题中,数据缺损的矩阵低秩分解模型可以提供很高的预测精度,并有很强的扩展性。这是非常有效的技术,已经受到很多学者的关注且取得了很大的应用性进展。但是该模型的效果以及相应的算法性态严重地依赖低秩分解模型的正则化方式,并存在比较明显的过度拟合现象。通常过度拟合会导致很差的结果。在计算机视觉相关的应用中,数据缺损下的矩阵分解基本模型所产生的最优解还很有可能缺乏物理意义。在现有的文献中,大部分的工作主要集中在针对现有的分解模型设计比较稳定有效的算法。然而关于数据缺损下的矩阵低秩逼近的正则化问题讨论的很少。虽然不少学者提出了图正则化的矩阵分解模型,以保持数据点之间的邻近关系,提高矩阵分解的效果。但现有的图正则化方式导致矩阵分解模型变成一个不容易求解的优化问题,即使不考虑数据缺损的情况下也很难找到最优解。在实际应用中,比如协同过滤问题,矩阵低秩分解涉及的数据矩阵通常来说规模都很大且极其稀疏。在此情形下,如何同时保证正则化技术具有有效性和易用性,是一个困难的问题。为了具有实际应用价值,正则化方法也需要具有可扩展性。本文比较系统地、完整地综述了我们在矩阵低秩分解模型正则化及其算法设计方面的研究进展。有效的正则化方式应与具体应用背景、问题的特点以及数据性质相适应。对于数据缺损问题,我们给出了现有基本模型问题的不适定性理论分析,并考虑了中等程度的数据缺损和高度元素缺损的矩阵低秩逼近情况。对于社会化数据的降维表示问题,我们提出了一个新的图正则化的矩阵分解模型。本文也同时介绍了相应的快速有效的数值算法。在一些实际的大规模数值例子中,这些新的正则化算法均表现出比现有其它方法都好的数值特性。本文的主要贡献如下:(1)我们分析了数据缺损下矩阵分解模型的不适定性(2.2节),指出:在一定条件下,基本模型可能存在多重最优解,且两个最优解之间可以相差任意远。并给出两类存在多个最优解充分条件。对于一般情况,我们为基本模型的∈-最优解做了误差分析,给出一个误差下界。(2)我们提出引导正则项的思想(3.2节),用于解决极度数据缺损的大规模矩阵分解问题,并给出了两个引导正则化模型:引导最小二乘算法(IALS)和口引导随机梯度下降算法(ISGD).其中,引导最小二乘算法改善了用于原先的正则化模型的交替最小二乘算法的收敛性态;能够同时保持对已观测元素的逼近误差和对未知元素的逼近误差的单调下降性。与用于原先的正则化模型的随机梯度下降算法相比,引导随机梯度下降算法能够随着矩阵秩的增大有效地提高逼近的准确性。这两个用于改进模型的算法IALS和ISGD都能够比原来的算法ALS和SGD达到更高的预测精度。(3)我们提出基于元素约束的正则化方法(4.2节),以解决中等程度的数据缺损的矩阵低秩分解问题。这个方法比较适合计算机视觉相关的问题,且恢复精度比较高。元素约束的范围可以根据实际的应用问题事先确定,或者用已经观测到的数据做出一个大致的估计。我们提出了用持续交替最小二乘迭代算法(SALS)求解这个元素约束的矩阵分解模型,它可以在每步迭代中保持低秩分解因子交替优化方法的快速性的同时,提升算法整体的收敛性和有效性。相比基本模型下的交替最小二乘算法和牛顿型算法,SALS算法在最优解的准确性和计算时间上都得到很大改进。(4)提出一个新的图正则化的矩阵低秩分解模型(5.1节),它用于处理包含社会化信息的数据,该模型存在一个全局最优的解析解。依据矩阵列数的大小我们分别提出了直接法和用不精确内迭代的迭代法去求解模型的最优解,并且讨论了迭代法的收敛性。(5)我们结合在协同过滤,场景重建,社会化数据降维表示等领域的背景问题给出了几个模拟例子和大量的实际例子,通过将我们提出的基于正则化模型的几个算法与相应的原来模型下的算法对比和分析,从理论和实际两种角度说明了本文所提出的几类矩阵低秩分解的正则化方法在不同应用中的有效性.