论文部分内容阅读
矩阵分解算法因其模型简单效果显著在很多机器学习任务中备受欢迎，尤其在社区发现、个性化推荐以及文本分析等任务中更是有着极其广泛的应用，然而，矩阵分解算法在处理大规模训练数据时需要面对两个突出的技术挑战。一方面，数据规模越大，所含的信息也就越复杂，与普通的机器学习算法不同，大规模矩阵分解需要面对模型参数随数据规模增大而增多的困扰;另一方面，将模型的参数分布存储在不同计算节点上势必会给分布式计算带来很大的通信负担，所以在提高模型的可扩展性的基础上大规模矩阵分解还要解决因参数分布式存储而带来的计算效率问题。因此，在保证大规模矩阵分解的可扩展性的基础上提高矩阵分解效率在矩阵分解的实际应用场景中具有重要意义。 针对大多数分布式矩阵分解算法可扩展性不足以及效率不高的问题，本文通过模型分布式实现以及在线图分割算法对其进行深入研究。论文的基本思路是采用模型分布方式来实现大规模矩阵分解，并围绕基于模型分布的大规模矩阵分解算法的效率问题进行深入的分析。为了减少该算法的通信开销，论文提出了一种新的在线图分割算法BiEdgePartition2D。最后，本文将算法应用于个性化推荐以及语义分析两个任务中。本文的主要贡献如下: (1)首先，传统的机器学习模型不会随着训练样本规模的增大而增大，但是矩阵分解模型需要解决伴随矩阵规模增大模型越来越大的问题，以及由此带来的参数存储能力的问题，所以传统的分布式矩阵分解面临着可扩展性不足的缺憾。本文基于spark平台的Pregel计算框架，将矩阵抽象成一个二部图，将模型参数分布存储在不同的计算节点上，提高模型的可扩展性，并探究得出基于模型分布的大规模矩阵分解相较于传统基于数据分布的矩阵分解在计算效率上的差异主要是机器间的通信开销造成的; (2)其次，在很多大规模矩阵分解的应用场景中，比如单词文档矩阵以及用户商品矩阵等，数据普遍具有分布不均衡以及呈度幂率分布等特点，传统的分布式矩阵分解算法实现中很少将这些特点加以利用以减少机器间的通信开销，所以算法难以获得性能上的进一步提升。本文针对传统算法无法利用二部图源、目顶点往往分布不均匀以及节点度呈skew-distributed的特点提出一种BiEdgePartition2D的在线图分割算法，在保证子图的平衡的基础上减少复制因子来降低大规模矩阵分解的通信开销; (3)最后，本文将BiEdgePartition2D算法应用于基于模型分布的大规模矩阵分解算法中，并成功将其应用于两个典型的应用场景个性化推荐问题以及语义分析问题中，实验结果表明基于模型分布的大规模矩阵分解在效率上相较之前的算法有了明显的提升，同时更加验证了BiEdgePartition2D算法在减少通信开销方面的有效性。