Difference between revisions of "Class meeting for 10-605 Randomized Algorithms"
From Cohen Courses
Jump to navigationJump to searchLine 23: | Line 23: | ||
* The API for the randomized methods we studied: Bloom filters, LSH, CM sketches, and LSH. | * 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. | * When you would use which technique. | ||
* The relationship between hash kernels and CM sketches. | * The relationship between hash kernels and CM sketches. |
Revision as of 11:16, 7 November 2016
This is one of the class meetings on the schedule for the course Machine Learning with Large Datasets 10-605 in Fall_2016.
Slides
- Lecture 1 Powerpoint, PDF.
- Lecture 2 Powerpoint, PDF.
Quizzes
Sample Code
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, 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).