Editing Perceptron (section)

=== Multiclass perceptron ===
Like most other techniques for training linear classifiers, the perceptron generalizes naturally to [[multiclass classification]].  Here, the input <math>x</math> and the output <math>y</math> are drawn from arbitrary sets. A feature representation function <math>f(x,y)</math> maps each possible input/output pair to a finite-dimensional real-valued feature vector.  As before, the feature vector is multiplied by a weight vector <math>w</math>, but now the resulting score is used to choose among many possible outputs:

:<math>\hat y = \operatorname{argmax}_y f(x,y) \cdot w.</math>

Learning again iterates over the examples, predicting an output for each, leaving the weights unchanged when the predicted output matches the target, and changing them when it does not.  The update becomes:

:<math> w_{t+1} = w_t + f(x, y) - f(x,\hat y).</math>

This multiclass feedback formulation reduces to the original perceptron when <math>x</math> is a real-valued vector, <math>y</math> is chosen from <math>\{0,1\}</math>, and <math>f(x,y) = y x</math>.

For certain problems, input/output representations and features can be chosen so that <math>\mathrm{argmax}_y f(x,y) \cdot w</math> can be found efficiently even though <math>y</math> is chosen from a very large or even infinite set.

Since 2002, perceptron training has become popular in the field of [[natural language processing]] for such tasks as [[part-of-speech tagging]] and [[syntactic parsing]] (Collins, 2002). It has also been applied to large-scale machine learning problems in a [[distributed computing]] setting.<ref>{{cite book |last1=McDonald |first1=R. |last2=Hall |first2=K. |last3=Mann |first3=G. |year=2010 |chapter=Distributed Training Strategies for the Structured Perceptron |title=Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL |pages=456–464 |publisher=Association for Computational Linguistics |chapter-url=https://www.aclweb.org/anthology/N10-1069.pdf }}</ref>