Class meeting for 10-605 Randomized

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

Slides

Comment: I'm going to start off with a few slides related to the upcoming assignment on MF with Spark.

• Spark for MF in PowerPoint, Spark for MF in PDF.
• Randomized Algorithms in Powerpoint, in PDF

Supplement:

• Python demo code for Bloom filter

Optional Readings

• Randomized Algorithms and NLP: Using Locality Sensitive Hash Functions for High Speed Noun Clustering Deepak Ravichandran, Patrick Pantel, and Eduard Hovy
• Online Generation of Locality Sensitive Hash Signatures. Benjamin Van Durme and Ashwin Lall. ACL Short. 2010
• Sketch Algorithms for Estimating Point Queries in NLP. Amit Goyal, Hal Daume III, and Graham Cormode, EMNLP 2012]

Key things to remember

• The API for the randomized methods we studied: Bloom filters, LSH, CM sketches
• What are the key tradeoffs associated with these methods, in terms of space/time efficiency.
• What guarantees are possible, and how space grows as you require more accuracy.
• Which algorithms allow one to combine sketches easily.