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

A DC-Programming Algorithm for Kernel Selection

by Andreas Argyriou, Raphael Hauser, Charles A. Micchelli and Massimiliano Pontil

There are several points in this paper:
One single kernel might not be desirable, since if we know nothing about the data, the kernel is selected empirically from a set of known kernels.
Given a set of parameterized kernels, how is it possible to select one that is the convex combination of them? The authors mention a finite representation in Learning convex combinations of continuously parameterized basic kernels (in COTL 2005).

A procedure for calculating the kernel selection is illustrated in the following algorithm:

The first step is carried out in convex optimization algorithm and the second is a DC programming problem. The stopping criterion ensures the procedure will increase the object function.

But it is a little strange why Step 2 is a DC programming problem. The authors cite a result from On functions representable as a difference of convex functions by Hartman, which implies:

• Every two continuously differentiable function on Omega is DC;
• Every continuous function on Omega is the limit of a sequence of DC functions that converges uniformly on Omega.

I have to check these things.

A New Approach to Data Driven Clustering

by Arik Azran, Zoubin Ghahramani

Well, on seeing Ghahramani, I guess it's no easy job @@ At first I was curious why their starting point resembles a lot from the paper on diffusion map. But soon I knew I was wrong. The first author is a Ph.D. student whose advisor is the second author. I wonder when I can publish a paper like he did in the top conferences. Sigh~ Maybe never.

Like diffusion map, they show us a Markov random walk model on a graph of samples. Then they notice the similarity of distributions starting at each sample can help clustering. They propose a clustering algorithm analogous to K-means(the proposed version minimizes KL divergence instead of L² norm). The optimization problem can be solved as K-means, yielding an local minima. I thought they might stop here, but they didn't.

Careful readers notice that the number of clusters, K and the time t for random walk are not determined yet. So the following part deals with these two parameters. Given K, learn t. It's an easy problem. If the distribution matrix should be maximally preserved, low rank approximation will take the leading eigen values and we abandon the rest when the gap between them is maximized.

Then how can we obtain the desired parameters from data? Well, it's not that difficult. With the similar idea, when some gap is maximized while we don't know which K.

But then, is it possible to formulate a hierarchical clustering algorithm with this random walk? Well, use the gap size as the plausibility for the partition. Choose the smallest number of plausible clusters(big gap and few clusters). And do partition and recursively carry out the algorithm.

A piece of fresh work needs few references.

A Regularization Framework for Multiple-Instance Learning

by Pak-Ming Cheung and James T. Kwok

God... I see the name again... James T. Kwok 郭天佑. Although he's an associate professor, I have heard him very active in the field of machine learning. And last November I saw him in the conference held in Nanjing for native experts in this area. The name of the first author... I thought he was the one Tak-ming Chan :-(

In this paper, I find more information on multiple instance learning, esp. formal formulation of the problem. Thanks to Prof. Zhou's talk for us, I follow the idea of the authors without much trouble. However, as is introduced in this paper, many SVM-based algorithms in MIL were proposed in the past few years, which I am not quite familiar with. So I listed several literatures at the end from the refereces for future study.

The authors emphasize that they put not only bag regularizers but also instance regularizers to the original SVM objective function. Then they prove the representer theorem in this case so as to formulate the dual form. In the latter one, it can be easily seen that the optimization is not convex. There is a DC-style constraint. So C³P can be applied. Later they examine the regression problem as well.

I decide to stop scanning for a while(in a week's time). I have to peruse the SVM theory and these related stuffs. I guess then I will review all these papers and see whether I can understand better.

Here are several references:

• Support vector machines for multiple-instance learning, by S. Andrew and et al., in NIPS 2003
• Solving the multiple instance problem with axis-parallel rectangles, by T. Dietterich and et al, in AI
• Supervised versus multiple instance learning: An empirical comparison, by S. Ray and et al., in ICML 2005
• Multiple Instance Regression, by S. Ray and et al., ICML 2001
• EM-DD: An improved multiple-instance learning, by Zhang Q., in NIPS

Trading Convexity for Scalability

by Ronan Collobert, Gabin Sinz, Jason Weston and L\'eon Botton

The significant information the author wanna show us is that it might not be forbidden when the objective function is not convex. The paper demonstrates us how to solve a non-convex case when the objective is a diference of convex functions by ConCave Convex Programming(CCCP, C³P). The idea is illustrated in the following picture.

Then SVM with Hinge loss is critisized since the number of SVs will increase linearly when the training set grows larger, at last hindering the training and recognition. By analyzing the objective function and according to the Fermat's lemma, those misclassified samples become SVs because the derivative of Hinge loss there is not zero and according to KKT condition, they are SVs.

So the loss function is replaced with Ramp loss, which is the difference of Hinge loss with another convex function.

And then the objective of SVM can be regarded as a difference of convex fucntions and can be solved with C³P.

This technique also applies to TSVM, because the difficulty of TSVM is the non-convexity of the objective. So the algorithm can be used without a touch. The original penalty for unlabelled samples, namely symmetric Hinge loss, now is substituted for an extended version, difference of Ramp loss.

Here are some related work to be checked:

• On (psi)-learning, by Shen, X. and et al., Journal of the American Statistical Association
• Convex Neural Networks, by Bengio, Y. and et al., in NIPS
• Convex methods for transduction, by Bie, T.D. and et al., in NIPS
• Semi-supervised classification by low density separation, by Chapelle, O. and et al., Workshop on AI and Stat.
• The Concave-Convex Procedure, by Yuille, A.L. and et al, in NIPS

Locally Adaptive Classification Piloted by Uncertainty

by Juan Dai, Shuicheng Yan, Xiaoou Tang and James T. Kwok

It is known that the region mixed with samples from different classes requires special attention in the classification task. So how should be model these regions? The authors propose a criteria for this property, uncertainty, which is simply the similarity of samples from other classes divided by the total similarity of the whole region(nearest L neighbors), where the similarity is analogous to that of Laplacian eigenmap(heat kernel). Then each sample is associated with an uncertainty factor. GMM is adopted to describe the distribution of the uncertainty. Here the only difference between the original GMM and the one here denoted as RMM is the log-likelihood function of the latter one is weighted by uncertainty factors.

But the model can still be trained with EM algorithms as with GMM. The RMM tells us the probability of each sample's membership of each Gaussian(cluster).

Then for each cluster, it is desired to find a linear transform(reduction) such that

the sum of correctly-classified probability weighted by the probability of membership of the corresponding cluster(c.f. the equation below)

is maximized. This objective function is not necessarily a convex one, so gradient descent with simulated annealing is applied.

To classify a testing sample, first find the probability of its membership of each cluster. And the class it belongs to is the one that maximizes correctly-classified probability weighted by the probability of membership of corresponding cluster.

This work is related to NCA(neighborhood component analysis) when the number of Gaussians is 1. And we might read something on loc boost(Localized boosting by Meir, R and et al.)

ps: These equations are copied from the original paper, thus copyrighted by the authors above.