perceptron algorithm

(55 minutes to learn)

Summary

The perceptron is a simple algorithm for binary classification where the weights are adjusted in the direction of each misclassified example.

Context

This concept has the prerequisites:

Goals

  • Know the perceptron update rule
  • Optional: show that the algorithm terminates if the data are separated by some margin
  • Why can't the algorithm terminate if the data are not linearly separable?

Core resources (read/watch one of the following)

-Free-

Stanford's Machine Learning lecture notes
Lecture notes for Stanford's machine learning course, aimed at graduate and advanced undergraduate students.
Author: Andrew Y. Ng
Coursera: Machine Learning
An online machine learning course aimed at advanced undergraduates.
Author: Pedro Domingos
Other notes:
  • Click on "Preview" to see the videos.

-Paid-

Supplemental resources (the following are optional, but you may find them useful)

-Paid-

See also

  • The perceptron was proposed in the 50s, although it's still in use. More modern algorithms have a similar form, but are put on a more mathematical footing: The perceptron algorithm can be used to learn to predict structured objects (e.g. trees and graphs), not just binary values.
  • The perceptron convergence proof requires the assumption that the data are linearly separable by a nonzero margin. Support vector machines (SVMs) are geared towards the same case.
  • The perceptron can be kernelized in order to capture nonlinear dependencies.