Timezone: »

 
Poster
Blind Regression: Nonparametric Regression for Latent Variable Models via Collaborative Filtering
Dogyoon Song · Christina Lee · Yihua Li · Devavrat Shah

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #39
in Tuesday Posters »
We introduce the framework of blind regression motivated by matrix completion for recommendation systems: given $m$ users, $n$ movies, and a subset of user-movie ratings, the goal is to predict the unobserved user-movie ratings given the data, i.e., to complete the partially observed matrix. Following the framework of non-parametric statistics, we posit that user $u$ and movie $i$ have features $x1(u)$ and $x2(i)$ respectively, and their corresponding rating $y(u,i)$ is a noisy measurement of $f(x1(u), x2(i))$ for some unknown function $f$. In contrast with classical regression, the features $x = (x1(u), x2(i))$ are not observed, making it challenging to apply standard regression methods to predict the unobserved ratings. Inspired by the classical Taylor's expansion for differentiable functions, we provide a prediction algorithm that is consistent for all Lipschitz functions. In fact, the analysis through our framework naturally leads to a variant of collaborative filtering, shedding insight into the widespread success of collaborative filtering in practice. Assuming each entry is sampled independently with probability at least $\max(m^{-1+\delta},n^{-1/2+\delta})$ with $\delta > 0$, we prove that the expected fraction of our estimates with error greater than $\epsilon$ is less than $\gamma^2 / \epsilon^2$ plus a polynomially decaying term, where $\gamma^2$ is the variance of the additive entry-wise noise term. Experiments with the MovieLens and Netflix datasets suggest that our algorithm provides principled improvements over basic collaborative filtering and is competitive with matrix factorization methods.
Keywords: Learning Theory · (Other) Probabilistic Models and Methods · Similarity and Distance Learning · (Application) Collaborative Filtering and Recommender Systems · Ranking and Preference Learning

Author Information

Dogyoon Song (MIT)
Christina Lee (MIT)
Yihua Li (MIT)
Devavrat Shah (Massachusetts Institute of Technology)

Devavrat Shah is a professor of Electrical Engineering & Computer Science and Director of Statistics and Data Science at MIT. He received PhD in Computer Science from Stanford. He received Erlang Prize from Applied Probability Society of INFORMS in 2010 and NeuIPS best paper award in 2008.

More from the Same Authors