Chenghao Liu
Ee-Peng Lim
ABSTRACT
This paper aims to investigate efficient and scalable machine learning algorithms for resolving Non-negative Matrix Factorization (NMF), which is important for many real-world applications, particularly for collaborative filtering and recommender systems. Unlike traditional batch learning methods, a recently proposed online learning technique named "NN-PA" tackles NMF by applying the popular Passive-Aggressive (PA) online learning, and found promising results. Despite its simplicity and high efficiency, NN-PA falls short in at least two critical limitations: (i) it only exploits the first-order information and thus may converge slowly especially at the beginning of online learning tasks; (ii) it is sensitive to some key parameters which are often difficult to be tuned manually, particularly in a practical online learning system. In this work, we present a novel family of online Adaptive Passive-Aggressive (APA) learning algorithms for NMF, named "NN-APA", which overcomes two critical limitations of NN-PA by (i) exploiting second-order information to enhance PA in making more informative updates at each iteration; and (ii) achieving the parameter auto-selection by exploring the idea of online learning with expert advice in deciding the optimal combination of the key parameters in NMF. We theoretically analyze the regret bounds of the proposed method and show its advantage over the state-of-the-art NN-PA method, and further validate the efficacy and scalability of the proposed technique through an extensive set of experiments on a variety of large-scale real recommender systems datasets.
- M. W. Berry, M. Browne, A. N. Langville, V. P. Pauca, and R. J. Plemmons. Algorithms and applications for approximate nonnegative matrix factorization. Computational statistics & data analysis, 52(1):155--173, 2007.Google Scholar
- M. Blondel, Y. Kubo, and N. Ueda. Online passive-aggressive algorithms for non-negative matrix factorization and completion. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, pages 96--104, 2014.Google Scholar
- B. Cao, D. Shen, J.-T. Sun, X. Wang, Q. Yang, and Z. Chen. Detect and track latent factors with online nonnegative matrix factorization. In IJCAI, volume 7, pages 2689--2694, 2007. Google ScholarDigital Library
- N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, 2006. Google ScholarCross Ref
- A. Cichocki and P. Anh-Huy. Fast local algorithms for large scale nonnegative matrix and tensor factorizations. IEICE transactions on fundamentals of electronics, communications and computer sciences, 92(3):708--721, 2009.Google Scholar
- K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. Online passive-aggressive algorithms. The Journal of Machine Learning Research, 7:551--585, 2006. Google ScholarDigital Library
- J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research, 12:2121--2159, 2011. Google ScholarDigital Library
- Y. Freund and R. E. Schapire. A desicion-theoretic generalization of on-line learning and an application to boosting. In Computational learning theory, pages 23--37. Springer, 1995. Google ScholarCross Ref
- N. Guan, D. Tao, Z. Luo, and J. Shawe-Taylor. Mahnmf: Manhattan non-negative matrix factorization. arXiv preprint arXiv:1207.3438, 2012.Google Scholar
- N. Guan, D. Tao, Z. Luo, and B. Yuan. Online nonnegative matrix factorization with robust stochastic approximation. Neural Networks and Learning Systems, IEEE Transactions on, 23(7):1087--1099, 2012.Google Scholar
- S. C. Hoi, J. Wang, and P. Zhao. Libol: A library for online learning algorithms. The Journal of Machine Learning Research, 15(1):495--499, 2014. Google ScholarDigital Library
- C.-J. Hsieh and I. S. Dhillon. Fast coordinate descent methods with variable selection for non-negative matrix factorization. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1064--1072. ACM, 2011. Google ScholarDigital Library
- Y. Koren, R. Bell, and C. Volinsky. Matrix factorization techniques for recommender systems. Computer, (8):30--37, 2009. Google ScholarDigital Library
- D. D. Lee and H. S. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401(6755):788--791, 1999.Google ScholarCross Ref
- D. D. Lee and H. S. Seung. Algorithms for non-negative matrix factorization. In Advances in neural information processing systems, pages 556--562, 2001. Google ScholarDigital Library
- J. Li, X. Hu, L. Wu, and H. Liu. Robust unsupervised feature selection on networked data. SDM, 2016.Google ScholarCross Ref
- C.-J. Lin. On the convergence of multiplicative update algorithms for nonnegative matrix factorization. Neural Networks, IEEE Transactions on, 18(6):1589--1596, 2007. Google ScholarDigital Library
- C.-J. Lin. Projected gradient methods for nonnegative matrix factorization. Neural computation, 19(10):2756--2779, 2007. Google ScholarDigital Library
- J. Lu, S. C. Hoi, J. Wang, and P. Zhao. Second order online collaborative filtering. JMLR Workshop and Conference Proceedings, 29:325--340, 2013.Google Scholar
- J. Mairal, F. Bach, J. Ponce, and G. Sapiro. Online learning for matrix factorization and sparse coding. The Journal of Machine Learning Research, 11:19--60, 2010. Google ScholarDigital Library
- V. G. Vovk. A game of prediction with expert advice. In Proceedings of the eighth annual conference on Computational learning theory, pages 51--60. ACM, 1995. Google ScholarDigital Library
- F. Wang, P. Li, and A. C. König. Efficient document clustering via online nonnegative matrix factorizations. In SDM, volume 11, pages 908--919. SIAM, 2011.Google ScholarCross Ref
- J. Wang, S. C. Hoi, P. Zhao, and Z.-Y. Liu. Online multi-task collaborative filtering for on-the-fly recommender systems. In Proceedings of the 7th ACM conference on Recommender systems, pages 237--244. ACM, 2013. Google ScholarDigital Library
- X. Wang, R. Donaldson, C. Nell, P. Gorniak, M. Ester, and J. Bu. Recommending groups to users using user-group engagement and time-dependent matrix factorization. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.Google ScholarDigital Library
- X. Yan, J. Guo, S. Liu, X. Cheng, and Y. Wang. Learning topics in short texts by non-negative matrix factorization on term correlation matrix. In Proceedings of the SIAM International Conference on Data Mining, 2013.Google ScholarCross Ref
Index Terms
- Online Adaptive Passive-Aggressive Methods for Non-Negative Matrix Factorization and Its Applications
Recommendations
Sparse Passive-Aggressive Learning for Bounded Online Kernel Methods
Research Survey and Regular PapersOne critical deficiency of traditional online kernel learning methods is their unbounded and growing number of support vectors in the online learning process, making them inefficient and non-scalable for large-scale applications. Recent studies on ...
Rectifying the representation learned by Non-negative Matrix Factorization
This paper proposes a novel method to the problem of non-orthogonality of features obtained using the Non-negative Matrix Factorization NMF method. For any given non-negative data matrix, the NMF method provides a learned local representation by ...
New SVD based initialization strategy for non-negative matrix factorization
We give a new method to determine the rank of the factorization for NMF algorithms.We propose a novel method SVD-NMF to enhance initialization for NMF.The compute process is cheap.Numerical results show that SVD-NMF convergent faster than NNDSVD and ...
Comments