Large Margin Methods for Structured Output Prediction

Many real-life data problems require effective classification algorithms able to model structural dependencies between multiple labels and to perform classification in a multivariate setting, i.e. such that complex, non-scalar predictions must be produced in correspondence to input vectors. Examples of these tasks range from natural language parsing to speech recognition, machine translation, image segmentation, handwritten character recognition or gene prediction. Recently many algorithms have been developed in this direction in the machine learning community. They are commonly referred as structured output learning approaches. The main idea behind them is to produce an effective and flexible representation of the data exploiting general dependencies between labels. It has been shown that in many applications structured prediction methods outperform models that do not directly represent correlation between inputs and output labels. Among the variety of the approaches developed in last few years, in particular large margin methods deserve attention since they have proved to be successful in several tasks. These techniques are based on the smart integration between Support Vector Machines (SVMs) and probabilistic graphical models (PGMs), so they combine the ability to learn in high dimensional feature spaces typical of kernel methods with the algorithmic efficiency and the flexibility in representing data inherited by PGMs. In this paper we review some of the most recent large margin methods summarizing the main theoretical results, addressing some important computational issues, and presenting the most successful applications. Specifically, we show results in the context of biological sequence alignment and for sequence labeling and parsing in the natural language processing field. We finally discuss some of the main challenges in this new and promising research field.