Name
Abstract | ||
|---|---|---|
Author(s): Pezeshkpour, Pouya | Advisor(s): Singh, Sameer | Abstract: Matrix factorization is a popular machine learning technique, with applications invariety of domains, such as recommendation systems [16, 28], natural language processing[26], and computer vision [10]. Due to this widespread use of these models,there has been considerable theoretical analysis of the various properties of low-rankapproximations of real-valued matrices, including approximation rank [1, 5] and samplecomplexity [2].Rather than assume real-valued data, a number of studies (particularly ones on practicalapplications) focus on more specific data types, such as binary data [23], integerdata [17], and ordinal data [12, 30]. For such matrices, existing approaches have useddifferent link functions, applied in an element-wise manner to the low-rank representation[21], i.e. the output Y is ψ(U^TV) instead of the conventional U^TV. Theselink functions have been justified from a probabilistic point of view [4, 27], and haveprovided considerable success in empirical settings. However, theoretical results forlinear factorization do not apply here, and thus the expressive power of the factorizationmodels with non-linear link functions is not clear, and neither is the relation ofthe rank of a matrix to the link function used.In this work, we first define a generalized notion of rank based on the link function ψ,as the rank of a latent matrix before the link function is applied. We focus on a linkfunction that applies to factorization of integer-valued matrices: the generalized roundfunction (GRF), and define the corresponding generalized round-rank (GRR). Afterproviding background on GRR, we show that there are many low-GRR matrices thatare full rank1. Moreover, we also study the approximation limitations of linear rank, byshowing, for example, that low GRR matrices often cannot be approximated by lowranklinear matrices. We define uniqueness for GRR-based matrix completion, andderive its necessary and sufficient conditions. These properties demonstrate that manyfull linear-rank matrices can be factorized using low-rank matrices if an appropriatelink function is used.We also present an empirical evaluation of factorization with different link functions formatrix reconstruction and completion. We show that using link functions is efficientcompared to linear rank, in that gradient-based optimization approach learns moreaccurate reconstructions using a lower rank representation and fewer training samples.We also perform experiments on matrix completion on two recommendation datasets,and demonstrate that appropriate link function outperform linear factorization, thuscan play a crucial role in accurate matrix completion. |
Year | Venue | Field |
|---|---|---|
2018 | arXiv: Machine Learning | Rank (linear algebra),Integer,Uniqueness,Mathematical optimization,Matrix completion,Algebra,Matrix (mathematics),Matrix decomposition,Factorization,Binary data,Mathematics |
DocType | Volume | Citations |
Journal | abs/1805.00184 | 0 |
PageRank | References | Authors |
0.34 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pouya Pezeshkpour | 1 | 0 | 1.69 |
| Carlos Guestrin | 2 | 9220 | 488.92 |
| Sameer Singh | 3 | 1060 | 71.63 |