在共享記憶體系統的快速平行隨機梯度下降法矩陣分解

A Fast Parallel Stochastic Gradient Method for Matrix Factorization in Shared Memory Systems

阮毓欽(Yu-Chin Juan)

指導教授 ： 林智仁

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2014年)

https://doi.org/10.6342/NTU.2014.02485

摘要

在推薦系統上，矩陣分解是一個非常有效的技術。
對於矩陣分解問題，隨機梯度下降法是一個高效的演算法。
然而，這個演算法並不容易被平行。
這篇論文，在共享記憶體系統中，我們開發一個新的平行演算法叫做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.

並列關鍵字

Recommender system ； Matrix factorization ； Stochastic gradient descent ； Parallel computing ； Shared memory algorithm

參考文獻

R. M. Bell and Y. Koren. Lessons from the Netflix prize challenge. ACM SIGKDD Explorations Newsletter, 9(2):75–79, 2007.

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.

I. Pil ́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.