On the Influence of the Kernel on the Consistency of Support Vector Machines

by Ingo Stainwart

This is kind of math paper. I haven't really delved into some mathematical stuffs for a long time.This paper might be the first to explore the consistency of SVM (that is the asymptotic behavior of the classifier compared with the optimal, Bayes decision error). The main result might be as follows:
For universal kernels we have consistency result for L2 and L1 soft margin classifiers.
The universal kernels are those whose induced RKHS is dense in continuous function space. Gaussian and Laplacian kernels are both universal. The author derived the corresponding consistency.
At first glance I thought they find some tricks in choosing regularization parameters. But I didn't find anything truely usable (e.g. corollary 18).

The editor is Scholkopf... I guess only huge bulls like him understands the key points. For now I just have quite a faint idea.

On Sampling-based Approximate Spectral Decomposition

by Sanjiv Kumar, Mehryar Mohri and Ameet Talwalkar

This paper proposed another approximation of kernel methods based on former Nystrom method and column sampling. The prime disadvantage of the earlier method is that they must compute the whole Gram matrix while the proposed adaptive method does not need to. They prove several results (not that interesting though): column sampling is best for rank 1 approximation (no one will use rank 1 approximation I guess...); for a given form, neither is optimal approximation (that is why they are not good enough?); under some cases (looks not useful in practice), Nystrom's recovery is exact.

The improvement of approximation is not salient though, but I guess the efficiency might be improved.

Regression by Dependence Minimization and its Application to Causal Inference in Additive Noise Models

by Joris Mooij, Dominik Janzing, Jonas Peters and Bernhard Scholkopf

This paper follows the NIPS 08 paper, with a different regressor. We know HSIC could be used for dependence maximization as well as independence maximization. Here we simply use its dependence. Basically there are two ways of doing regression, one to minimize the dependence of the residual and the input, the other to maximize the dependence of the response and the prediction (is that possible?)

With HSIC it is easier to minimize the dependence of the response and the residue. The pro is that we do not need to specify the additive noise's distribution. In many regression problems, we actually assume the noise is a Gaussian. Now we may forget about the possible violation of this assumption. But the con is that now the optimization of the model will be much more difficult.

The good thing about HSIC is that we have a statistical test, which allows us to judge whether it is statistically reliable to assert the independence. I am not sure whether we have a similar statistic for KDR-like terms.

Nonlinear Causal Discovery with Additive Noise Models

by Patrik O. Hoyer, Dominik Janzing, Joris Mooij, Jonas Peters and Bernhard Scholkopf

This paper talks about making causal inference from data. We know if two r.v.s have an additive linear relationship (with noise), the reverse relationship also holds. If there is a non-linear relationship, our causal inference will be easier since the inverse might not hold. This is the main result of this paper, finding if there exists a reverse relationship, the probability must satisfy a differential equation. From this equation we know, if \nv''' = \xi''' = 0, where the two function are the logarithm of the PDF of x and the additive noise n, f must be linear.

This also suggests a way of making causal inference on DAGs. This leaves us to find a powerful regressor to capture the possible relationship between two r.v.s. The authors chooses GPR. Then the residue should be statistically independent of x, which can be tested with HSIC.

However, if we are to find the latent structure instead of doing a statistical test, this search will be intolerable if the DAG size is beyond 7.

Geometric-aware Metric Learning

by Zhengdong Lu, Prateek Jain and Inderjit S. Dhillon

This is an extension to the ICML 07 paper, with introduction of graph regularization. The idea is to find a pair of kernel matrices, one from task-dependent kernel set and the other from a parametrized data-dependent kernels. The two sets are quite different. The former is used in later classification or related tasks and they choose the Mahalanobis kernel. The later contains locality information and is created with the graph kernels (a subspace spanned by the eigen vectors corresponding to the smallest eigenvalues of the Laplacian matrix). To measure the similarity of the two distance, the Bregman divergence is employed. the difference between the current optimization and the one in the ICML 07 paper is that the other matrix is not fixed. The rough idea is to update them alternatively (just as in LSQ in tensor).

We may change the data-dependent kernel for different tasks (e.g. unsupervised tasks using graph kernels, supervised tasks using labels). There are connections with regularization theory: the solution has a representation of a combination of graph kernel and another term which can be interpreted as a regularizer. Another possible connection is to GP: GP could be regarded as a special case of the proposed framework. I think this topic is by then very interesting. I will come back later to this topic when I have time.

Characteristic Kernels on Groups and Semigroups

by Kenji Fukumizu, Bharath Sriperumbudur, Arthur Gretton and Bernhard Scholkopf

First let's see some key ideas in kernel-based methods for r.v.s:
To see whether two r.v.s have the same distribution, we test the mean of arbitrary function values for two r.v.s. The leads to distances between two means in the RKHS \mathcal{H}. Hence we introduce an map of the r.v. X into the linear functional of a RKHS \mathbb{E}_X K(\cdot, X). Then for arbitrary function f \in \mathcal{H}, the mean value is \mathbb{E} \langle K(\cdot, X), f(\cdot) = \mathcal{E} f(X). Given two r.v.s X, Y, we can see the discrepancies on any given function f \in \mathcal{H}, \mathrm{MMD}(X, Y; \mathcal{H}) = \max_{f \in \mathcal{H}} \E f(X) - \E f(Y). In practice we calculate the empirical squared version.

The critical problem of this method is the mapping from the r.v. to the linear functional is unique. Given that the conjugate space of the RKHS is simply itself, we can also interpret this as the uniqueness of the mapping from the r.v. to the feature space (RKHS) is unique. Please notice the RKHS is induced by the kernel and their relationship is one-to-one. Hence the thing that matters is what kind of kernel might cause the uniqueness of the mapping.

This is explored in this paper, the so-called characteristic kernel, which has the property that the induced mapping is injective. With this kind of kernel, criterions such as MMD will be a well-defined distance between two r.v.s (or measures as in the paper). Here are some main results:
Lemma 1. Let (\Omega, \mathcal{B}) be a measurable space, k be a measurable, postive definite kernel on \Omega and \mathcal{H} be the corresponding RKHS. Then k is characteristic iff \mathcal{H} \oplus \mathbb{R} is dense in L^2(\mu) for every probability \mu on (\Omega, \mathcal{B}).

A positive definite function \phi is one such that the induced kernel k(x, y) = \phi(y^{-1} x) is positive definite. Here the inverse is defined on a group. E.g. for \mathbb{R}^n the linear space, the group is simply defined by the vector addition, therefore we get kernels in the form of k(x, y) = \phi(x - y) which is simply the so-called RBF. Gaussian kernels, Laplacian kernels are both in this domain. They are called shift-invariant kernels. Bochner theorem characterizes all the shift-invariant kernels defined on \mathbb{R}^n: all these functions are characteristic function (Fourier transform) of a given Borel measure.

With some analysis they come to the result if the shift-invariant kernel induced by positive definite function \phi is characteristic, the corresponding Borel measure has \mathbb{R}^n as its support or we may say the inverse Fourier transform of \phi has \mathbb{R}^n as its support.

This paper takes the result furthur onto more general algebraic structures, i.e. groups and semi-groups. Their claim is as long as we might find an analog of Fourier transform, we might have something similar to Bochner's theorem. So the algebraic structure is a locally-compact Abelian group.

The paper also consider non-Abelian groups and semi-groups. They get similar results. It's very theoretical... hmm... not enough mathematical preparation though.

Supervised Feature Selection via Dependence Estimation

by Le Song, Alex Smola, Arthur Gretton, Karsten M. Borgwardt and Justin Bedo

Feature selection has been mentioned in a KDR paper. This paper uses HSIC and backward greedy algorithm. That's each time they pick up a dimension to throw away while the rest has the highest HSIC. I thought they might throw away the one with lowest HSIC but they enjoyed using HSIC as an lower bound of dependence.

The paper also mentions the connection between HSIC and other criterion such as MMD in a prevously scanned paper and KTA (it looks like an uncentered version of HSIC).

A Dependence Maximaization View of Clustering

by Le Song, Alex Smola, Arthur Gretton and Karsten M. Borgwardt

HSIC is an upper bound of the COCO which in theory has been proved to be equivalent to independence. Therefore HSIC can be used as an independence test. However, as an upper bound, it might not be suitable if we want to maximize the dependence of r.v.s IMHO. So the motivation of using HSIC for this purpose (clustering) is still vague.

For clustering, we maximize

\tr HK_xH K_y

for making features and labels dependent. So we have to find a kernel for the discrete variable y: delta kernel; or the kernel in the paper,

\Pi A \Pi^\top

where A is the Gram matrix for different clusters and \Pi is the assignment matrix. The paper also consider other kernels, relating this algorithm with kernel PCA (maybe kernel k-means also?).

The optimization is quite difficult as other clustering algorithms. It initialize an assignment matrix randomly and repeat updating the assignment matrix until it converges. We loop by the samples, finding the best assignment that maximizes the HSIC. Please notice the matrix A will be updated when the assignment matrix is updated. Like k-means, each sample has the same weight and A is simply a diagonal matrix with the inverse of number of samples in this cluster. Another choice generalizes the weights. This leads to a family of clustering algorithms by choosing A.

Maybe it's worth considering about the designing idea more carefully.

A Kernel Approach to Comparing Distributions

by Arthur Gretton, Karsten M. Borgwardt, Malte Rasch, Bernhard Scholkopf and Alexander J. Smola

This paper takes advantage of kernel method to test whether two r.v.s have the same distribution. The idea is very close to independence test based on kernel method. We know two r.v.s \mathbb{E} f(x) = \mathbb{E} f(y) if their distribution is identical. Given a large enough function set, we may use

\mathrm{MMD}(\mathcal{F}, x, y ) = \sup_{f \in \mathcal{F}} \mathbb{E} f(x) - \mathbb{E} f(y).

Then we try some universal kernel and its corresponding RKHS. With some derivation, the empirical evalutation of MMD is based on

\mathrm{MMD}^2(\mathcal{F}, x, y) = \mathbb{E} \langle \phi(x), \phi(x')\rangle + \mathbb{E} \langle \phi(y), \phi(y')\rangle - 2 \mathbb{E} \langle \phi(x), \phi(y)\rangle \approx \frac{1}{m^2} \sum_{i, j = 1}^m k(x_i, x_j) + \frac{1}{n^2} \sum_{i, j = 1}^n k(y_i, y_j) - 2 \frac{1}{mn} \sum_{i = 1}^m \sum_{j = 1}^n k(x_i, y_j).

I am not sure whether a later work in NIPS 2008 is based on this, which will be scanned soon.

Measuring Statistical Dependence with Hilbert-Schmidt Norms

by Arthur Gretton, Olivier Bousquet, Alex Smola and Berhand Scholkopf

This paper uses the so-called Hilbert-Schmidt norms instead of L^2 norm (corresponding to the COCO independence test) in the previously scanned paper, resulting in the so-called HSIC (Hilbert-Schmidt independence criterion), which is in practice much easier to calculate. Compared with COCO, which using the square root of the largest singular value of \tilde{K}^{(x)} \tilde{K}^{(y)}, HSIC actually uses the whole spectrum, i.e. the trace of \tilde{K}^{(x)} \tilde{K}^{(y)}. Since the Frobenius norm is an upper bound for the L^2 norm, therefore the similar independence equivalence can be obtained.

Please notice the relationship of KCC, COCO and HSIC. For KCC, we use the maximum kernel correlation as the criterion for independence test, but then we have to use the regularized version to avoid the common case when it does not give desired result. In COCO, we constrain both covariances to identity and then the the problem becomes seeking the largest singular value of the product of two centered Gram matrices while KCC solves the generalized eigenvalue problem. Therefore when we deal with multiple r.v.s, we can do it in the same ways as CCA does. So in a way you know why it is called COCO. These three ideas are closely related, just as in the KMI paper, KMI and KGV are closely related.

Kernel Constrained Covariance for Dependence Measurement

by Arthur Gretton, Alexander Smola, Olivier Bousquet, Ralf Herbrich, Andrei Belitski, Mark Augath, Yusuke Murayama, Jon Pauls, Bernhard Scholkopf and Nikos Logothetis

For measuring independence, they propose another kernel-based criterion COCO (constrained covariance, in a previous paper, it is called kernel covariance, KC, however their objective actually comes from the multual information of Gaussian r.v.s) other than the previously scanned paper of Jordan's (KCC and KGV). This has been mentioned in their earlier work.

This work has quite different concerns. Since previous papers did not say how to choose the kernels. They prove COCO is only zero at independence for universal kernels. The so called universal kernel is a kernel such that on a compact metric space (\mathcal{X}, d), the RKHS induced by the kernel k(\cdot, \cdot) is dense in the continous function space over \mathcal{X}, namely C(\mathcal{X}) w.r.t. the topology induced by the infinity norm \| f - g \|_\infty. They proved Gaussian kernels and Laplacian kernels are universal.

They also point out the limitation of independence tests based on universal kernels. The proposed COCO also has its adversary. That is when we do have small COCO, the r.v.s are still dependent. But they found their calculation of COCO has an exponential convergence rate to the true COCO value.

The calculation of COCO is equivalent to

\mathrm{COCO}(z, F, G) = \frac{1}{n}\sqrt{\| \tilde{K}^f \tilde{K}^g \|_2}.

Their later paper actually uses Frobenius norm. Their experiment shows an example of applying COCO to ICA on fMRI data, compared with KMI and correlation method (only using correlation as a testing of independence).

The Kernel Mutual Information

by Arthur Gretton, Ralf Herbrich and Alexander J. Smola

We know mutual information can be used to test the independence of r.v.s. The difficulty with mutual information is that the distribution is usually unknown, either we have to make a density estimation or entropy estimation from samples.

This paper introduces the so-called KMI (kernel mutual information), which in practice has comparable performance with KGV (in Bach and Jordan's paper). It comes from measuring the mutual information between two multi-variate Gaussian vector,

I(x; y) = -\frac{1}{2} \log \left( \prod_{i = 1}^{\min(p_x, p_y)} (1 - \rho_i^2)\right).

We use the correlation in the RKHS for this \rho_i,

\rho_i = \frac{c_i^\top( P_{x, y} - p_x p_y) d_i}{\sqrt{c_i^\top D_x c_i d_i^\top D_y d_i}},

where P_{x, y}, p_x, p_y, D_x, D_y are approximated with samples and an assumed grid(it will be cancelled out in the end). By relaxing the denominator (to a bigger value), we find an upper bound for the mutual information,

M(z) = -\frac{1}{2} \log\left( \big| I - (\nu_x \nu_y)\tilde{K}^{(x)} \tilde{K}^{(y)} \big|\right),

where \tilde{K}^{(x)} and \tilde{K}^{(y)} are centered Gram matrices. This is the criterion for KMI. Since it's an upper bound for the mutual information, we can use it as a contast function (I don't know why the authors think we ca derive the result from the theorem 1, confused about their idea).

In their formulation, (regularized) KGV can be regarded as another way of relaxing the covariance. Therefore likewise this independence measurement can also be used for ICA task. In a way, this paper is a generalization of KGV, but I am still confused about their idea.

==
later I realized that the KMI is the upper bound of KC, therefore when KMI = 0 the KC will be 0 too.

Dimensionality Reduction for Supervised Learning with Reproducing Kernel Hilbert Spaces

by Kenji Fukumizu, Francis R. Bach and Michael I. Jordan

This paper tells us one way of SDR (sufficient dimensionality reduction) using KDR (kernel dimensionality reduction), though it has a somewhat different path to reach the conclusion. I will scan the earlier nonparametric version.

This model proposed by the author is kind of semi-parametric. The sufficiency of a dimensionality reduction algorithm for a regression problem is that y is independent of x conditioned on the projection of x in a subspace (let the projection be Px = u and v is the residual). Therefore either we maximize the mutual information of y and u or we minimize the mutual information of y and v. Consider about the KDR technique: the mutual information can be approximated with Kernel CCA or KGV (kernel generalized variance).

The different derivation starts with two definitions: one for covariance operator and the other conditional covariance operator. In a way, these operators formulates the idea of ``two r.v.s are independent when arbitrary functions of them are independent,'' but in a more abstract and rigorous way. With these concept we know that the conditional covariance operator Σ_YY|U is no less than Σ_YY|X and the equality happens when Y is independent of V. And Σ_YX|U = 0 when Y is independent of V.

When we concretize these operators with matrices, we have the same formulation as in KDR. Therefore the optimization is done in the same way. This procedure is analogous to feature selection and may be applied to variable selection.

Kernel Independent Component Analysis

by Francis R. Bach and Michael I. Jordan

ICA has long been studied by researchers from signal processing, machine learning and alike. However, though the independency can be depicted with mutual information mathematically, it is not computable in practice. Many ideas have been proposed: approximation of mutual information (e.g. using moments) or finding an alternative contrast function (kurtosis).

In recent years, I noticed Bach does have published lots of papers in machine learning and I found him another student of Jordan. What a supervisor! After reading this piece of work, I have no doubt about their novel ideas of approaching ICA. This relates to a later work closely. The idea of ICA: independent components, must be formulated with a certain idea and the independency calculated in this way will surely be applicable to other problems as well, e.g. one concept of dimensionality reduction for regression (supervised dimensionality reduction) is sufficiency: finding a subspace such that the response y is independent to x conditioned on the projection of x onto it. Therefore it is the key idea to understand the following papers to be scanned.

There are several steps in tackling the independency:

• Correlation-to-independency: if x and z are independent, then f(x) and g(z) will be independent and therefore will be uncorrelated (correlation coefficient is 0). Though given a fixed (f, g), we cannot assert that x and z are independent given f(x) and g(z) are uncorrelated, it holds that x and z are independent if for arbitrary (f, g), f(x) and g(z) are uncorrelated (then we can put Fourier transform into it).
• Kernel provides us with RKHS, which means we can use many many functions for the r.v. to be tested. But empirically with given samples, for ICA we have to minimize the maximum correlation of x and z with all pairs of (f, g).
• The maximum correlation can be obtained with standard CCA idea or it's kernelized version (a generalized eigenvalue problem). This can be extended to multiple r.v.s (variables or vectors). It is argued that the smallest eigenvalues (for (C, D)-generalized eigenvalue problem, where C is the co-variance matrix, K_iK_j in kernelized form and D is a regularized diagonal variance matrix (K_i+sI)²) are more suitable. (KCCA as a contrastive function.)
  
• The last idea is that when the r.v.s are Gaussian, the mutual information is -log( |C|/|D| )/2. So we just need to minimize this. This is another contrastive function (kernel generalized variance, KGV).
  

So we must get these ideas into a working algorithm. There are several important tips,

• As in ICA, we first whiten the data Y such that we have 0 mean and unitary covariance. Then we just need to find an orthogonal matrix instead of an affine transform.
• The matrix (C, D) which, converted into a eigenvalue problem, is too difficult to compute. Therefore we need to approximate this matrix with incomplete Cholesky decompostion (another candidate is Nystrom approximation).
• Please notice the optimization is constrained on the orthogonal matrix, which is on a Stielfel manifold. We must use the gradient on this manifold (so as not to break the constraints). The overall optimization is simply steepest gradient decent.
• The author then proposed two possible initial values for gradient decent. One point is when we use a kernel which implies complicate features, the optimization might be tough while a simple kernel such as polynomial kernels might be easier for the optimization.
  

This journal paper contains much more information about everything :-D I will return to it when considering implementation.

Diffusion Kernels on Graphs and Other Discrete Structures

by Risi Imre Kondor and John Lafferty

This paper introduces a diffusion kernel for graphs. First please notice that the exponential of any symetric matrix is positive definite and therefore is a Gram matrix. Then we consider a diffusion process. At time t, each node would give a proportion α of its value to it neighbors. In matrix form, it corresponds to the negative Laplacian of a graph and we simply use it for the generating matrix of the kernel (diffusion kernel).

The authors studied its continuous form, its relationship to random walks on graphs and cases on special graphs. The interesting findings are: 1) Gaussian kernel on graphs is a special case of diffusion kernel; 2) its application in images and strings.

Fast Sparse Gaussian Process Methods: The Informative Vector Machine

by Neil Lawrence, Matthias Seeger and Ralf Herbrich

This NIPS paper doesn't cover much as the technical report does. They are exploring a sample selection methods for Gaussian processes. They have studied regression, classification and ordinal regression problems. The idea originates from ADF (looks like EP). It is a kind of greedy algorithm that selects the best d samples that maximizes a certain criterion---differential entropy score.

I am thinking about Nystrom approximation. The two methods have different intention (perhaps?): IVM aims at finding sparse representation (just like what SVM achieves via optimization, IVM is a little brute-force though); Nystrom method is a more general approximation method for all kernel methods. The former is supervised while the latter unsupervised.

But is IVM extensible for other kernel-based classifiers and regressors?

Exploiting Generative Model in Discriminative Classifier

by Tommi S. Jaakkola and David Haussler

This is a classic semi-supervised style of learning. First a generative model is trained with all samples without labels. The generative model has parameters and the Fisher information matrix I could be calculated (Hessian of the Likelihood function). With this a kernel could be introduced as the quadratic form of the score:

k( x, z ) = U_x^T I^-1 U_z

The kernel could be exploited by later discriminative models, such as GLIMs and SVMs.

It can be easily proved the proposed kernel has several nice properties:

• It is a qualified kernel.
• As Jeffreys's rule, it is invariant under continuously differentiable transform of parameters.
• A kernel classifier employing this kernel derived from a model whose latent variable is the label is asymptotically as good as a MAP labelling.

Using the Nyström Method to Speed Up Kernel Machines

by Christopher K. I. Willians and Matthias Seeger

This is an old paper, which I must scan for recent research. The Nyström method originates from the numerical solution of integral equations. Since in kernel methods, we have to eigen decompose a large Gram matrix (of size N, the number of samples), which requires O( N3 ).

The eigen decomposition yields the basis functions evaluating at the sample points and the eigenvalues, which could be used to approximate the basis functions evaluating at an arbitrary position. This is the so-called Nyström method. What this paper says is to select randomly a subset of the samples, for which the required elements in Nyström method are derived. As is written in the paper, only comparatively small amount of calculation needs to be done.

This technique is verified on Gaussian Process in the experiment, yielding a good approximation.

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?

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