Publications | Empirical Inference - Max Planck Institute for Intelligent Systems

62 results (View BibTeX file of all listed publications)

2008

no image

Frequent Subgraph Retrieval in Geometric Graph Databases

Nowozin, S., Tsuda, K.

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

Abstract

Discovery of knowledge from geometric graph databases is of particular importance in chemistry and biology, because chemical compounds and proteins are represented as graphs with 3D geometric coordinates. In such applications, scientists are not interested in the statistics of the whole database. Instead they need information about a novel drug candidate or protein at hand, represented as a query graph. We propose a polynomial-delay algorithm for geometric frequent subgraph retrieval. It enumerates all subgraphs of a single given query graph which are frequent geometric epsilon-subgraphs under the entire class of rigid geometric transformations in a database. By using geometric epsilon-subgraphs, we achieve tolerance against variations in geometry. We compare the proposed algorithm to gSpan on chemical compound data, and we show that for a given minimum support the total number of frequent patterns is substantially limited by requiring geometric matching. Although the computation time per pattern is larger than for non-geometric graph mining, the total time is within a reasonable level even for small minimum support.

2008

Nowozin, S., Tsuda, K. Frequent Subgraph Retrieval in Geometric Graph Databases (180), Max-Planck Institute for Biological Cybernetics, Tübingen, Germany, November 2008 (techreport)

no image

Simultaneous Implicit Surface Reconstruction and Meshing

Giesen, J., Maier, M., Schölkopf, B.

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

Abstract

We investigate an implicit method to compute a piecewise linear representation of a surface from a set of sample points. As implicit surface functions we use the weighted sum of piecewise linear kernel functions. For such a function we can partition Rd in such a way that these functions are linear on the subsets of the partition. For each subset in the partition we can then compute the zero level set of the function exactly as the intersection of a hyperplane with the subset.

Giesen, J., Maier, M., Schölkopf, B. Simultaneous Implicit Surface Reconstruction and Meshing (179), Max-Planck Institute for Biological Cybernetics, Tübingen, Germany, November 2008 (techreport)

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.

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

Infinite Kernel Learning

Gehler, P., Nowozin, S.

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

Abstract

In this paper we consider the problem of automatically learning the kernel from general kernel classes. Specifically we build upon the Multiple Kernel Learning (MKL) framework and in particular on the work of (Argyriou, Hauser, Micchelli, & Pontil, 2006). We will formulate a Semi-Infinite Program (SIP) to solve the problem and devise a new algorithm to solve it (Infinite Kernel Learning, IKL). The IKL algorithm is applicable to both the finite and infinite case and we find it to be faster and more stable than SimpleMKL (Rakotomamonjy, Bach, Canu, & Grandvalet, 2007) for cases of many kernels. In the second part we present the first large scale comparison of SVMs to MKL on a variety of benchmark datasets, also comparing IKL. The results show two things: a) for many datasets there is no benefit in linearly combining kernels with MKL/IKL instead of the SVM classifier, thus the flexibility of using more than one kernel seems to be of no use, b) on some datasets IKL yields impressive increases in accuracy over SVM/MKL due to the possibility of using a largely increased kernel set. In those cases, IKL remains practical, whereas both cross-validation or standard MKL is infeasible.

PDF Web [BibTex]

Gehler, P., Nowozin, S. Infinite Kernel Learning (178), Max-Planck Institute for Biological Cybernetics, Tübingen, Germany, October 2008 (techreport)

PDF Web [BibTex]

no image

Large Scale Variational Inference and Experimental Design for Sparse Generalized Linear Models

Seeger, M., Nickisch, H.

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

Seeger, M., Nickisch, H. Large Scale Variational Inference and Experimental Design for Sparse Generalized Linear Models (175), Max-Planck Institute for Biological Cybernetics, Tübingen, Germany, September 2008 (techreport)

no image

Block-Iterative Algorithms for Non-Negative Matrix Approximation

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

Abstract

In this report we present new algorithms for non-negative matrix approximation (NMA), commonly known as the NMF problem. Our methods improve upon the well-known methods of Lee & Seung [19] for both the Frobenius norm as well the Kullback-Leibler divergence versions of the problem. For the latter problem, our results are especially interesting because it seems to have witnessed much lesser algorithmic progress as compared to the Frobenius norm NMA problem. Our algorithms are based on a particular block-iterative acceleration technique for EM, which preserves the multiplicative nature of the updates and also ensures monotonicity. Furthermore, our algorithms also naturally apply to the Bregman-divergence NMA algorithms of Dhillon and Sra [8]. Experimentally, we show that our algorithms outperform the traditional Lee/Seung approach most of the time.

Sra, S. Block-Iterative Algorithms for Non-Negative Matrix Approximation (176), Max-Planck Institute for Biological Cybernetics, Tübingen, Germany, September 2008 (techreport)

no image

Approximation Algorithms for Bregman Clustering Co-clustering and Tensor Clustering

Sra, S., Jegelka, S., Banerjee, A.

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

Abstract

The Euclidean K-means problem is fundamental to clustering and over the years it has been intensely investigated. More recently, generalizations such as Bregman k-means [8], co-clustering [10], and tensor (multi-way) clustering [40] have also gained prominence. A well-known computational difficulty encountered by these clustering problems is the NP-Hardness of the associated optimization task, and commonly used methods guarantee at most local optimality. Consequently, approximation algorithms of varying degrees of sophistication have been developed, though largely for the basic Euclidean K-means (or `1-norm K-median) problem. In this paper we present approximation algorithms for several Bregman clustering problems by building upon the recent paper of Arthur and Vassilvitskii [5]. Our algorithms obtain objective values within a factor O(logK) for Bregman k-means, Bregman co-clustering, Bregman tensor clustering, and weighted kernel k-means. To our knowledge, except for some special cases, approximation algorithms have not been considered for these general clustering problems. There are several important implications of our work: (i) under the same assumptions as Ackermann et al. [1] it yields a much faster algorithm (non-exponential in K, unlike [1]) for information-theoretic clustering, (ii) it answers several open problems posed by [4], including generalizations to Bregman co-clustering, and tensor clustering, (iii) it provides practical and easy to implement methodsin contrast to several other common approximation approaches.

Sra, S., Jegelka, S., Banerjee, A. Approximation Algorithms for Bregman Clustering Co-clustering and Tensor Clustering (177), Max-Planck Institute for Biological Cybernetics, Tübingen, Germany, September 2008 (techreport)

no image

Combining Appearance and Motion for Human Action Classification in Videos

Dhillon, P., Nowozin, S., Lampert, C.

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

Abstract

We study the question of activity classification in videos and present a novel approach for recognizing human action categories in videos by combining information from appearance and motion of human body parts. Our approach uses a tracking step which involves Particle Filtering and a local non - parametric clustering step. The motion information is provided by the trajectory of the cluster modes of a local set of particles. The statistical information about the particles of that cluster over a number of frames provides the appearance information. Later we use a Bag ofWords model to build one histogram per video sequence from the set of these robust appearance and motion descriptors. These histograms provide us characteristic information which helps us to discriminate among various human actions and thus classify them correctly. We tested our approach on the standard KTH and Weizmann human action datasets and the results were comparable to the state of the art. Additionally our approach is able to distinguish between activities that involve the motion of complete body from those in which only certain body parts move. In other words, our method discriminates well between activities with gross motion like running, jogging etc. and local motion like waving, boxing etc.

Dhillon, P., Nowozin, S., Lampert, C. Combining Appearance and Motion for Human Action Classification in Videos (174), Max-Planck-Institute for Biological Cybernetics, Tübingen, Germany, August 2008 (techreport)

no image

Example-based Learning for Single-image Super-resolution and JPEG Artifact Removal

Kim, K., Kwon, Y.

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

Abstract

This paper proposes a framework for single-image super-resolution and JPEG artifact removal. The underlying idea is to learn a map from input low-quality images (suitably preprocessed low-resolution or JPEG encoded images) to target high-quality images based on example pairs of input and output images. To retain the complexity of the resulting learning problem at a moderate level, a patch-based approach is taken such that kernel ridge regression (KRR) scans the input image with a small window (patch) and produces a patchvalued output for each output pixel location. These constitute a set of candidate images each of which reflects different local information. An image output is then obtained as a convex combination of candidates for each pixel based on estimated confidences of candidates. 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 it has been done in existing example-based super-resolution 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 super-resolution and JPEG artifact removal methods shows the effectiveness of the proposed method. Furthermore, the proposed method is generic in that it has the potential to be applied to many other image enhancement applications.

Kim, K., Kwon, Y. Example-based Learning for Single-image Super-resolution and JPEG Artifact Removal (173), Max-Planck-Institute for Biological Cybernetics, Tübingen, Germany, August 2008 (techreport)

no image

Unsupervised Bayesian Time-series Segmentation based on Linear Gaussian State-space Models

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

Abstract

Unsupervised time-series segmentation in the general scenario in which the number of segment-types and segment boundaries are a priori unknown is a fundamental problem in many applications and requires an accurate segmentation model as well as a way of determining an appropriate number of segment-types. In most approaches, segmentation and determination of number of segment-types are addressed in two separate steps, since the segmentation model assumes a predefined number of segment-types. The determination of number of segment-types is thus achieved by training and comparing several separate models. In this paper, we take a Bayesian approach to a segmentation model based on linear Gaussian state-space models to achieve structure selection within the model. An appropriate prior distribution on the parameters is used to enforce a sparse parametrization, such that the model automatically selects the smallest number of underlying dynamical systems that explain the data well and a parsimonious structure for each dynamical system. As the resulting model is computationally intractable, we introduce a variational approximation, in which a reformulation of the problem enables to use an efficient inference algorithm.

Chiappa, S. Unsupervised Bayesian Time-series Segmentation based on Linear Gaussian State-space Models (171), Max-Planck-Institute for Biological Cybernetics, Tübingen, Germany, June 2008 (techreport)

no image

A New Non-monotonic Gradient Projection Method for the Non-negative Least Squares Problem

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

(TR-08-28), University of Texas, Austin, TX, USA, June 2008 (techreport)

Kim, D., Sra, S., Dhillon, I. A New Non-monotonic Gradient Projection Method for the Non-negative Least Squares Problem (TR-08-28), University of Texas, Austin, TX, USA, June 2008 (techreport)

no image

Non-monotonic Poisson Likelihood Maximization

Sra, S., Kim, D., Schölkopf, B.

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

Abstract

This report summarizes the theory and some main applications of a new non-monotonic algorithm for maximizing a Poisson Likelihood, which for Positron Emission Tomography (PET) is equivalent to minimizing the associated Kullback-Leibler Divergence, and for Transmission Tomography is similar to maximizing the dual of a maximum entropy problem. We call our method non-monotonic maximum likelihood (NMML) and show its application to different problems such as tomography and image restoration. We discuss some theoretical properties such as convergence for our algorithm. Our experimental results indicate that speedups obtained via our non-monotonic methods are substantial.

Sra, S., Kim, D., Schölkopf, B. Non-monotonic Poisson Likelihood Maximization (170), Max-Planck Institute for Biological Cybernetics, Tübingen, Germany, June 2008 (techreport)

no image

A Kernel Method for the Two-sample Problem

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

(157), Max-Planck-Institute for Biological Cybernetics Tübingen, April 2008 (techreport)

Abstract

We propose a framework for analyzing and comparing distributions, allowing us to design 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). We present two tests based on large deviation bounds for the test statistic, while a third is based on the asymptotic distribution of this statistic. The test statistic can be computed in quadratic time, although efficient linear time approximations are available. Several classical metrics on distributions are recovered when the function space used to compute the difference in expectations is allowed to be more general (eg.~a Banach space). 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.

Gretton, A., Borgwardt, K., Rasch, M., Schölkopf, B., Smola, A. A Kernel Method for the Two-sample Problem (157), Max-Planck-Institute for Biological Cybernetics Tübingen, April 2008 (techreport)

no image

Energy Functionals for Manifold-valued Mappings and Their Properties

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

(167), Max Planck Institute for Biological Cybernetics, Tübingen, January 2008 (techreport)

Abstract

This technical report is merely an extended version of the appendix of Steinke et.al. "Manifold-valued Thin-Plate Splines with Applications in Computer Graphics" (2008) with complete proofs, which had to be omitted due to space restrictions. This technical report requires a basic knowledge of differential geometry. However, apart from that requirement the technical report is self-contained.

Hein, M., Steinke, F., Schölkopf, B. Energy Functionals for Manifold-valued Mappings and Their Properties (167), Max Planck Institute for Biological Cybernetics, Tübingen, January 2008 (techreport)

2006

no image

A New Projected Quasi-Newton Approach for the Nonnegative Least Squares Problem

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

(TR-06-54), Univ. of Texas, Austin, December 2006 (techreport)

2006

Kim, D., Sra, S., Dhillon, I. A New Projected Quasi-Newton Approach for the Nonnegative Least Squares Problem (TR-06-54), Univ. of Texas, Austin, December 2006 (techreport)

no image

Probabilistic inference for solving (PO)MDPs

Toussaint, M., Harmeling, S., Storkey, A.

(934), School of Informatics, University of Edinburgh, December 2006 (techreport)

Toussaint, M., Harmeling, S., Storkey, A. Probabilistic inference for solving (PO)MDPs (934), School of Informatics, University of Edinburgh, December 2006 (techreport)

no image

Minimal Logical Constraint Covering Sets

Sinz, F., Schölkopf, B.

(155), Max Planck Institute for Biological Cybernetics, Tübingen, December 2006 (techreport)

Abstract

We propose a general framework for computing minimal set covers under class of certain logical constraints. The underlying idea is to transform the problem into a mathematical programm under linear constraints. In this sense it can be seen as a natural extension of the vector quantization algorithm proposed by Tipping and Schoelkopf. We show which class of logical constraints can be cast and relaxed into linear constraints and give an algorithm for the transformation.

Sinz, F., Schölkopf, B. Minimal Logical Constraint Covering Sets (155), Max Planck Institute for Biological Cybernetics, Tübingen, December 2006 (techreport)

no image

New Methods for the P300 Visual Speller

Biessmann, F.

(1), (Editors: Hill, J. ), Max-Planck Institute for Biological Cybernetics, Tübingen, Germany, November 2006 (techreport)

Biessmann, F. New Methods for the P300 Visual Speller (1), (Editors: Hill, J. ), Max-Planck Institute for Biological Cybernetics, Tübingen, Germany, November 2006 (techreport)

no image

Geometric Analysis of Hilbert Schmidt Independence criterion based ICA contrast function

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

(PA006080), National ICT Australia, Canberra, Australia, October 2006 (techreport)

Shen, H., Jegelka, S., Gretton, A. Geometric Analysis of Hilbert Schmidt Independence criterion based ICA contrast function (PA006080), National ICT Australia, Canberra, Australia, October 2006 (techreport)

no image

A tutorial on spectral clustering

von Luxburg, U.

(149), Max Planck Institute for Biological Cybernetics, Tübingen, August 2006 (techreport)

Abstract

In recent years, spectral clustering has become one of the most popular modern clustering algorithms. It is simple to implement, can be solved efficiently by standard linear algebra software, and very often outperforms traditional clustering algorithms such as the k-means algorithm. Nevertheless, on the first glance spectral clustering looks a bit mysterious, and it is not obvious to see why it works at all and what it really does. This article is a tutorial introduction to spectral clustering. We describe different graph Laplacians and their basic properties, present the most common spectral clustering algorithms, and derive those algorithms from scratch by several different approaches. Advantages and disadvantages of the different spectral clustering algorithms are discussed.

von Luxburg, U. A tutorial on spectral clustering (149), Max Planck Institute for Biological Cybernetics, Tübingen, August 2006 (techreport)

no image

Towards the Inference of Graphs on Ordered Vertexes

Zien, A., Raetsch, G., Ong, C.

(150), Max Planck Institute for Biological Cybernetics, Tübingen, August 2006 (techreport)

Abstract

We propose novel methods for machine learning of structured output spaces. Specifically, we consider outputs which are graphs with vertices that have a natural order. We consider the usual adjacency matrix representation of graphs, as well as two other representations for such a graph: (a) decomposing the graph into a set of paths, (b) converting the graph into a single sequence of nodes with labeled edges. For each of the three representations, we propose an encoding and decoding scheme. We also propose an evaluation measure for comparing two graphs.

Zien, A., Raetsch, G., Ong, C. Towards the Inference of Graphs on Ordered Vertexes (150), Max Planck Institute for Biological Cybernetics, Tübingen, August 2006 (techreport)

no image

Nonnegative Matrix Approximation: Algorithms and Applications

Sra, S., Dhillon, I.

Univ. of Texas, Austin, May 2006 (techreport)

Sra, S., Dhillon, I. Nonnegative Matrix Approximation: Algorithms and Applications Univ. of Texas, Austin, May 2006 (techreport)

no image

An Automated Combination of Sequence Motif Kernels for Predicting Protein Subcellular Localization

Zien, A., Ong, C.

(146), Max Planck Institute for Biological Cybernetics, Tübingen, April 2006 (techreport)

Abstract

Protein subcellular localization is a crucial ingredient to many important inferences about cellular processes, including prediction of protein function and protein interactions. While many predictive computational tools have been proposed, they tend to have complicated architectures and require many design decisions from the developer. We propose an elegant and fully automated approach to building a prediction system for protein subcellular localization. We propose a new class of protein sequence kernels which considers all motifs including motifs with gaps. This class of kernels allows the inclusion of pairwise amino acid distances into their computation. We further propose a multiclass support vector machine method which directly solves protein subcellular localization without resorting to the common approach of splitting the problem into several binary classification problems. To automatically search over families of possible amino acid motifs, we generalize our method to optimize over multiple kernels at the same time. We compare our automated approach to four other predictors on three different datasets.

PDF Web [BibTex]

Zien, A., Ong, C. An Automated Combination of Sequence Motif Kernels for Predicting Protein Subcellular Localization (146), Max Planck Institute for Biological Cybernetics, Tübingen, April 2006 (techreport)

PDF Web [BibTex]

no image

Training a Support Vector Machine in the Primal

(147), Max Planck Institute for Biological Cybernetics, Tübingen, April 2006, The version in the "Large Scale Kernel Machines" book is more up to date. (techreport)

Abstract

Most literature on Support Vector Machines (SVMs) concentrate on the dual optimization problem. In this paper, we would like to point out that the primal problem can also be solved efficiently, both for linear and non-linear SVMs, and there is no reason for ignoring it. Moreover, from the primal point of view, new families of algorithms for large scale SVM training can be investigated.

Chapelle, O. Training a Support Vector Machine in the Primal (147), Max Planck Institute for Biological Cybernetics, Tübingen, April 2006, The version in the "Large Scale Kernel Machines" book is more up to date. (techreport)

no image

Cross-Validation Optimization for Structured Hessian Kernel Methods

Seeger, M., Chapelle, O.

Max-Planck Institute for Biological Cybernetics, Tübingen, Germany, February 2006 (techreport)

Abstract

We address the problem of learning hyperparameters in kernel methods for which the Hessian of the objective is structured. We propose an approximation to the cross-validation log likelihood whose gradient can be computed analytically, solving the hyperparameter learning problem efficiently through nonlinear optimization. Crucially, our learning method is based entirely on matrix-vector multiplication primitives with the kernel matrices and their derivatives, allowing straightforward specialization to new kernels or to large datasets. When applied to the problem of multi-way classification, our method scales linearly in the number of classes and gives rise to state-of-the-art results on a remote imaging task.

PDF Web [BibTex]

Seeger, M., Chapelle, O. Cross-Validation Optimization for Structured Hessian Kernel Methods Max-Planck Institute for Biological Cybernetics, Tübingen, Germany, February 2006 (techreport)

PDF Web [BibTex]

Thumb xl screen shot 2012 06 06 at 11.31.38 am

Implicit Wiener Series, Part II: Regularised estimation

Gehler, P., Franz, M.

(148), Max Planck Institute, 2006 (techreport)

Gehler, P., Franz, M. Implicit Wiener Series, Part II: Regularised estimation (148), Max Planck Institute, 2006 (techreport)

2005

no image

Popper, Falsification and the VC-dimension

Corfield, D., Schölkopf, B., Vapnik, V.

(145), Max Planck Institute for Biological Cybernetics, November 2005 (techreport)

2005

Corfield, D., Schölkopf, B., Vapnik, V. Popper, Falsification and the VC-dimension (145), Max Planck Institute for Biological Cybernetics, November 2005 (techreport)

no image

A Combinatorial View of Graph Laplacians

(144), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, August 2005 (techreport)

Abstract

Discussions about different graph Laplacian, mainly normalized and unnormalized versions of graph Laplacian, have been ardent with respect to various methods in clustering and graph based semi-supervised learning. Previous research on graph Laplacians investigated their convergence properties to Laplacian operators on continuous manifolds. There is still no strong proof on convergence for the normalized Laplacian. In this paper, we analyze different variants of graph Laplacians directly from the ways solving the original graph partitioning problem. The graph partitioning problem is a well-known combinatorial NP hard optimization problem. The spectral solutions provide evidence that normalized Laplacian encodes more reasonable considerations for graph partitioning. We also provide some examples to show their differences.

Huang, J. A Combinatorial View of Graph Laplacians (144), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, August 2005 (techreport)

no image

Beyond Pairwise Classification and Clustering Using Hypergraphs

Zhou, D., Huang, J., Schölkopf, B.

(143), Max Planck Institute for Biological Cybernetics, August 2005 (techreport)

Abstract

In many applications, relationships among objects of interest are more complex than pairwise. Simply approximating complex relationships as pairwise ones can lead to loss of information. An alternative for these applications is to analyze complex relationships among data directly, without the need to first represent the complex relationships into pairwise ones. A natural way to describe complex relationships is to use hypergraphs. A hypergraph is a graph in which edges can connect more than two vertices. Thus we consider learning from a hypergraph, and develop a general framework which is applicable to classification and clustering for complex relational data. We have applied our framework to real-world web classification problems and obtained encouraging results.

Zhou, D., Huang, J., Schölkopf, B. Beyond Pairwise Classification and Clustering Using Hypergraphs (143), Max Planck Institute for Biological Cybernetics, August 2005 (techreport)

no image

Generalized Nonnegative Matrix Approximations using Bregman Divergences

Sra, S., Dhillon, I.

Univ. of Texas at Austin, June 2005 (techreport)

Sra, S., Dhillon, I. Generalized Nonnegative Matrix Approximations using Bregman Divergences Univ. of Texas at Austin, June 2005 (techreport)

no image

Measuring Statistical Dependence with Hilbert-Schmidt Norms

Gretton, A., Bousquet, O., Smola, A., Schölkopf, B.

(140), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, June 2005 (techreport)

Abstract

We propose an independence criterion based on the eigenspectrum of covariance operators in reproducing kernel Hilbert spaces (RKHSs), consisting of an empirical estimate of the Hilbert-Schmidt norm of the cross-covariance operator (we term this a Hilbert-Schmidt Independence Criterion, or HSIC). This approach has several advantages, compared with previous kernel-based independence criteria. First, the empirical estimate is simpler than any other kernel dependence test, and requires no user-defined regularisation. Second, there is a clearly defined population quantity which the empirical estimate approaches in the large sample limit, with exponential convergence guaranteed between the two: this ensures that independence tests based on HSIC do not suffer from slow learning rates. Finally, we show in the context of independent component analysis (ICA) that the performance of HSIC is competitive with that of previously published kernel-based criteria, and of other recently published ICA methods.

Gretton, A., Bousquet, O., Smola, A., Schölkopf, B. Measuring Statistical Dependence with Hilbert-Schmidt Norms (140), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, June 2005 (techreport)

no image

Consistency of Kernel Canonical Correlation Analysis

Fukumizu, K., Bach, F., Gretton, A.

(942), Institute of Statistical Mathematics, 4-6-7 Minami-azabu, Minato-ku, Tokyo 106-8569 Japan, June 2005 (techreport)

Fukumizu, K., Bach, F., Gretton, A. Consistency of Kernel Canonical Correlation Analysis (942), Institute of Statistical Mathematics, 4-6-7 Minami-azabu, Minato-ku, Tokyo 106-8569 Japan, June 2005 (techreport)

no image

Approximate Inference for Robust Gaussian Process Regression

Kuss, M., Pfingsten, T., Csato, L., Rasmussen, C.

(136), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, 2005 (techreport)

Abstract

Gaussian process (GP) priors have been successfully used in non-parametric Bayesian regression and classification models. Inference can be performed analytically only for the regression model with Gaussian noise. For all other likelihood models inference is intractable and various approximation techniques have been proposed. In recent years expectation-propagation (EP) has been developed as a general method for approximate inference. This article provides a general summary of how expectation-propagation can be used for approximate inference in Gaussian process models. Furthermore we present a case study describing its implementation for a new robust variant of Gaussian process regression. To gain further insights into the quality of the EP approximation we present experiments in which we compare to results obtained by Markov chain Monte Carlo (MCMC) sampling.

Kuss, M., Pfingsten, T., Csato, L., Rasmussen, C. Approximate Inference for Robust Gaussian Process Regression (136), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, 2005 (techreport)

no image

Maximum-Margin Feature Combination for Detection and Categorization

BakIr, G., Wu, M., Eichhorn, J.

Max Planck Institute for Biological Cybernetics, Tübingen, Germany, 2005 (techreport)

Abstract

In this paper we are concerned with the optimal combination of features of possibly different types for detection and estimation tasks in machine vision. We propose to combine features such that the resulting classifier maximizes the margin between classes. In contrast to existing approaches which are non-convex and/or generative we propose to use a discriminative model leading to convex problem formulation and complexity control. Furthermore we assert that decision functions should not compare apples and oranges by comparing features of different types directly. Instead we propose to combine different similarity measures for each different feature type. Furthermore we argue that the question: Which feature type is more discriminative for task X? is ill-posed and show empirically that the answer to this question might depend on the complexity of the decision function.

BakIr, G., Wu, M., Eichhorn, J. Maximum-Margin Feature Combination for Detection and Categorization Max Planck Institute for Biological Cybernetics, Tübingen, Germany, 2005 (techreport)

no image

Towards a Statistical Theory of Clustering. Presented at the PASCAL workshop on clustering, London

von Luxburg, U., Ben-David, S.

Presented at the PASCAL workshop on clustering, London, 2005 (techreport)

Abstract

The goal of this paper is to discuss statistical aspects of clustering in a framework where the data to be clustered has been sampled from some unknown probability distribution. Firstly, the clustering of the data set should reveal some structure of the underlying data rather than model artifacts due to the random sampling process. Secondly, the more sample points we have, the more reliable the clustering should be. We discuss which methods can and cannot be used to tackle those problems. In particular we argue that generalization bounds as they are used in statistical learning theory of classification are unsuitable in a general clustering framework. We suggest that the main replacements of generalization bounds should be convergence proofs and stability considerations. This paper should be considered as a road map paper which identifies important questions and potentially fruitful directions for future research about statistical clustering. We do not attempt to present a complete statistical theory of clustering.

von Luxburg, U., Ben-David, S. Towards a Statistical Theory of Clustering. Presented at the PASCAL workshop on clustering, London Presented at the PASCAL workshop on clustering, London, 2005 (techreport)

no image

Approximate Bayesian Inference for Psychometric Functions using MCMC Sampling

Kuss, M., Jäkel, F., Wichmann, F.

(135), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, 2005 (techreport)

Abstract

In psychophysical studies the psychometric function is used to model the relation between the physical stimulus intensity and the observer's ability to detect or discriminate between stimuli of different intensities. In this report we propose the use of Bayesian inference to extract the information contained in experimental data estimate the parameters of psychometric functions. Since Bayesian inference cannot be performed analytically we describe how a Markov chain Monte Carlo method can be used to generate samples from the posterior distribution over parameters. These samples are used to estimate Bayesian confidence intervals and other characteristics of the posterior distribution. In addition we discuss the parameterisation of psychometric functions and the role of prior distributions in the analysis. The proposed approach is exemplified using artificially generate d data and in a case study for real experimental data. Furthermore, we compare our approach with traditional methods based on maximum-likelihood parameter estimation combined with bootstrap techniques for confidence interval estimation. The appendix provides a description of an implementation for the R environment for statistical computing and provides the code for reproducing the results discussed in the experiment section.

Kuss, M., Jäkel, F., Wichmann, F. Approximate Bayesian Inference for Psychometric Functions using MCMC Sampling (135), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, 2005 (techreport)

2003

no image

Support Vector Channel Selection in BCI

Lal, T., Schröder, M., Hinterberger, T., Weston, J., Bogdan, M., Birbaumer, N., Schölkopf, B.

(120), Max Planck Institute for Biological Cybernetics, Tuebingen, Germany, December 2003 (techreport)

Abstract

Designing a Brain Computer Interface (BCI) system one can choose from a variety of features that may be useful for classifying brain activity during a mental task. For the special case of classifying EEG signals we propose the usage of the state of the art feature selection algorithms Recursive Feature Elimination [3] and Zero-Norm Optimization [13] which are based on the training of Support Vector Machines (SVM) [11]. These algorithms can provide more accurate solutions than standard filter methods for feature selection [14]. We adapt the methods for the purpose of selecting EEG channels. For a motor imagery paradigm we show that the number of used channels can be reduced significantly without increasing the classification error. The resulting best channels agree well with the expected underlying cortical activity patterns during the mental tasks. Furthermore we show how time dependent task specific information can be visualized.

PDF Web [BibTex]

2003

Lal, T., Schröder, M., Hinterberger, T., Weston, J., Bogdan, M., Birbaumer, N., Schölkopf, B. Support Vector Channel Selection in BCI (120), Max Planck Institute for Biological Cybernetics, Tuebingen, Germany, December 2003 (techreport)

PDF Web [BibTex]

no image

Technical report on Separation methods for nonlinear mixtures

Jutten, C., Karhunen, J., Almeida, L., Harmeling, S.

(D29), EU-Project BLISS, October 2003 (techreport)

Jutten, C., Karhunen, J., Almeida, L., Harmeling, S. Technical report on Separation methods for nonlinear mixtures (D29), EU-Project BLISS, October 2003 (techreport)

no image

Image Reconstruction by Linear Programming

Tsuda, K., Rätsch, G.

(118), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, October 2003 (techreport)

Tsuda, K., Rätsch, G. Image Reconstruction by Linear Programming (118), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, October 2003 (techreport)

no image

Technical report on implementation of linear methods and validation on acoustic sources

Harmeling, S., Bünau, P., Ziehe, A., Pham, D.

EU-Project BLISS, September 2003 (techreport)

Harmeling, S., Bünau, P., Ziehe, A., Pham, D. Technical report on implementation of linear methods and validation on acoustic sources EU-Project BLISS, September 2003 (techreport)

no image

On optimization, parallelization and convergence of the Expectation-Maximization algorithm for finite mixtures of Bernoulli distributions.

Helsinki University of Technology, Helsinki, Finland, August 2003 (techreport)

Erhan, D. On optimization, parallelization and convergence of the Expectation-Maximization algorithm for finite mixtures of Bernoulli distributions. Helsinki University of Technology, Helsinki, Finland, August 2003 (techreport)

no image

Ranking on Data Manifolds

Zhou, D., Weston, J., Gretton, A., Bousquet, O., Schölkopf, B.

(113), Max Planck Institute for Biological Cybernetics, 72076 Tuebingen, Germany, June 2003 (techreport)

Abstract

The Google search engine has had a huge success with its PageRank web page ranking algorithm, which exploits global, rather than local, hyperlink structure of the World Wide Web using random walk. This algorithm can only be used for graph data, however. Here we propose a simple universal ranking algorithm for vectorial data, based on the exploration of the intrinsic global geometric structure revealed by a huge amount of data. Experimental results from image and text to bioinformatics illustrates the validity of our algorithm.

Zhou, D., Weston, J., Gretton, A., Bousquet, O., Schölkopf, B. Ranking on Data Manifolds (113), Max Planck Institute for Biological Cybernetics, 72076 Tuebingen, Germany, June 2003 (techreport)

no image

Kernel Hebbian Algorithm for Iterative Kernel Principal Component Analysis

Kim, K., Franz, M., Schölkopf, B.

(109), MPI f. biologische Kybernetik, Tuebingen, June 2003 (techreport)

Abstract

A new method for performing a kernel principal component analysis is proposed. By kernelizing the generalized Hebbian algorithm, one can iteratively estimate the principal components in a reproducing kernel Hilbert space with only linear order memory complexity. The derivation of the method, a convergence proof, and preliminary applications in image hyperresolution are presented. In addition, we discuss the extension of the method to the online learning of kernel principal components.

Kim, K., Franz, M., Schölkopf, B. Kernel Hebbian Algorithm for Iterative Kernel Principal Component Analysis (109), MPI f. biologische Kybernetik, Tuebingen, June 2003 (techreport)

no image

Learning with Local and Global Consistency

Zhou, D., Bousquet, O., Lal, T., Weston, J., Schölkopf, B.

(112), Max Planck Institute for Biological Cybernetics, Tuebingen, Germany, June 2003 (techreport)

Abstract

We consider the learning problem in the transductive setting. Given a set of points of which only some are labeled, the goal is to predict the label of the unlabeled points. A principled clue to solve such a learning problem is the consistency assumption that a classifying function should be sufficiently smooth with respect to the structure revealed by these known labeled and unlabeled points. We present a simple algorithm to obtain such a smooth solution. Our method yields encouraging experimental results on a number of classification problems and demonstrates effective use of unlabeled data.

Zhou, D., Bousquet, O., Lal, T., Weston, J., Schölkopf, B. Learning with Local and Global Consistency (112), Max Planck Institute for Biological Cybernetics, Tuebingen, Germany, June 2003 (techreport)

no image

The Metric Nearness Problem with Applications

Dhillon, I., Sra, S., Tropp, J.

Univ. of Texas at Austin, June 2003 (techreport)

Dhillon, I., Sra, S., Tropp, J. The Metric Nearness Problem with Applications Univ. of Texas at Austin, June 2003 (techreport)

no image

Implicit Wiener Series

Franz, M., Schölkopf, B.

(114), Max Planck Institute for Biological Cybernetics, June 2003 (techreport)

Abstract

The Wiener series is one of the standard methods to systematically characterize the nonlinearity of a neural system. The classical estimation method of the expansion coefficients via cross-correlation suffers from severe problems that prevent its application to high-dimensional and strongly nonlinear systems. We propose a new estimation method based on regression in a reproducing kernel Hilbert space that overcomes these problems. Numerical experiments show performance advantages in terms of convergence, interpretability and system size that can be handled.

Franz, M., Schölkopf, B. Implicit Wiener Series (114), Max Planck Institute for Biological Cybernetics, June 2003 (techreport)

no image

Machine Learning approaches to protein ranking: discriminative, semi-supervised, scalable algorithms

Weston, J., Leslie, C., Elisseeff, A., Noble, W.

(111), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, June 2003 (techreport)

Abstract

A key tool in protein function discovery is the ability to rank databases of proteins given a query amino acid sequence. The most successful method so far is a web-based tool called PSI-BLAST which uses heuristic alignment of a profile built using the large unlabeled database. It has been shown that such use of global information via an unlabeled data improves over a local measure derived from a basic pairwise alignment such as performed by PSI-BLAST's predecessor, BLAST. In this article we look at ways of leveraging techniques from the field of machine learning for the problem of ranking. We show how clustering and semi-supervised learning techniques, which aim to capture global structure in data, can significantly improve over PSI-BLAST.

Weston, J., Leslie, C., Elisseeff, A., Noble, W. Machine Learning approaches to protein ranking: discriminative, semi-supervised, scalable algorithms (111), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, June 2003 (techreport)

no image

The Geometry Of Kernel Canonical Correlation Analysis

Kuss, M., Graepel, T.

(108), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, May 2003 (techreport)

Abstract

Canonical correlation analysis (CCA) is a classical multivariate method concerned with describing linear dependencies between sets of variables. After a short exposition of the linear sample CCA problem and its analytical solution, the article proceeds with a detailed characterization of its geometry. Projection operators are used to illustrate the relations between canonical vectors and variates. The article then addresses the problem of CCA between spaces spanned by objects mapped into kernel feature spaces. An exact solution for this kernel canonical correlation (KCCA) problem is derived from a geometric point of view. It shows that the expansion coefficients of the canonical vectors in their respective feature space can be found by linear CCA in the basis induced by kernel principal component analysis. The effect of mappings into higher dimensional feature spaces is considered critically since it simplifies the CCA problem in general. Then two regularized variants of KCCA are discussed. Relations to other methods are illustrated, e.g., multicategory kernel Fisher discriminant analysis, kernel principal component regression and possible applications thereof in blind source separation.

Kuss, M., Graepel, T. The Geometry Of Kernel Canonical Correlation Analysis (108), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, May 2003 (techreport)

no image

The Kernel Mutual Information

Gretton, A., Herbrich, R., Smola, A.

Max Planck Institute for Biological Cybernetics, April 2003 (techreport)

Abstract

We introduce two new functions, the kernel covariance (KC) and the kernel mutual information (KMI), to measure the degree of independence of several continuous random variables. The former is guaranteed to be zero if and only if the random variables are pairwise independent; the latter shares this property, and is in addition an approximate upper bound on the mutual information, as measured near independence, and is based on a kernel density estimate. We show that Bach and Jordan‘s kernel generalised variance (KGV) is also an upper bound on the same kernel density estimate, but is looser. Finally, we suggest that the addition of a regularising term in the KGV causes it to approach the KMI, which motivates the introduction of this regularisation. The performance of the KC and KMI is verified in the context of instantaneous independent component analysis (ICA), by recovering both artificial and real (musical) signals following linear mixing.

PostScript [BibTex]

Gretton, A., Herbrich, R., Smola, A. The Kernel Mutual Information Max Planck Institute for Biological Cybernetics, April 2003 (techreport)

PostScript [BibTex]

no image

Expectation Maximization for Clustering on Hyperspheres

Banerjee, A., Dhillon, I., Ghosh, J., Sra, S.

Univ. of Texas at Austin, February 2003 (techreport)

Banerjee, A., Dhillon, I., Ghosh, J., Sra, S. Expectation Maximization for Clustering on Hyperspheres Univ. of Texas at Austin, February 2003 (techreport)

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

Bernhard Schölkopf meets French President Emmanuel Macron 30 October 2019
Verleihung des Körber-Preises 2019 04 September 2019
NeurIPS2019 Disentanglement Challenge kicks off - Bringing Disentanglement to the Real World 03 July 2019
Körber Prize 2019 goes to Bernhard Schölkopf 26 June 2019

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:

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