Relational learning via collective matrix factorization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Relational learning via collective matrix factorization

Full text

Pdf (358 KB)

Source

International Conference on Knowledge Discovery and Data Mining archive
Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining table of contents

Las Vegas, Nevada, USA

SESSION: Research papers table of contents

Pages 650-658

Year of Publication: 2008

ISBN:978-1-60558-193-4

Authors

Ajit P. Singh	Carnegie Mellon University, Pittsburgh, PA, USA
Geoffrey J. Gordon	Carnegie Mellon University, Pittsburgh, PA, USA

Sponsors

ACM: Association for Computing Machinery
SIGKDD: ACM Special Interest Group on Knowledge Discovery in Data
SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 210, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1401890.1401969 What is a DOI?

ABSTRACT

Relational learning is concerned with predicting unknown values of a relation, given a database of entities and observed relations among entities. An example of relational learning is movie rating prediction, where entities could include users, movies, genres, and actors. Relations encode users' ratings of movies, movies' genres, and actors' roles in movies. A common prediction technique given one pairwise relation, for example a #users x #movies ratings matrix, is low-rank matrix factorization. In domains with multiple relations, represented as multiple matrices, we may improve predictive accuracy by exploiting information from one relation while predicting another. To this end, we propose a collective matrix factorization model: we simultaneously factor several matrices, sharing parameters among factors when an entity participates in multiple relations. Each relation can have a different value type and error distribution; so, we allow nonlinear relationships between the parameters and outputs, using Bregman divergences to measure error. We extend standard alternating projection algorithms to our model, and derive an efficient Newton update for the projection. Furthermore, we propose stochastic optimization methods to deal with large, sparse matrices. Our model generalizes several existing matrix factorization methods, and therefore yields new large-scale optimization algorithms for these problems. Our model can handle any pairwise relational schema and a wide variety of error models. We demonstrate its efficiency, as well as the benefit of sharing parameters among relations.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Deepak Agarwal , Srujana Merugu, Predictive discrete latent factor models for large scale dyadic data, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281199]
	2	D. J. Aldous. Representations for partially exchangeable arrays of random variables. J. Multi. Anal., 11(4):581--598, 1981.
	3	D. J. Aldous. Exchangeability and related topics, chapter 1. Springer, 1985.
	4	Katy S. Azoury , M. K. Warmuth, Relative Loss Bounds for On-Line Density Estimation with the Exponential Family of Distributions, Machine Learning, v.43 n.3, p.211-246, June 2001 [doi>10.1023/A:1010896012157]
	5	A. Banerjee, S. Basu, and S. Merugu. Multi-way clustering on relation graphs. In SDM. SIAM, 2007.
	6	Arindam Banerjee , Srujana Merugu , Inderjit S. Dhillon , Joydeep Ghosh, Clustering with Bregman Divergences, The Journal of Machine Learning Research, 6, p.1705-1749, 12/1/2005
	7	Léon Bottou, On-line learning and stochastic approximations, On-line learning in neural networks, Cambridge University Press, New York, NY, 1999
	8	L. Bottou and Y. LeCun. Large scale online learning. In NIPS, 2003.
	9	Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
	10	L. Bregman. The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming. USSR Comp. Math and Math. Phys., 7:200--217, 1967.
	11	Yair Al Censor , Stavros A. Zenios, Parallel Optimization: Theory, Algorithms and Applications, Oxford University Press, 1997
	12	Peter Pin-Shan Chen, The entity-relationship model—toward a unified view of data, ACM Transactions on Database Systems (TODS), v.1 n.1, p.9-36, March 1976 [doi>10.1145/320434.320440]
	13	D. Cohn and T. Hofmann. The missing link-a probabilistic model of document content and hypertext connectivity. In NIPS, 2000.
	14	M. Collins, S. Dasgupta, and R. E. Schapire. A generalization of principal component analysis to the exponential family. In NIPS, 2001.
	15	Jürgen Forster , Manfred K. Warmuth, Relative Expected Instantaneous Loss Bounds, Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, p.90-99, June 28-July 01, 2000
	16	G. H. Golub and C. F. V. Loan. Matrix Computions. John Hopkins UP, 3rd edition, 1996.
	17	G. J. Gordon. Generalized² linear² models. In NIPS, 2002.
	18	Donna Harman, Overview of the second text retrieval conference (TREC-2), Information Processing and Management: an International Journal, v.31 n.3, p.271-289, May-June 1995
	19	Thomas Hofmann, Probabilistic latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.50-57, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312649]
	20	Internet Movie Database Inc. IMDB interfaces. http://www.imdb.com/interfaces, Jan. 2007.
	21	D. D. Lee and H. S. Seung. Algorithms for non-negative matrix factorization. In NIPS, 2001.
	22	J. D. Leeuw. Block relaxation algorithms in statistics, 1994.
	23	Bo Long , Zhongfei (Mark) Zhang , Xiaoyun Wú , Philip S. Yu, Spectral clustering for multi-type relational data, Proceedings of the 23rd international conference on Machine learning, p.585-592, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143918]
	24	Bo Long , Zhongfei (Mark) Zhang , Xiaoyun Wu , Philip S. Yu, Relational clustering by symmetric convex coding, Proceedings of the 24th international conference on Machine learning, p.569-576, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273568]
	25	Bo Long , Zhongfei Mark Zhang , Philip S. Yu, A probabilistic framework for relational clustering, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281244]
	26	P. McCullagh and J. Nelder. Generalized Linear Models. Chapman and Hall: London., 1989.
	27	Netflix. Netflix prize dataset. http://www.netflixprize.com, Jan. 2007.
	28	J. Nocedal and S. J. Wright. Numerical Optimization. Springer, 1999.
	29	Francisco Pereira , Geoffrey Gordon, The support vector decomposition machine, Proceedings of the 23rd international conference on Machine learning, p.689-696, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143931]
	30	Jasson D. M. Rennie , Nathan Srebro, Fast maximum margin matrix factorization for collaborative prediction, Proceedings of the 22nd international conference on Machine learning, p.713-719, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102441]
	31	A. P. Singh and G. J. Gordon. Relational learning via collective matrix factorization. Technical Report CMU-ML-08-109, Machine Learning Department, Carnegie Mellon University, 2008.
	32	N. Srebro and T. Jaakola. Weighted low-rank approximations. In ICML, 2003.
	33	N. Srebro, J. D. Rennie, and T. S. Jaakkola. Maximum-margin matrix factorization. In NIPS, 2004.
	34	P. Stoica and Y. Selen. Cyclic minimizers, majorization techniques, and the expectation-maximization algorithm: a refresher. Sig. Process. Mag., IEEE, 21(1):112--114, 2004.
	35	Kai Yu , Shipeng Yu , Volker Tresp, Multi-label informed latent semantic indexing, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076080]
	36	Shipeng Yu , Kai Yu , Volker Tresp , Hans-Peter Kriegel , Mingrui Wu, Supervised probabilistic principal component analysis, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150454]
	37	Shenghuo Zhu , Kai Yu , Yun Chi , Yihong Gong, Combining content and link for classification using matrix factorization, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277825]