Poster
Transduction with Matrix Completion: Three Birds with One Stone
Andrew B Goldberg · Jerry Zhu · Benjamin Recht · Junming Sui · Rob Nowak

Tue Dec 7th 12:00 -- 12:00 AM @ None #None

We pose transductive classification as a matrix completion problem. By assuming the underlying matrix has a low rank, our formulation is able to handle three problems simultaneously: i) multi-label learning, where each item has more than one label, ii) transduction, where most of these labels are unspecified, and iii) missing data, where a large number of features are missing. We obtained satisfactory results on several real-world tasks, suggesting that the low rank assumption may not be as restrictive as it seems. Our method allows for different loss functions to apply on the feature and label entries of the matrix. The resulting nuclear norm minimization problem is solved with a modified fixed-point continuation method that is guaranteed to find the global optimum.

Author Information

Andrew B Goldberg (Arcode Corporation)
Jerry Zhu (University of Wisconsin-Madison)
Benjamin Recht (UW-Madison)
Junming Sui
Rob Nowak (Wisconsin)

More from the Same Authors