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.

A Duality View of Spectral Methods for Dimensionality Reduction

by Lin Xiao, Jun Sun and Stephen Boyd

One important trick in this paper is to apply basic optimization theory to the proposed optimization problem. They choose the MVU algorithms proposed by Weinberger. As for the theory, I seldom noticed its importance, although I did try it for several times. I guess I must pay attention to the theoretical importance of it later.

The optimization of MVU is as following,

then get the Lagrange function,

And last the dual problem

By analyzing the KKT conditions and weak/strong duality, we get an insight of the relationship of the sparse Laplacian matrix and the dense Gram matrix. This is really an interesting thing. Later the authors analyzed ISOMAP, LLE, Laplacian Eigenmap.

It is worth redo their analysis to enhence your own ability.

Null Space versus Orthogonal Linear Discriminant Analysis

by Jieping Ye and Tao Xiong

This article tells me one important thing. LDA or Fisher discriminant criterion is still being studied by lots of guy. Last time I read one by Manli Zhu, in which they propose another different criterion than the traditional ones when the co-variance matrix is rank-deficient.

One of the simplest idea is applying a ridge purturbation to the singular with-in class covariance matrix, which is usu. called regularization. The other is finding an approximation in the principal subspace of S_w. Zhu's idea roots from the latter one, in which all principal directions are selected for later general eigenvalue problem. Zhu rejects those principal directions that are almost perpendicular to the subspace spanned by S_b.

In this paper, the author mentions several other strategies for dealing with the singularity of S_w, two of which they put attention to Orthognal LDA (OLDA) and Null Space LDA (NLDA). Their main result is they yield the same result under certain condtions. The condition is mild when dealing with high dimensional data (the number of dimension is much higher than the number of samples).

I guess I will review this article after I check those LDAs, which personally I suspect their usability. Here are those literatures:

• A new LDA-based face recognition system which can solve the small size problem, Pattern Recognition 33 (2000) by Chen and et al.
• Solving the small sample size problem of LDA, ICPR 2002, by Huang and et al.
• Characterization of a family of algorithms for generalized discriminant analysis on undersampled problems, JMLR 2005.
• Penalized discriminant analysis, Anals of Statistics 23 (1995) by Hastie and et al.

Semi-supervised Nonlinear Dimensionality Reduction

by Xin Yang, Haoying Fu, Hongyuan Zha, Jesse Barlow

I guess those guys working on semi-supervised manifold learning are far away from practical applications. In this paper, the so-called SS-LLE and SS-LTSA are so obvious that they are not mentioning. Just consider the original algorithm, since the optimization will result the required coordinates while now some of them are known, the blockwise formulation will immediately show us the semi-supervised problem is an even easier one to solve.

Something a little more difficult is how to make the traditional ISOMAP semi-supervised. Since in LLE and LTSA, the to-be-minimized term has the meaning that the reconstruction error in the corresponding settings should be minimized. However, as a spectral embedding, the optimization in ISOMAP doesn't share a similar meaning. They use an ugly way to incorporate their idea in the case of ISOMAP:

As you can see, A is the Gram matrix obtained after the double-centering step in ISOMAP. With the shifting of the eigen values, now the desired coordinates can be obtained in the terms of M, which is similar to the one in LLE and LTSA. But somehow you can sense their non-sense. Their paper states a similar result, complaining SS-ISOMAP is not as good as the other two.

Maybe their latter part is more interesting, analysing the numerical stability of their algorithms. But somehow it is not a mathematical paper and I don't like their style in machine learning.

Statistical Debugging: Simultaneous Identification of Multiple Bugs

by Alice X. Zheng, Michael I. Jordan, Ben Liblit, Mayur Naik and Alex Aiken

Look at those authors' addresses, CMU, Berkeley, Wisconsin-Madison and Stanford and consider who Jordan is. I am really curious how statisical learning is applied to such a delicated area, debugging. In my personal experience, debugging is really time-consuming and confidence-consuming :-p

However, I don't think that paper gives me a basic idea of how it is gonna work. Perhaps I have to know what they did previously. Here are several paper in its references:

• Statistical debugging of sampled programs, NIPS 2004, the same authors
• The first author's home page. I find her a Ph.D. of Jordan and now post-doctor at CMU. Astonished.

Parallel Analysis

This technique is used to decide the dimension for PCA. I know little about its theory and I am searching for some related materials.

The current algorithm I am applying for my experiments is very simple. It is only required to do a PCA once more. For example, X is the data matrix whose vectors are samples. Then each row of X should be randomly permuted when the new PCA is applied to it. Then compare the eigenvalues (sorted in the descending order) of the two. The dimension for PCA is the number of eigenvalues that the second PCA gets and are smaller than those the first PCA gets correspondingly.

According to the experiments result, with the dimension determined by the parallel analysis, the data and projected data yield very similar results with linear algorithms.