Madhavan Mukund

Data Mining and Machine Learning

Jan-May, 2022

Administrative details

• Teaching assistants: Avirup Das, Ameya Kamat, Anuja Pal, Tanuj Sur

• Lectures and Tutorials: Two live online classes each week. Zoom link on Moodle page. Tutorials as needed.

• 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, 2nd edition (2019)

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, 1 March 2022, due 12 March 22 March, 2022 25 March, 2022.

• Assignment 2, 4 April 2022, due 17 April 20 April, 2022.

• Assignment 3, 30 April 2022, due 15 May 18 May 23 May, 2022.

Lecture summary

• Lecture 1: 24 Jan 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  Introduction, market-basket analysis, frequent itemsets

  • Liu, Chapter 2.1

• Lecture 2: 27 Jan 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  Apriori algorithm, association rules, class association rules

  • Liu, Chapter 2.2.1, 2.2.2, 2.5, 2.5.1

• Lecture 3: 31 Jan 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  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: 03 Feb 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  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: 07 Feb 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  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: 10 Feb 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  Linear Regression: gradient descent, probabilistic justification for SSE loss

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

  Polynomial regression, regularization

  • Géron, Chapter 4

• Lecture 7: 14 Feb 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  Regression: 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
    

  Regression using decision trees

  • Géron, Chapter 6

• Lecture 8: 17 Feb 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  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 )

  Handling overfitting in decision trees

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

• Lecture 9: 21 Feb 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  Naïve Bayesian classifiers

  • Liu, Chapter 3.6

  Naïve Bayes text classification

  • Liu, Chapter 3.7

• Lecture 10: 24 Feb 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  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: 28 Feb 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  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: 03 Mar 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  Ensemble Classifiers: Gradient Boosting

  • Boosting, Géron, Chapter 7,
    (Jupyter notebook, pdf )
  • Supplementary reading:
    
    Greedy Function Approximation: A Gradient Boosting Machine by Jerome H. Friedman
    • A Gentle Introduction to Gradient Boosting by Cheng Li

• Lecture 13: 07 Mar 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  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: 10 Mar 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

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

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

• Lecture 15: 21 Mar 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  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: 24 Mar 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  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: 31 Mar 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  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: 4 Apr 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  Kernel methods

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

• Lecture 19: 7 Apr 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  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: 11 Apr 2022
  (Class Notes (pdf), Slides (pdf), Lecture 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?
    
  • Géron, Chapter 10
    (Jupyter notebook, pdf)

• Lecture 21: 18 Apr 2022
  (Class Notes (pdf), Slides (pdf), Lecture 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

• Lecture 22: 21 Apr 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  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: 28 Apr 2022
  (Class Notes (pdf), Slides (pdf), Lecture video)

  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: 02 May 2022
  (Class Notes (pdf), Lecture video)

  Markov Chain Monte Carlo: Metropolis-Hastings, Gibbs Sampling

  • Understanding Probability by Henk Tijms, Chapter 15.5