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.

Simpler Knowledge-based Support Vecor Machines

by Quoc V. Le, Alex J. Smola and Thomas G\"artner

This paper proposed another version of knowledge-based SVM. The former versions can be regarded as adding constraints to the original SVM. To ensure the optimization can still be solved in quadratic programming, the polyhedra-like constraints might introduce non-separability into the separable cases.

The authors of this paper introduce a transformation of the classifier f. The transformation ensures constraints in several cases, e.g. fixing labels for several samples in binary classification, setting an upper and lower bound for regression, setting monotonicity, exclusion of some labels in multi-class classification, setting the even or odd property. It seems a more general method compared to the former version. I don't quite catch the analysis part of this paper. Their result seemingly relies upon the transformation adopted. Sometimes, they are lucky to find a convex optimization problem while they have to use C³P and other analogous techniques for non-convex optimization problems.

Basically, to further understanding this paper, I have to explore the following papers:

• G. Fung, O. Mangasarian and J. Shavlik: Knowledge-based support vector machine classifiers, NIPS 2002.
• O.L. Mangasarian, J.W. Shavlik and E.W. Wild: Knowledge-based kernel approximation, JMLR 2004.
• Rademacher complexity

Tangent Distance Kernels for Support Vector Machines

by Bernaard Haasdonk, Daniel Keysers

This is a CVPR paper in 2002.

This paper doesnot explore the relationship between kernels and tangent distance(TD), which is difficult. On the contrary, they proposed two ways of incorperating both of them in a way:

• Run SVM to find sorpport vectors. Compute the TD between SVs for classification.
• Choose arbitrary RBKF, such as Gaussian, replace the Euclidian distance with TD.

Somehow, it is desirable to find a kernel representing the TD space, which is not Hilbert space, which is infeasible theoretically. Is there any other ways out?