Structured Perceptron

Structured prediction or structured output learning is an umbrella term for supervised machine learning techniques that involves predicting structured objects, rather than discrete or real values.

Similar to commonly used supervised learning techniques, structured prediction models are typically trained by means of observed data in which the predicted value is compared to the ground truth, and this is used to adjust the model parameters. Due to the complexity of the model and the interrelations of predicted variables, the processes of model training and inference are often computationally infeasible, so approximate inference and learning methods are used.

Applications

An example application is the problem of translating a natural language sentence into a syntactic representation such as a parse tree. This can be seen as a structured prediction problem in which the structured output domain is the set of all possible parse trees. Structured prediction is used in a wide variety of domains including bioinformatics, natural language processing (NLP), speech recognition, and computer vision.

Example: sequence tagging

Sequence tagging is a class of problems prevalent in NLP in which input data are often sequential, for instance sentences of text. The sequence tagging problem appears in several guises, such as part-of-speech tagging (POS tagging) and named entity recognition. In POS tagging, for example, each word in a sequence must be 'tagged' with a ''class label'' representing the type of word:

:

The main challenge of this problem is to resolve ambiguity: in the above example, the words "sentence" and "tagged" in English can also be verbs.

While this problem can be solved by simply performing classification of individual tokens, this approach does not take into account the empirical fact that tags do not occur independently; instead, each tag displays a strong conditional dependence on the tag of the previous word. This fact can be exploited in a sequence model such as a hidden Markov model or conditional random field
that predicts the entire tag sequence for a sentence (rather than just individual tags) via the Viterbi algorithm.

Techniques

Probabilistic graphical models form a large class of structured prediction models. In particular, Bayesian networks and random fields are popular. Other algorithms and models for structured prediction include inductive logic programming, case-based reasoning, structured SVMs, Markov logic networks, Probabilistic Soft Logic, and constrained conditional models. The main techniques are:

* Conditional random fields
* Structured support vector machines
* Structured ''k''-nearest neighbours
* Recurrent neural networks, in particular Elman networks
* Transformers.

Structured perceptron

One of the easiest ways to understand algorithms for general structured prediction is the structured perceptron by Collins. This algorithm combines the perceptron algorithm for learning linear classifiers with an inference algorithm (classically the Viterbi algorithm when used on sequence data) and can be described abstractly as follows:

# First, define a function $\phi(x,y)$ that maps a training sample $x$ and a candidate prediction $y$ to a vector of length $n$ ($x$ and $y$ may have any structure; $n$ is problem-dependent, but must be fixed for each model). Let $GEN$ be a function that generates candidate predictions.
# Then:

::Let $w$ be a weight vector of length $n$

::For a predetermined number of iterations:

:::For each sample $x$ in the training set with true output $t$:

::::Make a prediction $\hat$: $\hat=\, \\,(w^T, \phi(x,y))$

::::Update $w$ (from $\hat$ towards $t$): $w=w+c(-\phi(x, \hat)+ \phi(x,t))$, where $c$ is the learning rate.

In practice, finding the argmax over $({x})$ is done using an algorithm such as Viterbi or a max-sum, rather than an exhaustive search through an exponentially large set of candidates.

The idea of learning is similar to that for multiclass perceptrons.

References

* Noah Smith
Linguistic Structure Prediction
2011.
* Michael Collins
Discriminative Training Methods for Hidden Markov Models
2002.

External links

Implementation of Collins structured perceptron