Description:

Title: Sample completion, Netflix Prize Competition and $k$-dependence

Abstract: In the Netflix Prize Competition (2006-2009), we are given a finite set $U$ of users, a finite set $M$ of movies and a partial function $f: U\times M\rightharpoonup R$, where $f(u,m)$ indicates how user $u$ rates movie $m$ and we are tasked with completing $f$ to a total function to predict how all users $U$ rate all movies in $M$. Although some algorithms did fairly well in the competition, giving a satisfactory theoretical explanation for their success has been difficult.
In this talk I will discuss how this learning problem can be seen as an instance of a framework that we call "sample completion learning" and how sample completion learning is completely characterized by the model-theoretic notion of $k$-dependence introduced by Shelah (which can be seen as a high-dimensional version of the Vapnik--Chervonenkis dimension). In turn, this gives a full theoretical characterization of when the Netflix problem is "solvable".

No background in learning theory or model theory is required for this talk.

This talk is based on joint work with Maryanthe Malliaris.