Abstract:

Factor, or linear component (PCA), models are often natural in the
analysis of many kinds of tabulated data (e.g. collections of
documents or images, gene expression measurements and user
preferences).  The premise of such models is that important aspects of
the data can be captured by a small number dimensions ("components",
"factors" or "topics").

I will present a novel approach that allows an unbounded (infinite)
number of factors.  This is achieved by limiting the norm of the
factorization instead of its dimensionality.  The approach is inspired
by, and has strong connections to, large-margin linear discrimination.

I will show how such a max-margin matrix factorization can be learned
by solving a (very large, but efficiently solvable) semi-definite
program.  I will also present generalization error bounds for learning
with such factorization, and discuss the relationship between what can
be learned with max-margin and low-dimensional factorizations.

Joint work with Alexandre d'Aspremont, Tommi Jaakkola, Jason Rennie
and Adi Shraibman.