Sören Sonnenburg

NeurIPS Conference 2011 Conference Paper

Hierarchical Multitask Structured Output Learning for Large-scale Sequence Segmentation

• Nico Goernitz
• Christian Widmer
• Georg Zeller
• Andre Kahles
• Gunnar Rätsch
• Sören Sonnenburg

We present a novel regularization-based Multitask Learning (MTL) formulation for Structured Output (SO) prediction for the case of hierarchical task relations. Structured output learning often results in difficult inference problems and requires large amounts of training data to obtain accurate models. We propose to use MTL to exploit information available for related structured output learning tasks by means of hierarchical regularization. Due to the combination of example sets, the cost of training models for structured output prediction can easily become infeasible for real world applications. We thus propose an efficient algorithm based on bundle methods to solve the optimization problems resulting from MTL structured output learning. We demonstrate the performance of our approach on gene finding problems from the application domain of computational biology. We show that 1) our proposed solver achieves much faster convergence than previous methods and 2) that the Hierarchical SO-MTL approach clearly outperforms considered non-MTL methods.

JMLR Journal 2011 Journal Article

l p -Norm Multiple Kernel Learning

• Marius Kloft
• Ulf Brefeld
• Sören Sonnenburg
• Alexander Zien

Learning linear combinations of multiple kernels is an appealing strategy when the right choice of features is unknown. Previous approaches to multiple kernel learning (MKL) promote sparse kernel combinations to support interpretability and scalability. Unfortunately, this l 1 -norm MKL is rarely observed to outperform trivial baselines in practical applications. To allow for robust kernel mixtures that generalize well, we extend MKL to arbitrary norms. We devise new insights on the connection between several existing MKL formulations and develop two efficient interleaved optimization strategies for arbitrary norms, that is l p -norms with p ≥ 1. This interleaved optimization is much faster than the commonly used wrapper approaches, as demonstrated on several data sets. A theoretical analysis and an experiment on controlled artificial data shed light on the appropriateness of sparse, non-sparse and l ∞ -norm MKL in various scenarios. Importantly, empirical applications of l p -norm MKL to three real-world problems from computational biology show that non-sparse MKL achieves accuracies that surpass the state-of-the-art. Data sets, source code to reproduce the experiments, implementations of the algorithms, and further information are available at http://doc.ml.tu-berlin.de/nonsparse_mkl/. [abs] [ pdf ][ bib ] &copy JMLR 2011. ( edit, beta )

ICML Conference 2010 Conference Paper

COFFIN: A Computational Framework for Linear SVMs

• Sören Sonnenburg
• Vojtech Franc

JMLR Journal 2010 Journal Article

The SHOGUN Machine Learning Toolbox

• Sören Sonnenburg
• Gunnar Rätsch
• Sebastian Henschel
• Christian Widmer
• Jonas Behr
• Alexander Zien
• Fabio de Bona
• Alexander Binder

We have developed a machine learning toolbox, called SHOGUN, which is designed for unified large-scale learning for a broad range of feature types and learning settings. It offers a considerable number of machine learning models such as support vector machines, hidden Markov models, multiple kernel learning, linear discriminant analysis, and more. Most of the specific algorithms are able to deal with several different data classes. We have used this toolbox in several applications from computational biology, some of them coming with no less than 50 million training examples and others with 7 billion test examples. With more than a thousand installations worldwide, SHOGUN is already widely adopted in the machine learning community and beyond. SHOGUN is implemented in C++ and interfaces to MATLAB TM, R, Octave, Python, and has a stand-alone command line interface. The source code is freely available under the GNU General Public License, Version 3 at http://www.shogun-toolbox.org. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2010. ( edit, beta )

NeurIPS Conference 2009 Conference Paper

Efficient and Accurate Lp-Norm Multiple Kernel Learning

• Marius Kloft
• Ulf Brefeld
• Pavel Laskov
• Klaus-Robert Müller
• Alexander Zien
• Sören Sonnenburg

Learning linear combinations of multiple kernels is an appealing strategy when the right choice of features is unknown. Previous approaches to multiple kernel learning (MKL) promote sparse kernel combinations and hence support interpretability. Unfortunately, L1-norm MKL is hardly observed to outperform trivial baselines in practical applications. To allow for robust kernel mixtures, we generalize MKL to arbitrary Lp-norms. We devise new insights on the connection between several existing MKL formulations and develop two efficient interleaved optimization strategies for arbitrary p>1. Empirically, we demonstrate that the interleaved optimization strategies are much faster compared to the traditionally used wrapper approaches. Finally, we apply Lp-norm MKL to real-world problems from computational biology, showing that non-sparse MKL achieves accuracies that go beyond the state-of-the-art.

JMLR Journal 2009 Journal Article

Optimized Cutting Plane Algorithm for Large-Scale Risk Minimization

• Vojtěch Franc
• Sören Sonnenburg

We have developed an optimized cutting plane algorithm (OCA) for solving large-scale risk minimization problems. We prove that the number of iterations OCA requires to converge to a ε precise solution is approximately linear in the sample size. We also derive OCAS, an OCA-based linear binary Support Vector Machine (SVM) solver, and OCAM, a linear multi-class SVM solver. In an extensive empirical evaluation we show that OCAS outperforms current state-of-the-art SVM solvers like SVM light, SVM perf and BMRM, achieving speedup factor more than 1,200 over SVM light on some data sets and speedup factor of 29 over SVM perf, while obtaining the same precise support vector solution. OCAS, even in the early optimization steps, often shows faster convergence than the currently prevailing approximative methods in this domain, SGD and Pegasos. In addition, our proposed linear multi-class SVM solver, OCAM, achieves speedups of factor of up to 10 compared to SVM multi-class. Finally, we use OCAS and OCAM in two real-world applications, the problem of human acceptor splice site detection and malware detection. Effectively parallelizing OCAS, we achieve state-of-the-art results on an acceptor splice site recognition problem only by being able to learn from all the available 50 million examples in a 12-million-dimensional feature space. Source code, data sets and scripts to reproduce the experiments are available at http://cmp.felk.cvut.cz/~xfrancv/ocas/html/. [abs] [ pdf ][ bib ] &copy JMLR 2009. ( edit, beta )

ICML Conference 2008 Conference Paper

Optimized cutting plane algorithm for support vector machines

• Vojtech Franc
• Sören Sonnenburg

JMLR Journal 2007 Journal Article

The Need for Open Source Software in Machine Learning

• Sören Sonnenburg
• Mikio L. Braun
• Cheng Soon Ong
• Samy Bengio
• Leon Bottou
• Geoffrey Holmes
• Yann LeCun
• Klaus-Robert Müller

Open source tools have recently reached a level of maturity which makes them suitable for building large-scale real-world systems. At the same time, the field of machine learning has developed a large body of powerful learning algorithms for diverse applications. However, the true potential of these methods is not used, since existing implementations are not openly shared, resulting in software with low usability, and weak interoperability. We argue that this situation can be significantly improved by increasing incentives for researchers to publish their software under an open source model. Additionally, we outline the problems authors are faced with when trying to publish algorithmic implementations of machine learning methods. We believe that a resource of peer reviewed software accompanied by short articles would be highly valuable to both the machine learning and the general scientific community. [abs] [ pdf ][ bib ] &copy JMLR 2007. ( edit, beta )

NeurIPS Conference 2006 Conference Paper

Computation of Similarity Measures for Sequential Data using Generalized Suffix Trees

• Konrad Rieck
• Pavel Laskov
• Sören Sonnenburg

We propose a generic algorithm for computation of similarity measures for se- quential data. The algorithm uses generalized suffix trees for efficient calculation of various kernel, distance and non-metric similarity functions. Its worst-case run-time is linear in the length of sequences and independent of the underlying embedding language, which can cover words, k-grams or all contained subse- quences. Experiments with network intrusion detection, DNA analysis and text processing applications demonstrate the utility of distances and similarity coeffi- cients for sequences as alternatives to classical kernel functions.

NeurIPS Conference 2006 Conference Paper

Large Scale Hidden Semi-Markov SVMs

• Gunnar Rätsch
• Sören Sonnenburg

We describe Hidden Semi-Markov Support Vector Machines (SHM SVMs), an extension of HM SVMs to semi-Markov chains. This allows us to predict segmentations of sequences based on segment-based features measuring properties such as the length of the segment. We propose a novel technique to partition the problem into sub-problems. The independently obtained partial solutions can then be recombined in an efficient way, which allows us to solve label sequence learning problems with several thousands of labeled sequences. We have tested our algorithm for predicting gene structures, an important problem in computational biology. Results on a well-known model organism illustrate the great potential of SHM SVMs in computational biology.

JMLR Journal 2006 Journal Article

Large Scale Multiple Kernel Learning

• Sören Sonnenburg
• Gunnar Rätsch
• Christin Schäfer
• Bernhard Schölkopf

While classical kernel-based learning algorithms are based on a single kernel, in practice it is often desirable to use multiple kernels. Lanckriet et al. (2004) considered conic combinations of kernel matrices for classification, leading to a convex quadratically constrained quadratic program. We show that it can be rewritten as a semi-infinite linear program that can be efficiently solved by recycling the standard SVM implementations. Moreover, we generalize the formulation and our method to a larger class of problems, including regression and one-class classification. Experimental results show that the proposed algorithm works for hundred thousands of examples or hundreds of kernels to be combined, and helps for automatic model selection, improving the interpretability of the learning result. In a second part we discuss general speed up mechanism for SVMs, especially when used with sparse feature maps as appear for string kernels, allowing us to train a string kernel SVM on a 10 million real-world splice data set from computational biology. We integrated multiple kernel learning in our machine learning toolbox SHOGUN for which the source code is publicly available at http://www.fml.tuebingen.mpg.de/raetsch/projects/shogun. [abs] [ pdf ][ bib ] &copy JMLR 2006. ( edit, beta )

NeurIPS Conference 2005 Conference Paper

A General and Efficient Multiple Kernel Learning Algorithm

• Sören Sonnenburg
• Gunnar Rätsch
• Christin Schäfer

While classical kernel-based learning algorithms are based on a single kernel, in practice it is often desirable to use multiple kernels. Lankriet et al. (2004) considered conic combinations of kernel matrices for classi- fication, leading to a convex quadratically constraint quadratic program. We show that it can be rewritten as a semi-infinite linear program that can be efficiently solved by recycling the standard SVM implementa- tions. Moreover, we generalize the formulation and our method to a larger class of problems, including regression and one-class classifica- tion. Experimental results show that the proposed algorithm helps for automatic model selection, improving the interpretability of the learn- ing result and works for hundred thousands of examples or hundreds of kernels to be combined. f (x) = sign N Xi=1 αiyik(xi, x) + b! ,

ICML Conference 2005 Conference Paper

Large scale genomic sequence SVM classifiers

• Sören Sonnenburg
• Gunnar Rätsch
• Bernhard Schölkopf

NeurIPS Conference 2001 Conference Paper

A New Discriminative Kernel From Probabilistic Models

• Koji Tsuda
• Motoaki Kawanabe
• Gunnar Rätsch
• Sören Sonnenburg
• Klaus-Robert Müller

Recently, Jaakkola and Haussler proposed a method for construct(cid: 173) ing kernel functions from probabilistic models. Their so called "Fisher kernel" has been combined with discriminative classifiers such as SVM and applied successfully in e. g. DNA and protein analysis. Whereas the Fisher kernel (FK) is calculated from the marginal log-likelihood, we propose the TOP kernel derived from Tangent vectors Of Posterior log-odds. Furthermore we develop a theoretical framework on feature extractors from probabilistic models and use it for analyzing FK and TOP. In experiments our new discriminative TOP kernel compares favorably to the Fisher kernel.