In this thesis, we tackle three challenges in recommendation systems (RS): scalability, privacy and structured prediction.
We first develop a scalable primal dual algorithm for matrix completion based on trace norm regularization. The regularization problem is solved via a constraint generation method that explicitly maintains a sparse dual and the corresponding low rank primal solution. We provide a new dual block coordinate descent algorithm for solving the dual problem with a few spectral constraints. Empirical results illustrate the effectiveness of our method in comparison to recently proposed alternatives. In addition, we extend the method to non-negative matrix factorizations (NMF) and dictionary learning for sparse coding.
Privacy is another important issue in RS. Indeed, there is an inherent trade-off between accuracy of recommendations and the extent to which users are willing to release information about their preferences. We explore a two-tiered notion of privacy where there is a small set of public users who are willing to share their preferences openly, and a large set of private users who require privacy guarantees. We show theoretically, and demonstrate empirically, that a moderate number of public users with no access to private user information already suffices for reasonable accuracy. Moreover, we introduce a new privacy concept for gleaning relational information from private users while maintaining a first order deniability. We demonstrate gains from controlled access to private user preferences.
We further extend matrix completion to high-order tensors. We illustrate tensor completion in the context of recommending a set of items to users as a tensor completion problem. We develop methods for directly controlling tensor factorizations in terms of the degree of nonlinearity, the number of non-uniform modes in rank-1 components, as well as the overall number of components.
Finally, we develop a tensor factorization approach for dependency parsing. Instead of manually selecting features, we use tensors to map high-dimensional feature into low dimensional space. Our parser achieves state of the art results on multiple languages.
Thesis Supervisor: Professor Tommi Jaakkola