Class meeting for 10-405 Randomized Algorithms

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 Powerpoint, PDF.
• Lecture 2 Powerpoint, PDF.

Quizzes

• Quiz for lecture 1
• Quiz for lecture 2

Sample Code

• Python demo code for Bloom filter

Readings

• William's lecture notes on randomized algorithms (covering Bloom filters and countmin sketches).
• Online Generation of Locality Sensitive Hash Signatures. Benjamin Van Durme and Ashwin Lall. ACL Short. 2010

Optional Readings

• Randomized Algorithms and NLP: Using Locality Sensitive Hash Functions for High Speed Noun Clustering Deepak Ravichandran, Patrick Pantel, and Eduard Hovy
• Sketch Algorithms for Estimating Point Queries in NLP. Amit Goyal, Hal Daume III, and Graham Cormode, EMNLP 2012]

Also discussed

• Short and Deep: Sketching and Neural Networks: Amit Daniely, Nevena Lazic, Yoram Singer, Kunal Talwar, ICLR 2017
• Compact Embedding of Binary-coded Inputs and Outputs using Bloom Filters, Serra & Alexandros Karatzoglou 2017
• Lin, Jie, et al. "DeepHash for Image Instance Retrieval: Getting Regularization, Depth and Fine-Tuning Right." Proceedings of the 2017 ACM on International Conference on Multimedia Retrieval. ACM, 2017.

Key things to remember

• The API for the randomized methods we studied: Bloom filters, LSH, CM sketches, and LSH.
• The benefits of the online LSH method.
• The key algorithmic ideas behind these methods: random projections, hashing and allowing collisions, controlling probability of collisions with multiple hashes, and use of pooling to avoid storing many randomly-created objects.
• When you would use which technique.
• The relationship between hash kernels and CM sketches.
• What are the key tradeoffs associated with these methods, in terms of space/time efficiency and accuracy, and what sorts of errors are made by which algorithms (e.g., if they give over/under estimates, false positives/false negatives, etc).
• What guarantees are possible, and how space grows as you require more accuracy.
• Which algorithms allow one to combine sketches easily (i.e., when are the sketches additive).