论文部分内容阅读
通过社交媒体、购物网站、以及多传感器融合获取的数据呈现高阶、高维度以及稀疏张量数据（High-order,High-dimension,and Sparse Tensor,HOHDST）的数据形态,高维度、稀疏数据（High-dimensional,and Sparse,Hi DS）是HOHDST数据在二阶情况下的简称。同时,实际应用产生的HOHDST数据呈现低秩特征,机器学习领域的降维方法成为获取HOHDST数据的低秩因子矩阵主要工具。在降维算法中,矩阵分解可以用来提取二阶数据的低秩因子。同时,张量分解用来提取三阶甚至高阶数据的低秩因子。常见的矩阵分解方法,例如,奇异值分解（Singular Value Decomposition,SVD）以及特征值分解（Eigenvalue Decomposition,ED）处理稠密矩阵,张量分解方法,例如,高阶正交迭代方法（High-order Orthogonal Iteration,HOOI）用来处理稠密张量数据。上述针对稠密矩阵以及稠密张量分解方法的基本代数操作为SVD,然而,在计算机中,SVD通过若干矩阵向量乘法组合实现,因此进一步挖掘加速计算的空间非常少。稠密数据的SVD方法不适合处理Hi DS以及HOHDST数据,在实际问题的优化目标中,需要加入约束项目,在计算过程中涉及到频繁的Top-K SVD操作。因此针对HOHDST数据提取低秩因子的计算过程,需要考虑稀疏数据中分布不均衡的非零元素,进而设计计算效率更高的优化工具。本文的主要工作以及创新点如下:（1）基于图像处理器（Graphic Processing Unit,GPU）细粒度随机梯度稀疏矩阵分解算法。针对大规模协同过滤（Collaborative Filtering,CF）推荐系统实时、精确、可扩展的用户缺失评分预测问题,提出一种基于GPU上CUDA框架的、细粒度并行的稀疏矩阵分解随机梯度（Multi-streaming Stochastic Gradient Descent,MSGD）算法（CUDA-based MSGD,CUMSGD）。基于SGD算法的矩阵分解可以融合诸如数据隐式、显式以及邻域特征,因此SGD成为矩阵分解中常用的优化的算法。然而在CF推荐系统的矩阵分解问题中,用户与物品的相关性导致SGD并行的过载写问题。在GPU中流式处理器（Streaming Processors,SPs;Streaming Multi-processors,SMs）中数据加载和计算过程中,相关性会导致写后读以及读后写的问题。MSGD能够去除CF推荐系统矩阵分解问题中用户与物品的特征低秩因子矩阵的相关性问题,因此MSGD具有在GPU上细粒度并行特性。针对Hi DS数据集导致单GPU内存过载问题,进一步提出多GPU上Hi DS数据分割措施以及多GPU上CUMSGD（MCUMSGD）。（2）基于SGD优化算法的稀疏Tucker张量分解高性能、可扩展、并行计算方法。稀疏Tucker张量分解在计算过程中需要矩阵Khatri-Rao乘积、Knronecker乘积以及矩阵-矩阵乘法,因此稀疏Tucker张量分解面临中间结果矩阵维度大幅度增加的问题。造成中间结果维度大幅度增加的原因在于稀疏Tucker张量分解算法在优化目标中需要考虑HOHDST数据所有的非零元素。为了解决中间结果占用庞大的内存开销以及计算开销的问题,提出基于SGD优化算法的稀疏Tucker张量分解高性能、可扩展、并行计算的方法。该方法将非凸的稀疏Tucker张量分解优化问题转换为交替训练的几个凸优化问题组合。在L-Lipschitz连续以及μ凸约束下,交替的凸优化问题可以用SGD解决,因此可以将原始大规模的中间矩阵分解为小的部分矩阵,同时不影响算法的精度以及收敛性。更进一步,基于SGD优化算法的稀疏Tucker张量分解适用于细粒度的并行,因此可以更进一步加速稀疏Tucker张量分解计算开销。（3）基于GPU的细粒度、线性可扩展的稀疏非负矩阵分解方法。非负矩阵分解在提取低秩因子矩阵过程中施加了非负约束,在图像处理、推荐系统、社交网络应用中,低秩因子矩阵的非负性具有现实意义。因此非负矩阵分解能够有效提取矩阵的低秩因子。从优化角度来看,矩阵分解施加非负约束的优化过程为,对产生的二阶导数（Hessian矩阵）进行了对角近似,因此计算的结果产生的非负项目能够与其他项目相互抵消。然而计算过程中,中间结果矩阵消耗的内存资源十分巨大。同时,稀疏矩阵各行、各列非零元素分布不均衡,这种情况造成利用非负矩阵分解提取Hi DS数据的低秩因子不能共享Hessian矩阵,加剧非负矩阵分解的计算开销。我们提出一种基于单线程的稀疏非负矩阵分解方法,该方法可以利用GPU中并行处理的线程块,以线性复杂度的计算方式同时更新各个因子向量。针对大规模Hi DS矩阵,我们提出多GPU版本的单线程、稀疏非负矩阵分解方法。提出的模型也能够进一步解决基于流形空间图正则的稀疏非负矩阵分解、可扩展计算以及GPU并行难题。（4）提出一种单线程图正则、稀疏非负矩阵分解方法,该方法的计算过程中考虑的是Hi DS数据的非零元素及其位置,因此可以避免巨大的中间矩阵的巨大开销。传统的稀疏非负矩阵分解方法的优化策略为最小化稀疏矩阵与因子矩阵的测度距离,但是只考虑了欧式距离、Kullback-Leibler（KL）测度,并没有考虑数据条目之间的邻域关系。流形学习考虑的是高维流形空间的距离求解问题,利用图正则将全局流形空间上距离问题转换为局部欧式空间距离。然而现有的图正则方法考虑的是图像矩阵数据向量化以后的稠密空间,忽略了高维度、稀疏空间的邻域问题。直接将图正则的稠密非负矩阵分解方法引入,解决高维度的Hi DS数据降维问题,会造成邻域矩阵占用内存空间过于巨大的问题。在此基础上,我们进一步提出基于GPU的细粒度的并行方法,能够解决图正则、稀疏非负矩阵分解并行过载写问题。