Publications | Empirical Inference - Max Planck Institute for Intelligent Systems

162 results (View BibTeX file of all listed publications)

2010

Markerless tracking of Dynamic 3D Scans of Faces

Walder, C., Breidt, M., Bülthoff, H., Schölkopf, B., Curio, C.

In Dynamic Faces: Insights from Experiments and Computation, pages: 255-276, (Editors: Curio, C., Bülthoff, H. H. and Giese, M. A.), MIT Press, Cambridge, MA, USA, December 2010 (inbook)

Web [BibTex]

2010

Walder, C., Breidt, M., Bülthoff, H., Schölkopf, B., Curio, C. Markerless tracking of Dynamic 3D Scans of Faces In Dynamic Faces: Insights from Experiments and Computation, pages: 255-276, (Editors: Curio, C., Bülthoff, H. H. and Giese, M. A.), MIT Press, Cambridge, MA, USA, December 2010 (inbook)

Web [BibTex]

Causal relationships between frequency bands of extracellular signals in visual cortex revealed by an information theoretic analysis

Besserve, M., Schölkopf, B., Logothetis, N., Panzeri, S.

Journal of Computational Neuroscience, 29(3):547-566, December 2010 (article)

PDF DOI [BibTex]

Besserve, M., Schölkopf, B., Logothetis, N., Panzeri, S. Causal relationships between frequency bands of extracellular signals in visual cortex revealed by an information theoretic analysis Journal of Computational Neuroscience, 29(3):547-566, December 2010 (article)

PDF DOI [BibTex]

Tackling Box-Constrained Optimization via a New Projected Quasi-Newton Approach

Kim, D., Sra, S., Dhillon, I.

SIAM Journal on Scientific Computing, 32(6):3548-3563 , December 2010 (article)

Abstract

Numerous scientific applications across a variety of fields depend on box-constrained convex optimization. Box-constrained problems therefore continue to attract research interest. We address box-constrained (strictly convex) problems by deriving two new quasi-Newton algorithms. Our algorithms are positioned between the projected-gradient [J. B. Rosen, J. SIAM, 8 (1960), pp. 181–217] and projected-Newton [D. P. Bertsekas, SIAM J. Control Optim., 20 (1982), pp. 221–246] methods. We also prove their convergence under a simple Armijo step-size rule. We provide experimental results for two particular box-constrained problems: nonnegative least squares (NNLS), and nonnegative Kullback–Leibler (NNKL) minimization. For both NNLS and NNKL our algorithms perform competitively as compared to well-established methods on medium-sized problems; for larger problems our approach frequently outperforms the competition.

Web DOI [BibTex]

Kim, D., Sra, S., Dhillon, I. Tackling Box-Constrained Optimization via a New Projected Quasi-Newton Approach SIAM Journal on Scientific Computing, 32(6):3548-3563 , December 2010 (article)

Web DOI [BibTex]

Algorithmen zum Automatischen Erlernen von Motorfähigkeiten

Peters, J., Kober, J., Schaal, S.

at - Automatisierungstechnik, 58(12):688-694, December 2010 (article)

Abstract

Robot learning methods which allow autonomous robots to adapt to novel situations have been a long standing vision of robotics, artificial intelligence, and cognitive sciences. However, to date, learning techniques have yet to fulfill this promise as only few methods manage to scale into the high-dimensional domains of manipulator robotics, or even the new upcoming trend of humanoid robotics. If possible, scaling was usually only achieved in precisely pre-structured domains. In this paper, we investigate the ingredients for a general approach policy learning with the goal of an application to motor skill refinement in order to get one step closer towards human-like performance. For doing so, we study two major components for such an approach, i. e., firstly, we study policy learning algorithms which can be applied in the general setting of motor skill learning, and, secondly, we study a theoretically well-founded general approach to representing the required control structures for task representation and execution.

Web DOI [BibTex]

Peters, J., Kober, J., Schaal, S. Algorithmen zum Automatischen Erlernen von Motorfähigkeiten at - Automatisierungstechnik, 58(12):688-694, December 2010 (article)

Web DOI [BibTex]

PAC-Bayesian Analysis of Co-clustering and Beyond

Seldin, Y., Tishby, N.

Journal of Machine Learning Research, 11, pages: 3595-3646, December 2010 (article)

PDF PDF [BibTex]

Seldin, Y., Tishby, N. PAC-Bayesian Analysis of Co-clustering and Beyond Journal of Machine Learning Research, 11, pages: 3595-3646, December 2010 (article)

PDF PDF [BibTex]

Policy Gradient Methods

Peters, J., Bagnell, J.

In Encyclopedia of Machine Learning, pages: 774-776, (Editors: Sammut, C. and Webb, G. I.), Springer, Berlin, Germany, December 2010 (inbook)

PDF Web DOI [BibTex]

Peters, J., Bagnell, J. Policy Gradient Methods In Encyclopedia of Machine Learning, pages: 774-776, (Editors: Sammut, C. and Webb, G. I.), Springer, Berlin, Germany, December 2010 (inbook)

PDF Web DOI [BibTex]

Gaussian Processes for Machine Learning (GPML) Toolbox

Rasmussen, C., Nickisch, H.

Journal of Machine Learning Research, 11, pages: 3011-3015, November 2010 (article)

Abstract

The GPML toolbox provides a wide range of functionality for Gaussian process (GP) inference and prediction. GPs are specified by mean and covariance functions; we offer a library of simple mean and covariance functions and mechanisms to compose more complex ones. Several likelihood functions are supported including Gaussian and heavy-tailed for regression as well as others suitable for classification. Finally, a range of inference methods is provided, including exact and variational inference, Expectation Propagation, and Laplace's method dealing with non-Gaussian likelihoods and FITC for dealing with large regression tasks.

Web [BibTex]

Rasmussen, C., Nickisch, H. Gaussian Processes for Machine Learning (GPML) Toolbox Journal of Machine Learning Research, 11, pages: 3011-3015, November 2010 (article)

Web [BibTex]

Cryo-EM structure and rRNA model of a translating eukaryotic 80S ribosome at 5.5-Å resolution

Proceedings of the National Academy of Sciences of the United States of America, 107(46):19748-19753, November 2010 (article)

Abstract

Protein biosynthesis, the translation of the genetic code into polypeptides, occurs on ribonucleoprotein particles called ribosomes. Although X-ray structures of bacterial ribosomes are available, high-resolution structures of eukaryotic 80S ribosomes are lacking. Using cryoelectron microscopy and single-particle reconstruction, we have determined the structure of a translating plant (Triticum aestivum) 80S ribosome at 5.5-Å resolution. This map, together with a 6.1-Å map of a Saccharomyces cerevisiae 80S ribosome, has enabled us to model ∼98% of the rRNA. Accurate assignment of the rRNA expansion segments (ES) and variable regions has revealed unique ES–ES and r-protein–ES interactions, providing insight into the structure and evolution of the eukaryotic ribosome.

Web DOI [BibTex]

Armache, J-P., Jarasch, A., Anger, AM., Villa, E., Becker, T., Bhushan, S., Jossinet, F., Habeck, M., Dindar, G., Franckenberg, S., Marquez, V., Mielke, T., Thomm, M., Berninghausen, O., Beatrix, B., Söding, J., Westhof, E., Wilson, DN., Beckmann, R. Cryo-EM structure and rRNA model of a translating eukaryotic 80S ribosome at 5.5-Å resolution Proceedings of the National Academy of Sciences of the United States of America, 107(46):19748-19753, November 2010 (article)

Web DOI [BibTex]

Policy gradient methods

Peters, J.

Scholarpedia, 5(11):3698, November 2010 (article)

Abstract

Policy gradient methods are a type of reinforcement learning techniques that rely upon optimizing parametrized policies with respect to the expected return (long-term cumulative reward) by gradient descent. They do not suffer from many of the problems that have been marring traditional reinforcement learning approaches such as the lack of guarantees of a value function, the intractability problem resulting from uncertain state information and the complexity arising from continuous states & actions.

Web DOI [BibTex]

Peters, J. Policy gradient methods Scholarpedia, 5(11):3698, November 2010 (article)

Web DOI [BibTex]

Localization of eukaryote-specific ribosomal proteins in a 5.5-Å cryo-EM map of the 80S eukaryotic ribosome

Proceedings of the National Academy of Sciences of the United States of America, 107(46):19754-19759, November 2010 (article)

Abstract

Protein synthesis in all living organisms occurs on ribonucleoprotein particles, called ribosomes. Despite the universality of this process, eukaryotic ribosomes are significantly larger in size than their bacterial counterparts due in part to the presence of 80 r proteins rather than 54 in bacteria. Using cryoelectron microscopy reconstructions of a translating plant (Triticum aestivum) 80S ribosome at 5.5-Å resolution, together with a 6.1-Å map of a translating Saccharomyces cerevisiae 80S ribosome, we have localized and modeled 74/80 (92.5%) of the ribosomal proteins, encompassing 12 archaeal/eukaryote-specific small subunit proteins as well as the complete complement of the ribosomal proteins of the eukaryotic large subunit. Near-complete atomic models of the 80S ribosome provide insights into the structure, function, and evolution of the eukaryotic translational apparatus.

Web DOI [BibTex]

Armache, J-P., Jarasch, A., Anger, AM., Villa, E., Becker, T., Bhushan, S., Jossinet, F., Habeck, M., Dindar, G., Franckenberg, S., Marquez, V., Mielke, T., Thomm, M., Berninghausen, O., Beatrix, B., Söding, J., Westhof, E., Wilson, DN., Beckmann, R. Localization of eukaryote-specific ribosomal proteins in a 5.5-Å cryo-EM map of the 80S eukaryotic ribosome Proceedings of the National Academy of Sciences of the United States of America, 107(46):19754-19759, November 2010 (article)

Web DOI [BibTex]

Approximate Inference in Graphical Models

Hennig, P.

University of Cambridge, November 2010 (phdthesis)

Web [BibTex]

Hennig, P. Approximate Inference in Graphical Models University of Cambridge, November 2010 (phdthesis)

Web [BibTex]

Spatio-Spectral Remote Sensing Image Classification With Graph Kernels

Camps-Valls, G., Shervashidze, N., Borgwardt, K.

IEEE Geoscience and Remote Sensing Letters, 7(4):741-745, October 2010 (article)

Abstract

This letter presents a graph kernel for spatio-spectral remote sensing image classification with support vector machines (SVMs). The method considers higher order relations in the neighborhood (beyond pairwise spatial relations) to iteratively compute a kernel matrix for SVM learning. The proposed kernel is easy to compute and constitutes a powerful alternative to existing approaches. The capabilities of the method are illustrated in several multi- and hyperspectral remote sensing images acquired over both urban and agricultural areas.

Web DOI [BibTex]

Camps-Valls, G., Shervashidze, N., Borgwardt, K. Spatio-Spectral Remote Sensing Image Classification With Graph Kernels IEEE Geoscience and Remote Sensing Letters, 7(4):741-745, October 2010 (article)

Web DOI [BibTex]

Causal Inference Using the Algorithmic Markov Condition

Janzing, D., Schölkopf, B.

IEEE Transactions on Information Theory, 56(10):5168-5194, October 2010 (article)

Abstract

Inferring the causal structure that links $n$ observables is usually based upon detecting statistical dependences and choosing simple graphs that make the joint measure Markovian. Here we argue why causal inference is also possible when the sample size is one. We develop a theory how to generate causal graphs explaining similarities between single objects. To this end, we replace the notion of conditional stochastic independence in the causal Markov condition with the vanishing of conditional algorithmic mutual information and describe the corresponding causal inference rules. We explain why a consistent reformulation of causal inference in terms of algorithmic complexity implies a new inference principle that takes into account also the complexity of conditional probability densities, making it possible to select among Markov equivalent causal graphs. This insight provides a theoretical foundation of a heuristic principle proposed in earlier work. We also sketch some ideas on how to replace Kolmogorov complexity with decidable complexity criteria. This can be seen as an algorithmic analog of replacing the empirically undecidable question of statistical independence with practical independence tests that are based on implicit or explicit assumptions on the underlying distribution.

PDF Web DOI [BibTex]

Janzing, D., Schölkopf, B. Causal Inference Using the Algorithmic Markov Condition IEEE Transactions on Information Theory, 56(10):5168-5194, October 2010 (article)

PDF Web DOI [BibTex]

Recurrent Policy Gradients

Wierstra, D., Förster, A., Peters, J., Schmidhuber, J.

Logic Journal of the IGPL, 18(5):620-634, October 2010 (article)

Abstract

Reinforcement learning for partially observable Markov decision problems (POMDPs) is a challenge as it requires policies with an internal state. Traditional approaches suffer significantly from this shortcoming and usually make strong assumptions on the problem domain such as perfect system models, state-estimators and a Markovian hidden system. Recurrent neural networks (RNNs) offer a natural framework for dealing with policy learning using hidden state and require only few limiting assumptions. As they can be trained well using gradient descent, they are suited for policy gradient approaches. In this paper, we present a policy gradient method, the Recurrent Policy Gradient which constitutes a model-free reinforcement learning method. It is aimed at training limited-memory stochastic policies on problems which require long-term memories of past observations. The approach involves approximating a policy gradient for a recurrent neural network by backpropagating return-weighted characteristic eligibilities through time. Using a Long Short-Term Memory RNN architecture, we are able to outperform previous RL methods on three important benchmark tasks. Furthermore, we show that using history-dependent baselines helps reducing estimation variance significantly, thus enabling our approach to tackle more challenging, highly stochastic environments.

PDF Web DOI [BibTex]

Wierstra, D., Förster, A., Peters, J., Schmidhuber, J. Recurrent Policy Gradients Logic Journal of the IGPL, 18(5):620-634, October 2010 (article)

PDF Web DOI [BibTex]

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]

Bayesian Inference and Experimental Design for Large Generalised Linear Models

Nickisch, H.

Biologische Kybernetik, Technische Universität Berlin, Berlin, Germany, September 2010 (phdthesis)

PDF Web [BibTex]

Nickisch, H. Bayesian Inference and Experimental Design for Large Generalised Linear Models Biologische Kybernetik, Technische Universität Berlin, Berlin, Germany, September 2010 (phdthesis)

PDF Web [BibTex]

Combining active learning and reactive control for robot grasping

Kroemer, O., Detry, R., Piater, J., Peters, J.

Robotics and Autonomous Systems, 58(9):1105-1116, September 2010 (article)

Abstract

Grasping an object is a task that inherently needs to be treated in a hybrid fashion. The system must decide both where and how to grasp the object. While selecting where to grasp requires learning about the object as a whole, the execution only needs to reactively adapt to the context close to the grasps location. We propose a hierarchical controller that reflects the structure of these two sub-problems, and attempts to learn solutions that work for both. A hybrid architecture is employed by the controller to make use of various machine learning methods that can cope with the large amount of uncertainty inherent to the task. The controllers upper level selects where to grasp the object using a reinforcement learner, while the lower level comprises an imitation learner and a vision-based reactive controller to determine appropriate grasping motions. The resulting system is able to quickly learn good grasps of a novel object in an unstructured environment, by executing smooth reaching motions and preshapin g the hand depending on the objects geometry. The system was evaluated both in simulation and on a real robot.

PDF Web DOI [BibTex]

Kroemer, O., Detry, R., Piater, J., Peters, J. Combining active learning and reactive control for robot grasping Robotics and Autonomous Systems, 58(9):1105-1116, September 2010 (article)

PDF Web DOI [BibTex]

Nonparametric Regression between General Riemannian Manifolds

Steinke, F., Hein, M., Schölkopf, B.

SIAM Journal on Imaging Sciences, 3(3):527-563, September 2010 (article)

Abstract

We study nonparametric regression between Riemannian manifolds based on regularized empirical risk minimization. Regularization functionals for mappings between manifolds should respect the geometry of input and output manifold and be independent of the chosen parametrization of the manifolds. We define and analyze the three most simple regularization functionals with these properties and present a rather general scheme for solving the resulting optimization problem. As application examples we discuss interpolation on the sphere, fingerprint processing, and correspondence computations between three-dimensional surfaces. We conclude with characterizing interesting and sometimes counterintuitive implications and new open problems that are specific to learning between Riemannian manifolds and are not encountered in multivariate regression in Euclidean space.

Web DOI [BibTex]

Steinke, F., Hein, M., Schölkopf, B. Nonparametric Regression between General Riemannian Manifolds SIAM Journal on Imaging Sciences, 3(3):527-563, September 2010 (article)

Web DOI [BibTex]

Hybrid PET/MRI of Intracranial Masses: Initial Experiences and Comparison to PET/CT

Boss, A., Bisdas, S., Kolb, A., Hofmann, M., Ernemann, U., Claussen, C., Pfannenberg, C., Pichler, B., Reimold, M., Stegger, L.

Journal of Nuclear Medicine, 51(8):1198-1205, August 2010 (article)

Web DOI [BibTex]

Boss, A., Bisdas, S., Kolb, A., Hofmann, M., Ernemann, U., Claussen, C., Pfannenberg, C., Pichler, B., Reimold, M., Stegger, L. Hybrid PET/MRI of Intracranial Masses: Initial Experiences and Comparison to PET/CT Journal of Nuclear Medicine, 51(8):1198-1205, August 2010 (article)

Web DOI [BibTex]

libDAI: A Free and Open Source C++ Library for Discrete Approximate Inference in Graphical Models

Mooij, JM.

Journal of Machine Learning Research, 11, pages: 2169-2173, August 2010 (article)

Abstract

This paper describes the software package libDAI, a free & open source C++ library that provides implementations of various exact and approximate inference methods for graphical models with discrete-valued variables. libDAI supports directed graphical models (Bayesian networks) as well as undirected ones (Markov random fields and factor graphs). It offers various approximations of the partition sum, marginal probability distributions and maximum probability states. Parameter learning is also supported. A feature comparison with other open source software packages for approximate inference is given. libDAI is licensed under the GPL v2+ license and is available at http://www.libdai.org.

PDF PDF [BibTex]

Mooij, JM. libDAI: A Free and Open Source C++ Library for Discrete Approximate Inference in Graphical Models Journal of Machine Learning Research, 11, pages: 2169-2173, August 2010 (article)

PDF PDF [BibTex]

Convolutive blind source separation by efficient blind deconvolution and minimal filter distortion

Zhang, K., Chan, L.

Neurocomputing, 73(13-15):2580-2588, August 2010 (article)

Abstract

Convolutive blind source separation (BSS) usually encounters two difficulties—the filter indeterminacy in the recovered sources and the relatively high computational load. In this paper we propose an efficient method to convolutive BSS, by dealing with these two issues. It consists of two stages, namely, multichannel blind deconvolution (MBD) and learning the post-filters with the minimum filter distortion (MFD) principle. We present a computationally efficient approach to MBD in the first stage: a vector autoregression (VAR) model is first fitted to the data, admitting a closed-form solution and giving temporally independent errors; traditional independent component analysis (ICA) is then applied to these errors to produce the MBD results. In the second stage, the least linear reconstruction error (LLRE) constraint of the separation system, which was previously used to regularize the solutions to nonlinear ICA, enforces a MFD principle of the estimated mixing system for convolutive BSS. One can then easily learn the post-filters to preserve the temporal structure of the sources. We show that with this principle, each recovered source is approximately the principal component of the contributions of this source to all observations. Experimental results on both synthetic data and real room recordings show the good performance of this method.

PDF PDF DOI [BibTex]

Zhang, K., Chan, L. Convolutive blind source separation by efficient blind deconvolution and minimal filter distortion Neurocomputing, 73(13-15):2580-2588, August 2010 (article)

PDF PDF DOI [BibTex]

Inferring High-Dimensional Causal Relations using Free Probability Theory

Zscheischler, J.

Humboldt Universität Berlin, Germany, August 2010 (diplomathesis)

PDF [BibTex]

Zscheischler, J. Inferring High-Dimensional Causal Relations using Free Probability Theory Humboldt Universität Berlin, Germany, August 2010 (diplomathesis)

PDF [BibTex]

Biased Feedback in Brain-Computer Interfaces

Barbero, A., Grosse-Wentrup, M.

Journal of NeuroEngineering and Rehabilitation, 7(34):1-4, July 2010 (article)

Abstract

Even though feedback is considered to play an important role in learning how to operate a brain-computer interface (BCI), to date no significant influence of feedback design on BCI-performance has been reported in literature. In this work, we adapt a standard motor-imagery BCI-paradigm to study how BCI-performance is affected by biasing the belief subjects have on their level of control over the BCI system. Our findings indicate that subjects already capable of operating a BCI are impeded by inaccurate feedback, while subjects normally performing on or close to chance level may actually benefit from an incorrect belief on their performance level. Our results imply that optimal feedback design in BCIs should take into account a subject‘s current skill level.

PDF DOI [BibTex]

Barbero, A., Grosse-Wentrup, M. Biased Feedback in Brain-Computer Interfaces Journal of NeuroEngineering and Rehabilitation, 7(34):1-4, July 2010 (article)

PDF DOI [BibTex]

Predictive Representations For Sequential Decision Making Under Uncertainty

Boularias, A.

Université Laval, Quebec, Canada, July 2010 (phdthesis)

Abstract

The problem of making decisions is ubiquitous in life. This problem becomes even more complex when the decisions should be made sequentially. In fact, the execution of an action at a given time leads to a change in the environment of the problem, and this change cannot be predicted with certainty. The aim of a decision-making process is to optimally select actions in an uncertain environment. To this end, the environment is often modeled as a dynamical system with multiple states, and the actions are executed so that the system evolves toward a desirable state. In this thesis, we proposed a family of stochastic models and algorithms in order to improve the quality of of the decision-making process. The proposed models are alternative to Markov Decision Processes, a largely used framework for this type of problems. In particular, we showed that the state of a dynamical system can be represented more compactly if it is described in terms of predictions of certain future events. We also showed that even the cognitive process of selecting actions, known as policy, can be seen as a dynamical system. Starting from this observation, we proposed a panoply of algorithms, all based on predictive policy representations, in order to solve different problems of decision-making, such as decentralized planning, reinforcement learning, or imitation learning. We also analytically and empirically demonstrated that the proposed approaches lead to a decrease in the computational complexity and an increase in the quality of the decisions, compared to standard approaches for planning and learning under uncertainty.

PDF [BibTex]

Boularias, A. Predictive Representations For Sequential Decision Making Under Uncertainty Université Laval, Quebec, Canada, July 2010 (phdthesis)

PDF [BibTex]

Varieties of Justification in Machine Learning

Corfield, D.

Minds and Machines, 20(2):291-301, July 2010 (article)

Abstract

Forms of justification for inductive machine learning techniques are discussed and classified into four types. This is done with a view to introduce some of these techniques and their justificatory guarantees to the attention of philosophers, and to initiate a discussion as to whether they must be treated separately or rather can be viewed consistently from within a single framework.

PDF DOI [BibTex]

Corfield, D. Varieties of Justification in Machine Learning Minds and Machines, 20(2):291-301, July 2010 (article)

PDF DOI [BibTex]

Dirichlet Process Gaussian Mixture Models: Choice of the Base Distribution

Görür, D., Rasmussen, C.

Journal of Computer Science and Technology, 25(4):653-664, July 2010 (article)

Abstract

In the Bayesian mixture modeling framework it is possible to infer the necessary number of components to model the data and therefore it is unnecessary to explicitly restrict the number of components. Nonparametric mixture models sidestep the problem of finding the “correct” number of mixture components by assuming infinitely many components. In this paper Dirichlet process mixture (DPM) models are cast as infinite mixture models and inference using Markov chain Monte Carlo is described. The specification of the priors on the model parameters is often guided by mathematical and practical convenience. The primary goal of this paper is to compare the choice of conjugate and non-conjugate base distributions on a particular class of DPM models which is widely used in applications, the Dirichlet process Gaussian mixture model (DPGMM). We compare computational efficiency and modeling performance of DPGMM defined using a conjugate and a conditionally conjugate base distribution. We show that better density models can result from using a wider class of priors with no or only a modest increase in computational effort.

PDF PDF DOI [BibTex]

Görür, D., Rasmussen, C. Dirichlet Process Gaussian Mixture Models: Choice of the Base Distribution Journal of Computer Science and Technology, 25(4):653-664, July 2010 (article)

PDF PDF DOI [BibTex]

Robust probabilistic superposition and comparison of protein structures

Mechelke, M., Habeck, M.

BMC Bioinformatics, 11(363):1-13, July 2010 (article)

PDF DOI [BibTex]

Mechelke, M., Habeck, M. Robust probabilistic superposition and comparison of protein structures BMC Bioinformatics, 11(363):1-13, July 2010 (article)

PDF DOI [BibTex]

Results of the GREAT08 Challenge: An image analysis competition for cosmological lensing

Bridle, S., Balan, S., Bethge, M., Gentile, M., Harmeling, S., Heymans, C., Hirsch, M., Hosseini, R., Jarvis, M., Kirk, D., Kitching, T., Kuijken, K., Lewis, A., Paulin-Henriksson, S., Schölkopf, B., Velander, M., Voigt, L., Witherick, D., Amara, A., Bernstein, G., Courbin, F., Gill, M., Heavens, A., Mandelbaum, R., Massey, R., Moghaddam, B., Rassat, A., Refregier, A., Rhodes, J., Schrabback, T., Shawe-Taylor, J., Shmakova, M., van Waerbeke, L., Wittman, D.

Monthly Notices of the Royal Astronomical Society, 405(3):2044-2061, July 2010 (article)

Abstract

We present the results of the GREAT08 Challenge, a blind analysis challenge to infer weak gravitational lensing shear distortions from images. The primary goal was to stimulate new ideas by presenting the problem to researchers outside the shear measurement community. Six GREAT08 Team methods were presented at the launch of the Challenge and five additional groups submitted results during the 6 month competition. Participants analyzed 30 million simulated galaxies with a range in signal to noise ratio, point-spread function ellipticity, galaxy size, and galaxy type. The large quantity of simulations allowed shear measurement methods to be assessed at a level of accuracy suitable for currently planned future cosmic shear observations for the first time. Different methods perform well in different parts of simulation parameter space and come close to the target level of accuracy in several of these. A number of fresh ideas have emerged as a result of the Challenge including a re-examination of the process of combining information from different galaxies, which reduces the dependence on realistic galaxy modelling. The image simulations will become increasingly sophis- ticated in future GREAT challenges, meanwhile the GREAT08 simulations remain as a benchmark for additional developments in shear measurement algorithms.

Web DOI [BibTex]

Semi-supervised Subspace Learning and Application to Human Functional Magnetic Brain Resonance Imaging Data

Shelton, J.

Biologische Kybernetik, Eberhard Karls Universität, Tübingen, Germany, July 2010 (diplomathesis)

PDF [BibTex]

Shelton, J. Semi-supervised Subspace Learning and Application to Human Functional Magnetic Brain Resonance Imaging Data Biologische Kybernetik, Eberhard Karls Universität, Tübingen, Germany, July 2010 (diplomathesis)

PDF [BibTex]

Remote Sensing Feature Selection by Kernel Dependence Estimation

Camps-Valls, G., Mooij, J., Schölkopf, B.

IEEE Geoscience and Remote Sensing Letters, 7(3):587-591, July 2010 (article)

Abstract

This letter introduces a nonlinear measure of independence between random variables for remote sensing supervised feature selection. The so-called HilbertSchmidt independence criterion (HSIC) is a kernel method for evaluating statistical dependence and it is based on computing the HilbertSchmidt norm of the cross-covariance operator of mapped samples in the corresponding Hilbert spaces. The HSIC empirical estimator is easy to compute and has good theoretical and practical properties. Rather than using this estimate for maximizing the dependence between the selected features and the class labels, we propose the more sensitive criterion of minimizing the associated HSIC p-value. Results in multispectral, hyperspectral, and SAR data feature selection for classification show the good performance of the proposed approach.

PDF Web DOI [BibTex]

Camps-Valls, G., Mooij, J., Schölkopf, B. Remote Sensing Feature Selection by Kernel Dependence Estimation IEEE Geoscience and Remote Sensing Letters, 7(3):587-591, July 2010 (article)

PDF Web DOI [BibTex]

Clustering stability: an overview

von Luxburg, U.

Foundations and Trends in Machine Learning, 2(3):235-274, July 2010 (article)

Abstract

A popular method for selecting the number of clusters is based on stability arguments: one chooses the number of clusters such that the corresponding clustering results are "most stable". In recent years, a series of papers has analyzed the behavior of this method from a theoretical point of view. However, the results are very technical and difficult to interpret for non-experts. In this paper we give a high-level overview about the existing literature on clustering stability. In addition to presenting the results in a slightly informal but accessible way, we relate them to each other and discuss their different implications.

PDF DOI [BibTex]

von Luxburg, U. Clustering stability: an overview Foundations and Trends in Machine Learning, 2(3):235-274, July 2010 (article)

PDF DOI [BibTex]

Justifying Additive Noise Model-Based Causal Discovery via Algorithmic Information Theory

Janzing, D., Steudel, B.

Open Systems and Information Dynamics, 17(2):189-212, June 2010 (article)

Abstract

A recent method for causal discovery is in many cases able to infer whether X causes Y or Y causes X for just two observed variables X and Y. It is based on the observation that there exist (non-Gaussian) joint distributions P(X,Y) for which Y may be written as a function of X up to an additive noise term that is independent of X and no such model exists from Y to X. Whenever this is the case, one prefers the causal model X → Y. Here we justify this method by showing that the causal hypothesis Y → X is unlikely because it requires a specific tuning between P(Y) and P(X|Y) to generate a distribution that admits an additive noise model from X to Y. To quantify the amount of tuning, needed we derive lower bounds on the algorithmic information shared by P(Y) and P(X|Y). This way, our justification is consistent with recent approaches for using algorithmic information theory for causal reasoning. We extend this principle to the case where P(X,Y) almost admits an additive noise model. Our results suggest that the above conclusion is more reliable if the complexity of P(Y) is high.

PDF Web DOI [BibTex]

Janzing, D., Steudel, B. Justifying Additive Noise Model-Based Causal Discovery via Algorithmic Information Theory Open Systems and Information Dynamics, 17(2):189-212, June 2010 (article)

PDF Web DOI [BibTex]

Dynamic Dissimilarity Measure for Support-Based Clustering

Lee, D., Lee, J.

IEEE Transactions on Knowledge and Data Engineering, 22(6):900-905, June 2010 (article)

Abstract

Clustering methods utilizing support estimates of a data distribution have recently attracted much attention because of their ability to generate cluster boundaries of arbitrary shape and to deal with outliers efficiently. In this paper, we propose a novel dissimilarity measure based on a dynamical system associated with support estimating functions. Theoretical foundations of the proposed measure are developed and applied to construct a clustering method that can effectively partition the whole data space. Simulation results demonstrate that clustering based on the proposed dissimilarity measure is robust to the choice of kernel parameters and able to control the number of clusters efficiently.

Web DOI [BibTex]

Lee, D., Lee, J. Dynamic Dissimilarity Measure for Support-Based Clustering IEEE Transactions on Knowledge and Data Engineering, 22(6):900-905, June 2010 (article)

Web DOI [BibTex]

Sparse Spectrum Gaussian Process Regression

Lázaro-Gredilla, M., Quiñonero-Candela, J., Rasmussen, CE., Figueiras-Vidal, AR.

Journal of Machine Learning Research, 11, pages: 1865-1881, June 2010 (article)

Abstract

We present a new sparse Gaussian Process (GP) model for regression. The key novel idea is to sparsify the spectral representation of the GP. This leads to a simple, practical algorithm for regression tasks. We compare the achievable trade-offs between predictive accuracy and computational requirements, and show that these are typically superior to existing state-of-the-art sparse approximations. We discuss both the weight space and function space representations, and note that the new construction implies priors over functions which are always stationary, and can approximate any covariance function in this class.

PDF [BibTex]

Lázaro-Gredilla, M., Quiñonero-Candela, J., Rasmussen, CE., Figueiras-Vidal, AR. Sparse Spectrum Gaussian Process Regression Journal of Machine Learning Research, 11, pages: 1865-1881, June 2010 (article)

PDF [BibTex]

Unsupervised Object Discovery: A Comparison

Tuytelaars, T., Lampert, CH., Blaschko, MB., Buntine, W.

International Journal of Computer Vision, 88(2):284-302, June 2010 (article)

Abstract

The goal of this paper is to evaluate and compare models and methods for learning to recognize basic entities in images in an unsupervised setting. In other words, we want to discover the objects present in the images by analyzing unlabeled data and searching for re-occurring patterns. We experiment with various baseline methods, methods based on latent variable models, as well as spectral clustering methods. The results are presented and compared both on subsets of Caltech256 and MSRC2, data sets that are larger and more challenging and that include more object classes than what has previously been reported in the literature. A rigorous framework for evaluating unsupervised object discovery methods is proposed.

PDF DOI [BibTex]

Tuytelaars, T., Lampert, CH., Blaschko, MB., Buntine, W. Unsupervised Object Discovery: A Comparison International Journal of Computer Vision, 88(2):284-302, June 2010 (article)

PDF DOI [BibTex]

How to Explain Individual Classification Decisions

Baehrens, D., Schroeter, T., Harmeling, S., Kawanabe, M., Hansen, K., Müller, K.

Journal of Machine Learning Research, 11, pages: 1803-1831, June 2010 (article)

Abstract

After building a classifier with modern tools of machine learning we typically have a black box at hand that is able to predict well for unseen data. Thus, we get an answer to the question what is the most likely label of a given unseen data point. However, most methods will provide no answer why the model predicted a particular label for a single instance and what features were most influential for that particular instance. The only method that is currently able to provide such explanations are decision trees. This paper proposes a procedure which (based on a set of assumptions) allows to explain the decisions of any classification method.

PDF PDF [BibTex]

Baehrens, D., Schroeter, T., Harmeling, S., Kawanabe, M., Hansen, K., Müller, K. How to Explain Individual Classification Decisions Journal of Machine Learning Research, 11, pages: 1803-1831, June 2010 (article)

PDF PDF [BibTex]

Single-Image Super-Resolution Using Sparse Regression and Natural Image Prior

Kim, K., Kwon, Y.

IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(6):1127-1133, June 2010 (article)

Abstract

This paper proposes a framework for single-image super-resolution. The underlying idea is to learn a map from input low-resolution images to target high-resolution images based on example pairs of input and output images. Kernel ridge regression (KRR) is adopted for this purpose. To reduce the time complexity of training and testing for KRR, a sparse solution is found by combining the ideas of kernel matching pursuit and gradient descent. As a regularized solution, KRR leads to a better generalization than simply storing the examples as has been done in existing example-based algorithms and results in much less noisy images. However, this may introduce blurring and ringing artifacts around major edges as sharp changes are penalized severely. A prior model of a generic image class which takes into account the discontinuity property of images is adopted to resolve this problem. Comparison with existing algorithms shows the effectiveness of the proposed method.

Web DOI [BibTex]

Kim, K., Kwon, Y. Single-Image Super-Resolution Using Sparse Regression and Natural Image Prior IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(6):1127-1133, June 2010 (article)

Web DOI [BibTex]

Imitation and Reinforcement Learning

Kober, J., Peters, J.

IEEE Robotics and Automation Magazine, 17(2):55-62, June 2010 (article)

Abstract

In this article, we present both novel learning algorithms and experiments using the dynamical system MPs. As such, we describe this MP representation in a way that it is straightforward to reproduce. We review an appropriate imitation learning method, i.e., locally weighted regression, and show how this method can be used both for initializing RL tasks as well as for modifying the start-up phase in a rhythmic task. We also show our current best-suited RL algorithm for this framework, i.e., PoWER. We present two complex motor tasks, i.e., ball-in-a-cup and ball paddling, learned on a real, physical Barrett WAM, using the methods presented in this article. Of particular interest is the ball-paddling application, as it requires a combination of both rhythmic and discrete dynamical systems MPs during the start-up phase to achieve a particular task.

PDF Web DOI [BibTex]

Kober, J., Peters, J. Imitation and Reinforcement Learning IEEE Robotics and Automation Magazine, 17(2):55-62, June 2010 (article)

PDF Web DOI [BibTex]

Diffusion Tensor Imaging in a Human PET/MR Hybrid System

Boss, A., Kolb, A., Hofmann, M., Bisdas, S., Nägele, T., Ernemann, U., Stegger, L., Rossi, C., Schlemmer, H., Pfannenberg, C., Reimold, M., Claussen, C., Pichler, B., Klose, U.

Investigative Radiology, 45(5):270-274, May 2010 (article)

Web DOI [BibTex]

Boss, A., Kolb, A., Hofmann, M., Bisdas, S., Nägele, T., Ernemann, U., Stegger, L., Rossi, C., Schlemmer, H., Pfannenberg, C., Reimold, M., Claussen, C., Pichler, B., Klose, U. Diffusion Tensor Imaging in a Human PET/MR Hybrid System Investigative Radiology, 45(5):270-274, May 2010 (article)

Web DOI [BibTex]

A Bayesian Framework to Account for Complex Non-Genetic Factors in Gene Expression Levels Greatly Increases Power in eQTL Studies

Stegle, O., Parts, L., Durbin, R., Winn, JM.

PLoS Computational Biology, 6(5):1-11, May 2010 (article)

PDF Web DOI [BibTex]

Stegle, O., Parts, L., Durbin, R., Winn, JM. A Bayesian Framework to Account for Complex Non-Genetic Factors in Gene Expression Levels Greatly Increases Power in eQTL Studies PLoS Computational Biology, 6(5):1-11, May 2010 (article)

PDF Web DOI [BibTex]

Estimation of a Structural Vector Autoregression Model Using Non-Gaussianity

Hyvärinen, A., Zhang, K., Shimizu, S., Hoyer, P.

Journal of Machine Learning Research, 11, pages: 1709-1731, May 2010 (article)

Abstract

Analysis of causal effects between continuous-valued variables typically uses either autoregressive models or structural equation models with instantaneous effects. Estimation of Gaussian, linear structural equation models poses serious identifiability problems, which is why it was recently proposed to use non-Gaussian models. Here, we show how to combine the non-Gaussian instantaneous model with autoregressive models. This is effectively what is called a structural vector autoregression (SVAR) model, and thus our work contributes to the long-standing problem of how to estimate SVAR‘s. We show that such a non-Gaussian model is identifiable without prior knowledge of network structure. We propose computationally efficient methods for estimating the model, as well as methods to assess the significance of the causal influences. The model is successfully applied on financial and brain imaging data.

PDF Web [BibTex]

Hyvärinen, A., Zhang, K., Shimizu, S., Hoyer, P. Estimation of a Structural Vector Autoregression Model Using Non-Gaussianity Journal of Machine Learning Research, 11, pages: 1709-1731, May 2010 (article)

PDF Web [BibTex]

A Robust Bayesian Two-Sample Test for Detecting Intervals of Differential Gene Expression in Microarray Time Series

Stegle, O., Denby, KJ., Cooke, EJ., Wild, DL., Ghahramani, Z., Borgwardt, KM.

Journal of Computational Biology, 17(3):355-367, May 2010 (article)

Abstract

Understanding the regulatory mechanisms that are responsible for an organism‘s response to environmental change is an important issue in molecular biology. A first and important step towards this goal is to detect genes whose expression levels are affected by altered external conditions. A range of methods to test for differential gene expression, both in static as well as in time-course experiments, have been proposed. While these tests answer the question whether a gene is differentially expressed, they do not explicitly address the question when a gene is differentially expressed, although this information may provide insights into the course and causal structure of regulatory programs. In this article, we propose a two-sample test for identifying intervals of differential gene expression in microarray time series. Our approach is based on Gaussian process regression, can deal with arbitrary numbers of replicates, and is robust with respect to outliers. We apply our algorithm to study the response of Arabidopsis thaliana genes to an infection by a fungal pathogen using a microarray time series dataset covering 30,336 gene probes at 24 observed time points. In classification experiments, our test compares favorably with existing methods and provides additional insights into time-dependent differential expression.

Web DOI [BibTex]

Stegle, O., Denby, KJ., Cooke, EJ., Wild, DL., Ghahramani, Z., Borgwardt, KM. A Robust Bayesian Two-Sample Test for Detecting Intervals of Differential Gene Expression in Microarray Time Series Journal of Computational Biology, 17(3):355-367, May 2010 (article)

Web DOI [BibTex]

Statistical Tests for Detecting Differential RNA-Transcript Expression from Read Counts

Stegle, O., Drewe, P., Bohnert, R., Borgwardt, K., Rätsch, G.

Nature Precedings, 2010, pages: 1-11, May 2010 (article)

Abstract

As a fruit of the current revolution in sequencing technology, transcriptomes can now be analyzed at an unprecedented level of detail. These advances have been exploited for detecting differential expressed genes across biological samples and for quantifying the abundances of various RNA transcripts within one gene. However, explicit strategies for detecting the hidden differential abundances of RNA transcripts in biological samples have not been defined. In this work, we present two novel statistical tests to address this issue: a "gene structure sensitive" Poisson test for detecting differential expression when the transcript structure of the gene is known, and a kernel-based test called Maximum Mean Discrepancy when it is unknown. We analyzed the proposed approaches on simulated read data for two artificial samples as well as on factual reads generated by the Illumina Genome Analyzer for two C. elegans samples. Our analysis shows that the Poisson test identifies genes with differential transcript expression considerably better that previously proposed RNA transcript quantification approaches for this task. The MMD test is able to detect a large fraction (75%) of such differential cases without the knowledge of the annotated transcripts. It is therefore well-suited to analyze RNA-Seq experiments when the genome annotations are incomplete or not available, where other approaches have to fail.

PDF DOI [BibTex]

Stegle, O., Drewe, P., Bohnert, R., Borgwardt, K., Rätsch, G. Statistical Tests for Detecting Differential RNA-Transcript Expression from Read Counts Nature Precedings, 2010, pages: 1-11, May 2010 (article)

PDF DOI [BibTex]

Parameter-exploring policy gradients

Sehnke, F., Osendorfer, C., Rückstiess, T., Graves, A., Peters, J., Schmidhuber, J.

Neural Networks, 21(4):551-559, May 2010 (article)

Abstract

We present a model-free reinforcement learning method for partially observable Markov decision problems. Our method estimates a likelihood gradient by sampling directly in parameter space, which leads to lower variance gradient estimates than obtained by regular policy gradient methods. We show that for several complex control tasks, including robust standing with a humanoid robot, this method outperforms well-known algorithms from the fields of standard policy gradients, finite difference methods and population based heuristics. We also show that the improvement is largest when the parameter samples are drawn symmetrically. Lastly we analyse the importance of the individual components of our method by incrementally incorporating them into the other algorithms, and measuring the gain in performance after each step.

PDF PDF DOI [BibTex]

Sehnke, F., Osendorfer, C., Rückstiess, T., Graves, A., Peters, J., Schmidhuber, J. Parameter-exploring policy gradients Neural Networks, 21(4):551-559, May 2010 (article)

PDF PDF DOI [BibTex]

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]

Estimating predictive stimulus features from psychophysical data: The decision image technique applied to human faces

Macke, J., Wichmann, F.

Journal of Vision, 10(5:22):1-24, May 2010 (article)

Abstract

One major challenge in the sensory sciences is to identify the stimulus features on which sensory systems base their computations, and which are predictive of a behavioral decision: they are a prerequisite for computational models of perception. We describe a technique (decision images) for extracting predictive stimulus features using logistic regression. A decision image not only defines a region of interest within a stimulus but is a quantitative template which defines a direction in stimulus space. Decision images thus enable the development of predictive models, as well as the generation of optimized stimuli for subsequent psychophysical investigations. Here we describe our method and apply it to data from a human face classification experiment. We show that decision images are able to predict human responses not only in terms of overall percent correct but also in terms of the probabilities with which individual faces are (mis-) classified by individual observers. We show that the most predictive dimension for gender categorization is neither aligned with the axis defined by the two class-means, nor with the first principal component of all faces-two hypotheses frequently entertained in the literature. Our method can be applied to a wide range of binary classification tasks in vision or other psychophysical contexts.

Web DOI [BibTex]

Macke, J., Wichmann, F. Estimating predictive stimulus features from psychophysical data: The decision image technique applied to human faces Journal of Vision, 10(5:22):1-24, May 2010 (article)

Web DOI [BibTex]

Animal detection in natural scenes: Critical features revisited

Wichmann, F., Drewes, J., Rosas, P., Gegenfurtner, K.

Journal of Vision, 10(4):1-27, April 2010 (article)

Abstract

S. J. Thorpe, D. Fize, and C. Marlot (1996) showed how rapidly observers can detect animals in images of natural scenes, but it is still unclear which image features support this rapid detection. A. B. Torralba and A. Oliva (2003) suggested that a simple image statistic based on the power spectrum allows the absence or presence of objects in natural scenes to be predicted. We tested whether human observers make use of power spectral differences between image categories when detecting animals in natural scenes. In Experiments 1 and 2 we found performance to be essentially independent of the power spectrum. Computational analysis revealed that the ease of classification correlates with the proposed spectral cue without being caused by it. This result is consistent with the hypothesis that in commercial stock photo databases a majority of animal images are pre-segmented from the background by the photographers and this pre-segmentation causes the power spectral differences between image categories and may, furthermore, help rapid animal detection. Data from a third experiment are consistent with this hypothesis. Together, our results make it exceedingly unlikely that human observers make use of power spectral differences between animal- and no-animal images during rapid animal detection. In addition, our results point to potential confounds in the commercially available “natural image” databases whose statistics may be less natural than commonly presumed.

Web DOI [BibTex]

Wichmann, F., Drewes, J., Rosas, P., Gegenfurtner, K. Animal detection in natural scenes: Critical features revisited Journal of Vision, 10(4):1-27, April 2010 (article)

Web DOI [BibTex]

A generative model approach for decoding in the visual event-related potential-based brain-computer interface speller

Martens, SMM., Leiva, JM.

Journal of Neural Engineering, 7(2):1-10, April 2010 (article)

Abstract

There is a strong tendency towards discriminative approaches in brain-computer interface (BCI) research. We argue that generative model-based approaches are worth pursuing and propose a simple generative model for the visual ERP-based BCI speller which incorporates prior knowledge about the brain signals. We show that the proposed generative method needs less training data to reach a given letter prediction performance than the state of the art discriminative approaches.

PDF PDF DOI [BibTex]

Martens, SMM., Leiva, JM. A generative model approach for decoding in the visual event-related potential-based brain-computer interface speller Journal of Neural Engineering, 7(2):1-10, April 2010 (article)

PDF PDF DOI [BibTex]

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)

PDF [BibTex]

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)

PDF [BibTex]

Graph Kernels

Vishwanathan, SVN., Schraudolph, NN., Kondor, R., Borgwardt, KM.

Journal of Machine Learning Research, 11, pages: 1201-1242, April 2010 (article)

Abstract

We present a unified framework to study graph kernels, special cases of which include the random walk (G{\"a}rtner et al., 2003; Borgwardt et al., 2005) and marginalized (Kashima et al., 2003, 2004; Mahét al., 2004) graph kernels. Through reduction to a Sylvester equation we improve the time complexity of kernel computation between unlabeled graphs with n vertices from O(n6) to O(n3). We find a spectral decomposition approach even more efficient when computing entire kernel matrices. For labeled graphs we develop conjugate gradient and fixed-point methods that take O(dn3) time per iteration, where d is the size of the label set. By extending the necessary linear algebra to Reproducing Kernel Hilbert Spaces (RKHS) we obtain the same result for d-dimensional edge kernels, and O(n4) in the infinite-dimensional case; on sparse graphs these algorithms only take O(n2) time per iteration in all cases. Experiments on graphs from bioinformatics and other application domains show that these techniques can speed up computation of the kernel by an order of magnitude or more. We also show that certain rational kernels (Cortes et al., 2002, 2003, 2004) when specialized to graphs reduce to our random walk graph kernel. Finally, we relate our framework to R-convolution kernels (Haussler, 1999) and provide a kernel that is close to the optimal assignment kernel of kernel of Fr{\"o}hlich et al. (2006) yet provably positive semi-definite.

PDF Web [BibTex]

Vishwanathan, SVN., Schraudolph, NN., Kondor, R., Borgwardt, KM. Graph Kernels Journal of Machine Learning Research, 11, pages: 1201-1242, April 2010 (article)

PDF Web [BibTex]

MPI Papers

Publication Type

Year

2010

2010

Latest News

Links

Contact Us