Document Actions

Efficient Algorithms for Structured Output Learning

We work on the development of novel inference algorithms for predicting structured outputs, such as gene structures, RNA secondary structures, etc. We are particularly interested in designing efficient learning methods that can be used for problems arising in computational biology.

Hidden Markov SVMs are a recently-proposed method for predicting a label sequence based on an input sequence which are often used in speech recognition for part-of-speech tagging or named entity recognition. They combine the power and flexibility of kernel methods with the capability of Hidden Markov Models (HMM) to predict label sequences. In HM-SVMs and HMMs there is usually a state for every input symbol. This model does not allow for modeling segment lengths or other contributions that depend on the start and the end of the segment. We proposed a generalization of Hidden Markov SVMs, called Hidden Semi-Markov SVMs (HSM SVMs). In semi-Markov processes it is allowed to persist in a state for a number of time steps before transitioning into a new state. Within this segment, the system’s behavior is allowed to be non-Markovian. This adds flexibility in modeling often which is needed for applications computational biology. One of the largest problems with HM SVMs and also SHM SVMs is their high computational complexity. To solve the resulting optimization problems may become computationally infeasible when training on more than just a few hundred examples. We have developed a simple, yet very effective two-stage learning strategy based on partitioning the problem into independent sub-problems. It involves using kernels only in the first step to analyse the input sequences and to non-linearly combine kernel-based predictions in the second step. The used non-linear combination is less powerful than kernels, but still sufficient in this context and computationally much more efficient. This strategy allows us to tackle significantly larger structured output learning problems than previously possible (with several thousands of sequences) leading to a significantly better generalization ability of the trained predictor.

People specializing in this area

Group Leader

Gunnar Rätsch, Dr.

More about Gunnar Rätsch, Dr....

Alumnae and Alumni

Sören Sonnenburg, Dr.

I am interested in developing large scale structured output learning algorithms and was involved the initial algorithm used in``mSplicer''. This algorithm underwent various changes and is now used in mGene - our gene finding system.

More about Sören Sonnenburg, Dr....