Uncovering Shared Structures in Multiclass Classification

by Yonatan Amit, Michael Fink, Nathan Srebro and Shimon Ullman

In this paper, we have Srebro, one of the authors of previous papers on MMMF. Now we are finding linear projection, a matrix W. To get a good projection, they define a loss function:

which is regularized by the norm of W. Thus we have,

But, they argue the Frobenius norm can be substituted for the trace norm, resulted in the following problem which is formally the same as MMMF:

After analyzing the dual problem of the equation above, it is found out the problem can be kernelized as

Then to solve these problem, SDP or PR-GC can be used.

Fast Maximum Margin Matrix Factorization for Collaborative Prediction

by Jason D.M. Rennie and Nathan Srebro

This paper is published just a little after the one in NIPS, the latter aiming at introdcing MMMF. This paper shows how to compute MMMF faster.

There is something strange in the two. The first one in NIPS claims the trace-norm regularizer is good, since it provides global optimal solution (convex optimization solved by SDP). The second one in ICML claims the following is better for computation:

For this non-convex optimization, they use PR-CG. OK... I am an illiterate of optimization techniques.

Maximum-Margin Matrix Factorization

by Nathan Srebo, Jason D.M. Rennie and Tommi S. Jaakkola

Actually I didn't intend to read this piece. But I am wondering why the trace norm is chosen in another paper I am reading. And here is the homepage of the first author, where you can find related code and slides.

We know there are several matrix factorization problem. One is that SVD helps find the low-rank approximation of a matrix under Frobenius norm. Later in NMF, for non-negative matrix, we hope find a set of non-negative vectors, in the cone spanned by which the matrix can be best approximated, under Frobenius norm or a KL-like divergence.

Here we mainly deal with sparse matrix. The non-zeros elements might be binary. Usually we use a loss that resembles Hinge loss, which is applied to each element of UV'. Then a regularizer is added to the loss. The trace norm is adopted as the lower bound for the Frobenius norm square of U and V, so as to avoid the non-convexity caused by them.

The optimization is solved with SDP. I guess I must get something working with the latest optimization techniques, such as SDP, CCCP and etc. To get a better understanding of this work, I will read the Ph.D. thesis of the first author:
Learning with Matrix Factorizations.

Collabrarive Prediction Using Ensembles of Maximum Margin Matrix Factorization

by Dennis DeCoste

There are two key techniques in this article. One is Maximum Margin Matrix Factorization(MMMF), which I should consult the article Fast maximum margin matrix factorization for collaborative prediction in ICML 2005, the other is the ensemble method used for later classifications.

The setting of MMMF is similar to that of NMF. It has a huge and sparse matrix, Y, representing the ratings from the users, each column of which stands for an item and each row of which stands for an user. Since it's a rating matrix, the elements should be a discrete value taken from 0--R. We'd like to find matrices U, V and discretization parameters thetair such that the following objective can be minimized:

J( U, V, theta) = lambda * ( |U|_F² + |V|_F² )/2 + sum_{over r} sum_{over ij} h( T_ij^r * ( theta_ir - U_i V_j') )

where T_ij^r is 1 if r >= Y_ij and -1 if r < Y_ij. h is a loss function, called Hinge loss, which is differentiable. And hence the optimization can be carried out with gradient-based methods. There is another version of MMMF based on SDP (c.f. Maximum margin matrix factorization in NIPS 2005). MMMF stated here can only be solved with local minima and susceptible.

As for the ensemble part, there are not very new techniques. Simply several voting methods and emsemble with different initial values or bagging.

Notice that in the objective function, there won't be anything for non-rated movies. Here is the setting of weak test of generalization. Held out one column, which is the ratings of a single movie. Compute the MMMF of the remaining matrix so that from the computed U, V and theta, we can predict the ratings for the held-out movie. Another strong test of generation differs. A subset of users are held out first. With the remaining users' ratings, MMMF is done. Then give a held-out user's ratings of all movies except one and ask for the unknown rating. This is done by fixing V and tuning U.

The regularization parameter lambda is chosen with a validation set. The error rate will suggest a proper lambda for later usage.