Ke Zhou
ABSTRACT
This paper tackles the efficiency problem of making recommendations in the context of large user and item spaces. In particular, we address the problem of learning binary codes for collaborative filtering, which enables us to efficiently make recommendations with time complexity that is independent of the total number of items. We propose to construct binary codes for users and items such that the preference of users over items can be accurately preserved by the Hamming distance between their respective binary codes. By using two loss functions measuring the degree of divergence between the training and predicted ratings, we formulate the problem of learning binary codes as a discrete optimization problem. Although this optimization problem is intractable in general, we develop effective relaxations that can be efficiently solved by existing methods. Moreover, we investigate two methods to obtain the binary codes from the relaxed solutions. Evaluations are conducted on three public-domain data sets and the results suggest that our proposed method outperforms several baseline alternatives.
Supplemental Material
- G. Adomavicius and a. Tuzhilin. Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions. IEEE Transactions on Knowledge and Data Engineering, 17(6):734--749, June 2005. Google Scholar
Digital Library
- D. Agarwal, B. Chen, and P. Elango. Fast online learning through offline initialization for time-sensitive recommendation. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 703--712. ACM, 2010. Google ScholarDigital Library
- Y. Bachrach and R. Herbrich. Fingerprinting Ratings For Collaborative Filtering Theoretical and Empirical Analysis. String Processing and Information Retrieval, pages 25--36, 2010. Google ScholarDigital Library
- Y. Bachrach, E. Porat, and J. Rosenschein. Sketching techniques for collaborative filtering. In Proceedings of the 21st international joint conference on Artifical intelligence, pages 2016--2021. Morgan Kaufmann Publishers Inc., 2009. Google ScholarDigital Library
- A. S. Das, M. Datar, A. Garg, and S. Rajaram. Google news personalization: scalable online collaborative filtering. In Proceedings of the 16th international conference on World Wide Web - WWW '07, page 271, New York, New York, USA, 2007. ACM Press. Google ScholarDigital Library
- M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry - SCG '04, page 253, New York, New York, USA, 2004. ACM Press. Google ScholarDigital Library
- J. He and W. Liu. Scalable similarity search with optimized kernel hashing. Proceedings of the 16th ACM SIGKDD, pages 1129--1138, 2010. Google ScholarDigital Library
- P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98, pages 604--613, New York, New York, USA, 1998. ACM Press. Google ScholarDigital Library
- H. Jégou, T. Furon, and J.-J. Fuchs. Anti-sparse coding for approximate nearest neighbor search. Arxiv preprint arXiv:1110.3767, (October):577--580, Oct. 2011.Google Scholar
- J. Kekzäläinen. Binary and graded relevance in IR evaluations - Comparison of the effects on ranking of IR systems. Information Processing and Management, 41:1019--1033, 2005. Google ScholarDigital Library
- Y. Koren. Factor in the neighbors: Scalable and accurate collaborative filtering. ACM Transactions on Knowledge Discovery from Data (TKDD), 4(1):1--24, 2010. Google ScholarDigital Library
- B. Kulis and T. Darrell. Learning to hash with binary reconstructive embeddings. Proceedings of Advances in Neural Information Processing Systems, 2009.Google Scholar
- W. Liu, J. Wang, S. Kumar, and S. Chang. Hashing with Graphs. In Proceedings of the 28th International Conference on Machine Learning, 2011.Google Scholar
- M. Norouzi and D. Fleet. Minimal Loss Hashing for Compact Binary Codes. In Proceedings of the 28th International Conference on Machine Learning, volume 1, 2011.Google Scholar
- A. Paterek. Improving regularized singular value decomposition for collaborative filtering. In Proceedings of KDD Cup and Workshop, volume 2007, pages 5--8. Citeseer, 2007.Google Scholar
- S. Rendle, C. Freudenthaler, and L. Schmidt-Thieme. Factorizing personalized Markov chains for next-basket recommendation. Proceedings of the 19th international conference on World wide web - WWW'10, page 811, 2010. Google ScholarDigital Library
- R. Salakhutdinov and G. Hinton. Semantic hashing. International Journal of Approximate Reasoning, 50(7):969--978, July 2009. Google ScholarDigital Library
- G. Shakhnarovich, P. Viola, and T. Darrell. Fast pose estimation with parameter-sensitive hashing. In Proceedings Ninth IEEE International Conference on Computer Vision, pages 750--757 vol.2. IEEE, 2003. Google ScholarDigital Library
- X. Su and T. M. Khoshgoftaar. A Survey of Collaborative Filtering Techniques. Advances in Artificial Intelligence, 2009(Section 3):1--20, 2009. Google ScholarDigital Library
- J. Wang and S. Kumar. Sequential projection learning for hashing with compact codes. International Conference on Machine Learning, 2010.Google ScholarDigital Library
- Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. In Neural Information Processing Systems, number 1, pages 1--8, 2008.Google Scholar
- S. X. Yu and J. Shi. Multiclass spectral clustering. In Proceedings Ninth IEEE International Conference on Computer Vision, number 0, pages 313--319 vol.1, Washington, DC, USA, 2003. IEEE. Google ScholarDigital Library
- D. Zhang, J. Wang, D. Cai, and J. Lu. Laplacian co-hashing of terms and documents. Advances in Information Retrieval, pages 577--580, 2010. Google ScholarDigital Library
- D. Zhang, J. Wang, D. Cai, and J. Lu. Self-taught hashing for fast similarity search. In Proceeding of the 33rd international ACM SIGIR conference on Research and development in information retrieval, pages 18--25. ACM, 2010. Google ScholarDigital Library
- C. Zhu, R. H. Byrd, P. Lu, and J. Nocedal. Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization. ACM Transactions on Mathematical Software, 23(4):550--560, Dec. 1997. Google ScholarDigital Library
Recommendations
Discrete Collaborative Filtering
SIGIR '16: Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information RetrievalWe address the efficiency problem of Collaborative Filtering (CF) by hashing users and items as latent vectors in the form of binary codes, so that user-item affinity can be efficiently calculated in a Hamming space. However, existing hashing methods for ...
Neural Collaborative Filtering
WWW '17: Proceedings of the 26th International Conference on World Wide WebIn recent years, deep neural networks have yielded immense success on speech recognition, computer vision and natural language processing. However, the exploration of deep neural networks on recommender systems has received relatively less scrutiny. In ...
Deep Learning Based Recommender System: A Survey and New Perspectives
With the growing volume of online information, recommender systems have been an effective strategy to overcome information overload. The utility of recommender systems cannot be overstated, given their widespread adoption in many web applications, along ...
Comments