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 x M ⇀ 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 second talk of the series on high-arity learning frameworks, I will discuss how the Netflix Prize Competition can be seen as an instance of a high-arity learning framework called “sample completion learning”. I will also discuss 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.