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?

I have to catch up with the papers!

Now ICML 2007 has released its online proceedings. Each time there will be about 150 papers waiting to be read. Now, I still haven't finished ICML 2006, perhaps, there are still 70+.
So, I have to speed up to catch up with papers!

Optimal Dimentionality of Metric Space for Classification

by Wei Zhang, Xiangyang Xue, Zichen Sun, Yue-Fei Guo and Hong Lu

This is an ICML 2007 paper. After reading it, I found nothing really astonishing. However it gives another direction of research. The idea is based on one of the papers I read long ago, LPP. The technique of LPP is based on Laplacian Eigenmap by finding a linear transform that minimize a similar object function as Laplacian Eigenmap. However, they are both unsupervised learning techniques.

This paper however, when the Laplacian matrix is constructed, supervised information is incorporated by setting a positive value for samples of the same class, 0 for too far away samples and a negative value for samples of different classes.

Then the so-called optimal projection uses the eigen vectors of negative eigenvalues. Though the idea is simple and direct, it works anyway and the experiment and analysis are both detailed and convincing.

Ranking on Graph Data

by Shivani Agarwal

The ranking problem asks for a function which gives us an order of samples. This requirement can be found on search engines, which give the user a sequence of search results of the preferred order of the user. I don't have earlier experience of ranking problems, so I am just curious about this article. After scanning, it turns out highly related to SVM theory.

There is a ranking risk matrix that descibe the risk of ranking error.

So the empirical ranking risk can be formulated as a functional of ranking function, which is what we are looking for. As for a graph, the function degenerates to a vector. As is in SVM, a regularizer is chosen so as to smooth the function by punish the divergence of values on nearby vertices. On thinking about this, the Laplacian regularizer is a commonly used one. (Just think about the Laplacian Eigenmap, the optimized value)

Directed graphs can be treated likewise. The paper later suggests a connection to RKHS and application in bioinformatics. Indeed, multiple alignment requires a ranking result.

Since the loss function relaxed in this paper is still Hinge loss, the idea of Trading Convexity for Scalability should be applicable to it.

Graph Model Selection using Maximum Likelihood

by Ivona Besakova, Adam Kalai and Rahul Santhanam

This might be the first paper that I read on random graphs. Although I have learnt graph theory a bit so far, theoretical preparation still impedes a quick understanding. There are several comman sense in random graph theory:

• Power-law degree distr---In some graph, the degree distr looks like a exponential/geometry distr.
• Small world---The avaraged shorest length between two vertices is not as long as what we might imagine.

This paper shows the ability to describe a real world network (graph) that several random graph generating strategies might have. In order to compare them, the authors suggest comparing their likelihood value. Each generating strategy has several parameters that control the procedure and the parameters are estimated via MLE. At last, by comparison of likelihood values, the authors states the suitability of each model.

The four strategy exemplified in the paper are:

• PA model: The graph is obtained by growing from a single vertex. New vertices are added by connect to existent ones, with a preferable probability to those of large degree/lots of neighbors.
• PRG Model: First generate the ingree/outgree of each node and match them.
• SW model: The nodes are placed on a grid, which has already edges connecting the neighbors. By adding more edges according to the Manhattan distance of every pair of vertices, the final model is obtained.
• ER model: The existence of each potential edge has the probability p.

It can be seen that, MLE of ER model can be obtained easily. For others, it is somehow difficult and MCMC is adopted to overcome it. However, I decide to examine the technical details later.

A possible problem of this paper is that it doesn't take into account the complexity of the generating strategies. It is natural that the more complex a model is, it better fits the real world data. However a better fitting won't necessary yield a good explanation, since a more complicated procedure might have better fitting than one of the four models. So the conclution of this paper is dubious.

Some thinking on Parzen window and Semi-supervised learning

Here is an idea originates from the following refereces:
Pattern Classification, by O. Duda: It presents me a basic form of Parzen window. And I think it is quite natural to use other distributons instead of a uniform distribution in a super cube. So I wondered where I can find more information on this topic. PageRank then suggested severl useful links and mnauce gave several more and comments.

• Emaneul Parzen, On estimation of a probability density function and mode. Annals of Mathematical Statistics, 33(3):1065-1076, 1962.<available from JSTOR>
• B. Silverman, Density estimation for statistics and data analysis, Chapman and Hall, London, 1986<books.google>
• Asymptotic Statistics, by Vann Der vaart<in library>
• A framework for probability density estimation, by John Shawe-Taylor<PASCAL>

Learning with Kernels, by Bernhard Schölkopf and Alex Smola: There is a simple mean classifier in it which indicates that kernel framework will convert many algorithms to superior ones. And then it tells us this classifier can be taken as a difference of Parzen windows. And then I think about SVM. The solution of a SVM tells us which samples are necessary to establish a discriminant classifier and what's their weight.

Manifold Parzen Window, by Vincent, Bengio(in NIPS 2003): They suggested a method to incorporate manifold learning ideas with density estimation. The final version is not far from what I have thought about the problem, local PCA just as MFA does. But I suddenly realize that the neighborhood sellection method used by Zhenyue Zhang is also feasible here. However they indeed extended this version in their later work.

Non-local Manifold Parzen Window, by by Vincent, Bengio(in NIPS 2005). However, then they still stayed at manifold learning. They haven't progressed as fast as I imagined. Though I am still confused about the value of this work now(am silly), I guess there can be something if we try to put the problem in the field of semi-supervised learning paradigm.

Efficient Co-Regularized Least Squares Regression

by Ulf Brefeld, Thomas Gärtner, Tobias Scheffer and Stefan Wrobel

In semisupervised learning, there is an important technique called co-learning. The basic idea is to train two independent classifier. Let them mutually interact with training errors in order to agree on unlabelled examples at last. Two phrase: independent classifiers, agree on unlabelled data.

Now let's focus on what the authors show us. As is know, the framework of SVM give a regularization technique for supervised learning already. So in order to incorporate unsupervised data, add a "agreement regularizer".

Then by representer theorem, the optimization result requires O(M³(m+n)³) where M is the number of different views, m is the number of unlabelled data and n the number of labelled data.

However, usually m will be huge due to the accessibility of unlabelled data and we will suffer with a cubic algorithm. An alternative simply uses a subspace of the original RKHS, namely the one expanded with labelled data only. Then the optimization becomes the following equation:

and this can be solved in O(M³n³+M²m).

Another result given in this paper is a distributed algorithm for the optimization problems mentioned above. The algorithm called block coordinate descent is analogous to steepest gradient descent while the former one only scrambles along several coordinates associated with the message sent by another classifier in a different site.

The paper also lists several literatures on co-learning for my future study:

• Combining labled and unlabeled data, by Blum and et al.(the one who proposed co-training)
• Learning classification with unlabeled data, by de Sa, in NIPS(the first who noticed the consensus of multiple hypothesis)
• Unsupervised models for named entity classification, by Collins and et al.(a variant of adaboost)
• PAC generalization bounds for co-training, by Dasgupta and et al., in NIPS
• The value of agreement, a new boosting algorithm, by Leskes, in COLT
• Two view learning: SVM-2K, theory and practice, by Hardoon and et al., in NIPS

Here is another survey:

• Semi-supervised learning in literature survey, by Zhu