2015 PULearningforMatrixCompletion

• (Hsieh et al., 2015) ⇒ Cho-Jui Hsieh, Nagarajan Natarajan, and Inderjit S Dhillon. (2015). “PU Learning for Matrix Completion.” In: Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37.

Subject Headings:

Notes

• http://www.cs.utexas.edu/~cjhsieh/pu_mc_slides.pdf

Cited By

• http://scholar.google.com/scholar?q=%222015%22+PU+Learning+for+Matrix+Completion
• http://dl.acm.org/citation.cfm?id=3045118.3045378&preflayout=flat#citedby

Quotes

Abstract

In this paper, we consider the matrix completion problem when the observations are one-bit measurements of some underlying matrix M, and in particular the observed samples consist only of ones and no zeros. This problem is motivated by modern applications such as recommender systems and social networks where only “likes" or “friendships" are observed. The problem is an instance of PU (positive-unlabeled) learning, i.e. learning from only positive and unlabeled examples that has been studied in the context of binary classification. Under the assumption that M has bounded nuclear norm, we]] provide recovery guarantees for two different observation models: 1) M parameterizes a distribution that generates a binary matrix, 2) M is thresholded to obtain a binary matrix. For the first case, we propose a "shifted matrix completion" method that recovers M using only a subset of indices corresponding to ones; for the second case, we propose a " biased matrix completion " method that recovers the (thresholded) binary matrix. Both methods yield strong error bounds - - if [math]\displaystyle{ M \in R^{n \times n} }[/math] the error is bounded as O (1 / (1-ρ) ⁿ), where 1 - - ρ denotes the fraction of ones observed. This implies a sample complexity of O(n log n) ones to achieve a small error, when M is dense and n is large. We extend our analysis to the inductive matrix completion problem, where rows and columns of M have associated features. We develop efficient and scalable optimization procedures for both the proposed methods and demonstrate their effectiveness for link prediction (on real-world networks consisting of over 2 million nodes and 90 million links) and semi-supervised clustering tasks.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 PULearningforMatrixCompletion	Inderjit S. Dhillon Cho-Jui Hsieh Nagarajan Natarajan			PU Learning for Matrix Completion						2015