Semi-supervised Classification Using Linear Neighborhood Propagation

by Fei Wang, Jingdong Wang, Changshui Zhang and Helen C. Shen

The so-called linear neighborhood propagation relies on the idea from LLE. Instead of using the graph weights directly, as in former methods (c.f. Zhou and Zhu's papers, two previous paper), the weights are computed using the idea from LLE. Therefore, in a way Zhou's version is something like diffusion map, Zhu's Laplacian eigenmap while this one LLE. We may find those counterparts in manifold learning.

The procedure to calculate the weights are identical to that of LLE (by minimizing the affine reconstruction error). Then the weights are used to propagate the labels with the same objective function as in semi-supervised LLE (or landmark LLE). In this way, it eliminates the selection for a width for Gaussian kernels.

Well, why not make a LTSA version? Haha...

Manifold Learning: The Price of Normalization

by Yair Goldberg, Alon Zakai, Dan Kushnir and Ya'acov Ritov

Although many manifold learning algorithms have been proposed early from 2000, it is still seldom discussed how we can evaluate these algorithms. We may have a vague idea when we design a simple algorithm, but no further checking of these results are carried out. This paper focuses on the tough part.

The main idea of the paper is that several algorithms that exploits normalization (a feeble reason provided is to avoid collapse of projection) would not work well simply because of normalization. These algorithms include LLE, Laplacian Eigenmap (LEM), LTSA, HLLE and DFM. As is known, MVU will not suffer from this problem, though it is still a spectral algorithm (it seems that those solving largest eigenvalues are immune to this problem, they don't need normalization). An intuitive understanding of the problem is that in order to make the embedding normalized, the embedding might still be folded so as to make on several directions the data expand equally.

To analyze the properties of these algorithm, we must have a uniform framework to formulate these seeemingly unrelated algorithms. The author proposed a weight matrix W_i for each sample x_i. The projection later could be formulated as the minimization of the sum of || W_i y_i ||. Some of the weight matrices are simple vectors (e.g. LLE), while others are a little complicated. The optmization could be denoted as minimizing Phi( Y ) subject to normalization. This function is the key to understand this paper.

The embedding quality must be quantified. They mention the embedding result usually does not preserver neighborhood. However this preservation should be desired. Therefore it must be modified correspondingly: an affine transform A is allowed to be imposed on Y. The manifold learning algorithm fails if there exists another embedding Z such that it satisfies the normalization constraints and Phi( AY ) > Phi( Z ). This definition is quantifiable and computable.

With this tool, they analyze all five algorithms and propose several necessary conditions so as to make these algorithms effective, for both limited samples and asymptotic cases. They come to a conclusion that using these algorithms on real data might be problematic. It seems that this way of finding a good projection is not what practitioners want.

Label Propagation Through Linear Neighborhoods

by Fei Wang and Changshui Zhang

This is a semi-supervised learning algorithm based on graphs. First they use the idea from LLE to determine the weights for the graph (they also use the traditional way for selecting the neighborhood), however the weight has one more constraint. (in LLE the weights are those that best reconstruct the samples with the sum of 1, here additionally they have to be non-negative, which then yields a best convex combination approximation) Second they use the transductive learning idea (very similar to the ICML 06 paper on ranking graphs). The iteral procedure is paraphrased as label propagation:

To prove the convergence of the procedure, it is only necessary to analyze the eigen values of W (which they claim Perron-Frobenius theorems applies here for the non-negative matrix).

The analysis leads to another connection of their LNP with Laplacian-regularized Least Square Regression:

I must verify my intuition today.

To tackle those out-of-sample data, which turns transduction into induction, they use the similar idea to extend LLE, of coz with the additional constraint.

I am not familiar with this transductive result. But I don't think their algorithm will work any better than Laplacian-regularized least square regression. OK, let me check it.

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.

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.