Arthur Gretton

Research Scientist

Alumni

Empirical Inference

Publications

95 results (View BibTeX file of all listed publications)

2016

no image

Kernel Mean Shrinkage Estimators

Muandet, K., Sriperumbudur, B., Fukumizu, K., Gretton, A., Schölkopf, B.

Journal of Machine Learning Research, 17(48):1-41, 2016 (article)

link (url) [BibTex]

2016

Muandet, K., Sriperumbudur, B., Fukumizu, K., Gretton, A., Schölkopf, B. Kernel Mean Shrinkage Estimators Journal of Machine Learning Research, 17(48):1-41, 2016 (article)

link (url) [BibTex]

2014

no image

Kernel Mean Estimation and Stein Effect

Muandet, K., Fukumizu, K., Sriperumbudur, B., Gretton, A., Schölkopf, B.

In Proceedings of the 31st International Conference on Machine Learning, W&CP 32 (1), pages: 10-18, (Editors: Eric P. Xing and Tony Jebara), JMLR, ICML, 2014 (inproceedings)

2014

Muandet, K., Fukumizu, K., Sriperumbudur, B., Gretton, A., Schölkopf, B. Kernel Mean Estimation and Stein Effect In Proceedings of the 31st International Conference on Machine Learning, W&CP 32 (1), pages: 10-18, (Editors: Eric P. Xing and Tony Jebara), JMLR, ICML, 2014 (inproceedings)

2012

no image

Feature Selection via Dependence Maximization

Song, L., Smola, A., Gretton, A., Bedo, J., Borgwardt, K.

Journal of Machine Learning Research, 13, pages: 1393-1434, May 2012 (article)

Abstract

We introduce a framework of feature selection based on dependence maximization between the selected features and the labels of an estimation problem, using the Hilbert-Schmidt Independence Criterion. The key idea is that good features should be highly dependent on the labels. Our approach leads to a greedy procedure for feature selection. We show that a number of existing feature selectors are special cases of this framework. Experiments on both artificial and real-world data show that our feature selector works well in practice.

2012

Song, L., Smola, A., Gretton, A., Bedo, J., Borgwardt, K. Feature Selection via Dependence Maximization Journal of Machine Learning Research, 13, pages: 1393-1434, May 2012 (article)

no image

A Kernel Two-Sample Test

Gretton, A., Borgwardt, K., Rasch, M., Schölkopf, B., Smola, A.

Journal of Machine Learning Research, 13, pages: 723-773, March 2012 (article)

Abstract

We propose a framework for analyzing and comparing distributions, which we use to construct statistical tests to determine if two samples are drawn from different distributions. Our test statistic is the largest difference in expectations over functions in the unit ball of a reproducing kernel Hilbert space (RKHS), and is called the maximum mean discrepancy (MMD). We present two distribution-free tests based on large deviation bounds for the MMD, and a third test based on the asymptotic distribution of this statistic. The MMD can be computed in quadratic time, although efficient linear time approximations are available. Our statistic is an instance of an integral probability metric, and various classical metrics on distributions are obtained when alternative function classes are used in place of an RKHS. We apply our two-sample tests to a variety of problems, including attribute matching for databases using the Hungarian marriage method, where they perform strongly. Excellent performance is also obtained when comparing distributions over graphs, for which these are the first such tests.

PDF Web [BibTex]

Gretton, A., Borgwardt, K., Rasch, M., Schölkopf, B., Smola, A. A Kernel Two-Sample Test Journal of Machine Learning Research, 13, pages: 723-773, March 2012 (article)

PDF Web [BibTex]

no image

Modelling transition dynamics in MDPs with RKHS embeddings

Grünewälder, S., Lever, G., Baldassarre, L., Pontil, M., Gretton, A.

In Proceedings of the 29th International Conference on Machine Learning, pages: 535-542, (Editors: J Langford and J Pineau), Omnipress, New York, NY, USA, ICML, 2012 (inproceedings)

Grünewälder, S., Lever, G., Baldassarre, L., Pontil, M., Gretton, A. Modelling transition dynamics in MDPs with RKHS embeddings In Proceedings of the 29th International Conference on Machine Learning, pages: 535-542, (Editors: J Langford and J Pineau), Omnipress, New York, NY, USA, ICML, 2012 (inproceedings)

no image

On the Empirical Estimation of Integral Probability Metrics

Sriperumbudur, B., Fukumizu, K., Gretton, A., Schölkopf, B., Lanckriet, G.

Electronic Journal of Statistics, 6, pages: 1550-1599, 2012 (article)

Web DOI [BibTex]

Sriperumbudur, B., Fukumizu, K., Gretton, A., Schölkopf, B., Lanckriet, G. On the Empirical Estimation of Integral Probability Metrics Electronic Journal of Statistics, 6, pages: 1550-1599, 2012 (article)

Web DOI [BibTex]

no image

Conditional mean embeddings as regressors

Grünewälder, S., Lever, G., Baldassarre, L., Patterson, S., Gretton, A., Pontil, M.

In Proceedings of the 29th International Conference on Machine Learning, pages: 1823-1830, (Editors: J Langford and J Pineau), Omnipress, New York, NY, USA, ICML, 2012 (inproceedings)

Grünewälder, S., Lever, G., Baldassarre, L., Patterson, S., Gretton, A., Pontil, M. Conditional mean embeddings as regressors In Proceedings of the 29th International Conference on Machine Learning, pages: 1823-1830, (Editors: J Langford and J Pineau), Omnipress, New York, NY, USA, ICML, 2012 (inproceedings)

no image

Kernel Mean Embeddings of POMDPs

Nishiyama, Y., Boularias, A., Gretton, A., Fukumizu, K.

21st Machine Learning Summer School , 2012 (poster)

Nishiyama, Y., Boularias, A., Gretton, A., Fukumizu, K. Kernel Mean Embeddings of POMDPs 21st Machine Learning Summer School , 2012 (poster)

no image

Kernel Bellman Equations in POMDPs

Nishiyama, Y., Boularias, A., Gretton, A., Fukumizu, K.

Technical Committee on Infomation-Based Induction Sciences and Machine Learning (IBISML'12), 2012 (talk)

Nishiyama, Y., Boularias, A., Gretton, A., Fukumizu, K. Kernel Bellman Equations in POMDPs Technical Committee on Infomation-Based Induction Sciences and Machine Learning (IBISML'12), 2012 (talk)

no image

Hypothesis testing using pairwise distances and associated kernels

Sejdinovic, D., Gretton, A., Sriperumbudur, B., Fukumizu, K.

In Proceedings of the 29th International Conference on Machine Learning, pages: 1111-1118, (Editors: J Langford and J Pineau), Omnipress, New York, NY, USA, ICML, 2012 (inproceedings)

Sejdinovic, D., Gretton, A., Sriperumbudur, B., Fukumizu, K. Hypothesis testing using pairwise distances and associated kernels In Proceedings of the 29th International Conference on Machine Learning, pages: 1111-1118, (Editors: J Langford and J Pineau), Omnipress, New York, NY, USA, ICML, 2012 (inproceedings)

no image

Hilbert Space Embeddings of POMDPs

Nishiyama, Y., Boularias, A., Gretton, A., Fukumizu, K.

In Conference on Uncertainty in Artificial Intelligence (UAI), 2012 (inproceedings)

PDF Web [BibTex]

Nishiyama, Y., Boularias, A., Gretton, A., Fukumizu, K. Hilbert Space Embeddings of POMDPs In Conference on Uncertainty in Artificial Intelligence (UAI), 2012 (inproceedings)

PDF Web [BibTex]

no image

Optimal kernel choice for large-scale two-sample tests

Gretton, A., Sriperumbudur, B., Sejdinovic, D., Strathmann, H., Balakrishnan, S., Pontil, M., Fukumizu, K.

In Advances in Neural Information Processing Systems 25, pages: 1214-1222, (Editors: P Bartlett and FCN Pereira and CJC. Burges and L Bottou and KQ Weinberger), Curran Associates Inc., 26th Annual Conference on Neural Information Processing Systems (NIPS), 2012 (inproceedings)

Gretton, A., Sriperumbudur, B., Sejdinovic, D., Strathmann, H., Balakrishnan, S., Pontil, M., Fukumizu, K. Optimal kernel choice for large-scale two-sample tests In Advances in Neural Information Processing Systems 25, pages: 1214-1222, (Editors: P Bartlett and FCN Pereira and CJC. Burges and L Bottou and KQ Weinberger), Curran Associates Inc., 26th Annual Conference on Neural Information Processing Systems (NIPS), 2012 (inproceedings)

2011

no image

Semi-supervised kernel canonical correlation analysis with application to human fMRI

Blaschko, M., Shelton, J., Bartels, A., Lampert, C., Gretton, A.

Pattern Recognition Letters, 32(11):1572-1583 , August 2011 (article)

Abstract

Kernel canonical correlation analysis (KCCA) is a general technique for subspace learning that incorporates principal components analysis (PCA) and Fisher linear discriminant analysis (LDA) as special cases. By finding directions that maximize correlation, KCCA learns representations that are more closely tied to the underlying process that generates the data and can ignore high-variance noise directions. However, for data where acquisition in one or more modalities is expensive or otherwise limited, KCCA may suffer from small sample effects. We propose to use semi-supervised Laplacian regularization to utilize data that are present in only one modality. This approach is able to find highly correlated directions that also lie along the data manifold, resulting in a more robust estimate of correlated subspaces. Functional magnetic resonance imaging (fMRI) acquired data are naturally amenable to subspace techniques as data are well aligned. fMRI data of the human brain are a particularly interesting candidate. In this study we implemented various supervised and semi-supervised versions of KCCA on human fMRI data, with regression to single and multi-variate labels (corresponding to video content subjects viewed during the image acquisition). In each variate condition, the semi-supervised variants of KCCA performed better than the supervised variants, including a supervised variant with Laplacian regularization. We additionally analyze the weights learned by the regression in order to infer brain regions that are important to different types of visual processing.

PDF PDF DOI [BibTex]

2011

Blaschko, M., Shelton, J., Bartels, A., Lampert, C., Gretton, A. Semi-supervised kernel canonical correlation analysis with application to human fMRI Pattern Recognition Letters, 32(11):1572-1583 , August 2011 (article)

PDF PDF DOI [BibTex]

no image

Kernel Bayes’ Rule

Fukumizu, K., Song, L., Gretton, A.

In Advances in Neural Information Processing Systems 24, pages: 1737-1745, (Editors: J Shawe-Taylor and RS Zemel and P Bartlett and F Pereira and KQ Weinberger), Curran Associates, Inc., Red Hook, NY, USA, Twenty-Fifth Annual Conference on Neural Information Processing Systems (NIPS), 2011 (inproceedings)

Fukumizu, K., Song, L., Gretton, A. Kernel Bayes’ Rule In Advances in Neural Information Processing Systems 24, pages: 1737-1745, (Editors: J Shawe-Taylor and RS Zemel and P Bartlett and F Pereira and KQ Weinberger), Curran Associates, Inc., Red Hook, NY, USA, Twenty-Fifth Annual Conference on Neural Information Processing Systems (NIPS), 2011 (inproceedings)

no image

Kernel Belief Propagation

Song, L., Gretton, A., Bickson, D., Low, Y., Guestrin, C.

In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, Vol. 15, pages: 707-715, (Editors: G Gordon and D Dunson and M Dudík), JMLR, AISTATS, 2011 (inproceedings)

Song, L., Gretton, A., Bickson, D., Low, Y., Guestrin, C. Kernel Belief Propagation In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, Vol. 15, pages: 707-715, (Editors: G Gordon and D Dunson and M Dudík), JMLR, AISTATS, 2011 (inproceedings)

no image

Parallel Gibbs Sampling: From Colored Fields to Thin Junction Trees

Gonzalez, J., Low, Y., Gretton, A., Guestrin, C.

In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, Vol. 15, pages: 324-332, (Editors: G Gordon and D Dunson and M Dudík), JMLR, AISTATS, 2011 (inproceedings)

Gonzalez, J., Low, Y., Gretton, A., Guestrin, C. Parallel Gibbs Sampling: From Colored Fields to Thin Junction Trees In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, Vol. 15, pages: 324-332, (Editors: G Gordon and D Dunson and M Dudík), JMLR, AISTATS, 2011 (inproceedings)

2010

no image

Similarities in resting state and feature-driven activity: Non-parametric evaluation of human fMRI

Shelton, J., Blaschko, M., Gretton, A., Müller, J., Fischer, E., Bartels, A.

NIPS Workshop on Learning and Planning from Batch Time Series Data, December 2010 (poster)

PDF Web [BibTex]

2010

Shelton, J., Blaschko, M., Gretton, A., Müller, J., Fischer, E., Bartels, A. Similarities in resting state and feature-driven activity: Non-parametric evaluation of human fMRI NIPS Workshop on Learning and Planning from Batch Time Series Data, December 2010 (poster)

PDF Web [BibTex]

no image

Discriminative frequent subgraph mining with optimality guarantees

Thoma, M., Cheng, H., Gretton, A., Han, J., Kriegel, H., Smola, A., Song, L., Yu, P., Yan, X., Borgwardt, K.

Journal of Statistical Analysis and Data Mining, 3(5):302–318, October 2010 (article)

Abstract

The goal of frequent subgraph mining is to detect subgraphs that frequently occur in a dataset of graphs. In classification settings, one is often interested in discovering discriminative frequent subgraphs, whose presence or absence is indicative of the class membership of a graph. In this article, we propose an approach to feature selection on frequent subgraphs, called CORK, that combines two central advantages. First, it optimizes a submodular quality criterion, which means that we can yield a near-optimal solution using greedy feature selection. Second, our submodular quality function criterion can be integrated into gSpan, the state-of-the-art tool for frequent subgraph mining, and help to prune the search space for discriminative frequent subgraphs even during frequent subgraph mining.

Web DOI [BibTex]

Thoma, M., Cheng, H., Gretton, A., Han, J., Kriegel, H., Smola, A., Song, L., Yu, P., Yan, X., Borgwardt, K. Discriminative frequent subgraph mining with optimality guarantees Journal of Statistical Analysis and Data Mining, 3(5):302–318, October 2010 (article)

Web DOI [BibTex]

no image

Non-parametric estimation of integral probability metrics

Sriperumbudur, B., Fukumizu, K., Gretton, A., Schölkopf, B., Lanckriet, G.

In Proceedings of the IEEE International Symposium on Information Theory (ISIT 2010), pages: 1428-1432, IEEE, Piscataway, NJ, USA, IEEE International Symposium on Information Theory (ISIT), June 2010 (inproceedings)

Abstract

In this paper, we develop and analyze a nonparametric method for estimating the class of integral probability metrics (IPMs), examples of which include the Wasserstein distance, Dudley metric, and maximum mean discrepancy (MMD). We show that these distances can be estimated efficiently by solving a linear program in the case of Wasserstein distance and Dudley metric, while MMD is computable in a closed form. All these estimators are shown to be strongly consistent and their convergence rates are analyzed. Based on these results, we show that IPMs are simple to estimate and the estimators exhibit good convergence behavior compared to fi-divergence estimators.

PDF Web DOI [BibTex]

Sriperumbudur, B., Fukumizu, K., Gretton, A., Schölkopf, B., Lanckriet, G. Non-parametric estimation of integral probability metrics In Proceedings of the IEEE International Symposium on Information Theory (ISIT 2010), pages: 1428-1432, IEEE, Piscataway, NJ, USA, IEEE International Symposium on Information Theory (ISIT), June 2010 (inproceedings)

PDF Web DOI [BibTex]

no image

Temporal Kernel CCA and its Application in Multimodal Neuronal Data Analysis

Biessmann, F., Meinecke, F., Gretton, A., Rauch, A., Rainer, G., Logothetis, N., Müller, K.

Machine Learning, 79(1-2):5-27, May 2010 (article)

Abstract

Data recorded from multiple sources sometimes exhibit non-instantaneous couplings. For simple data sets, cross-correlograms may reveal the coupling dynamics. But when dealing with high-dimensional multivariate data there is no such measure as the cross-correlogram. We propose a simple algorithm based on Kernel Canonical Correlation Analysis (kCCA) that computes a multivariate temporal filter which links one data modality to another one. The filters can be used to compute a multivariate extension of the cross-correlogram, the canonical correlogram, between data sources that have different dimensionalities and temporal resolutions. The canonical correlogram reflects the coupling dynamics between the two sources. The temporal filter reveals which features in the data give rise to these couplings and when they do so. We present results from simulations and neuroscientific experiments showing that tkCCA yields easily interpretable temporal filters and correlograms. In the experiments, we simultaneously performed electrode recordings and functional magnetic resonance imaging (fMRI) in primary visual cortex of the non-human primate. While electrode recordings reflect brain activity directly, fMRI provides only an indirect view of neural activity via the Blood Oxygen Level Dependent (BOLD) response. Thus it is crucial for our understanding and the interpretation of fMRI signals in general to relate them to direct measures of neural activity acquired with electrodes. The results computed by tkCCA confirm recent models of the hemodynamic response to neural activity and allow for a more detailed analysis of neurovascular coupling dynamics.

PDF PDF DOI [BibTex]

Biessmann, F., Meinecke, F., Gretton, A., Rauch, A., Rainer, G., Logothetis, N., Müller, K. Temporal Kernel CCA and its Application in Multimodal Neuronal Data Analysis Machine Learning, 79(1-2):5-27, May 2010 (article)

PDF PDF DOI [BibTex]

no image

Hilbert Space Embeddings and Metrics on Probability Measures

Sriperumbudur, B., Gretton, A., Fukumizu, K., Schölkopf, B., Lanckriet, G.

Journal of Machine Learning Research, 11, pages: 1517-1561, April 2010 (article)

Sriperumbudur, B., Gretton, A., Fukumizu, K., Schölkopf, B., Lanckriet, G. Hilbert Space Embeddings and Metrics on Probability Measures Journal of Machine Learning Research, 11, pages: 1517-1561, April 2010 (article)

no image

Nonparametric Tree Graphical Models

Song, L., Gretton, A., Guestrin, C.

In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, Volume 9 , pages: 765-772, (Editors: YW Teh and M Titterington ), JMLR, AISTATS, 2010 (inproceedings)

Song, L., Gretton, A., Guestrin, C. Nonparametric Tree Graphical Models In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, Volume 9 , pages: 765-772, (Editors: YW Teh and M Titterington ), JMLR, AISTATS, 2010 (inproceedings)

no image

Consistent Nonparametric Tests of Independence

Gretton, A., Györfi, L.

Journal of Machine Learning Research, 11, pages: 1391-1423, 2010 (article)

Gretton, A., Györfi, L. Consistent Nonparametric Tests of Independence Journal of Machine Learning Research, 11, pages: 1391-1423, 2010 (article)

no image

Characteristic Kernels on Structured Domains Excel in Robotics and Human Action Recognition

Danafar, S., Gretton, A., Schmidhuber, J.

In Machine Learning and Knowledge Discovery in Databases, LNCS Vol. 6321, pages: 264-279, (Editors: JL Balcázar and F Bonchi and A Gionis and M Sebag), Springer, Berlin, Germany, ECML PKDD, 2010 (inproceedings)

Abstract

Embedding probability distributions into a sufficiently rich (characteristic) reproducing kernel Hilbert space enables us to take higher order statistics into account. Characterization also retains effective statistical relation between inputs and outputs in regression and classification. Recent works established conditions for characteristic kernels on groups and semigroups. Here we study characteristic kernels on periodic domains, rotation matrices, and histograms. Such structured domains are relevant for homogeneity testing, forward kinematics, forward dynamics, inverse dynamics, etc. Our kernel-based methods with tailored characteristic kernels outperform previous methods on robotics problems and also on a widely used benchmark for recognition of human actions in videos.

Danafar, S., Gretton, A., Schmidhuber, J. Characteristic Kernels on Structured Domains Excel in Robotics and Human Action Recognition In Machine Learning and Knowledge Discovery in Databases, LNCS Vol. 6321, pages: 264-279, (Editors: JL Balcázar and F Bonchi and A Gionis and M Sebag), Springer, Berlin, Germany, ECML PKDD, 2010 (inproceedings)

no image

Kernel Methods for Detecting the Direction of Time Series

Peters, J., Janzing, D., Gretton, A., Schölkopf, B.

In Advances in Data Analysis, Data Handling and Business Intelligence, pages: 57-66, (Editors: A Fink and B Lausen and W Seidel and A Ultsch), Springer, Berlin, Germany, 32nd Annual Conference of the Gesellschaft f{\"u}r Klassifikation e.V. (GfKl), 2010 (inproceedings)

Abstract

We propose two kernel based methods for detecting the time direction in empirical time series. First we apply a Support Vector Machine on the finite-dimensional distributions of the time series (classification method) by embedding these distributions into a Reproducing Kernel Hilbert Space. For the ARMA method we fit the observed data with an autoregressive moving average process and test whether the regression residuals are statistically independent of the past values. Whenever the dependence in one direction is significantly weaker than in the other we infer the former to be the true one. Both approaches were able to detect the direction of the true generating model for simulated data sets. We also applied our tests to a large number of real world time series. The ARMA method made a decision for a significant fraction of them, in which it was mostly correct, while the classification method did not perform as well, but still exceeded chance level.

PDF Web DOI [BibTex]

Peters, J., Janzing, D., Gretton, A., Schölkopf, B. Kernel Methods for Detecting the Direction of Time Series In Advances in Data Analysis, Data Handling and Business Intelligence, pages: 57-66, (Editors: A Fink and B Lausen and W Seidel and A Ultsch), Springer, Berlin, Germany, 32nd Annual Conference of the Gesellschaft f{\"u}r Klassifikation e.V. (GfKl), 2010 (inproceedings)

PDF Web DOI [BibTex]

2009

no image

Generalized Clustering via Kernel Embeddings

Jegelka, S., Gretton, A., Schölkopf, B., Sriperumbudur, B., von Luxburg, U.

In KI 2009: AI and Automation, Lecture Notes in Computer Science, Vol. 5803, pages: 144-152, (Editors: B Mertsching and M Hund and Z Aziz), Springer, Berlin, Germany, 32nd Annual Conference on Artificial Intelligence (KI), September 2009 (inproceedings)

Abstract

We generalize traditional goals of clustering towards distinguishing components in a non-parametric mixture model. The clusters are not necessarily based on point locations, but on higher order criteria. This framework can be implemented by embedding probability distributions in a Hilbert space. The corresponding clustering objective is very general and relates to a range of common clustering concepts.

PDF PDF Web DOI [BibTex]

2009

Jegelka, S., Gretton, A., Schölkopf, B., Sriperumbudur, B., von Luxburg, U. Generalized Clustering via Kernel Embeddings In KI 2009: AI and Automation, Lecture Notes in Computer Science, Vol. 5803, pages: 144-152, (Editors: B Mertsching and M Hund and Z Aziz), Springer, Berlin, Germany, 32nd Annual Conference on Artificial Intelligence (KI), September 2009 (inproceedings)

PDF PDF Web DOI [BibTex]

no image

Fast Kernel-Based Independent Component Analysis

Shen, H., Jegelka, S., Gretton, A.

IEEE Transactions on Signal Processing, 57(9):3498-3511, September 2009 (article)

Abstract

Recent approaches to independent component analysis (ICA) have used kernel independence measures to obtain highly accurate solutions, particularly where classical methods experience difficulty (for instance, sources with near-zero kurtosis). FastKICA (fast HSIC-based kernel ICA) is a new optimization method for one such kernel independence measure, the Hilbert-Schmidt Independence Criterion (HSIC). The high computational efficiency of this approach is achieved by combining geometric optimization techniques, specifically an approximate Newton-like method on the orthogonal group, with accurate estimates of the gradient and Hessian based on an incomplete Cholesky decomposition. In contrast to other efficient kernel-based ICA algorithms, FastKICA is applicable to any twice differentiable kernel function. Experimental results for problems with large numbers of sources and observations indicate that FastKICA provides more accurate solutions at a given cost than gradient descent on HSIC. Comparing with other recently published ICA methods, FastKICA is competitive in terms of accuracy, relatively insensitive to local minima when initialized far from independence, and more robust towards outliers. An analysis of the local convergence properties of FastKICA is provided.

PDF Web DOI [BibTex]

Shen, H., Jegelka, S., Gretton, A. Fast Kernel-Based Independent Component Analysis IEEE Transactions on Signal Processing, 57(9):3498-3511, September 2009 (article)

PDF Web DOI [BibTex]

no image

Consistent Nonparametric Tests of Independence

Gretton, A., Györfi, L.

(172), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, July 2009 (techreport)

Abstract

Three simple and explicit procedures for testing the independence of two multi-dimensional random variables are described. Two of the associated test statistics (L1, log-likelihood) are defined when the empirical distribution of the variables is restricted to finite partitions. A third test statistic is defined as a kernel-based independence measure. Two kinds of tests are provided. Distribution-free strong consistent tests are derived on the basis of large deviation bounds on the test statistcs: these tests make almost surely no Type I or Type II error after a random sample size. Asymptotically alpha-level tests are obtained from the limiting distribution of the test statistics. For the latter tests, the Type I error converges to a fixed non-zero value alpha, and the Type II error drops to zero, for increasing sample size. All tests reject the null hypothesis of independence if the test statistics become large. The performance of the tests is evaluated experimentally on benchmark data.

Gretton, A., Györfi, L. Consistent Nonparametric Tests of Independence (172), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, July 2009 (techreport)

no image

Detecting the Direction of Causal Time Series

Peters, J., Janzing, D., Gretton, A., Schölkopf, B.

In Proceedings of the 26th International Conference on Machine Learning, pages: 801-808, (Editors: A Danyluk and L Bottou and ML Littman), ACM Press, New York, NY, USA, ICML, June 2009 (inproceedings)

Abstract

We propose a method that detects the true direction of time series, by fitting an autoregressive moving average model to the data. Whenever the noise is independent of the previous samples for one ordering of the observations, but dependent for the opposite ordering, we infer the former direction to be the true one. We prove that our method works in the population case as long as the noise of the process is not normally distributed (for the latter case, the direction is not identificable). A new and important implication of our result is that it confirms a fundamental conjecture in causal reasoning - if after regression the noise is independent of signal for one direction and dependent for the other, then the former represents the true causal direction - in the case of time series. We test our approach on two types of data: simulated data sets conforming to our modeling assumptions, and real world EEG time series. Our method makes a decision for a significant fraction of both data sets, and these decisions are mostly correct. For real world data, our approach outperforms alternative solutions to the problem of time direction recovery.

PDF Web DOI [BibTex]

Peters, J., Janzing, D., Gretton, A., Schölkopf, B. Detecting the Direction of Causal Time Series In Proceedings of the 26th International Conference on Machine Learning, pages: 801-808, (Editors: A Danyluk and L Bottou and ML Littman), ACM Press, New York, NY, USA, ICML, June 2009 (inproceedings)

PDF Web DOI [BibTex]

no image

Learning Taxonomies by Dependence Maximization

Blaschko, M., Gretton, A.

In Advances in neural information processing systems 21, pages: 153-160, (Editors: Koller, D. , D. Schuurmans, Y. Bengio, L. Bottou), Curran, Red Hook, NY, USA, Twenty-Second Annual Conference on Neural Information Processing Systems (NIPS), June 2009 (inproceedings)

Abstract

We introduce a family of unsupervised algorithms, numerical taxonomy clustering, to simultaneously cluster data, and to learn a taxonomy that encodes the relationship between the clusters. The algorithms work by maximizing the dependence between the taxonomy and the original data. The resulting taxonomy is a more informative visualization of complex data than simple clustering; in addition, taking into account the relations between different clusters is shown to substantially improve the quality of the clustering, when compared with state-ofthe-art algorithms in the literature (both spectral clustering and a previous dependence maximization approach). We demonstrate our algorithm on image and text data.

PDF Web [BibTex]

Blaschko, M., Gretton, A. Learning Taxonomies by Dependence Maximization In Advances in neural information processing systems 21, pages: 153-160, (Editors: Koller, D. , D. Schuurmans, Y. Bengio, L. Bottou), Curran, Red Hook, NY, USA, Twenty-Second Annual Conference on Neural Information Processing Systems (NIPS), June 2009 (inproceedings)

PDF Web [BibTex]

no image

Characteristic Kernels on Groups and Semigroups

Fukumizu, K., Sriperumbudur, B., Gretton, A., Schölkopf, B.

In Advances in neural information processing systems 21, pages: 473-480, (Editors: D Koller and D Schuurmans and Y Bengio and L Bottou), Curran, Red Hook, NY, USA, 22nd Annual Conference on Neural Information Processing Systems (NIPS), June 2009 (inproceedings)

Abstract

Embeddings of random variables in reproducing kernel Hilbert spaces (RKHSs) may be used to conduct statistical inference based on higher order moments. For sufficiently rich (characteristic) RKHSs, each probability distribution has a unique embedding, allowing all statistical properties of the distribution to be taken into consideration. Necessary and sufficient conditions for an RKHS to be characteristic exist for Rn. In the present work, conditions are established for an RKHS to be characteristic on groups and semigroups. Illustrative examples are provided, including characteristic kernels on periodic domains, rotation matrices, and Rn+.

PDF Web [BibTex]

Fukumizu, K., Sriperumbudur, B., Gretton, A., Schölkopf, B. Characteristic Kernels on Groups and Semigroups In Advances in neural information processing systems 21, pages: 473-480, (Editors: D Koller and D Schuurmans and Y Bengio and L Bottou), Curran, Red Hook, NY, USA, 22nd Annual Conference on Neural Information Processing Systems (NIPS), June 2009 (inproceedings)

PDF Web [BibTex]

no image

Kernel Measures of Independence for Non-IID Data

Zhang, X., Song, L., Gretton, A., Smola, A.

In Advances in neural information processing systems 21, pages: 1937-1944, (Editors: Koller, D. , D. Schuurmans, Y. Bengio, L. Bottou), Curran, Red Hook, NY, USA, Twenty-Second Annual Conference on Neural Information Processing Systems (NIPS), June 2009 (inproceedings)

Abstract

Many machine learning algorithms can be formulated in the framework of statistical independence such as the Hilbert Schmidt Independence Criterion. In this paper, we extend this criterion to deal with structured and interdependent observations. This is achieved by modeling the structures using undirected graphical models and comparing the Hilbert space embeddings of distributions. We apply this new criterion to independent component analysis and sequence clustering.

PDF Web [BibTex]

Zhang, X., Song, L., Gretton, A., Smola, A. Kernel Measures of Independence for Non-IID Data In Advances in neural information processing systems 21, pages: 1937-1944, (Editors: Koller, D. , D. Schuurmans, Y. Bengio, L. Bottou), Curran, Red Hook, NY, USA, Twenty-Second Annual Conference on Neural Information Processing Systems (NIPS), June 2009 (inproceedings)

PDF Web [BibTex]

no image

Near-optimal supervised feature selection among frequent subgraphs

Thoma, M., Cheng, H., Gretton, A., Han, J., Kriegel, H., Smola, A., Song, L., Yu, P., Yan, X., Borgwardt, K.

In Proccedings of the 2009 SIAM Conference on Data Mining (SDM 2009), pages: 1076-1087, (Editors: Park, H. , S. Parthasarathy, H. Liu), Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, 9th SIAM Conference on Data Mining (SDM), May 2009 (inproceedings)

Abstract

Graph classification is an increasingly important step in numerous application domains, such as function prediction of molecules and proteins, computerised scene analysis, and anomaly detection in program flows. Among the various approaches proposed in the literature, graph classification based on frequent subgraphs is a popular branch: Graphs are represented as (usually binary) vectors, with components indicating whether a graph contains a particular subgraph that is frequent across the dataset. On large graphs, however, one faces the enormous problem that the number of these frequent subgraphs may grow exponentially with the size of the graphs, but only few of them possess enough discriminative power to make them useful for graph classification. Efficient and discriminative feature selection among frequent subgraphs is hence a key challenge for graph mining. In this article, we propose an approach to feature selection on frequent subgraphs, called CORK, that combines two central advantages. First, it optimizes a submodular quality criterion, which means that we can yield a near-optimal solution using greedy feature selection. Second, our submodular quality function criterion can be integrated into gSpan, the state-of-the-art tool for frequent subgraph mining, and help to prune the search space for discriminative frequent subgraphs even during frequent subgraph mining.

PDF PDF [BibTex]

Thoma, M., Cheng, H., Gretton, A., Han, J., Kriegel, H., Smola, A., Song, L., Yu, P., Yan, X., Borgwardt, K. Near-optimal supervised feature selection among frequent subgraphs In Proccedings of the 2009 SIAM Conference on Data Mining (SDM 2009), pages: 1076-1087, (Editors: Park, H. , S. Parthasarathy, H. Liu), Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, 9th SIAM Conference on Data Mining (SDM), May 2009 (inproceedings)

PDF PDF [BibTex]

no image

Covariate shift and local learning by distribution matching

Gretton, A., Smola, A., Huang, J., Schmittfull, M., Borgwardt, K., Schölkopf, B.

In Dataset Shift in Machine Learning, pages: 131-160, (Editors: Quiñonero-Candela, J., Sugiyama, M., Schwaighofer, A. and Lawrence, N. D.), MIT Press, Cambridge, MA, USA, 2009 (inbook)

Abstract

Given sets of observations of training and test data, we consider the problem of re-weighting the training data such that its distribution more closely matches that of the test data. We achieve this goal by matching covariate distributions between training and test sets in a high dimensional feature space (specifically, a reproducing kernel Hilbert space). This approach does not require distribution estimation. Instead, the sample weights are obtained by a simple quadratic programming procedure. We provide a uniform convergence bound on the distance between the reweighted training feature mean and the test feature mean, a transductive bound on the expected loss of an algorithm trained on the reweighted data, and a connection to single class SVMs. While our method is designed to deal with the case of simple covariate shift (in the sense of Chapter ??), we have also found benefits for sample selection bias on the labels. Our correction procedure yields its greatest and most consistent advantages when the learning algorithm returns a classifier/regressor that is simpler" than the data might suggest.

PDF Web [BibTex]

Gretton, A., Smola, A., Huang, J., Schmittfull, M., Borgwardt, K., Schölkopf, B. Covariate shift and local learning by distribution matching In Dataset Shift in Machine Learning, pages: 131-160, (Editors: Quiñonero-Candela, J., Sugiyama, M., Schwaighofer, A. and Lawrence, N. D.), MIT Press, Cambridge, MA, USA, 2009 (inbook)

PDF Web [BibTex]

no image

Kernel Choice and Classifiability for RKHS Embeddings of Probability Distributions

Sriperumbudur, B., Fukumizu, K., Gretton, A., Lanckriet, G., Schölkopf, B.

In Advances in Neural Information Processing Systems 22, pages: 1750-1758, (Editors: Y Bengio and D Schuurmans and J Lafferty and C Williams and A Culotta), Curran, Red Hook, NY, USA, 23rd Annual Conference on Neural Information Processing Systems (NIPS), 2009 (inproceedings)

Abstract

Embeddings of probability measures into reproducing kernel Hilbert spaces have been proposed as a straightforward and practical means of representing and comparing probabilities. In particular, the distance between embeddings (the maximum mean discrepancy, or MMD) has several key advantages over many classical metrics on distributions, namely easy computability, fast convergence and low bias of finite sample estimates. An important requirement of the embedding RKHS is that it be characteristic: in this case, the MMD between two distributions is zero if and only if the distributions coincide. Three new results on the MMD are introduced in the present study. First, it is established that MMD corresponds to the optimal risk of a kernel classifier, thus forming a natural link between the distance between distributions and their ease of classification. An important consequence is that a kernel must be characteristic to guarantee classifiability between distributions in the RKHS. Second, the class of characteristic kernels is broadened to incorporate all strictly positive definite kernels: these include non-translation invariant kernels and kernels on non-compact domains. Third, a generalization of the MMD is proposed for families of kernels, as the supremum over MMDs on a class of kernels (for instance the Gaussian kernels with different bandwidths). This extension is necessary to obtain a single distance measure if a large selection or class of characteristic kernels is potentially appropriate. This generalization is reasonable, given that it corresponds to the problem of learning the kernel by minimizing the risk of the corresponding kernel classifier. The generalized MMD is shown to have consistent finite sample estimates, and its performance is demonstrated on a homogeneity testing example.

PDF Web [BibTex]

Sriperumbudur, B., Fukumizu, K., Gretton, A., Lanckriet, G., Schölkopf, B. Kernel Choice and Classifiability for RKHS Embeddings of Probability Distributions In Advances in Neural Information Processing Systems 22, pages: 1750-1758, (Editors: Y Bengio and D Schuurmans and J Lafferty and C Williams and A Culotta), Curran, Red Hook, NY, USA, 23rd Annual Conference on Neural Information Processing Systems (NIPS), 2009 (inproceedings)

PDF Web [BibTex]

no image

Nonlinear directed acyclic structure learning with weakly additive noise models

Tillman, R., Gretton, A., Spirtes, P.

In Advances in Neural Information Processing Systems 22, pages: 1847-1855, (Editors: Bengio, Y. , D. Schuurmans, J. Lafferty, C. Williams, A. Culotta), Curran, Red Hook, NY, USA, 23rd Annual Conference on Neural Information Processing Systems (NIPS), 2009 (inproceedings)

Abstract

The recently proposed emph{additive noise model} has advantages over previous structure learning algorithms, when attempting to recover some true data generating mechanism, since it (i) does not assume linearity or Gaussianity and (ii) can recover a unique DAG rather than an equivalence class. However, its original extension to the multivariate case required enumerating all possible DAGs, and for some special distributions, e.g. linear Gaussian, the model is invertible and thus cannot be used for structure learning. We present a new approach which combines a PC style search using recent advances in kernel measures of conditional dependence with local searches for additive noise models in substructures of the equivalence class. This results in a more computationally efficient approach that is useful for arbitrary distributions even when additive noise models are invertible. Experiments with synthetic and real data show that this method is more accurate than previous methods when data are nonlinear and/or non-Gaussian.

PDF Web [BibTex]

Tillman, R., Gretton, A., Spirtes, P. Nonlinear directed acyclic structure learning with weakly additive noise models In Advances in Neural Information Processing Systems 22, pages: 1847-1855, (Editors: Bengio, Y. , D. Schuurmans, J. Lafferty, C. Williams, A. Culotta), Curran, Red Hook, NY, USA, 23rd Annual Conference on Neural Information Processing Systems (NIPS), 2009 (inproceedings)

PDF Web [BibTex]

no image

Discussion of: Brownian Distance Covariance

Gretton, A., Fukumizu, K., Sriperumbudur, B.

The Annals of Applied Statistics, 3(4):1285-1294, 2009 (article)

Gretton, A., Fukumizu, K., Sriperumbudur, B. Discussion of: Brownian Distance Covariance The Annals of Applied Statistics, 3(4):1285-1294, 2009 (article)

no image

A Fast, Consistent Kernel Two-Sample Test

Gretton, A., Fukumizu, K., Harchaoui, Z., Sriperumbudur, B.

In Advances in Neural Information Processing Systems 22, pages: 673-681, (Editors: Bengio, Y. , D. Schuurmans, J. Lafferty, C. Williams, A. Culotta), Curran, Red Hook, NY, USA, 23rd Annual Conference on Neural Information Processing Systems (NIPS), 2009 (inproceedings)

Abstract

A kernel embedding of probability distributions into reproducing kernel Hilbert spaces (RKHS) has recently been proposed, which allows the comparison of two probability measures P and Q based on the distance between their respective embeddings: for a sufficiently rich RKHS, this distance is zero if and only if P and Q coincide. In using this distance as a statistic for a test of whether two samples are from different distributions, a major difficulty arises in computing the significance threshold, since the empirical statistic has as its null distribution (where P = Q) an infinite weighted sum of x2 random variables. Prior finite sample approximations to the null distribution include using bootstrap resampling, which yields a consistent estimate but is computationally costly; and fitting a parametric model with the low order moments of the test statistic, which can work well in practice but has no consistency or accuracy guarantees. The main result of the present work is a novel estimate of the null distribution, computed from the eigenspectrum of the Gram matrix on the aggregate sample from P and Q, and having lower computational cost than the bootstrap. A proof of consistency of this estimate is provided. The performance of the null distribution estimate is compared with the bootstrap and parametric approaches on an artificial example, high dimensional multivariate data, and text.

PDF Web [BibTex]

Gretton, A., Fukumizu, K., Harchaoui, Z., Sriperumbudur, B. A Fast, Consistent Kernel Two-Sample Test In Advances in Neural Information Processing Systems 22, pages: 673-681, (Editors: Bengio, Y. , D. Schuurmans, J. Lafferty, C. Williams, A. Culotta), Curran, Red Hook, NY, USA, 23rd Annual Conference on Neural Information Processing Systems (NIPS), 2009 (inproceedings)

PDF Web [BibTex]

2008

no image

Taxonomy Inference Using Kernel Dependence Measures

Blaschko, M., Gretton, A.

(181), Max-Planck Institute for Biological Cybernetics, Tübingen, Germany, November 2008 (techreport)

Abstract

We introduce a family of unsupervised algorithms, numerical taxonomy clustering, to simultaneously cluster data, and to learn a taxonomy that encodes the relationship between the clusters. The algorithms work by maximizing the dependence between the taxonomy and the original data. The resulting taxonomy is a more informative visualization of complex data than simple clustering; in addition, taking into account the relations between different clusters is shown to substantially improve the quality of the clustering, when compared with state-of-the-art algorithms in the literature (both spectral clustering and a previous dependence maximization approach). We demonstrate our algorithm on image and text data.

2008

Blaschko, M., Gretton, A. Taxonomy Inference Using Kernel Dependence Measures (181), Max-Planck Institute for Biological Cybernetics, Tübingen, Germany, November 2008 (techreport)

no image

Nonparametric Independence Tests: Space Partitioning and Kernel Approaches

Gretton, A., Györfi, L.

In ALT08, pages: 183-198, (Editors: Freund, Y. , L. Györfi, G. Turán, T. Zeugmann), Springer, Berlin, Germany, 19th International Conference on Algorithmic Learning Theory (ALT08), October 2008 (inproceedings)

Abstract

Three simple and explicit procedures for testing the independence of two multi-dimensional random variables are described. Two of the associated test statistics (L1, log-likelihood) are defined when the empirical distribution of the variables is restricted to finite partitions. A third test statistic is defined as a kernel-based independence measure. All tests reject the null hypothesis of independence if the test statistics become large. The large deviation and limit distribution properties of all three test statistics are given. Following from these results, distributionfree strong consistent tests of independence are derived, as are asymptotically alpha-level tests. The performance of the tests is evaluated experimentally on benchmark data.

PDF Web DOI [BibTex]

Gretton, A., Györfi, L. Nonparametric Independence Tests: Space Partitioning and Kernel Approaches In ALT08, pages: 183-198, (Editors: Freund, Y. , L. Györfi, G. Turán, T. Zeugmann), Springer, Berlin, Germany, 19th International Conference on Algorithmic Learning Theory (ALT08), October 2008 (inproceedings)

PDF Web DOI [BibTex]

no image

Nonparametric Indepedence Tests: Space Partitioning and Kernel Approaches

Gretton, A., Györfi, L.

19th International Conference on Algorithmic Learning Theory (ALT08), October 2008 (talk)

PDF Web [BibTex]

Gretton, A., Györfi, L. Nonparametric Indepedence Tests: Space Partitioning and Kernel Approaches 19th International Conference on Algorithmic Learning Theory (ALT08), October 2008 (talk)

PDF Web [BibTex]

no image

Kernel Measures of Conditional Dependence

Fukumizu, K., Gretton, A., Sun, X., Schölkopf, B.

In Advances in neural information processing systems 20, pages: 489-496, (Editors: JC Platt and D Koller and Y Singer and S Roweis), Curran, Red Hook, NY, USA, 21st Annual Conference on Neural Information Processing Systems (NIPS), September 2008 (inproceedings)

Abstract

We propose a new measure of conditional dependence of random variables, based on normalized cross-covariance operators on reproducing kernel Hilbert spaces. Unlike previous kernel dependence measures, the proposed criterion does not depend on the choice of kernel in the limit of infinite data, for a wide class of kernels. At the same time, it has a straightforward empirical estimate with good convergence behaviour. We discuss the theoretical properties of the measure, and demonstrate its application in experiments.

PDF Web [BibTex]

Fukumizu, K., Gretton, A., Sun, X., Schölkopf, B. Kernel Measures of Conditional Dependence In Advances in neural information processing systems 20, pages: 489-496, (Editors: JC Platt and D Koller and Y Singer and S Roweis), Curran, Red Hook, NY, USA, 21st Annual Conference on Neural Information Processing Systems (NIPS), September 2008 (inproceedings)

PDF Web [BibTex]

no image

Comparison of Pattern Recognition Methods in Classifying High-resolution BOLD Signals Obtained at High Magnetic Field in Monkeys

Ku, S., Gretton, A., Macke, J., Logothetis, N.

Magnetic Resonance Imaging, 26(7):1007-1014, September 2008 (article)

Abstract

Pattern recognition methods have shown that functional magnetic resonance imaging (fMRI) data can reveal significant information about brain activity. For example, in the debate of how object categories are represented in the brain, multivariate analysis has been used to provide evidence of a distributed encoding scheme [Science 293:5539 (2001) 24252430]. Many follow-up studies have employed different methods to analyze human fMRI data with varying degrees of success [Nature reviews 7:7 (2006) 523534]. In this study, we compare four popular pattern recognition methods: correlation analysis, support-vector machines (SVM), linear discriminant analysis (LDA) and Gaussian naïve Bayes (GNB), using data collected at high field (7 Tesla) with higher resolution than usual fMRI studies. We investigate prediction performance on single trials and for averages across varying numbers of stimulus presentations. The performance of the various algorithms depends on the nature of the brain activity being categorized: for several tasks, many of the methods work well, whereas for others, no method performs above chance level. An important factor in overall classification performance is careful preprocessing of the data, including dimensionality reduction, voxel selection and outlier elimination.

PDF Web DOI [BibTex]

Ku, S., Gretton, A., Macke, J., Logothetis, N. Comparison of Pattern Recognition Methods in Classifying High-resolution BOLD Signals Obtained at High Magnetic Field in Monkeys Magnetic Resonance Imaging, 26(7):1007-1014, September 2008 (article)

PDF Web DOI [BibTex]

no image

Colored Maximum Variance Unfolding

Song, L., Smola, A., Borgwardt, K., Gretton, A.

In Advances in neural information processing systems 20, pages: 1385-1392, (Editors: Platt, J. C., D. Koller, Y. Singer, S. Roweis), Curran, Red Hook, NY, USA, Twenty-First Annual Conference on Neural Information Processing Systems (NIPS), September 2008 (inproceedings)

Abstract

Maximum variance unfolding (MVU) is an effective heuristic for dimensionality reduction. It produces a low-dimensional representation of the data by maximizing the variance of their embeddings while preserving the local distances of the original data. We show that MVU also optimizes a statistical dependence measure which aims to retain the identity of individual observations under the distancepreserving constraints. This general view allows us to design "colored" variants of MVU, which produce low-dimensional representations for a given task, e.g. subject to class labels or other side information.

PDF Web [BibTex]

Song, L., Smola, A., Borgwardt, K., Gretton, A. Colored Maximum Variance Unfolding In Advances in neural information processing systems 20, pages: 1385-1392, (Editors: Platt, J. C., D. Koller, Y. Singer, S. Roweis), Curran, Red Hook, NY, USA, Twenty-First Annual Conference on Neural Information Processing Systems (NIPS), September 2008 (inproceedings)

PDF Web [BibTex]

no image

A Kernel Statistical Test of Independence

Gretton, A., Fukumizu, K., Teo, C., Song, L., Schölkopf, B., Smola, A.

In Advances in neural information processing systems 20, pages: 585-592, (Editors: JC Platt and D Koller and Y Singer and S Roweis), Curran, Red Hook, NY, USA, 21st Annual Conference on Neural Information Processing Systems (NIPS), September 2008 (inproceedings)

Abstract

Whereas kernel measures of independence have been widely applied in machine learning (notably in kernel ICA), there is as yet no method to determine whether they have detected statistically significant dependence. We provide a novel test of the independence hypothesis for one particular kernel independence measure, the Hilbert-Schmidt independence criterion (HSIC). The resulting test costs O(m^2), where m is the sample size. We demonstrate that this test outperforms established contingency table-based tests. Finally, we show the HSIC test also applies to text (and to structured data more generally), for which no other independence test presently exists.

PDF Web [BibTex]

Gretton, A., Fukumizu, K., Teo, C., Song, L., Schölkopf, B., Smola, A. A Kernel Statistical Test of Independence In Advances in neural information processing systems 20, pages: 585-592, (Editors: JC Platt and D Koller and Y Singer and S Roweis), Curran, Red Hook, NY, USA, 21st Annual Conference on Neural Information Processing Systems (NIPS), September 2008 (inproceedings)

PDF Web [BibTex]

no image

Semi-Supervised Laplacian Regularization of Kernel Canonical Correlation Analysis

Blaschko, M., Lampert, C., Gretton, A.

In ECML PKDD 2008, pages: 133-145, (Editors: Daelemans, W. , B. Goethals, K. Morik), Springer, Berlin, Germany, 19th European Conference on Machine Learning, August 2008 (inproceedings)

Abstract

Kernel canonical correlation analysis (KCCA) is a dimensionality reduction technique for paired data. By finding directions that maximize correlation, KCCA learns representations that are more closely tied to the underlying semantics of the data rather than noise. However, meaningful directions are not only those that have high correlation to another modality, but also those that capture the manifold structure of the data. We propose a method that is simultaneously able to find highly correlated directions that are also located on high variance directions along the data manifold. This is achieved by the use of semi-supervised Laplacian regularization of KCCA. We show experimentally that Laplacian regularized training improves class separation over KCCA with only Tikhonov regularization, while causing no degradation in the correlation between modalities. We propose a model selection criterion based on the Hilbert-Schmidt norm of the semi-supervised Laplacian regularized cross-covariance operator, which we compute in closed form.

PDF PDF DOI [BibTex]

Blaschko, M., Lampert, C., Gretton, A. Semi-Supervised Laplacian Regularization of Kernel Canonical Correlation Analysis In ECML PKDD 2008, pages: 133-145, (Editors: Daelemans, W. , B. Goethals, K. Morik), Springer, Berlin, Germany, 19th European Conference on Machine Learning, August 2008 (inproceedings)

PDF PDF DOI [BibTex]

no image

RKHS Representation of Measures Applied to Homogeneity, Independence, and Fourier Optics

Schölkopf, B., Sriperumbudur, B., Gretton, A., Fukumizu, K.

In OWR 2008, pages: 42-44, (Editors: K Jetter and S Smale and D-X Zhou), Mathematisches Forschungsinstitut, Oberwolfach-Walke, Germany, 30. Oberwolfach Report, August 2008 (inproceedings)

PDF PDF [BibTex]

Schölkopf, B., Sriperumbudur, B., Gretton, A., Fukumizu, K. RKHS Representation of Measures Applied to Homogeneity, Independence, and Fourier Optics In OWR 2008, pages: 42-44, (Editors: K Jetter and S Smale and D-X Zhou), Mathematisches Forschungsinstitut, Oberwolfach-Walke, Germany, 30. Oberwolfach Report, August 2008 (inproceedings)

PDF PDF [BibTex]

no image

Tailoring density estimation via reproducing kernel moment matching

Song, L., Zhang, X., Smola, A., Gretton, A., Schölkopf, B.

In Proceedings of the 25th International Conference onMachine Learning, pages: 992-999, (Editors: WW Cohen and A McCallum and S Roweis), ACM Press, New York, NY, USA, ICML, July 2008 (inproceedings)

Abstract

Moment matching is a popular means of parametric density estimation. We extend this technique to nonparametric estimation of mixture models. Our approach works by embedding distributions into a reproducing kernel Hilbert space, and performing moment matching in that space. This allows us to tailor density estimators to a function class of interest (i.e., for which we would like to compute expectations). We show our density estimation approach is useful in applications such as message compression in graphical models, and image classification and retrieval.

PDF PDF DOI [BibTex]

Song, L., Zhang, X., Smola, A., Gretton, A., Schölkopf, B. Tailoring density estimation via reproducing kernel moment matching In Proceedings of the 25th International Conference onMachine Learning, pages: 992-999, (Editors: WW Cohen and A McCallum and S Roweis), ACM Press, New York, NY, USA, ICML, July 2008 (inproceedings)

PDF PDF DOI [BibTex]

no image

Injective Hilbert Space Embeddings of Probability Measures

Sriperumbudur, B., Gretton, A., Fukumizu, K., Lanckriet, G., Schölkopf, B.

In Proceedings of the 21st Annual Conference on Learning Theory, pages: 111-122, (Editors: RA Servedio and T Zhang), Omnipress, Madison, WI, USA, 21st Annual Conference on Learning Theory (COLT), July 2008 (inproceedings)

Abstract

A Hilbert space embedding for probability measures has recently been proposed, with applications including dimensionality reduction, homogeneity testing and independence testing. This embedding represents any probability measure as a mean element in a reproducing kernel Hilbert space (RKHS). The embedding function has been proven to be injective when the reproducing kernel is universal. In this case, the embedding induces a metric on the space of probability distributions defined on compact metric spaces. In the present work, we consider more broadly the problem of specifying characteristic kernels, defined as kernels for which the RKHS embedding of probability measures is injective. In particular, characteristic kernels can include non-universal kernels. We restrict ourselves to translation-invariant kernels on Euclidean space, and define the associated metric on probability measures in terms of the Fourier spectrum of the kernel and characteristic functions of these measures. The support of the kernel spectrum is important in finding whether a kernel is characteristic: in particular, the embedding is injective if and only if the kernel spectrum has the entire domain as its support. Characteristic kernels may nonetheless have difficulty in distinguishing certain distributions on the basis of finite samples, again due to the interaction of the kernel spectrum and the characteristic functions of the measures.

PDF Web [BibTex]

Sriperumbudur, B., Gretton, A., Fukumizu, K., Lanckriet, G., Schölkopf, B. Injective Hilbert Space Embeddings of Probability Measures In Proceedings of the 21st Annual Conference on Learning Theory, pages: 111-122, (Editors: RA Servedio and T Zhang), Omnipress, Madison, WI, USA, 21st Annual Conference on Learning Theory (COLT), July 2008 (inproceedings)

PDF Web [BibTex]

no image

A Hilbert-Schmidt Dependence Maximization Approach to Unsupervised Structure Discovery

Blaschko, M., Gretton, A.

In MLG 2008, pages: 1-3, 6th International Workshop on Mining and Learning with Graphs, July 2008 (inproceedings)

Abstract

In recent work by (Song et al., 2007), it has been proposed to perform clustering by maximizing a Hilbert-Schmidt independence criterion with respect to a predefined cluster structure Y , by solving for the partition matrix, II. We extend this approach here to the case where the cluster structure Y is not fixed, but is a quantity to be optimized; and we use an independence criterion which has been shown to be more sensitive at small sample sizes (the Hilbert-Schmidt Normalized Information Criterion, or HSNIC, Fukumizu et al., 2008). We demonstrate the use of this framework in two scenarios. In the first, we adopt a cluster structure selection approach in which the HSNIC is used to select a structure from several candidates. In the second, we consider the case where we discover structure by directly optimizing Y.

PDF Web [BibTex]

Blaschko, M., Gretton, A. A Hilbert-Schmidt Dependence Maximization Approach to Unsupervised Structure Discovery In MLG 2008, pages: 1-3, 6th International Workshop on Mining and Learning with Graphs, July 2008 (inproceedings)

PDF Web [BibTex]

Our goal is to understand the principles of Perception, Action and Learning in autonomous systems that successfully interact with complex environments and to use this understanding to design future systems

Latest News

Cambridge – Tübingen PhD Fellowships in Machine Learning (m/f/d) 10 November 2020
ELLIS PhD Program: Call for Applications 10 September 2020
Stefan Bauer elected CIFAR Azrieli Global Scholar 13 August 2020
From picking up a cube to writing with a pen – learning dexterous manipulation skills on real-world robotic systems 28 July 2020

Links

Contact Us

Max Planck Institute for Intelligent Systems

Max-Planck-Ring 4
72076 Tübingen

Heisenbergstr. 3
70569 Stuttgart

Germany

For website questions and technical problems please contact:

© 2020 Max-Planck-Gesellschaft - Imprint | Privacy Policy