Syllabus for Machine Learning with Large Datasets 10-605 in Spring 2012

This is the syllabus for Machine Learning with Large Datasets 10-605 in Spring 2012.

January

• Tues Jan 17. Overview of course, cost of various operations, asymptotic analysis.
• Thus Jan 19. Review of probabilities.
• Tues Jan 24. Streaming algorithms and Naive Bayes.
  • Assignment: streaming Naive Bayes 1 (with feature counts in memory)
• Thus Jan 26. Naive Bayes and logistic regression.
• Tues Jan 31. Streaming stochastic gradient descent.
  • Assignment: streaming logistic regression (with feature weghts in memory)

February

Thus Feb 2. The stream-and-sort design pattern; Naive Bayes. Tues Feb 7. Messages and records; finding informative phrases.

• Assignment: streaming Naive Bayes 2 (with feature counts on disk)

Thus Feb 9. Map-reduce and Hadoop 1 (Alona lecture). Tues Feb 14. Map-reduce and Hadoop 2. (Alona lecture).

• Assignment: finding informative phrases

Draft

• Overviews [1 week]
  • Lecture: Overview of course, cost of various operations, asymptotic analysis
  • Lecture: Review of probabilities
• Streaming Learning algorithms [2 weeks]
  • Lecture: Naive Bayes, and a streaming implementation of it (features in memory).
    • Assignment: streaming Naive Bayes w/ features in memory
  • Lecture: Naive Bayes and logistic regression.
  • Lecture: SGD implementation of LogReg, with lazy regularization
    • Assignment: streaming LogReg w/ features in memory
  • Lecture: other streaming methods - the perceptron algorithm and Rocchio's algorithm.
• Stream-and-sort [1.5 week]
  • Lecture: Naive Bayes when data's not in memory.
    • Assignment: stream-and-sort Naive Bayes (Twitter emoticon data?)
  • Lecture: finding informative phrases (with vocab counts in memory).
  • Lecture: messages and records; revisit finding informative phrases.
    • Assignment: finding informative phrases (Google books data)
• Map-reduce and Hadoop [1 week]
  • Lecture: Alona, Map-reduce
  • Lecture: Alona, Hadoop and map-reduce
    • Assignment: finding informative phrases
• Reducing memory usage with randomized methods [1.5 weeks]
  • Lecture: Locality-sensitive hashing.
  • Lecture: Bloom filters for counting events.
    • Assignment: LSH transformation of datasets
  • Lecture: Vowpal Wabbit and the hashing trick.

Planned Topics

• Week 6-7. Nearest-neighbor finding and bulk classification.
  • Using a search engine to find approximate nearest neighbors.
  • Using inverted indices to find approximate nearest neighbors or to perform bulk linear classification.
  • Implementing soft joins using map-reduce and nearest-neighbor methods.
  • The local k-NN graph for a dataset.
  • Assignment: Tool for approximate k-NN graph for a large dataset.

• Week 8-10. Working with large graphs.
  • PageRank and RWR/PPR.
  • Special issues involved with iterative processing on graphs in Map-Reduce: the schimmy pattern.
    • Formalisms/environments for iterative processing on graphs: GraphLab, Sparks, Pregel.
  • Extracting small graphs from a large one:
    • LocalSpectral - finding the meaningful neighborhood of a query node in a large graph.
    • Visualizing graphs.
  • Semi-supervised classification on graphs.
  • Clustering and community-finding in graphs.
  • Assignments: Snowball sampling a graph with LocalSpectral and visualizing the results.

• Week 11. Stochastic gradient descent and other streaming learning algorithms.
  • SGD for logistic regression.
  • Large feature sets SGD: delayed regularization-based updates; projection onto L1; truncated gradients.
  • Assignment: Proposal for a one-month project.

• Weeks 12-15. Additional topics.
  • Scalable k-means clustering.
  • Gibbs sampling and streaming LDA.
  • Stacking and cascaded learning approaches.
  • Decision tree learning for large datasets.
  • Assignment: Writeup of project results.