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.

Probabilistic Dyadic Data Analysis with Local and Global Consistency

by Deng Cai, Xuanhui Wang and Xiaofei He

This paper introduces a graph regularizer for PLSA. There are some interesting stories behind the NLP algorithms such as PLSA, LDA (latent Dirichlet allocation), I think, but I am not quite familiar with them. From the modeling aspect, they deal with the same thing. Given a term-document matrix, X, the element of which is the count of occurrences of a given word w_j in the document d_i. The generative model is each document is a mixture of multinomial distribution. Namely, we have several latent topics z_k such that a document is a mixture of the topics z_k with the mixing proportion \Pr(z_k \mid d_i). Each topic decide a kind of ditribution for the words, namely \Pr(w_j \mid z_k). The PLSA algorithm simply uses EM to train the mixture model.

The LDA is not as far as I think. It's just a Bayesian version of PLSA. We know the natural extesion of mixture models in frequentists' domain is adding a Dirichlet prior for the proportion of the latent variable. And the more sophisticated technique is non-parametric Bayesian, adding a Dirichlet process as the prior. The fully Bayesian method need the posterior distribution which is approximated with (global) variation inference.

The two algorithms do not take into consideration the local information. This paper simply adds a regularizer to the PLSA loss (-log likelihood). Here the authors assume if the documents are similar, their mixing proportions must be similar. So if d_{i_1} and d_{i_2} are similar, according to some rules (labels in classification or cosine of the angle between two tf-idf vectors in unsupervised case), the two distribution \Pr(z_k \mid d_{i_1}) and \Pr( z_k \mid d_{i_2}) are similar. This similarity is measured with the symmetric KL divergence:

\min -\sum_{i = 1}^N \sum_{j = 1}^M n(d_i, w_j) \log\sum_{k = 1}^K \Pr(w_j \mid z_k) \Pr(z_k \mid d_i) + \frac{\lambda}{2} \sum_{i_1, i_2 = 1}^N W_{i_1, i_2} \big( D(\Pr(z_k \mid d_{i_1})\parallel \Pr(z_k \mid d_{i_2})) + D(\Pr(z_k \mid d_{i_2})\parallel \Pr(z_k \mid d_{i_1})) \big)

The optimization can still be solved with EM with a little approximation. The difficult part is the maximization step.

The result is really good: in unsupervised case, it is better than NMF and PLSA, LDA and even N-cut.

Information Theoretic Metric Learning

by Jason V. Davis, Brian Kulis, Prateek Jain, Suvrit Sra and Inderjit S. Dhillon

This paper talks about a metric learning algorithm. The basic tool is the so-called Bregman divergence. the setting is to find a Mahalanobis distance, therefore a matrix A for inner product (x^\top A x). The trick is we need our matrix A is as close as to a given A_0, which is achieved via the KL divergence of two Gaussians with A_0 and A as their covariance matrix respectively. We further have two sets, one including pairs of samples that are near (their distances are less than a threshold), the other including dis-similar ones (their distances are larger than another threshold). It can be derived the KL divergence is actually a form of Bregman divergence and equals \mathrm{LogDet}(A_0, A) = \mathrm{tr}(A A_0^{-1}) - \log \det A A_0^{-1} - n. The constraints are linear to the matrix A to be optimized. This distance is the only scale-invariant and the loss leads to uniform minimum variance unbiased estimator. As SVM, we may introduct slack variabls to tackle the infeasible cases. To solve this optimization, a former algorithm (ICML 2006 paper) is extended.

There are some connection to the previous work to since it can be proved the low-rank kernel matrix is simply induced by the Mahalanobis kernel we find in the proposed metric learning algorithm. And the paper also addresses the online metric learning problem. They prove the proposed algorithm will converge.

Robust Feature Extraction via Information Theoretic Learning

by Xiao-Tong Yuan and Bao-Gang Hu

This paper is based on the so-called Renyi's entropy, which is defined as

H_2(p) = -log \int p^2(x) \,\mathrm{d} x

Given a random variable x's sample, the empirical Renyi's entropy is estimated with kernel density estimator

\hat{H}_2(X) = - \log \hat{V}(X) + \text{const}, \qquad \hat{V}(X) = \sum_i \sum_j g(x_i - x_j, \sigma)

where g(x-z, \sigma) = \exp( -\| x - z \|^2 / 2\sigma^2). \hat{V}(X) is called information potential. For two r.v.s, we have similar result,

\hat{H}_2(X_1, X_2) = -\log \hat{V}(X_1, X_2) + \text{const}, \qquad \hat{V}(X_1, X_2) = \sum_i \sum_j g(x_i^{(1)} - x_j^{(2)}, \sigma)

where the second term measures the correlation of two r.v.s.

The proposed objective is to find a projection Y = WX such that

\max_{W} (1 - \lambda) \hat{V}(WX) + \lambda \hat{V}(WX, C) - \gamma \| W \|_\text{fro}^2

They find that when \lambda = 1 we have a so-called robust M-estimator. The optimization algorithm they find is very similar to majorization minimization (auxilliary function). The interesting relationship they listed in the paper includes that with LPP. The iterative algorithm solves a LPP/LapRLS/SRDA in each iteration.

I am afraid this looks quite like the unsupervised HSIC for SDR problem. I will check it soon.

A Majorization-Minimization Algorithm for (Multiple) Hyperparameters Learning

by Chuan-Sheng Foo, Chuong B. Do and Andrew Ng

First we must understand what the majorization-minimization (MM) algorithm is. It is in fact the auxilliary function method, which might be regarded as a generalization of EM algorithm. To minimize (maximize) a function L(x), we find an upper (lower) bound for the objective which is more easier to minimize (maximize), Q(x; x') where the x' is the parameter for the upper (lower) bounding function. This can be seen as a generalization of the idea of CCCP, since in CCCP, we use linear functions to bound the convex (concave) functions and the parameter is simply the variable introduced by Legendre-Fenchel transform. And we require L(x) - Q(x; x') reaches its minimum (maximum) at x = x'. As we can see here, the following inequality holds

L(x) \leq Q(x; x') \qquad \text{or} \qquad L(x) \geq Q(x; x')

The idea is instead of optimizing L(x) directly due to its intractability, we may find suitable algorithm to optimize Q(x; x') where x' = x^{(n)}. Therefore for the minimization case we have the following inequality

L(x^{(n)}) = Q(x^{(n)}; x^{(n-1)}) + L(x^{(n)} - Q(x^{(n)}; x^{(n-1)})) \leq Q(x^{(n-1)}; x^{(n-1)}) + L(x^{(n-1)}) - Q(x^{(n-1)}; x^{(n-1)}) = L(x^{(n-1)})

where the inequality uses two optima, Q(x^{(n)}; x^{(n-1)}) is minimum of Q(x; x^{(n-1)}) and L(x) - Q(x; x^{(n-1)}) reaches its maximum at x = x^{(n-1)}.

Now let's come back to the Bayes learning problem. We know to select a proper hyperparameter, either we use cross validation, or we rely on maximization of Type II likelihood (EM solves it :-p). Here the author simply introduce another prior for the hyperparameter and integrate it out. E.g. for a Gaussian prior for the parameter, usually the hyperparameter is the precision, whose prior is then set to a Gamma distribution. But they kind of stealthly switch the concept. In Bayes framework, the joint distribution is then \Pr(\mathcal{D} \mid w) \Pr(w \mid \alpha) \Pr(\alpha). They first integrate out the hyperparameter \alpha, which leaves us \Pr(\mathcal{D} \mid w) \Pr(w). The we find the MAP estimation for simplicity, which results in

\min_w -\log \Pr(\mathcal{D} \mid w) - \log \Pr(w).

Now we may find the second term is of the form of - C\cdot\log (\| w \|^2 + \beta ), which is a different from the norm regularizer.

We solve this problem with MM optimization technique. We construct an upper bound for the second term

\log x \leq \log y + \frac{x - y}{y}

which is a linear function of x and therefore the optimization problem turns back to the original ``loss + norm regularizer'' form.

Don't see any thing special from this point of view.

Information Theoretic Measures for Clustering Comparisons: Is a Correction for Chance Nessary?

by Nguyen Xuan Vinh, Julien Epps and James Bailey

One problem in clustering is how to measure two clustering result. E.g. given two clustering results, which one is more closed to the true clustering?

There are many analytical methods, including Rand Index (RI) and Adjusted Rand Index (ARI). They are based on contingency table. Although RI could be useful since it is 1 iff the two clustering are identical and 0 when no pair are in the same cluster, it can not extinguish a random partition with a ``good clustering''.

To correct this (why it is called correction for chance), ARI is proposed. Another class comes from information theory. They use the mutual information of proportion of two clustering (each clustering's proportion is a density, therefore the mutual information is the common information in the two clustering). As we know we can create a distance based on entropy D(p, q) = H(p, q) - I(p, q) = H(p) + H(q) - 2 I(p, q) or its normalized version \mathrm{NMI}(p, q) = \frac{I(p, q)}{\sqrt{H(p) H(q)}}.

The authors proposed a corrected-for-chance version based on information method and from their experiments, we may find it works pretty well. Their criterion is

\mathrm{AMI}(U, V) = \frac{I(U, V) - \mathbb{E}( I(M) \mid a, b)}{\sqrt{H(U) H(V)} - \mathbb{E}(I(M) \mid a, b)}

or

\mathrm{AVI} = \frac{2 I(U, V) - 2 \mathbb{E}(I(M) \mid a, b)}{H(U) + H(V) - 2 \mathbb{E}(I(M) \mid a, b)}

where \mathbb{E}(I(M) \mid a, b) is computed from the contingency table.

The author provided examples where the correction is necessary. Esp. when samples in each cluster is few.

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.