Voted Perceptron Algorithm

A Voted Perceptron Algorithm is a Model-based Learning Algorithm that produces a Voted Perceptron Classifier.

• AKA: Voted Perceptron Training Algorithm, Voted Perceptron Learning Algorithm.
• Example(s):
  • votedperceptron 1.0.0,
  • the voted perceptron algorithm described in Sassano, 2008,
  • the voted perceptron algorithm described in Freund & Schapire (1999),
  • …
• Counter-Example(s):
  • Averaged Perceptron Algorithm,
  • Kernel Perceptron Algorithm.
• See: Perceptron Algorithm, Generalized Perceptron Model, Perceptron, Perceptron Training Algorithm.

---

---

References

2008

• (Sassano, 2008) ⇒ Manabu Sassano (2008). "An Experimental Comparison of the Voted Perceptron and Support Vector Machines in Japanese Analysis Tasks". In: Proceedings Third International Joint Conference on Natural Language Processing (IJCNLP 2008).
  • QUOTE: Following (Freund and Schapire, 1999), we show the training and prediction algorithm of the voted perceptron in Figure 1. The voted perceptron as well as SVM can use a kernel function. We show in Figure 2 the algorithm of the voted perceptron with a kernel function. This algorithm seems to require $O(k^2)$ kernel calculations. However, we can avoid them by taking advantage of the recurrence $\mathbf{v}_{j+1}\cdot \mathbf{x} =\mathbf{v}_j\cdots \mathbf{x}+y_{uj} K\left(\mathbf{x}_{uj},\mathbf{x}\right)$.

Figure 1: The voted-perceptron algorithm.

Figure 2: Algorithm of the voted-perceptron with a kernel function.

2002

• (Collins, 2002a) ⇒ Michael Collins. (2002). “Ranking Algorithms for Named–Entity Extraction: Boosting and the voted perceptron.” In: Proceedings of the ACL Conference (ACL 2002).

1999

• (Freund & Schapire, 1999) ⇒ Yoav Freund, and Robert E. Schapire. (1999). "Large Margin Classification Using the Perceptron Algorithm". In: Machine Learning, 37(3). doi:10.1023/A:1007662407062.
  • QUOTE: In the voted-perceptron algorithm, we store more information during training and then use this elaborate information to generate better predictions on the test data. The algorithm is detailed in figure 1.

Figure 1: The voted-perceptron algorithm.

---