臺灣博碩士論文加值系統

在推薦系統上，矩陣分解是一個非常有效的技術。
對於矩陣分解問題，隨機梯度下降法是一個高效的演算法。
然而，這個演算法並不容易被平行。
這篇論文，在共享記憶體系統中，我們開發一個新的平行演算法叫做FPSG。
藉由解決負載不平衡問題及快取失效問題，我們開發的平行演算法比現有的平行演算法更加有效。

Matrix factorization is known to be an effective method for recommender systems that are given only the ratings from users to items.
Currently, stochastic gradient (SG) method is one of the most popular algorithms for matrix factorization.
However, as a sequential approach, SG is difficult to be parallelized for handling web-scale problems.
In this thesis, we develop a fast parallel SG method, FPSG, for shared memory systems.
By dramatically reducing the cache-miss rate and carefully addressing the load balance of threads, FPSG is more efficient than state-of-the-art parallel algorithms for matrix factorization.

TABLE OF CONTENTS
口試委員會審定書................................ i
中文摘要...................................... ii
ABSTRACT .................................... iii
LISTOFFIGURES................................ vi
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
CHAPTER
I.Introduction ............................... 1
II. Existing Parallelized Stochastic Gradient Descent Algorithms andCoordinateDescentMethods.................. 6
2.1 HogWild .............................. 6
2.2 DSGD................................ 8
2.3 CCD++ .............................. 9
III. Problems in Parallel SG Methods for Matrix Factorization . . 13
3.1 LockingProblem.......................... 13
3.2 MemoryDiscontinuity....................... 14
IV.OurApproaches ............................. 16
4.1 Lock-FreeScheduling ....................... 16
4.2 PartialRandomMethod...................... 18
4.3 OverviewofFPSG......................... 21
4.4 ImplementationIssues....................... 22
V.Experiments ............................... 25
5.1 Settings............................... 25
5.2 Comparison of Methods on Training Time versus RMSE . . . . 27
5.2.1 The effectiveness of addressing the locking problem . 27
5.2.2 The effectiveness of having better memory locality . . 28
5.2.3 Comparison with the state-of-the-art methods . . . . 28
5.2.4 Comparison with CCD++ for Non-negative Matrix
Factorization....................... 29
5.3 SpeedupofFPSG ......................... 31
VI.Discussion................................. 33
6.1 DataLocalityandtheUpdateOrder............... 33
6.2 NumberofBlocks ......................... 34
VII.ConclusionsandFutureWorks.................... 38
BIBLIOGRAPHY................................. 40
APPENDICES................................... 42

R. M. Bell and Y. Koren. Lessons from the Netflix prize challenge. ACM SIGKDD Explorations Newsletter, 9(2):75–79, 2007.
K.-W. Chang, C.-J. Hsieh, and C.-J. Lin. Coordinate descent method for large- scale L2-loss linear SVM. Journal of Machine Learning Research, 9:1369–1398, 2008. URL http://www.csie.ntu.edu.tw/~cjlin/papers/cdl2.pdf.
G. Dror, N. Koenigstein, Y. Koren, and M. Weimer. The Yahoo! music dataset and KDD-Cup 11. In JMLR Workshop and Conference Proceedings: Proceedings of KDD Cup 2011, volume 18, pages 3–18, 2012.
R. Gemulla, E. Nijkamp, P. J. Haas, and Y. Sismanis. Large-scale matrix factor- ization with distributed stochastic gradient descent. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 69–77, 2011.
K. B. Hall, S. Gilpin, and G. Mann. MapReduce/Bigtable for distributed op- timization. In Neural Information Processing Systems Workshop on Leaning on Cores, Clusters, and Clouds, 2010.
C.-J. Hsieh and I. S. Dhillon. Fast coordinate descent methods with variable se- lection for non-negative matrix factorization. In Proceedings of the Seventeenth ACM SIGKDD International Conference on Knowledge Discovery and Data Min- ing, 2011.
J. Kiefer and J. Wolfowitz. Stochastic estimation of the maximum of a regression function. The Annals of Mathematical Statistics, 23(3):462–466, 1952.
Y. Koren, R. M. Bell, and C. Volinsky. Matrix factorization techniques for rec- ommender systems. Computer, 42(8):30–37, 2009.
A. Kyrola, G. Blelloch, and C. Guestrin. Graphchi: Large-scale graph computa- tion on just a pc. In Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI ’12), Hollywood, October 2012.
G. Mann, R. McDonald, M. Mohri, N. Silberman, and D. Walker. Efficient large- scale distributed training of conditional maximum entropy models. In Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems 22, pages 1231–1239. 2009.
40
&;#65532;R. McDonald, K. Hall, and G. Mann. Distributed training strategies for the struc- tured perceptron. In Proceedings of the 48th Annual Meeting of the Association of Computational Linguistics (ACL), pages 456–464, 2010.
F. Niu, B. Recht, C. R &;#769;e, and S. J. Wright. HOGWILD!: A lock-free ap- proach to parallelizing stochastic gradient descent. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Weinberger, editors, Advances in Neural Informa- tion Processing Systems 24, pages 693–701, 2011.
I. Pil &;#769;aszy, D. Zibriczky, and D. Tikk. Fast ALS-based matrix factorization for explicit and implicit feedback datasets. In Proceedings of the Fourth ACM Con- ference on Recommender Systems, pages 71–78, 2010.
H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400–407, 1951.
H.-F. Yu, C.-J. Hsieh, S. Si, and I. S. Dhillon. Scalable coordinate descent ap- proaches to parallel matrix factorization for recommender systems. In Proceedings of the IEEE International Conference on Data Mining, pages 765–774, 2012.
H. Yun, H.-F. Yu, C.-J. Hsieh, S. Vishwanathan, and I. S. Dhillon. Nomad: Non-locking, stochastic multi-machine algorithm for asynchronous and decentral- ized matrix completion. In International Conference on Very Large Data Bases (VLDB), 2014.
Y. Zhou, D. Wilkinson, R. Schreiber, and R. Pan. Large-scale parallel collabo- rative filtering for the Netflix prize. In Proceedings of the Fourth International Conference on Algorithmic Aspects in Information and Management, pages 337– 348, 2008.
Y. Zhuang, W.-S. Chin, Y.-C. Juan, and C.-J. Lin. A fast parallel SGD for matrix factorization in shared memory systems. In Proceedings of the ACM Rec- ommender Systems, 2013. URL http://www.csie.ntu.edu.tw/~cjlin/papers/ libmf.pdf.
M. Zinkevich, M. Weimer, A. Smola, and L. Li. Parallelized stochastic gradient de- scent. In J. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems 23, pages 2595–2603. 2010.