Madhavan Mukund

Data Mining and Machine Learning

Jan-Apr, 2020

Administrative details

• Teaching assistants: Debjit Paria, Kapil Pause

• Evaluation:

  • Assignments 40%, midsemester exam 20%, 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.

  • An Introduction to Information Retrieval by Christopher D Manning, Prabhakar Raghavan and Hinrich Schütze

  • 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: Frequent itemsets, association rules, regression, decision trees, naive Bayes, SVM, classifier evaluation, expectation maximization, ensemble classifiers.

• Unsupervised learning: Clustering, outlier detection.

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

• Other topics: Probabilistic graphical models, Bayesian networks, Markov models, neural networks, ranking and social choice, …

Assignments

• Assignment 1, 10 Feb 2020, due 21 Feb 1 Mar 2020.

• Assignment 2, 10 Apr 2020, due 20 Apr 26 Apr 2020.

Lecture summary

• Lecture 1, 7 Jan 2020: Class notes

  Frequent itemsets, a-priori algorithm

  • Liu, Chapter 2.1

• Lecture 2, 9 Jan 2020: Class notes

  A-priori algorithm, association rules

  • Liu, Chapter 2.2

• Lecture 3, 14 Jan 2020: Class notes

  Class association rules, supervised learning, decision trees

  • Liu, Chapter 2.5, 3.1, 3.2

• Lecture 4, 16 Jan 2020: Class notes

  Decision trees, different impurity measures – entropy, Gini index

  • Liu, Chapter 3.2.1, 3.2.2

• Lecture 5, 21 Jan 2020: Class notes

  Decision trees, information gain and information gain ratio

  • Liu, Chapter 3.2.2

  Discretizing continuous attributes

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

  Classification and regression trees (CART)

  • Some lecture slides by Mihaela van der Schaar, Oxford. (Here is the full set of slides for this lecture.)

  Classifier evaluation

  • Liu, Chapter 3.3.1

• Lecture 6, 23 Jan 2020: Class notes

  Classifier evaluation: confusion matrix, precision,recall, F-score

  • Liu, Chapter 3.3.2

  Regression: gradient descent

  • Lecture notes, Part I by Andrew Ng, from the Stanford course by Dan Boneh and Andrew Ng

• Lecture 7, 28 Jan 2020: Class notes

  Logistic regression

  • Lecture notes, Part II by Andrew Ng, from the Stanford course by Dan Boneh and Andrew Ng

  Overfitting, tree pruning

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

• Lecture 8, 29 Jan 2020:

  Using the Python scikit-learn library for regression and decision trees

  • Training Linear Models, Géron, Chapter 4, Chapter 4 notebook
  • Decision Trees, Géron, Chapter 6, Chapter 6 notebook

• Lecture 9, 04 Feb 2020: Class notes

  Naive Bayesian Classifiers, generative probablisitic models and parameter estimation, text classification: boolean document model

  • Liu, Chapter 3.6, 3.7.1

• Lecture 10, 06 Feb 2020: Class notes

  Text classification: multinomial (bag of words) document model

  • Liu, Chapter 3.7.2
  • Supplementary reading:
    A Comparison of Event Models for Naive Bayes Text Classification by Andrew McCallum and Kamal Nigam

  Clustering: K-Means

  • Liu, Chapter 4.1, 4.2

• Lecture 11, 11 Feb 2020: Class notes

  Clustering: K-Means, Hierarchical, Distance functions for non-numeric attributes, Normalizing values

  • Liu, Chapter 4.2-4.6

  Density based clustering

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

• Lecture 12, 18 Feb 2020: Class notes

  Density based local 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)

  Applications of clustering: image segmentation, preprocessing for classification

  • Géron, Chapter 9

  Mixture models, Expectation-Maximization, clustering using mixture of Gaussians

  • Mitchell, Chapter 6.12
  • What is the Expectation Maximization Algorithm?, by Chuong B Do and Serafim Batzoglou
  • Géron, Chapter 9

• Lecture 13, 20 Feb 2020: Class notes

  Semi-supervised learning: EM for text classification, nearest-neighbour label extrapolation for MNIST data

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

  Using the Python scikit-learn library for unsupervised learning

  • Unsupervised Learning, Géron, Chapter 9, Chapter 9 notebook

• Lecture 14, 3 Mar 2020: Class notes

  Perceptron algorithm

  • Blum, Hopcroft and Kannan, Chapter 5.2.

  Kernel methods

  • Blum, Hopcroft and Kannan, Chapter 5.3

• Lecture 15, 5 Mar 2020: Class notes

  Support vector machines

  • Liu, Chapter 3.8

  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.

• Lecture 16, 12 Mar 2020: Class notes

  Neural networks: Multilayer perceptrons, sigmoid neurons, network architecture, learning weights, 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 17: Lecture notes, Lecture video

  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,

• Lecture 18: Lecture notes, Lecture video

  Neural networks

  Cross entropy cost function

  • Neural Networks and Deep Learning by Michael Nielsen,
    Chapter 3, Improving the way neural networks learn

  Case study: MNIST, recognizing handwritten digits

  • Neural Networks and Deep Learning by Michael Nielsen,
    Chapter 1, Using neural nets to recognize handwritten digits

  Deep learning: structuring networks in layers, convolutional networks

  • Neural Networks and Deep Learning by Michael Nielsen,
    Chapter 5, Why are deep neural networks hard to train?
    Chapter 6, Deep Learning

• Lecture 19: Lecture notes, Lecture video

  Ensemble classifiers: Bagging, Random Forests

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

• Lecture 20: Lecture notes, Lecture video

  Boosting

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

• Lecture 21: Lecture notes, Lecture video

  Information retrieval

  Basic definitions, boolean document model, term-document matrix, evaluating boolean queries, inverted index, postings, stop words, lemmatization and stemming

  • Manning, Raghavan and Schütze, Chapter 1, 2.2

  Ranking: parametric indices and zone based scoring, TF-IDF weightage, vector space model and cosine similarity

  • Manning, Raghavan and Schütze, Chapter 6.1, 6.2, 6.3

• Lecture 22: Lecture notes, Lecture video

  Anchor text, web as a graph, social network analysis, Page Rank

  • Manning, Raghavan and Schütze, Chapter 21.1, 21.2.1, 21.2.2
  • Liu, Chapter 7.3.1

• Lecture 23: Lecture notes, Lecture video

  Singular Value Decomposition, Latent Semantic Indexing, Principal Component Analysis

  • Blum, Hopcroft and Kannan, Chapter 3.1–3.6, 3.9.2
  • Manning, Raghavan and Schütze, Chapter 18.1–18.4
  • Liu, Chapter 6.7