André Elisseeff

UAI Conference 2008 Conference Paper

Explanation Trees for Causal Bayesian Networks

• Ulf H. Nielsen
• Jean-Philippe Pellet
• André Elisseeff

Bayesian networks can be used to extract explanations about the observed state of a subset of variables. In this paper, we explicate the desiderata of an explanation and confront them with the concept of explanation proposed by existing methods. The necessity of taking into account causal approaches when a causal graph is available is discussed. We then introduce causal explanation trees, based on the construction of explanation trees using the measure of causal information ow (Ay and Polani, 2006). This approach is compared to several other methods on known networks.

NeurIPS Conference 2008 Conference Paper

Finding Latent Causes in Causal Networks: an Efficient Approach Based on Markov Blankets

• Jean-Philippe Pellet
• André Elisseeff

Causal structure-discovery techniques usually assume that all causes of more than one variable are observed. This is the so-called causal sufficiency assumption. In practice, it is untestable, and often violated. In this paper, we present an efficient causal structure-learning algorithm, suited for causally insufficient data. Similar to algorithms such as IC* and FCI, the proposed approach drops the causal sufficiency assumption and learns a structure that indicates (potential) latent causes for pairs of observed variables. Assuming a constant local density of the data-generating graph, our algorithm makes a quadratic number of conditional-independence tests w. r. t. the number of variables. We show with experiments that our algorithm is comparable to the state-of-the-art FCI algorithm in accuracy, while being several orders of magnitude faster on large problems. We conclude that MBCS* makes a new range of causally insufficient problems computationally tractable.

JMLR Journal 2008 Journal Article

Using Markov Blankets for Causal Structure Learning

• Jean-Philippe Pellet
• André Elisseeff

We show how a generic feature-selection algorithm returning strongly relevant variables can be turned into a causal structure-learning algorithm. We prove this under the Faithfulness assumption for the data distribution. In a causal graph, the strongly relevant variables for a node X are its parents, children, and children's parents (or spouses), also known as the Markov blanket of X. Identifying the spouses leads to the detection of the V-structure patterns and thus to causal orientations. Repeating the task for all variables yields a valid partially oriented causal graph. We first show an efficient way to identify the spouse links. We then perform several experiments in the continuous domain using the Recursive Feature Elimination feature-selection algorithm with Support Vector Regression and empirically verify the intuition of this direct (but computationally expensive) approach. Within the same framework, we then devise a fast and consistent algorithm, Total Conditioning (TC), and a variant, TC bw, with an explicit backward feature-selection heuristics, for Gaussian data. After running a series of comparative experiments on five artificial networks, we argue that Markov blanket algorithms such as TC/TC bw or Grow-Shrink scale better than the reference PC algorithm and provides higher structural accuracy. [abs] [ pdf ][ bib ] &copy JMLR 2008. ( edit, beta )

JMLR Journal 2003 Journal Article

An Introduction to Variable and Feature Selection (Kernel Machines Section)

• Isabelle Guyon
• André Elisseeff

Variable and feature selection have become the focus of much research in areas of application for which datasets with tens or hundreds of thousands of variables are available. These areas include text processing of internet documents, gene expression array analysis, and combinatorial chemistry. The objective of variable selection is three-fold: improving the prediction performance of the predictors, providing faster and more cost-effective predictors, and providing a better understanding of the underlying process that generated the data. The contributions of this special issue cover a wide range of aspects of such problems: providing a better definition of the objective function, feature construction, feature ranking, multivariate feature selection, efficient search methods, and feature validity assessment methods.

NeurIPS Conference 2003 Conference Paper

Semi-supervised Protein Classification Using Cluster Kernels

• Jason Weston
• Dengyong Zhou
• André Elisseeff
• William Noble
• Christina Leslie

A key issue in supervised protein classification is the representation of in- put sequences of amino acids. Recent work using string kernels for pro- tein data has achieved state-of-the-art classification performance. How- ever, such representations are based only on labeled data — examples with known 3D structures, organized into structural classes — while in practice, unlabeled data is far more plentiful. In this work, we de- velop simple and scalable cluster kernel techniques for incorporating un- labeled data into the representation of protein sequences. We show that our methods greatly improve the classification performance of string ker- nels and outperform standard approaches for using unlabeled data, such as adding close homologs of the positive examples to the training data. We achieve equal or superior performance to previously presented cluster kernel methods while achieving far greater computational efficiency.

JMLR Journal 2003 Journal Article

Use of the Zero-Norm with Linear Models and Kernel Methods (Kernel Machines Section)

• Jason Weston
• André Elisseeff
• Bernhard Schölkopf
• Mike Tipping

We explore the use of the so-called zero-norm of the parameters of linear models in learning. Minimization of such a quantity has many uses in a machine learning context: for variable or feature selection, minimizing training error and ensuring sparsity in solutions. We derive a simple but practical method for achieving these goals and discuss its relationship to existing techniques of minimizing the zero-norm. The method boils down to implementing a simple modification of vanilla SVM, namely via an iterative multiplicative rescaling of the training data. Applications we investigate which aid our discussion include variable and feature selection on biological microarray data, and multicategory classification.

ECAI Conference 2002 Conference Paper

A Simple Algorithm for Learning Stable Machines

• Savina Andonova
• André Elisseeff
• Theodoros Evgeniou
• Massimiliano Pontil

NeurIPS Conference 2002 Conference Paper

Kernel Dependency Estimation

• Jason Weston
• Olivier Chapelle
• Vladimir Vapnik
• André Elisseeff
• Bernhard Schölkopf

We consider the learning problem of finding a dependency between a general class of objects and another, possibly different, general class of objects. The objects can be for example: vectors, images, strings, trees or graphs. Such a task is made possible by employing similarity measures in both input and output spaces using ker(cid: 173) nel functions, thus embedding the objects into vector spaces. We experimentally validate our approach on several tasks: mapping strings to strings, pattern recognition, and reconstruction from par(cid: 173) tial images.

JMLR Journal 2002 Journal Article

Stability and Generalization

• Olivier Bousquet
• André Elisseeff

We define notions of stability for learning algorithms and show how to use these notions to derive generalization error bounds based on the empirical error and the leave-one-out error. The methods we use can be applied in the regression framework as well as in the classification one when the classifier is obtained by thresholding a real-valued function. We study the stability properties of large classes of learning algorithms such as regularization based algorithms. In particular we focus on Hilbert space regularization and Kullback-Leibler regularization. We demonstrate how to apply the results to SVM for regression and classification.

NeurIPS Conference 2001 Conference Paper

A kernel method for multi-labelled classification

• André Elisseeff
• Jason Weston

This article presents a Support Vector Machine (SVM) like learning sys- tem to handle multi-label problems. Such problems are usually decom- posed into many two-class problems but the expressive power of such a system can be weak [5, 7]. We explore a new direct approach. It is based on a large margin ranking system that shares a lot of common proper- ties with SVMs. We tested it on a Yeast gene functional classification problem with positive results.

NeurIPS Conference 2001 Conference Paper

On Kernel-Target Alignment

• Nello Cristianini
• John Shawe-Taylor
• André Elisseeff
• Jaz Kandola

We introduce the notion of kernel-alignment, a measure of similar(cid: 173) ity between two kernel functions or between a kernel and a target function. This quantity captures the degree of agreement between a kernel and a given learning task, and has very natural interpre(cid: 173) tations in machine learning, leading also to simple algorithms for model selection and learning. We analyse its theoretical properties, proving that it is sharply concentrated around its expected value, and we discuss its relation with other standard measures of per(cid: 173) formance. Finally we describe some of the algorithms that can be obtained within this framework, giving experimental results show(cid: 173) ing that adapting the kernel to improve alignment on the labelled data significantly increases the alignment on the test set, giving improved classification accuracy. Hence, the approach provides a principled method of performing transduction. Keywords: Kernels, alignment, eigenvectors, eigenvalues, transduction

NeurIPS Conference 2000 Conference Paper

Algorithmic Stability and Generalization Performance

• Olivier Bousquet
• André Elisseeff

We present a novel way of obtaining PAC-style bounds on the gen(cid: 173) eralization error of learning algorithms, explicitly using their stabil(cid: 173) ity properties. A stable learner is one for which the learned solution does not change much with small changes in the training set. The bounds we obtain do not depend on any measure of the complexity of the hypothesis space (e. g. VC dimension) but rather depend on how the learning algorithm searches this space, and can thus be applied even when the VC dimension is infinite. We demonstrate that regularization networks possess the required stability property and apply our method to obtain new bounds on their generalization performance.

NeurIPS Conference 1996 Conference Paper

Size of Multilayer Networks for Exact Learning: Analytic Approach

• André Elisseeff
• Hélène Paugam-Moisy

This article presents a new result about the size of a multilayer neural network computing real outputs for exact learning of a finite set of real samples. The architecture of the network is feedforward, with one hidden layer and several outputs. Starting from a fixed training set, we consider the network as a function of its weights. We derive, for a wide family of transfer functions, a lower and an upper bound on the number of hidden units for exact learning, given the size of the dataset and the dimensions of the input and output spaces.