Structured prediction

Short description: Supervised machine learning techniques

Machine learning and
data mining

Problems

* Classification
* Clustering
* Regression
* Anomaly detection
* AutoML
* Association rules
* Reinforcement learning
* Structured prediction
* Feature engineering
* Feature learning
* Online learning
* Semi-supervised learning
* Unsupervised learning
* Learning to rank
* Grammar induction

Supervised learning
(classification • regression)

* Decision trees
* Ensembles
* Bagging
* Boosting
* Random forest
* k-NN
* Linear regression
* Naive Bayes
* Artificial neural networks
* Logistic regression
* Perceptron
* Relevance vector machine (RVM)
* Support vector machine (SVM)

Clustering

* BIRCH
* CURE
* Hierarchical
* k-means
* Expectation–maximization (EM)

DBSCAN
* OPTICS
* Mean-shift

Dimensionality reduction

* Factor analysis
* CCA
* ICA
* LDA
* NMF
* PCA
* t-SNE

Structured prediction

* Graphical models
* Bayes net
* Conditional random field
* Hidden Markov

Anomaly detection

* k-NN
* Local outlier factor

Artificial neural networks

* Autoencoder
* Deep learning
* DeepDream
* Multilayer perceptron
* RNN
* LSTM
* GRU
* Restricted Boltzmann machine
* GAN
* SOM
* Convolutional neural network
* U-Net

Reinforcement learning

* Q-learning
* SARSA
* Temporal difference (TD)

Theory

* Bias–variance dilemma
* Computational learning theory
* Empirical risk minimization
* Occam learning
* PAC learning
* Statistical learning
* VC theory

Machine-learning venues

* NeurIPS
* ICML
* ML
* JMLR
* ArXiv:cs.LG

Glossary of artificial intelligence

* Glossary of artificial intelligence

Related articles

* List of datasets for machine-learning research
* Outline of machine learning

* v
* t
* e

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.[1]

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.

## Contents

* 1 Applications
* 1.1 Example: sequence tagging
* 2 Techniques
* 2.1 Structured perceptron
* 3 References
* 4 External links

## 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[2] 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:

This | DT

|

is | VBZ
a | DT
tagged | JJ
sentence. | NN

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[2] 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.[3] 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:

1. First, define a function ϕ(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.
2. 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 y^: y^=argmax{y∈GEN(x)}(wT,ϕ(x,y))

Update w (from y^ towards t): w=w+c(−ϕ(x,y^)+ϕ(x,t)), where c is the learning rate.

In practice, finding the argmax over GEN(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

1. ↑ Gökhan BakIr, Ben Taskar, Thomas Hofmann, Bernhard Schölkopf, Alex Smola and SVN Vishwanathan (2007), Predicting Structured Data, MIT Press.
2. ↑ 2.0 2.1 Lafferty, J.; McCallum, A.; Pereira, F. (2001). "Conditional random fields: Probabilistic models for segmenting and labeling sequence data". pp. 282–289. http://www.cis.upenn.edu/~pereira/papers/crf.pdf.
3. ↑ Collins, Michael (2002). "Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms". Proc. EMNLP. 10. http://acl.ldc.upenn.edu/W/W02/W02-1001.pdf.

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

## External links

* Implementation of Collins structured perceptron

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Structured prediction. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Structured_prediction&oldid=4349548"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template