Maximum Margin Matrix Factorization
for Collaborative Ranking
Joint work with Quoc Le,
Alexandros Karatzoglou and Markus Weimer
Alexander J. Smolasml.nicta.com.au
Statistical Machine Learning Program
Canberra, ACT 0200 AustraliaAlex.Smola@nicta.com.au

October 6, 2007, DMSS

Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

1 / 30Outline

1Collaborative Ranking

2

A Convex Upper Bound for Ranking

3

Low Rank Factorization

4

Convex Optimization via Bundle Methods

5Experiments

Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

2 / 30Collaborative Ranking
Setting
Internet retailer (e.g. Netflix) sells movies M to users U.
Users rate movies if they liked them.
Retailer wants to suggest some more movies whichmight be interesting for users.
GoalSuggest movies that user will like. Pointless to recommend
movies that users do not like since they are unlikely to rent.
Problems with Netflix contest
Error criterion is uniform over all movies.
Can only recommend a small number of movies at atime (probably no more than 10).
Need to do well only on top scoring movies.
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

3 / 30More Applications
RetaileTailer (e.g. Amazon) wants to suggest new books and otherproducts based on past purchase decisions and reviews.
Collaborative photo viewing site
Want to suggest some more photos user might want to see
given past viewing behavior (e.g. Flickr.com).
Collaborative bookmark site
Suggest new bookmarks based on which ones users clicked
at before. Do this in a personalized fashion. This immediatelyavoids click spam: only spammer is affected by spam clicks:
each user gets his personalized view (e.g. Digg.com).
News site
Suggest new stories personalized to click behavior, such as
news.{google, yahoo}.com.
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

4 / 30Even More Applications
Blogs and Internet Discussions
Show mainly stories that the Specific User likes. E.g. acustomized version of Slashdot or Groklaw.
Internet Dating
Suggest new dates based on previous viewing behavior,number of contact attempts, collaboratively.
Advertising
Use more fine-grained information on link following behavior,e.g. a) customer visits site, b) puts things into shoppingbasket, c) registers for an account, d) purchases item. Use
the entire range of decisions to predict better.

Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

5 / 30Requirements
Direct Optimization
Want to optimize scoring function directly, or at least convex(or at least continuous) uppoer bound of this.
Featureless Estimation
Algorithm should not need inherent features of objects.
Incorporating Features
If features exist, algorithm should be able to include them.
Scalability
Implementation needs to scale to hundreds of millions ofrecords. Parallel and multi-core implementation needed.
Cheap deployment phase.

Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

6 / 30

The Ingredients
Convex Upper Bound
Bound ranking loss, such as NDCG@k directly via convex
ranking bound (e.g. Chapelle, Le and Smola, 2007).
Low Rank Matrix Factorization
Use tools of Srebro et al. and factorize the scoring matrix into
a product of user and movie matrix: F = MU.
Features
Use movie specific, user specific, and (movie, user) specificinformation to add to factorization
F = MU + fm wm + wu fu + fmu · wmu .
|{z}optional

Bundle Method Solver
Scalable convex optimization for movie and user phase.
Parallelize over users.
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

7 / 30Outline

1

Collaborative Ranking

2A Convex Upper Bound for Ranking

3

Low Rank Factorization

4

Convex Optimization via Bundle Methods

5Experiments

Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

8 / 30Ranking Movies for a UserData(movie,user) pairs (i, j)ratings Yij ∈ {1, . . . , 5} of movie i by user j
Goal
For a given user j rank unseen movies i such that themovies he likes most are suggested first.
Modified goal
Rank by assigning scores Fij to (movie,user) pairs.
This is fast at training time since it decouples the movies(only quicksort needed).
Ranking loss
Multivariate performance score (couples the Fij scores)
We use Normalized Discounted Cumulative Gains
truncated at 10 retrieved movies (NDCG@10).
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

9 / 30Scoring Function

movie score
F(user,movie)
moviesmoviesGoal is to find a scoring function Fij which optimizes auser-defined ranking and performance score.

Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

10 / 30

Ranking Scores
Normalized Discounted Cumulative GainkX
(2yi − 1)
DCG@k (π, y ) =andlog(πi + 1)
i=1

NDCG@k (π, y ) =DCG@k (π, y ).
DCG@k (argsort(y ), y )π is permutation and y are user ratings. Score = a(π)> b(y )Extensions
Alternatives are unnormalized, not truncated, different
decay, different position weighting, . . .
We can take position specific ranking into account. E.g.
last position in the list should be a romantic comedy, etc.
But more expensive at prediction time!
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

11 / 30

A Convex Upper Bound
ProblemFinding F such that DCG@k is maximized is highly
nonconvex (it is piecewise constant).
Solution
Structured estimation yields convex upper bound. We use
XG(π, f ) :=cπj fj which is maximized for π ∗ = argsort f .
jHere cj is a monotonically decreasing function in j.
TheoremThe loss ∆(y , π ∗ ) for choosing π ∗ is bounded by ξ whereG(argsort y , f ) − G(π, f ) ≥ ∆(y , π) − ξ for all π.
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

12 / 30

Putting it together
Per-user lossl(y , f ) = max ∆(y , π) + G(π, f ) − G(argsort y , f ).
πMaximization is carried out by solving a Linear Assignment
Problem: the linear programming relaxation of the integer
programming problem is totally unimodular. This allows us tocompute gradients and values efficiently.
Use Joncker and Volgenant or Orlin and Yee algorithm.
Cumulative upper boundX
L(Y , F ) :=l(Yi· , Fi· )i∈Users

We only sum over a subset of movies per user.
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

13 / 30

Outline

1

Collaborative Ranking

2

A Convex Upper Bound for Ranking

3

Low Rank Factorization

4

Convex Optimization via Bundle Methods

5Experiments

Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

14 / 30

Low Rank Factorization
Estimating F
Srebro and coworkers define regularizer for Fi1hkMk2 + kUk2kF k := inf
MU=F 2
Semidefinite Convex Problem
Replace with semidefinite construction for matrix via

1
ZM F >
 0 and kF k → [tr ZM + tr ZU ] .
F ZU
2Problem
The optimization problem is huge. Even storing full F isimpossible (1010 entries).
Solution
Factorize F = MU or low rank M and U (10-200 dimensions).
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

15 / 30

Optimization Problem
Objective Function
L(Y , MU) +iλhkUk2 + kMk2
2Algorithm
Objective function is convex in U for fixed M and vice versa.
1
Minimize L(Y , MU) + λ2 kMk2
2
Minimize L(Y , MU) + λ2 kUk2
Repeat until converged.
Extensions
Add user, movie specific features
Different regularization for different movie, user numbers
Different regularization for each dimension
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

16 / 30

Features
Improved low rank factorizationUse movie specific, user specific, and (movie, user) specificinformation to add to factorization
F = MU + fm wm + wu fu + fmu · wmu .
{z}|optionalOptimization
Optimize over all parameters except for M or U.
Problem is still convex.
Domain knowledge
The right place for feature engineering. In particular fmu
contains (movie, user) features.
Christmas movies are not popular in August.
Die Hard will not sell well on Good Friday.
Soccer movies are popular in worldcup years . . .
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

17 / 30

Outline

1

Collaborative Ranking

2

A Convex Upper Bound for Ranking

3

Low Rank Factorization

4

Convex Optimization via Bundle Methods

5Experiments

Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

18 / 30

Basic Constraints
Empirical Risk
Evaluating it is expensive (linear assignment is killer).
Almost equally expensive to compute value or value andgradient.
Regularizer
Cheap to compute
Easy to minimize over regularizer plus piecewise linearfunction
Idea
Use past gradients to build up successively improving
lower bound on empirical risk.
Solve regularized lower bound problem successively.
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

19 / 30

Bundle Approximation

Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

20 / 30

AlgorithmLower boundRt [w] := max hat , wi + bt ≤ Remp [w]j≤twhere at = ∂w Remp [wt−1 ] and bt = Remp [wt−1 ] − hat , wt−1 i .
Pseudocode
Initialize t = 0, w0 = 0, a0 = 0, b0 = 0
repeatFind minimizer wt := argminw Rt (w) + λ2 kwk2
Compute gradient at+1 and offset bt+1 .
Increment t ← t + 1.
until t ≤ Upper Bound
Note that Rt+1 [wt ] = Remp [wt ]. Hence Rt+1 [wt ] − Rt [wt ] upperbounds gap size. We get a cheap convergence monitor.
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

21 / 30

Dual Problem
Good News
Dual optimization problem is Quadratic Program regardlessof the choice of the empirical risk.
Details
1 > >β AA β − β > bβ2λX
subject to βi ≥ 0 andβi = 1minimize

iThe primal coefficient w is given by w = −λ−1 A> β.
Very Cheap Variant
Can even use simple line search for update (almost as good).
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

22 / 30

Convergence
Theorem
The number of iterations to reach  precision is bounded byn ≤ log2

λRemp [0] 8G2+−4G2λsteps. If the Hessian of Remp [w] is bounded, convergence toany  ≤ H/2 takes at most the following number of steps:n ≤ log2

 4H ∗
λRemp [0] 42 ∗+max0,1−8GH/λ−log 2
4G2λλAdvantages
Linear convergence for smooth loss
For non-smooth loss almost as good in practice (as longas smooth on a course scale).
General solver (works for any loss)
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

23 / 30

Outline

1

Collaborative Ranking

2A Convex Upper Bound for Ranking

3Low Rank Factorization

4

Convex Optimization via Bundle Methods

5Experiments

Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

24 / 30

Datasets

Data set sizes
DatasetUsers
EachMovie 61265
MovieLens
983
Netflix
480189MoviesRatings
1623
28117171682
10000017770 100480507

Very sparse matrix. Ratings between 1 and 5.

Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

25 / 30

Comparators
Regression
Plain regression on the labels
Very easy to implement, only solve least mean squares
problems iteratively.
This is what the Netflix contest wants.
Ordinal Regression
Retain absolute ordering between users
Relax the actual scores (retain only margin)
Suggested by Herbrich and Gräpel, 2000
ProtocolSame protocol for all solvers (same function space)
Weak generalization: new movies for the same user
Strong generalization: new movies for a new user (donot optimize for the user we want to test on).
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

26 / 30

Weak Generalization (NDCG@10)
MethodEachMovie NDCG
OrdinalRegr.

N=100.6673 ± 0.0015
0.5592 ± 0.0040
0.5349 ± 0.0214
p = 2.7e-14

N=200.7589 ± 0.0006
0.6619 ± 0.0062
0.6291 ± 0.0161
p = 3.0e-12

MovieLens NDCG0.6364 ± 0.0064 0.7153 ± 0.0038
Ordinal0.6291 ± 0.0004 0.6601 ± 0.0013
Regression 0.6404 ± 0.0057 0.7015 ± 0.0056
MMMF
0.6061 ± 0.0037 0.6937 ± 0.0039
p = 0.011
p = 6e-5
Netflix NDCG
Regression

0.60810.6082

Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

0.62040.628727 / 30

Strong Generalization (NDCG@10)
MethodEachMovie NDCG
GPR
CGPR
GPOR
CGPOR
MMMF

N=100.6367 ± 0.001
0.4558 ± 0.015
0.5734 ± 0.014
0.3692 ± 0.002
0.3789 ± 0.011
0.4746 ± 0.034

N=200.6619 ± 0.0022
0.4849 ± 0.0066
0.5989 ± 0.0118
0.3678 ± 0.0030
0.3781 ± 0.0056
0.4786 ± 0.0139

MovieLens NDCG
0.6237 ± 0.0241 0.6711 ± 0.0065
GPR0.4937 ± 0.0108 0.5020 ± 0.0089
CGPR
0.5101 ± 0.0081 0.5249 ± 0.0073
GPOR
0.4988 ± 0.0035 0.5004 ± 0.0046
CGPOR 0.5053 ± 0.0047 0.5089 ± 0.0044
MMMF
0.5521 ± 0.0183 0.6133 ± 0.0180
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

28 / 30

Discussion
Open Question
Why is strong generalization with our solver so muchbetter? Not much difference for weak generalization.
Parallelization
User optimization easy: embarassingly parallel.
Movie optimization almost as easy: precompute gradientof loss in parallel.
MMMF is very slow (up to 1 day) vs. 20 minutes for ourimplementation.
Improvements
Adaptive regularization for dimensions, sample sizes(movies, users)
Better initialization
Better sparse matrix library
Use QuickMatch (faster than current implementation)
Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

29 / 30

Summary

1Collaborative Ranking

2

A Convex Upper Bound for Ranking

3

Low Rank Factorization

4

Convex Optimization via Bundle Methods

5Experiments

Alexander J. Smola: Maximum Margin Matrix Factorization for Collaborative Ranking

30 / 30