Madhavan Mukund

Data Mining and Machine Learning

Jan-Apr, 2025

Administrative details

• Teaching assistants: Alok Dhar Dubey, Ankan Kar, Rohit Roy

• Evaluation:

  • Assignments 30-40%, quizzes and midsemester exam 20-30%, final exam 40%

  • Copying is fatal

• Course outline (tentative)

  • Supervised learning: Association rules, regression, decision trees, naive Bayes, SVM, classifier evaluation, expectation maximization, ensemble classifiers.

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

  • Text mining: Basic ideas from information retrieval, TF/IDF model, Page Rank, HITS

  • Other topics (if time permits): Probabilistic graphical models, Bayesian networks, Markov models, neural networks, ranking and social choice, …

• Text and reference books:

  • Web Data Mining by Bing Liu, 2nd edition, Springer (2011).

  • 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 by Stuart J Russell and Peter Norvig, 3rd edition, Pearson (2016).

  • Hands-On Machine Learning with Scikit-Learn, Keras and Tensorflow by Aurélien Géron, 3rd edition, O'Reilly (2022)

    Github repository with code from the book by Aurélien Géron

  • Reinforcement Learning: An Introduction, by Richard S. Sutton and Andrew G. Barto, MIT Press, 2nd ed (2018)

Assignments

• Practice Assignment 1, 3 Feb 2025

• Assignment 1, 8 Feb 2025, due 21 Feb 23 Feb 2025

• Assignment 2, 17 Feb 2025, due 2 Mar 9 Mar 2025

• Assignment 3, 15 Apr 2025, due 27 Apr 4 May 2025

Lecture summary

• Lecture 1: 7 Jan 2025
  (Class Notes (pdf))

  Introduction to supervised and unsupervised learning

• Lecture 2: 16 Jan 2025
  (Class Notes (pdf))

  Market-basket analysis, frequent itemsets, Apriori algorithm

  • Liu, Chapter 2.1, 2.2, 2.2.1

• Lecture 3: 21 Jan 2025
  (Class Notes (pdf), Lecture Slides (pdf))

  Association rules, class association rules

  • Liu, Chapter 2.2.1, 2.2.2

  Supervised learning, decision trees, impurity

  • Liu, Chapter 3.1, 3.2, 3.2.1
  • Mitchell, Chapter 3
  • Quinlan, Chapters 1,2
  • Supplementary reading (optional):
    Laurent Hyafil and Ronald Rivest: Constructing optimal binary decision trees is NP-complete

• Lecture 4: 23 Jan 2025
  (Class Notes (pdf), Lecture Slides (pdf))

  Decision trees: impurity measures (entropy, Gini index), information gain ratio, handling numeric attributes

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

  Evaluating classifiers: training/test sets, confusion matrix

  • Liu, Chapter 3.3.1

• Lecture 5: 28 Jan 2025
  (Class Notes (pdf))

  Decision Trees in Python

  • Decision Trees, Géron, Chapter 6,
    (Jupyter notebook, pdf )

• Lecture 6: 30 Jan 2025
  (Class Notes (pdf), Lecture Slides (pdf))

  Linear Regression: loss functions, normal equation, gradient descent

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

• Lecture 7: 4 Feb 2025
  (Class Notes (pdf), Slides (pdf))

  Linear Regression: gradient descent, probabilistic justification for SSE loss

  • Lecture notes by Andrew Ng, Sections 1, 2, 3

  Polynomial regression, regularization, the non-polynomial case

  • Géron, Chapter 4

  Quiz 1, Solutions.

• Lecture 8: 06 Feb 2025
  (Class Notes (pdf), Slides (pdf))

  Regression using decision trees

  • Géron, Chapter 6

  Handling overfitting in decision trees

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

  Regression for Classification

  • Lecture notes by Andrew Ng, Section 5
  • Neural Networks and Deep Learning by Michael Nielsen, Chapter 3, Improving the way neural networks learn
    

• Lecture 9: 11 Feb 2025
  (Class Notes (pdf))

  Scaling regression inputs

  Linear, polynomial and logistic regression in Python

  • Training Models, Géron, Chapter 4,
    (Jupyter notebook, pdf )

  Regression Trees in Python

  • Decision Trees, Géron, Chapter 6,
    (Jupyter notebook, pdf )

• Lecture 10: 13 Feb 2025
  (Class Notes (pdf), Slides (pdf))

  Naïve Bayesian classifiers

  • Liu, Chapter 3.6

  Naïve Bayes text classification

  • Liu, Chapter 3.7

• 20 Feb 2025
  

  Quiz 2, Solutions.

• Lecture 11: 25 Feb 2025
  (Class Notes (pdf), Slides (pdf))

  Ensemble Classifiers: Bagging

  • Bagging Predictors by Leo Breiman.
  • Random Forests by Leo Breiman.
  • Random Forests by Leo Breiman and Adele Cutler
  • Ensemble Learning and Random Forests, Géron, Chapter 7,
    (Jupyter notebook, pdf )

• Lecture 12: 27 Feb 2025
  (Class Notes (pdf), Slides (pdf))

  Ensemble Classifiers: Boosting

  • Liu, Chapter 3.10
  • Blum, Hopcroft and Kannan, Chapter 5.11
  • Supplementary reading:
    
    • A Short Introduction to Boosting by Yoav Freund and Robert E. Schapire
    • AdaBoost and the Super Bowl of Classifiers A Tutorial Introduction to Adaptive Boosting by Raul Rojas.
    • Greedy Function Approximation: A Gradient Boosting Machine by Jerome H. Friedman
    • A Gentle Introduction to Gradient Boosting by Cheng Li

• Lecture 13: 11 Mar 2025
  (Class Notes (pdf), Slides (pdf))

  Unsupervised learning: Clustering — K-Means, Hierarchical, Density-based

  • Liu, Chapter 4.2–4.4
  • 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)

  Unsupervised learning: Local density based outlier detection

  • LOF: Identifying Density-Based Local Outliers, by Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng and Jörg Sander (Sections 3–4)

• Lecture 14: 13 Mar 2025
  (Class Notes (pdf), Slides (pdf))

  Applications of unsupervised learning: semi-supervised learning, preprocessing, image segmentation

  • Géron, Chapter 9 (Jupyter notebook, pdf )

• Lecture 15: 18 Mar 2025
  (Class Notes (pdf), Slides (pdf))

  Dimensionality reduction: PCA, manifold learning, locally linear embeddings

  • Blum, Hopcroft and Kannan, Chapter 3.1–3.6, 3.9.2
  • Géron, Chapter 8
  • An Introduction to Locally Linear Embedding, by Lawrence K. Saul and Sam T. Roweis

• Lecture 16: 20 Mar 2025
  (Class Notes (pdf), Slides (pdf))

  Expectation maximization and applications

  • Expectation maximization
    • Liu, Chapter 5.1.1
    • Mitchell, Chapter 6.12
    • What is the Expectation Maximization Algorithm?, by Chuong B Do and Serafim Batzoglou
    • The Expectation Maximization Algorithm, A short tutorial by Sean Borman
  • Semi-supervised topic classification
    • Liu, Chapter 5 Appendix
    • Semi-Supervised Text Classification Using EM by Kamal Nigam, Andrew McCallum and Tom Mitchell
  • Clustering with mixture of Gaussians
    • Géron, Chapter 9

• Lecture 17: 25 Mar 2025
  (Class Notes (pdf), Slides (pdf))

  Linear Separators — Perceptrons

  • Blum, Hopcroft and Kannan, Chapter 5.2, 5.3

  Quiz 3, Solutions.

• Lecture 18: 27 Mar 2025
  (Class Notes (pdf), Slides (pdf))

  Linear Separators — SVMs

  • Liu, Chapter 3.8, 3.8.1, 3.8.2, 3.8.3

  Kernel methods

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

• Lecture 19: 3 Apr 2025
  (Class Notes (pdf), Slides (pdf))

  Kernel methods

  • Géron, Chapter 5
    (Jupyter notebook, pdf)

  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

• Lecture 20: 8 Apr 2025
  (Class Notes (pdf), Slides (pdf))

  Neural networks: Backpropagation

  • 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?
    

• Lecture 21: 10 Apr 2025
  

  Neural networks in Python

  • Géron, Chapter 10
    (Jupyter notebook, pdf )

  Bayesian networks: basic definitions, semantics
  (Class Notes (pdf), Slides (pdf))

  • Russell and Norvig, Chapter 14.1, 14.2.1, 14.4.1

• Lecture 22: 15 Apr 2025
  (Class Notes (pdf), Slides (pdf))

  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

• Lecture 23: 17 Apr 2025
  (Class Notes (pdf), Slides (pdf))

  Bayesian networks: approximate inference, sampling

  • Russell and Norvig, Chapter 14.5.1

  Introduction to Markov chains

  • Understanding Probability by Henk Tijms, Chapter 15.4

• Lecture 24: 22 Apr 2025
  (Class Notes (pdf), Slides (pdf))

  Markov Chain Monte Carlo: Gibbs Sampling

  • Russell and Norvig, Chapter 14.5.2
  • Understanding Probability by Henk Tijms, Chapter 15.5

  Quiz 4, Solutions.

• Lecture 25: 24 Apr 2025
  (Class Notes (pdf), Slides (pdf))

  Causal graphical models, confounding, intervention

  Additional reading:

  • The Art and Science of Cause and Effect, Judea Pearl
  • Advanced Data Analysis from an Elementary Point of View, Cosma Rohilla Shalizi (Chapters 19–22)
  • Introduction to Causal Inference from a Machine Learning Perspective, Brady Neal