Class meeting for 10-405 Parallel Perceptrons

This is one of the class meetings on the schedule for the course Machine Learning with Large Datasets 10-405 in Spring 2018.

Slides

• Lecture 1: in Powerpoint, in PDF.
• Lecture 2: in Powerpoint, in PDF.
• Lecture 3: : in Powerpoint, in PDF.

Quiz

• Lecture 1 quiz
• Lecture 2 quiz
• Lecture 3 quiz

Readings

• Notes on voted perceptron.

Readings

• Large Margin Classification Using the Perceptron Algorithm, Freund and Schapire, MLJ 1999
• Discriminative Training Methods for Hidden Markov Models, Collins EMNLP 2002.
• Distributed Training Strategies for the Structured Perceptron, R. McDonald, K. Hall and G. Mann, North American Association for Computational Linguistics (NAACL), 2010.

Things to Remember

• Definition of mistake bound
• Definition of perceptron algorithm
  • Mistake bound analysis for perceptrons, in terms of margin and example radius
• Converting perceptrons to batch: voted perceptron, averaged perceptron
• Definition of the ranking perceptron and kernel perceptron
• Relationship of hash trick to kernels

• Parallellizing streaming ML algorithms
  • Parameter mixing, and the effect it has on the mistake bounds for perceptrons
  • Iterative parameter mixing, and the effect it has on the mistake bounds for perceptrons
• The ALLREDUCE algorithm and its complexity