论文部分内容阅读
近年来，数据量的激增迫切需要对可扩展机器学习关键技术的研究，而当前丰富的计算资源又为可扩展机器学习提供了机遇。为实现可扩展机器学习，本文从高效算法设计和并行与分布方法两条技术途径入手，对机器学习如何有效应对大数据挑战展开深入研究。基于算法与系统的协同设计，在保证精度的前提下，有效提高了机器学习的速度，增强了机器学习在计算和内存方面的扩展性，取得了以下几个方面的研究成果：
1.提出了两种数据和模型并行极限学习机，即LDMP-ELM和GDMP-ELM。LDMP-ELM运行更快且更易实现，而GDMP-ELM能够支持更大模型，二者优势互补，统称为DMP-ELMs。DMP-ELMs因解决了现有方法中存在的计算和内存瓶颈而具有更好的可扩展性，能够处理大规模数据集、支持大量隐层节点。这得益于DMP-ELMs同时使用数据并行和模型并行方法来提高ELM的并行性，主要是利用矩阵分块与分布矩阵计算实现，并充分利用了ELM随机生成隐层参数的特性。DMP-ELMs完全基于超级计算机的软件栈，如MPI等进行开发。在实验中将算法成功扩展到128个节点，能有效处理数据和模型大到无法载入单机内存的情况。尽所知，这是第一次成功地在有着810万个样本和784维特征的mnist8m数据集上训练出一个具有5万个隐层神经元的大ELM模型。目前多数并行与分布机器学习研究集中于商用计算集群，基于超算系统的研究还较少，该工作是完全基于超算软硬件系统进行并行与分布机器学习的一项探索研究。
2.提出了一种基于方差缩减的分布异步随机梯度下降方法，即DisSVRG。DisSVRG将方差缩减技术和异步通信协议有机结合，采用方差缩减梯度更新模型参数，并使用异步通信协议在集群节点间共享新学到的参数。另外，提出带有加速因子的自适应学习率，加速DisSVRG。同时，提出一种自适应采样策略，大大减少了迭代过程中由straggler问题引起的等待。另一方面，在发现超算软件栈进行并行与分布机器学习研究抽象层次过低的问题后，使用兴起于商用计算集群的参数服务器计算框架，将其迁移到超算生态圈，而参数服务器底层又使用MPI通信，这样两种计算框架得以融合。实质上参数服务器此时可看作是在MPI基础上又进行了一层封装，提供适于机器学习的抽象层次更高且更简洁的编程模型。而通过对参数服务器的分析、使用、再开发，极大简化了DisSVRG的实现。
3.提出了两种分布可扩展的k-means聚类方法，即Scalable Lloyd’s K-Means和Scalable Mini-Batch K-Means。两者都能基于数据并行技术和参数服务器系统扩展超越单节点的计算和内存限制。前者能够找到更高质量的解，而后者能够更快收敛到一个合适的解。它们都具有良好的可扩展性并完全进行内存计算。此外，为Scalable Mini-Batch K-Means提出了一个新的聚合方法使得分布聚类能够收敛。大量实验表明提出的算法具有良好的收敛性能并能达到几乎线性的加速比，例如使用分布在4个计算节点上的16个CPU核进行计算时，可以达到14倍左右的加速比。在此项研究中，将前述研究的并行与分布随机梯度下降优化算法用于求解k-means聚类问题，仍然在超算系统中基于参数服务器实现，进一步证明了这种软件栈融合的通用性。
4.提出了两种基于方差缩减的k-means聚类方法，即VRKM和VRKM++。具体来说，首先提出了一种位置校正机制来校正在基于方差缩减优化k-means问题时的聚类中心漂移问题，并使用常数学习率来更新k-means中的参数。在此基础上，提出了方差缩减k-means，即VRKM。进一步，通过理论推导优化VRKM，降低其计算成本，进而提出一种新的方差缩减k-means，即VRKM++。与VRKM相比，VRKM++可以避免计算批量梯度，减少计算量，因而效率更高。两种方法都在超算系统的单节点上串行实现。大量实验表明，提出的VRKM和VRKM++方法性能优于当前水平，并分别获得大约2倍和4倍的大规模聚类加速。在本项工作中，从高效算法设计角度入手，在不占用更多计算资源的情况下，增加k-means聚类的可扩展性。
5.提出了一种基于局部敏感哈希的近似k-means方法，即LSH k-means。其在样本点上建立局部敏感哈希（Locality-Sensitive Hashing，LSH）索引，而不是在聚类中心上建立索引。具体而言，LSH k-means首先建立LSH哈希表，使得相互靠近的样本点有更大可能被哈希到相同的桶中。然后将聚类中心作为查询，从LSH表中查询其潜在近邻样本点。之后LSH k-means引入一个指示矩阵，其能将聚类中心的潜在近邻样本点转换为样本点的潜在近邻聚类中心。最后，各样本点可以在指示矩阵的引导下不用与所有聚类中心计算距离就能找到其最近聚类中心。此外，提出了一个自动调参策略，在构建于指示矩阵的两个指标的帮助下自动地确定LSH k-means的超参数。在三个数据集上进行的大量实验表明所提算法具有良好的收敛性能并实现了显著的加速。该项工作在工作站上串行实现，继续从高效算法设计角度入手，研究低资源占用高可扩展的方法。
1.提出了两种数据和模型并行极限学习机，即LDMP-ELM和GDMP-ELM。LDMP-ELM运行更快且更易实现，而GDMP-ELM能够支持更大模型，二者优势互补，统称为DMP-ELMs。DMP-ELMs因解决了现有方法中存在的计算和内存瓶颈而具有更好的可扩展性，能够处理大规模数据集、支持大量隐层节点。这得益于DMP-ELMs同时使用数据并行和模型并行方法来提高ELM的并行性，主要是利用矩阵分块与分布矩阵计算实现，并充分利用了ELM随机生成隐层参数的特性。DMP-ELMs完全基于超级计算机的软件栈，如MPI等进行开发。在实验中将算法成功扩展到128个节点，能有效处理数据和模型大到无法载入单机内存的情况。尽所知，这是第一次成功地在有着810万个样本和784维特征的mnist8m数据集上训练出一个具有5万个隐层神经元的大ELM模型。目前多数并行与分布机器学习研究集中于商用计算集群，基于超算系统的研究还较少，该工作是完全基于超算软硬件系统进行并行与分布机器学习的一项探索研究。
2.提出了一种基于方差缩减的分布异步随机梯度下降方法，即DisSVRG。DisSVRG将方差缩减技术和异步通信协议有机结合，采用方差缩减梯度更新模型参数，并使用异步通信协议在集群节点间共享新学到的参数。另外，提出带有加速因子的自适应学习率，加速DisSVRG。同时，提出一种自适应采样策略，大大减少了迭代过程中由straggler问题引起的等待。另一方面，在发现超算软件栈进行并行与分布机器学习研究抽象层次过低的问题后，使用兴起于商用计算集群的参数服务器计算框架，将其迁移到超算生态圈，而参数服务器底层又使用MPI通信，这样两种计算框架得以融合。实质上参数服务器此时可看作是在MPI基础上又进行了一层封装，提供适于机器学习的抽象层次更高且更简洁的编程模型。而通过对参数服务器的分析、使用、再开发，极大简化了DisSVRG的实现。
3.提出了两种分布可扩展的k-means聚类方法，即Scalable Lloyd’s K-Means和Scalable Mini-Batch K-Means。两者都能基于数据并行技术和参数服务器系统扩展超越单节点的计算和内存限制。前者能够找到更高质量的解，而后者能够更快收敛到一个合适的解。它们都具有良好的可扩展性并完全进行内存计算。此外，为Scalable Mini-Batch K-Means提出了一个新的聚合方法使得分布聚类能够收敛。大量实验表明提出的算法具有良好的收敛性能并能达到几乎线性的加速比，例如使用分布在4个计算节点上的16个CPU核进行计算时，可以达到14倍左右的加速比。在此项研究中，将前述研究的并行与分布随机梯度下降优化算法用于求解k-means聚类问题，仍然在超算系统中基于参数服务器实现，进一步证明了这种软件栈融合的通用性。
4.提出了两种基于方差缩减的k-means聚类方法，即VRKM和VRKM++。具体来说，首先提出了一种位置校正机制来校正在基于方差缩减优化k-means问题时的聚类中心漂移问题，并使用常数学习率来更新k-means中的参数。在此基础上，提出了方差缩减k-means，即VRKM。进一步，通过理论推导优化VRKM，降低其计算成本，进而提出一种新的方差缩减k-means，即VRKM++。与VRKM相比，VRKM++可以避免计算批量梯度，减少计算量，因而效率更高。两种方法都在超算系统的单节点上串行实现。大量实验表明，提出的VRKM和VRKM++方法性能优于当前水平，并分别获得大约2倍和4倍的大规模聚类加速。在本项工作中，从高效算法设计角度入手，在不占用更多计算资源的情况下，增加k-means聚类的可扩展性。
5.提出了一种基于局部敏感哈希的近似k-means方法，即LSH k-means。其在样本点上建立局部敏感哈希（Locality-Sensitive Hashing，LSH）索引，而不是在聚类中心上建立索引。具体而言，LSH k-means首先建立LSH哈希表，使得相互靠近的样本点有更大可能被哈希到相同的桶中。然后将聚类中心作为查询，从LSH表中查询其潜在近邻样本点。之后LSH k-means引入一个指示矩阵，其能将聚类中心的潜在近邻样本点转换为样本点的潜在近邻聚类中心。最后，各样本点可以在指示矩阵的引导下不用与所有聚类中心计算距离就能找到其最近聚类中心。此外，提出了一个自动调参策略，在构建于指示矩阵的两个指标的帮助下自动地确定LSH k-means的超参数。在三个数据集上进行的大量实验表明所提算法具有良好的收敛性能并实现了显著的加速。该项工作在工作站上串行实现，继续从高效算法设计角度入手，研究低资源占用高可扩展的方法。