請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/49587
標題: | 高效且穩定收斂的平行非同步隨機對偶座標梯度下降演算法 Parallel Asynchronous Stochastic Dual Coordinate Descent Algorithms for High Efficiency and Stable Convergence |
作者: | Yung-Chen Chen 陳勇辰 |
指導教授: | 劉邦鋒(Pangfeng Liu) |
關鍵字: | 機器學習,平行對偶座標梯度下降算法,非同步算法,線性模型,支撐向量機, machine learning,parallel dual coordinate descent,asynchronous algorithm,linear model,support vector machine, |
出版年 : | 2020 |
學位: | 碩士 |
摘要: | 平行非同步隨機對偶座標梯度下降演算法(PASSCoDe)是一種用於在單台多核心且共用記憶體的機器上訓練線性模型的演算法。 當執行緒的數目小於8時,PASSCoDe在稀疏資料集(非零項所佔的比例很低的資料集)上有著十分良好的加速。 但是因為記憶體的衝突及延遲參數存取的因素,PASSCoDe時常無法收斂到和循序隨機對偶座標梯度下降演算法相同的準確度或是無法收斂。 在此篇論文中,我們提出了兩個演算法 - 適應性混合算法及惰性同步算法以克服平行算法無法收斂的議題。實驗結果指出,我們所提出的兩個演算法在所有資料集中皆可以收斂至和循序隨機對偶座標梯度下降演算法相同的準確度除了一個極小的資料集例外。相比之下PASSCoDe收斂至一個較差的準確度或是不收斂。我們所提出的演算法在收斂的穩定度、執行時間和可擴展性上超越了PASSCoDe的一個改進過後的版本PASSCoDe-Fix. Parallel asynchronous stochastic dual coordinate descent algorithm (PASSCoDe) is an efficient method to train linear models in multi-core shared-memory systems. PASSCoDe enjoys a good speedup when the number of threads is less than 8 on sparse datasets, i.e., the percentage of nonzero elements in the training data is relatively small. However, due to the memory conflict and delayed parameter access problem in parallel execution, it often diverges or does not converge to the best accuracy as a serial dual coordinate descent algorithm does. In this paper, we proposed two algorithms - Adaptive Hybrid algorithm and Lazy-Sync algorithm, to overcome the convergence issues in parallel execution. Experiment results indicate that both algorithms converge to the same high accuracy as a sequential program does on all datasets we tested, except on one extremely small dataset. On the other hand, PASSCoDe sometimes converges to a less accurate value or does not converge at all on some datasets. Our methods also outperform PASSCoDe-Fix, an improved version of PASSCoDe, in stable convergence, execution speed, and scalability. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/49587 |
DOI: | 10.6342/NTU202003062 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊網路與多媒體研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-1208202011160800.pdf 目前未授權公開取用 | 1.33 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。