4th Workshop on Ensemble Methods

[ Organization | Schedule | Abstracts | Conference Site | Participation/Accomodation ]

This workshop will focus on novel theoretical and practical developments for prediction models such as boosting and bagging. In particular, the workshop aims at bringing together the machine learning view with the statistical view on ensemble methods.

This workshop is sponsored by the EU PASCAL Network of Excellence.

Organization

• Axel Benner DKFZ Heidelberg

• Torsten Hothorn LMU München

• Nicole Krämer TU Berlin

• Klaus-Robert Müller TU Berlin

• Gunnar Rätsch Friedrich-Miescher-Labor, Max Planck Gesellschaft, Tübingen

Local Organization

• Nicole Krämer TU Berlin

Schedule

The workshop takes place on February 11-12, from 9 am to 5 pm (tbc)

Abstracts

• Gunnar Rätsch Friedrich-Miescher-Labor, Max Planck Gesellschaft, Tübingen
  
  Boosting Algorithms for Maximizing the Soft Margin

  We present a novel boosting algorithm, called SoftBoost, designed for sets of binary labeled examples that are not necessarily separable by convex combinations of base hypotheses. Our algorithm achieves robustness by capping the distributions on the examples. Our update of the distribution is motivated by minimizing a relative entropy subject to the capping constraints and constraints on the edges of the obtained base hypotheses. The capping constraints imply a soft margin in the dual optimization problem. Our algorithm produces a convex combination of hypotheses whose soft margin is within delta of its maximum. We employ relative entropy projection methods to prove an O( ln N/delta^2 ) iteration bound for our algorithm, where N is number of examples. We compare our algorithm with other approaches including LPBoost, Brown- Boost, and SmoothBoost. We show that there exist cases where the number of iterations required by LPBoost grows linearly in N instead of the logarithmic growth for SoftBoost. In simulation studies we show that our algorithm converges about as fast as LPBoost, faster than BrownBoost, and much faster than SmoothBoost. In a benchmark comparison we illustrate the competitiveness of our approach.

• Harald Binder Albert-Ludwigs-Universität Freiburg
  
  Boosting for high-dimensional survival models with a focus on mandatory covariates

  There are several techniques for fitting of survival models to high-dimensional data, including several proposals for estimation by boosting. However, most of these put restrictions on estimated coefficients uniformly for all covariates. This is not adequate when there is e.g. a small number of clinical scores compared to a large number of microarray features. We therefore introduce a new boosting algorithm for censored time-to-event data using an offset-based update mechanism, that allows for tailored penalization of the covariates under consideration. Specifically, unpenalized mandatory covariates can be introduced. This allows to answer e.g. the question whether improved predictions are obtained by including microarray features in addition to classical clinical criteria. Microarray survival data from patients with diffuse large B-cell lymphoma, in combination with the recent, bootstrap-based prediction error curve technique, is used to illustrate this. In addition, the new approach also shares the favorable properties of existing boosting approaches, i.e., it results in sparse models with good prediction performance. In the present application prediction performance can be increased by using an estimation procedure that incorporates mandatory covariates into high-dimensional survival models.

  This is joint work with Martin Schumacher, Institut für Medizinische Biometrie und Medizinische Informatik, Universitätsklinikum Freiburg

• Jochen Garcke TU Berlin
  
  Machine learning with sparse grids
  

  In this talk I will introduce sparse grids and the sparse grid combination technique and then consider this discretisation approach for the machine learning problems of regression and classification. We regard regression as a problem of function reconstruction in some function space over a higher-dimensional domain. We use a regularised least squares approach and solve it using the sparse grid combination technique, where a certain sequence of conventional grids is employed. The sparse grid solution is then obtained by addition of the partial solutions using certain combination coefficients. The approach results in a non-linear function which achieves very competitive results while the computational complexity of the method scales only linearly in regard to the number of data.

• Thomas Kneib Ludwig-Maximilian-Universität München
  
  Model Choice and Variable Selection in Geoadditive Regression Models
  

  Model choice and variable selection are issues of major concern in practical regression analyses. This is not only true in generalised linear models but becomes even more obvious in geoadditive regression models comprising spatial effects, nonparametric effects of continuous covariates, interaction surfaces, random effects, and varying coefficient terms. Variable selection and model choice questions arising in such models are as follows: Should a continuous covariate be included into the model at all and if so as a linear effect or as a nonparametric, flexible effect? Is the spatial effect required in the model, i.e., is spatial correlation present beyond the spatial variation accounted for by spatially varying covariates? Are some of the covariate effects spatially varying? To answer these questions, we propose a systematic, fully automated componentwise boosting procedure. The general idea is to specify a set of candidate terms for the model and to iteratively apply the best-fitting candidate term to an updated residual vector. When applying a suitable stopping rule to the iterative process, the boosting algorithm implements a means of model choice and variable selection. Each candidate term is associated with a base-learning procedure that, in our modelling framework, can be derived based on penalised splines for univariate nonparametric effects and varying coefficients, bivariate tensor product penalised splines for spatial effects and interactions, and cluster-specific random effects. All base-learning procedures can be cast into a general modelling framework leading to simple penalised least-squares fits. This, in turn, allows to devise a generic componentwise boosting procedure for a comprehensive model class. One major difficulty is to obtain base-learners that are comparable in complexity to avoid biased selection towards more flexible effects. The trace of the hat matrix, i.e. the equivalent degrees of freedom of a flexible effect will be used as a general measure of complexity for the base-learners. A suitable reparametrisation allows us to specify any desired degree of freedom for a base-learner and to answer additional model choice questions. We demonstrate the versatility of our approach with two case studies. In the first example, an analysis of habitat suitability based on species abundance data, we demonstrate the impact of spatial correlation on variable selection and address further model choice problems in geoadditive models and models with space-varying coefficients. In the second example, forest health data are analyzed based on a complex model including nonparametric, spatial, interaction and random effects.

• Matthias Schmid Friedrich-Alexander-Universität Erlangen-Nürnberg
  
  Boosting Additive Models using Component-wise P-Splines (joint work with Torsten Hothorn)

  In recent years boosting has developed into one of the most important techniques for regularization and model fitting in high-dimensional data settings. The technique can be considered as a gradient-descent algorithm in function space and can therefore be used for a large variety of loss functions and statistical problems. An important example is boosting with the least squares (L2) loss function in combination with smoothing spline baselearners, which has been established by Buhlmann and Yu (2003) as a technique for fitting additive regression models with continuous outcomes. From a computational point of view, Buhlmann & Yu's L2-Boosting algorithm can be further improved, since the integrated squared second-order derivative penalty of smoothing spline baselearners is relatively time-consuming to evaluate. We therefore consider an efficient approximation of L2-Boosting with smoothing splines where the smoothing spline baselearners are replaced by P-spline baselearners. P-splines (Eilers and Marx 1996), which have become a standard tool for estimating generalized additive models, use a penalty based on higher-order differences of regression coefficients of adjacent knots. If the difference order is equal to 2, the penalty is a discrete approximation of the smoothing spline penalty. A major benefit of this approximation is that the dimensionlity of the penalty is reduced. Thus, when used as baselearners for a large number of variables, P-splines increase the efficiency of a boosting algorithm while yielding similar prediction errors as boosting with smoothing spline baselearners.

  By means of theoretical results and a simulation study, we additionally investigate the relationship between the boosting stopping iteration and the step length factor used for shrinking the boosting estimates. Moreover, we give a detailed analysis on the effect of various P-spline hyper-parameters on the boosting fit. Our results are illustrated by a recent application example from clinical research (Schild et al. 2007).

  
  References:
  

  • Buhlmann, P., Yu, B., 2003. Boosting with the L2 loss: regression and classification. Journal of the American Statistical Association 98, 324–339.

  • Eilers, P. H. C., Marx, B. D., 1996. Flexible smoothing with B-splines and penalties (with comments and rejoinder). Statistical Science 11 (2), 89–121.

  • Schild, R. L., Maringa, M., Siemer, J., Meurer, B., Hart, N., Goecke, T. W., Schmid, M., Hothorn, T., Hansmann, M. E., 2007. Weight estimation by three-dimensional ultrasound in the small fetus. Submitted manuscript, University of Erlangen-Nuremberg.

  • Schmid, M., Hothorn, T. (2007): Boosting additive models using component-wise P-splines. Technical Report 002, Department of Statistics, University of Munich. .pdf

• Florian Leitenstorfer Ludwig-Maximilian-Universität München
  
  Boosting in Nonparametric Regression: Constrained and Unconstrained Modeling Approaches

  Nonparametric regression provides a flexible modeling tool in modern data analysis which becomes increasingly popular. In many applications the underlying data generating structure is complex. Moreover, often one seeks to incorporate qualitative assumptions such as monotonicity in a regression framework, which one implies by prior knowledge or theoretical considerations.

  In this talk, boosting techniques for estimation of nonparametric regression models with and without qualitative restrictions are presented. These approaches are based on an expansion of the unknown functions into basis functions. The focus lies initially on the estimation of complex regression structures. The idea is to use a high-dimensional set of radial basis functions. Selection of appropriate candidates and estimation of corresponding coefficients is done simultaneously by boosting techniques. Furthermore, novel algorithms for estimation of smooth regression functions with monotonicity constraints are developed. One distinguishes between approaches for monotonic basis functions and B-splines. The stepwise structure of boosting algorithms enables one to incorporate the constraints in an elegant way. The procedures are extended to additive models with binary or Poisson response.

• Antony Unwin Universität Augsburg
  
  The Plots Thicken — Graphics and Sets of Graphics for Model Ensembles

  Graphical displays complement analytic approaches and are commonly, if inadequately and rather reluctantly, used to report results. With ensembles of models many more graphics can be useful, but they need to be chosen and organised well. How can results from many different models be informatively displayed? How can the development of iterative models be shown? Can graphics make combinations of results more intelligible and hence more interpretable? This paper builds on earlier work with Chris Volinsky and Sylvia Winkler, on ideas developed by Simon Urbanek in his doctorate at Augsburg and on joint work with Ralf Seger for his software MORET.

  References

  • Seger, R. MORET link
  • Unwin AR, Volinsky, C., Winkler S. 2003. Parallel Coordinates for Exploratory Modelling Analysis. Computational Statistics & Data Analysis 43: 553-64
  • Urbanek S. 2006. Exploratory Model Analysis: Books on Demand

• Yvan Saeys Universität Ghent
  
  Ensemble Methods and Feature Selection

  Feature selection is an important preprocessing step in many data mining applications. Important advantages of feature selection in the context of supervised learning include the ability to construct better and more compact classification models, as well as the ability to gain a deeper understanding of the problem being investigated, a characteristic that is of high importance in many bioinformatics and biomedical applications.

  In this talk, we discuss the use of ensemble feature selection techniques. Opposed to the traditional case where feature selection is often constructed only once, or in combination with one model, ensemble feature selection addresses the relevance of features by combining multiple models. Such practice is a likely promising field for many small sample/large feature space problems that are very important in the biomedical field, e.g. microarray and mass spectrometry analysis, as it might to lead to more robust feature selection.

• Mikio Braun Technische Universität Berlin
  
  Boosting Kernel Bumps
  

  We propose an efficient kernel learning method by boosting single kernel bumps. Apart from its conceptual simplicity, it is equipped with linear runtime, scalability, automatic model selection, and adaptivity to an online setting. The basic idea is far from new, but we show how by the combination of several elegant modifications, linear run-time for the boosting algorithm is achieved even though a full model selection is performed in each step.

• Nicole Krämer Technische Universität Berlin
  
  Feature Selection for heterogeneous data and arbitrary loss
  

  We introduce Group Boost, a framework for supervised dimensionality reduction if the observed data are grouped into blocks of variables. By combining orthogonal feature construction (via Boosting Orthogonal Latent Features, (BOLS)) and the penalization approach of Group Lasso, we obtain sparse features that represent different blocks of variables rather than single variables. Due to the efficiency of BOLS, sparsity can be obtained by a soft-thresholding strategy. This scales favorably even for a large number of groups. We demonstrate the stability and usefulness of our method in several simulations. Moreover, we discuss an application to heterogeneous data from drug discovery.

• Koji Tsuda Max-Planck-Institut für Biologische Kybernetik, Tübingen
  
  Substructure Boosting Methods for Graphs, Sequences and Itemsets
  

  Traditionally, boosting methods are applied to classify or regress vectorial data. However, in many fields such as computational biology and image processing, structured data like graphs, sequences and itemsets are of increasing interest. I present new boosting methods for such structured data. Our weak hypothesis is a decision stump depending on only one substructure. For graph data, a subgraph corresponds to a hypothesis. In each iteration, the substructure which optimizes the edge is obtained by a variant of frequent substructure mining methods such as LCM, prefixspan and gspan. I report successful applications to images, videos, chemical compounds, and the mutation sets of HIV reverse transcriptase.

Conference Site

TU Berlin

Monday: H 1029

Tuesday: FR 5516

Participation and Accomodation

Participants can attend the workshop free of charge. To register, please send an email to Nicole Krämer.

We recommend the following hotels that are within walking distance to TU Berlin.

• Hotel Heidelberg Knesebeckstr. 15, 10623 Berlin, Tel. +49(0)30-313 01 03
• Dorint Novotel Am Tiergarten Strasse des 17 Juni 106-108, 10623 Berlin, Tel. (+49)30-600 35 0

Please contact Andra Gerdes (gerdes@cs.tu-berlin.de) (+49)30 - 314-78621 if you want to book a hotel room.

Preliminary list of participants

1. Axel Benner
2. Harald Binder
3. Mikio Braun
4. Paul von Bünau
5. Jochen Garcke
6. Stefan Haufe
7. Sebastian Henschel
8. Sigbert Klinke
9. Thomas Kneib
10. Nicole Krämer
11. Florian Leitenstorfer
12. Klaus-Robert Müller
13. Guido Nolte
14. Gunnar Rätsch
15. Yvan Sayes
16. Matthias Schmid
17. Michael Tangermann
18. Koji Tsuda
19. Gerhard Tutz
20. Anton Unwin
21. Andreas Ziehe