Madhavan Mukund

Data Mining and Machine Learning

Jan-Apr, 2024

Administrative details

• Teaching assistants: Varun Agrawal, Vinod Chincholi, Paarth Iyer

• Evaluation:

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

  • Copying is fatal

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

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

Course plan

Here is a tentative list of topics.

• 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, …

Assignments

• Assignment 1, 6 March 2024, due 17 March 2024.

• Assignment 2, 21 March 2024, due 31 March 2024.

• Assignment 3, 9 April 2024, due 21 April 2024.

Lecture summary

• Lecture 1: 9 Jan 2024
  (Class Notes (pdf)), Slides (pdf))

  Introduction, market-basket analysis, frequent itemsets, Apriori algorithm

  • Liu, Chapter 2.1

• Lecture 2: 11 Jan 2024
  (Class Notes (pdf), Slides (pdf))

  Apriori algorithm, association rules, class association rules

  • Liu, Chapter 2.2.1, 2.2.2, 2.5, 2.5.1

• Lecture 3: 16 Jan 2024
  (Class Notes (pdf), Slides (pdf))

  Supervised learning, decision trees, impurity measures (entropy, Gini index)

  • Liu, Chapter 3.1, 3.2, 3.2.2
  • 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: 18 Jan 2024
  (Class Notes (pdf), Slides (pdf))

  Decision trees: 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: 23 Jan 2024
  (Class Notes (pdf), Slides (pdf))

  Decision Trees in Python

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

  Linear Regression: loss functions, normal equation, gradient descent

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

• Lecture 6: 25 Jan 2024
  (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

• Lecture 7: 30 Jan 2024
  (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

  Quiz 1, Solutions.

• Lecture 8: 1 Feb 2024
  (Class Notes (pdf), Slides (pdf))

  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
    

  Regression Trees in Python

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

  Linear, polynomial and logistic regression in Python

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

• Lecture 9: 8 Feb 2024
  (Class Notes (pdf), Slides (pdf))

  Naïve Bayesian classifiers

  • Liu, Chapter 3.6

  Naïve Bayes text classification

  • Liu, Chapter 3.7

• Lecture 10: 13 Feb 2024
  (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 11: 15 Feb 2024
  (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 12: 20 Feb 2024
  (Class Notes (pdf), Slides (pdf))

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

  • Liu, Chapter 4.2–4.4
  • Géron, Chapter 9 (Jupyter notebook, pdf )
  • 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 13: 22 Feb 2024
  (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 14: 5 Mar 2024
  (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 15: 7 Mar 2024
  (Class Notes (pdf), Slides (pdf))

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

  • Géron, Chapter 9

  Linear Separators — Perceptrons

  • Blum, Hopcroft and Kannan, Chapter 5.2, 5.3

• Lecture 16: 14 Mar 2024
  (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 17: 19 Mar 2024
  (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 18: 21 Mar 2024
  (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?
    
  • Géron, Chapter 10
    (Jupyter notebook, pdf )

• Lecture 19: 26 Mar 2024
  (Class Notes (pdf), Slides (pdf))

  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

• Lecture 20: 28 Mar 2024
  (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 21: 2 Apr 2024
  (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 22: 4 Apr 2024
  (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 2, Solutions.

• Lecture 23: 16 Apr 2024
  (Class Notes (pdf), Slides (pdf))

  Introduction to reinforcement learning, multi-armed bandits

  • Sutton and Barto, Chapters 1, 2.1–2.5
  • Russell and Norvig, Chapter 17.1

  Quiz 3, Solutions.

• Lecture 24: 18 Apr 2024
  (Class Notes (pdf), Slides (pdf))

  Markov Decision Processes: Basic definitions and examples, policies and value functions, Bellman equation, optimal policies

  • Sutton and Barto, Chapter 3

• Lecture 25: 23 Apr 2024
  (Class Notes (pdf), Slides (pdf))

  Markov Decision Processes: Police evaluation, policy iteration, value iteration

  • Sutton and Barto, Chapter 4