Madhavan Mukund

Data Mining and Machine Learning

Aug–Dec, 2020

Administrative details

• Lectures and Tutorials: Video lectures will be uploaded each week. There will be one live online class discussion each week, details to be announced.

• Online discussion forum: Please sign up for the course on Piazza

• Teaching assistants: Debjit Paria, Samarth Ramesh

• Evaluation:

  • 15% for quizzes on Moodle

  • 35% for assignments

  • 50% for final exam

  • Copying is fatal

• Text and reference books:

  • Web Data Mining by Bing Liu.

  • Foundations of Data Science by Avrim Blum, John Hopcroft and Ravi Kannan

  • Machine Learning by Tom Mitchell.

  • C4.5: Programs for Machine Learning by Ross Quinlan.

  • Artificial Intelligence: A Modern Approach (3rd ed) by Stuart J Russell and Peter Norvig.

  • Hands-On Machine Learning with Scikit-Learn, Keras and Tensorflow (2nd ed) by Aurélien Géron

Course plan

Here is a tentative list of topics.

• Supervised learning: Frequent itemsets, association rules, regression, decision trees, naive Bayes, classifier evaluation, PAC learning, VC dimension, ensemble classifiers, expectation maximization, semi-supervised learning, linear classifiers, perceptrons, SVM, kernel methods, neural networks.

• Unsupervised learning: Clustering, outlier detection, PCA, dimensionality reduction.

• Other topics: Probabilistic graphical models, Bayesian networks, hidden Markov models, …

Assignments

• Assignment 1, 9 Oct 2020, due 19 Oct 2020.

• Assignment 2, 18 Nov 2020, due 29 Oct 2020.

• Assignment 3, 6 Dec 2020, due 20 Dec 2020.

Lecture summary

Week 1, August 17-23, 2020

• Lecture 1: Introduction (Slides), (Video)

• Lecture 2: Market-Basket Analysis (Slides), (Video)

• Lecture 3: The Apriori Algorithm (Slides), (Video)

• Lecture 4: Association Rules (Slides), (Video)

  • Liu, Chapter 2.1, 2.2, 2.5

---

Week 2, August 24-30, 2020

• Lecture 5: Supervised Learning (Slides), (Video)

  • Liu, Chapter 3.1

• Lecture 6: Decision Trees (Slides), (Video)

  • Liu, Chapter 3.2, 3.2.1
  • Supplementary reading:
    Laurent Hyafil and Ronald Rivest: Constructing optimal binary decision trees is NP-complete

• Lecture 7: Impurity Measures for Decision Trees (Slides), (Video)

  • Liu, Chapter 3.2.2
  • Mitchell, Chapter 3
  • Quinlan, Chapters 1,2

• Lecture 8: Handling Numeric Attributes (Slides), (Video)

  • Liu, Chapter 3.2.3
  • Mitchell, Chapter 3.7.2
  • Quinlan, Chapter 2.4

• Lecture 9: Evaluating Classifiers (Slides), (Video)

  • Liu, Chapter 3.3.1

• Live session: 28 August 2020 (Video)

---

Week 3, August 31-September 6, 2020

• Lecture 10: Linear Regression (Slides), (Video)

  • Lecture notes by Andrew Ng, Sections 1, 2, 3
  • Géron, Chapter 4

• Lecture 11: Regression, the non-linear case (Slides), (Video)

  • Géron, Chapter 4

• Lecture 12: Regression for Classification (Slides), (Video)

  • Lecture notes by Andrew Ng, Section 5

• Lecture 13: Regression using decision trees (Slides), (Video)

  • Géron, Chapter 6

• Lecture 14: Handling overfitting in decision trees (Slides), (Video)

  • Liu, Chapter 3.2.4
  • Mitchell, Chapter 3.7.1
  • Quinlan, Chapter 4

---

Week 4, September 7-13, 2020

• Live session: 12 September 2020 (Video)

---

Week 5, September 14-20, 2020

• Lecture 15: Naïve Bayes classifiers (Slides), (Video)

  • Liu, Chapter 3.6

• Lecture 16: Naïve Bayes text classification (Slides), (Video)

  • Liu, Chapter 3.7

• Live session: 18 September 2020 (Video)

---

Week 6, September 21-27, 2020

• Lecture 17: PAC Learning (Slides), (Video)

  • Blum, Hopcroft and Kannan, Chapter 5.4, upto 5.4.2

• Live session: 25 September 2020 (Video)

---

Week 8, October 5-11, 2020

• Lecture 18: VC-Dimension (Slides), (Video)

  • Blum, Hopcroft and Kannan, Chapter 5.5, upto 5.5.2

• Lecture 19: Shatter functions (Slides), (Video)

  • Blum, Hopcroft and Kannan, Chapter 5.5.3–5.5.5, 5.6

---

Week 9, October 12-18, 2020

• Lecture 20: Ensemble Classifiers — Bagging (Slides), (Video)

  • Bagging Predictors by Leo Breiman.
  • Random Forests by Leo Breiman.
  • Random Forests by Leo Breiman and Adele Cutler

• Lecture 21: Ensemble Classifiers — Boosting (Slides), (Video)

  • Liu, Chapter 3.10
  • Blum, Hopcroft and Kannan, Chapter 5.11
  • Supplementary reading:
    AdaBoost and the Super Bowl of Classifiers A Tutorial Introduction to Adaptive Boosting by Raul Rojas.

• Live session: 16 October 2020 (Video)

---

Week 10, October 19-25, 2020

• Lecture 22: Expectation Maximization (Slides), (Video)

  • Liu, Chapter 5.1.1
  • Mitchell, Chapter 6.12
  • What is the Expectation Maximization Algorithm?, by Chuong B Do and Serafim Batzoglou

• Lecture 23: Semi-supervised Learning (Slides), (Video)

  • Liu, Chapter 5 Appendix
  • Semi-Supervised Text Classification Using EM by Kamal Nigam, Andrew McCallum and Tom Mitchell

• Lecture 24: Theoretical foundations of EM (Slides), (Video)

  • The Expectation Maximization Algorithm, A short tutorial by Sean Borman

---

Week 11, October 26-November 1, 2020

• Live class, October 30: Latent Dirichlet Allocation (Class Notes), (Video)

  • Introduction to Latent Dirichlet Allocation, Edwin Chen's blog

---

Week 12, November 2-8, 2020

---

Week 13, November 9-15, 2020

• Live class, November 09: Clustering (Class Notes), (Video)

  • Liu, Chapter 4.2-4.6
  • Géron, Chapter 9
  • A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise, by Martin Ester, Hans-Peter Kriegel, Jörg Sander and Xiaowei Xu (Sections 3–4.1)

• Live class, November 13: Outlier Detection, Applications of Unsupervised Learning, Dimensionality Reduction (Class Notes), (Video)

  • LOF: Identifying Density-Based Local Outliers, by Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng and Jörg Sander (Sections 3–4)
  • Géron, Chapter 8 and 9
  • Blum, Hopcroft and Kannan, Chapter 3.1–3.6, 3.9.2

---

Week 14, November 16-22, 2020

• Live class, November 16: Linear Separators — Perceptrons, SVMs (Class Notes), (Video)

  • Blum, Hopcroft and Kannan, Chapter 5.2.
  • Liu, Chapter 3.8, 3.8.1, 3.8.2

• Live class, November 20: Kernel Methods, Neural Networks (Class Notes — Kernel Methods, Neural Networks ) (Video)

  Kernel methods

  • Blum, Hopcroft and Kannan, Chapter 5.3
  • Liu, Chapter 3.8.3
  • Supplementary reading:
    A Primer on Kernel Methods by Jean-Philippe Vert, Koji Tsuda, and Bernhard Schölkopf.

  Neural networks: Multilayer perceptrons, sigmoid neurons, network architecture, universality

  • Russell and Norvig, Chapter 18.7, 18.7.1, 18.7.2, 18.7.3
  • Neural Networks and Deep Learning by Michael Nielsen,
    Chapter 1, Using neural nets to recognize handwritten digits
    Chapter 4, A visual proof that neural nets can compute any function

---

Week 15, November 23-29, 2020

• Live class, November 23: Neural Networks: Learning parameters (Class notes ) (Video)

  Neural networks: Backpropagation, cost functions

  • Russell and Norvig, Chapter 18.7.4
  • Neural Networks and Deep Learning by Michael Nielsen,
    Chapter 2, How the backpropagation algorithm works
    Chapter 3, Improving the way neural networks learn
    Chapter 5, Why are deep neural networks hard to train?
    Chapter 6, Deep Learning

• Live class, November 27: Probabilistic Graphical Models (Class notes ) (Video)

  Bayesian networks: basic definitions, semantics, exact inference

  • Russell and Norvig, Chapter 14.1, 14.2.1, 14.4.1
  • The Computational Complexity of Probabilistic Inference using Bayesian Belief Networks by Gregory F Cooper

  Bayesian networks: Conditional independence, D-separation

  • Russell and Norvig, Chapter 14.2.2
  • Probabilistic Graphical Models: Principles and Techniques by Daphne Koller and Nir Friedman, Chapter 3.2, 3.3
  • Notes on D-separation by Richard Scheines

---

Week 16, November 30-December 6, 2020

• Live class, November 30: Hidden Markov Models (Class notes ) (Video)

  Hidden Markov Models: Filtering, prediction, smoothing, most likely explanation; Dynamic Bayesian Networks

  • Russell and Norvig, Chapter 15.1, 15.2, 15.5 (brief)

---