Fen bu shi ju li xue xi suan fa yu ying yong

Ph.D.Distance learning, also called distance metric learning is an effective similarity learning tool to learn a distance function from examples to enhance the performance of machine learning models in applications of classification, regression, and ranking and so on. Most distance learning algorithms involve a positive semi-definite matrix as critical parameters that scales quadratically with the number of dimensions of input data. This situation brings tremendous computational cost in the learning procedure and makes all proposed algorithms infeasible for extremely high-dimensional data even with the low-rank approximation. In this thesis, we consistently explore the computational complexity of distance learning algorithms from multiple perspectives. Our exploration ranges from the linear to non-linear models, from the shallow to deep models, and from the deterministic to probabilistic models. Specifically, we propose several distributed algorithms to enhance the distance learning algorithms performance in terms of computational speed and learning accuracy.Firstly, we focus on linear distance learning algorithms. To parallel the popular Information-Theoretic Metric Learning (ITML) with tolerated errors, we utilize the property that each positive semi-definite matrix can be decomposed into a combination of rank-one and trace-one matrices and convert the original sequential training procedure into a parallel one. In most cases, the communication demands of the proposed method are also reduced from O(d²) to O(cd), where d is the number of dimensions of the data and c is the number of constraints in linear distance learning and can be smaller than d by appropriate selection. Moreover importantly, we present a rigorous theoretical analysis to upper bound the Bregman divergence between the sequential algorithm and the parallel algorithm, which guarantees the correctness and performance of the proposed algorithm.Secondly, we continue to explore non-linear distance learning algorithms. To capture the local structures in non-linear metric space, we propose a novel parallel Riemannian metric learning algorithm. Then we successfully apply the proposed algorithms on the classical learning-to-rank problem to achieve the state-of- the-art in learning-to-rank community.Thirdly, we explore the distance learning algorithms from the shallow models to deep distance learning models, which is widely used in extreme classification and image retrieval because of its powerful ability to learn the semantic lowdimensional embedding of high-dimensional data. However, the high computational cost of evaluating mini-batch and updating models frequently in existing deep distance learning approaches becomes a barrier to apply such methods to a large-scale real-world context in a distributed environment. In this thesis, we introduce a novel distributed framework to speed up the training process of deep distance learning using multiple machines. Specifically, we design a hybrid communication pattern and implement a decentralized data-parallel framework to reduce the communication time while the quality of the trained deep distance models is preserved.Finally, we explore the distance learning algorithm in the probabilistic domain. In probability theory, Wasserstein distance is used to estimate the similarity between two distributions. However, the existing formulations with approximated Wasserstein loss converge slowly due to substantial computation cost and usually generate unstable results as well. In this thesis, we attempt to solve the computation cost problem by speeding up the computation of Wasserstein distance from a well-designed communication efficient parallel architecture. Then, we also employ a new formulation and the corresponding optimization method to improve the stability with a more accurate Wasserstein distance estimation. Compared to conventional parallel architecture for deep neural networks, our proposed framework enjoys a higher scalability performance.距离學習，又稱距離度量學習，是一種有效的相似性學習工具。它從數據中學習更有效的距離函數，用於提升分類、回歸、排序等機器學習模型的性能。傳統的距離學習方法會涉及計算複雜度極高的半正定矩陣計算，這無疑給機器學習過程帶來巨大的計算負擔，且難以應用於高維數據中。在本論文中，我們從多個層面探索距離學習的計算複雜度問題，包拓線性模型、非線性模型、深度學習模型、概率距離模型。基於複雜度分析，我們提出一系列分布式方法用於提升距離學習模型的計算速度與精度。第一部分，關於線性距離學習算法，我們利用半正定矩陣可以被分解單秩單跡矩陣的組合這一特性，將流行的信息論度量學習算法由串行算法改造為並行算法，並同時降低此並行算法的通信複雜度。最後我們通過嚴密的理論分析，給出了原始的串行算法與提出的並行算法的誤差上限。第二部分，我們繼續探索非線性距離學習。通過挖掘非線性距離度量空間中的局部結構，我們提出了一種有效的並行黎曼度量學習方法，並成功應用於排序問題。第三部分，我們探索深度度量學習模型。由於此模型可以從高維數據中學習具有語義含義的低維表示，因而它泛應用於圖像分類與圖像檢索任務。然而傳統深度度量學習的高計算複雜度問題使得此類方法無法以分布式的方式處理真實世界中大規模數據問題。在本論文中，我們介紹了一種新穎的分布式計算方法，可以有效解決此難題。與此同時，我們通過設計一種混合的去中心化的通信機制，在保證學習精度的情況下可以顯著降低通信時間。最後，我們試圖探索將分布式計算方法應用於概率分布距離的計算當中。在概率論中，Wasserstein距離是有效的估計概率分布距離的方法。然而，已有的方法大多基於近似計算，不僅收斂速度較慢，還會產生不穩定的計算結果。在此論文中，我們提出一種新型的Wasserstein距離的計算形式和與此對應的優化方法，並設計了一種高效的分布式計算策略，可以顯著提升計算精度與計算穩定性。Su, Yuxin.Thesis Ph.D. Chinese University of Hong Kong 2019.Includes bibliographical references (leaves 133-152).Abstracts also in Chinese.Title from PDF title page (viewed on 26, March 2021).Su, Yuxin