We introduce a general family of kernels based on weighted transducers orrational relations, rational kernels, that can be used for analysis of variable-length sequences or more generally weighted automata, in applications suchas computational biology or speech recognition. We show that rational kernels can be computed efficiently using a general algorithm ofcomposition of weighted transducers and a general single-source shortest-distance algorithm. We also describe several general families of positive definite symmetric rational kernels. These general kernels can be combined with Support Vector Machines to form efficient and powerful techniquesfor spoken-dialog classification: highly complex kernels become easy to design and implement and lead to substantial improvements inthe classification accuracy. We also show that the string kernels considered in applications to computational biology are all specific instances ofrational kernels.

Problems in which abnormal or novel situations should be detected can be approached by describing the domain of the class of typical examples. Theseapplications come from the areas of machine diagnostics, fault detection, illness identification or, in principle, refer to any problem wherelittle knowledge is available outside the typical class. In this paper we explain why proximities are natural representations for domain descriptors and we propose a simple one-class classifier for dissimilarity representations. By the use of linear programming an efficient one-class description can be found, based on a small number of prototype objects. This classifier can be made (1) more robust by transforming the dissimilarities and(2) cheaper to compute by using a reduced representation set. Finally, a comparison to a comparable one-class classifier by Campbell and Bennett is given.

Gaussian process regression allows a simple analytical treatment of exact Bayesianinference and has been found to provide good performance, yet scales badly with the number of training data. In this paper we compare severalapproaches towards scaling Gaussian processes regression to large data sets: the subset of representers method, the reduced rank approximation, online Gaussian processes, and the Bayesian committee machine.Furthermore we provide theoretical insight into some of our experimental results. We found that subset of representers methods can give good and particularly fast predictions for data sets with high and medium noise levels. On complex low noise data sets, the Bayesian committee machine achieves significantly better accuracy, yet at a higher computational cost.

We propose probabilistic generative models, called parametric mixture models(PMMs), for multiclass, multi-labeled text categorization problem.Conventionally, the binary classification approach has been employed, in which whether or not text belongs to a category isjudged by the binary classifier for every category. In contrast, our approach can simultaneously detect multiple categories of text using PMMs. We derive efficient learning and prediction algorithms forPMMs. We also empirically show that our method could significantly outperform the conventional binary methods when applied tomulti-labeled text categorization using real World Wide Web pages.

We consider two ubiquitous processes:an industrial dryer and a level tank. For these applications, wecompared three particle filtering variants: standard particle filtering, Rao-Blackwellised particle filtering and a version of Rao-Blackwellised particle filtering that does one-step look-ahead to select good sampling regions. We show that the overhead of the extra processing perparticle of the more sophisticated methods is more than compensated bythe decrease in error and variance.

Prior knowledge in the form of multiple polyhedral sets, each belonging toone of two categories, is introduced into a reformulation of a linear support vector machine classifier. The resulting formulation leadsto a linear program that can be solved efficiently. Real world examples, from DNA sequencing and breast cancer prognosis, demonstrate the effectiveness of the proposed method. Numerical results show improvement in test set accuracy after the incorporation ofprior knowledge into ordinary, data-based linear support vector machine classifiers. One experiment also shows that a linear classifier,based solely on prior knowledge, far outperforms the direct application of prior knowledge rules to classify data.

We address the question of feature selection in the context of visual recognition. It is shown that, besides efficient from a computational standpoint, the infomax principle is nearly optimal in the minimum Bayes error sense. The concept of marginal diversity is introduced, leading toa generic principle for feature selection (the principle of maximum marginal diversity) of extreme computational simplicity. The relationships betweeninfomax and the maximization of marginal diversity are identified, uncovering the existence of a family of classification procedures forwhich near optimal (in the Bayes error sense) feature selection does not require combinatorial search. Examination of this family in light of recent studies on the statistics of natural images suggests that visual recognition problems are a subset of it.

Pairwise data in empirical sciences typically violate metricity, either dueto noise or due to fallible estimates, and therefore are hard to analyze by conventional machine learning technology. In this paper we therefore study ways to work around this problem. First, we present an alternative embedding to multidimensional scaling (MDS) that allows us to apply a variety of classical machine learningand signal processing algorithms. The class of pairwise grouping algorithms which share the shift-invariance property is statistically invariant under this embedding procedure, leading to identical assignments of objects to clusters. Based on this new vectorial representation, denoising methods are applied in a second step.Both steps provide a theoretically well controlled setup to translate from pairwise data to the respective denoised metric representation.We demonstrate the practical usefulness of our theoretical reasoning by discovering structure in protein sequence data bases, visibly improving performance upon existing automatic methods. 1 Introduction Unsupervised grouping or clustering aims at extracting hidden structure from data (see e.g.

We present a meta-algorithm for learning in this framework that learns via a single linear classifier in high dimension. We discuss distribution independent as well as margin-based generalization bounds and present empirical and theoretical evidence showing that constraint classification benefits over existing methods of multiclass classification.

Recently, interest is growing to develop an effective communication interface connectingthe human brain to a computer, the'Brain-Computer Interface' (BCI). One motivation of BCI research is to provide a new communication channel substituting normal motor output in patients with severe neuromuscular disabilities. In the last decade, various neurophysiological corticalprocesses, such as slow potential shifts, movement related potentials (MRPs) or event-related desynchronization (ERD) of spontaneous EEG rhythms, were shown to be suitable for BCI, and, consequently, differentindependent approaches of extracting BCI-relevant EEGfeatures for single-trial analysis are under investigation. Here, we present and systematically compare several concepts for combining such EEGfeatures to improve the single-trial classification. Feature combinations areevaluated on movement imagination experiments with 3 subjects where EEGfeatures are based on either MRPs or ERD, or both. Those combination methods that incorporate the assumption that the single EEG-featuresare physiologically mutually independent outperform the plain method of'adding' evidence where the single-feature vectors are simply concatenated. These results strengthen the hypothesis that MRP and ERD reflect at least partially independent aspects of cortical processes and open a new perspective to boost BCI effectiveness.