Madhavan Mukund

Data Mining and Machine Learning

Jan-Apr, 2023

Administrative details

• Instructors: Pranabendu Misra, Madhavan Mukund

• Teaching assistants: Shourjya Basu, Sampad Kumar Kar, Shankar Ram V

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

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

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

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, 29 January 2023, due 12 February 2023.

• Assignment 2, 28 February 2023, due 14 March 2023.

• Assignment 3, 28 March 2023, due 15 April 18 April 2023.

Lecture summary

• Lecture 1: 5 Jan 2023
  (Class Notes (pdf), Slides (pdf))

  Introduction, market-basket analysis, frequent itemsets

  • Liu, Chapter 2.1

• Lecture 2: 10 Jan 2023
  (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: 12 Jan 2023
  (Slides)

  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: 17 Jan 2023
  (Slides)

  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

• Lecture 5: 19 Jan 2023
  

  Decision Trees in Python (pdf, ipynb)

  • Decision Trees, Géron, Chapter 6

  Evaluating classifiers: training/test sets, confusion matrix (see earlier slides)

  • Liu, Chapter 3.3.1

• Lecture 6: 24 Jan 2023
  (Slides)

  Naïve Bayesian classifiers

  • Liu, Chapter 3.6

  Naïve Bayes text classification

  • Liu, Chapter 3.7

• Lecture 7: 31 Jan 2023
  (Class Notes (pdf), Slides (pdf))

  Linear Regression: loss functions, normal equation, gradient descent, probabilistic justification for SSE loss

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

• Lecture 8: 2 Feb 2023
  (Class Notes (pdf), Slides (pdf))

  Polynomial regression, regularization, the non-polynomial case

  • Géron, 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: 7 Feb 2023
  (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

  Python notebooks from Aurelion Géron's code repository

  • Regression
  • Decision and Regression Trees

• Lecture 10: 9 Feb 2023
  (Slides (pdf), ipynb )

  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

• Lecture 11: 14 Feb 2023
  (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: 16 Mar 2022
  (Slides (pdf), ipynb )

  Ensemble Classifiers: Gradient Boosting

  • Supplementary reading:
    
    Greedy Function Approximation: A Gradient Boosting Machine by Jerome H. Friedman
    • A Gentle Introduction to Gradient Boosting by Cheng Li

• Lecture 13: 28 Feb 2023
  (Slides)

  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: 02 Mar 2023
  (Slides, Jupyter Notebook)

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

  • Géron, Chapter 9

• Lecture 15: 7 Mar 2023
  (Slides)

  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: 9 March 2023
  (Slides, Jupyter Notebook)

  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: 14 Mar 2023
  (Class Notes (pdf), Slides (pdf))

  Linear Separators — Perceptrons, SVMs

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

• Lecture 18: 21 Mar 2023
  (Class Notes (pdf), Slides (pdf), Jupyter notebook)

  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: 23 Mar 2023
  (Class Notes (pdf), Slides (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: 28 Mar 2023
  (Class Notes (pdf), Slides (pdf))

  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?
    
  • Géron, Chapter 10
    (Jupyter notebook)

• Lecture 21: 30 Mar 2023
  (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 22: 4 Apr 2023
  (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: 11 Apr 2023
  (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: 18 Apr 2023
  (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