Weekly lectures

Most of the linked content need IITB LDAP access. Introduction lecture boardwork. The scribed lecture notes are the primary contributions of the students who are split into scribing groups. The assignment of the students to the groups is here.

• Lecture 01: Introduction to Optimization
  A brief review of optimization and linear programming. Reading: any reference on linear optimization. [Boardwork] [Scribed lecture notes]
  
• Lecture 02: Refresher on Linear and Convex Optimization
  Basics of linear programming, simplex method, convex optimization, ideas of solving convex programs. Reading: any reference on linear optimization. To dig deeper into optimization, the book by Chong and Zak is useful (has a chapter dedicated to simplex method). [Boardwork] [Simplex video tutorial] [Scribed lecture notes]
  

• Lecture 03: Introduction to Regression
  Use cases of regression, general setup, parametrized, linear regression, closed form expression of linear regression. [Boardwork] [Scribed lecture notes]
  
• Lecture 04: Linear Regression, Solution techniques
  Geometric interpretation of linear regression, basis functions, probabilistic model of linear regression, maximum likelihood estimation, optimizing for linear regression, gradient descent. References: [MML] book for linear algebra and interpretation of linear equations, [Bis]. [Boardwork] [Scribed lecture notes]
  

Week 03


• Lecture 05: Maximum Aposteriori (MAP) Estimate
  Stochastic gradient descent, posterior probability, maximizing posterior: MAP estimator, conjugate priors, MAP for linear regression. [Boardwork] [Scribed lecture notes]
  
• Lecture 06: Bias-Variance, Regularization
  Bias and variance of models, tradeoffs, applications in overfitting and underfitting, regularization, Ridge and LASSO methods of regularization. [Boardwork] [Scribed lecture notes]
  

Week 04


• Lecture 07: Introduction to Classification
  Pending items from ridge and LASSO regressions, classification problem setup, naive Bayes classifier and its applications, introduction to logistic regression. [Boardwork] [Scribed lecture notes]
  
• Lecture 08: Logistic Regression and Multiclass Classification
  Binary logistic regression, multiclass classification: one-vs-rest classifier, softmax regression. Generative and discriminative models, special case of naive Bayes and logistic regression equivalence. Optional reading: convergence analysis of gradient descent (with certain assumptions). [Boardwork] [Scribed lecture notes]
  
Week 05


• Lecture 09: Perceptron
  Perceptron, algorithm, convergence, geometric interpretation, loss function interpretation. Introduction to decision trees. [Boardwork] [Scribed lecture notes]
  
• Lecture 10: Decision Trees
  Decision trees examples, creation rules using mutual information, stopping criteria, overfitting. [Boardwork] [Scribed lecture notes]
  
Week 06


• Lecture 11: Introduction to Neural Networks
  What are NNs, extension from logistic regression, neurons, activation functions, training an NN, loss function, chain rule of differentiation. [Boardwork] [Scribed lecture notes]
  
• Lecture 12: Backpropagation and Regularization
  Details of the backpropagation algorithm: forward pass, backward pass. Regularization in NNs: early stopping, dropout. [Boardwork] [Scribed lecture notes] [Detailed worked out example of backpropagation] [Video illustration of backpropagation] [Note on Backpropagation]
  Dropout regularization: [paper]
  
Week 07


• Lecture 13: Recurrent Neural Networks
  Need of recurrent neural networks: motivation from sequential data, different architectures of RNNs, training RNNs, backward propagation, vanishing gradients problem. Reading: [DL] [Boardwork] [Scribed lecture notes] [a complete worked out example of backpropagation in RNN] [optional reading: LSTM]
  
• Lecture 14: Convolutional Neural Networks
  Need of convolutional neural networks, the convolution operation, filtering with horizontal, vertical edge detectors, padding, striding, maxpooling, the CNN architecture, backpropagation in CNN. Reading: [DL] [Boardwork] [Scribed lecture notes] [backpropagation in CNN]
  
Week 08


• Lecture 15: Support Vector Machine
  Margin, maximum margin classification, support vectors, hard margin and soft margin classifiers. Classification of linearly inseparable data, SVM duals, Lagrangian, introduction to kernelization. [Boardwork] [Scribed lecture notes] [optional reading: Lagrange duality principle] (more details: Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization, Cambridge University Press)
  
• Lecture 16: SVM, Clustering
  Kernel functions and their use in support vector machine. Unsupervised learning: clustering, k-means clustering, convergence and local optima proof. [Boardwork] [Scribed lecture notes] [k-means convergence analysis] [optional reading: Kernel methods, Mercer's theorem] [optional reading: soft k-means algorithm (slide 18)]
  
Week 09


• Lecture 17: Dimensionality Reduction, Principal Component Analysis
  Supervised and unsupervised methods of dimensionality reduction. Unsupervised: principal component analysis, examples, mathematical formulation, solution to the optimization problem, PCA algorithm, limitations in class information retention. [Boardwork] [Scribed lecture notes] [PCA tutorial]
  
• Lecture 18: Linear Discriminant Analysis, Introduction to Multi-Agent AI
  Class information-retaining dimensionality reduction. Supervised: linear discriminant analysis, objective function, solution to LDA for 2 classes. Multiclass LDA, limitation to the maximum number of discriminant directions, LDA algorithm. Stepping back: the original idea of artificial intelligence and its classification: human replication and rationality approaches. Rational agents view. First multi-agent example: a two player bucket choice game. Reading for multi-agent AI: Chapters 1 and 2 of [RN] [Boardwork] [Scribed lecture notes] [LDA tutorial]
  
Week 10


• Lecture 19: Two Player Competitive Games
  Sequential move games, games with partial information, games with no information, subgame and subgame perfection. Reading: modules 20 and 21 of this course. Support reading: [RN] chapter 5 and [MSZ] chapter 3 (only relevant sections). [Boardwork] [Scribed lecture notes]
  
• Lecture 20: Sequential and Simultaneous Move Games
  Speedup techniques for solving sequential two player zero-sum games: depth-limited search, pruning. Examples in real-life. Simultaneous move two player zero-sum games, idea of an equilibrium. [Boardwork] [Scribed lecture notes] [Alpha-Beta pruning example] [Python code to visualize saddle point]. Optional: [RBC slides] [Fun video: repeated Prisoner's dilemma] [Fun reading: Axelrod's experiment]
  
Week 11


• Lecture 21: Normal Form Games
  General games with any finite number of players and utilities, normal form game representation, equilibria concepts: dominant strategy equilibrium, pure and mixed Nash equilibrium. [Boardwork] [Scribed lecture notes] [Notation for mixed strategy Nash] Latex help for scribing: [xgames package]
  
• Lecture 22: Social Choice
  Remaining discussions of mixed strategy Nash equilibrium. Algorithm to find MSNE. Inverse game theory: mechanism design. Voting rules: plurality, Borda, single transferable vote, Condorcet consistency, Copeland voting rule. Reading: chapter 2 of [COMSOC] (only the relevant portion) [Boardwork] [Scribed lecture notes] [wikipedia page on Copeland rule]
  
Week 12


• Lecture 23: Stable Matching
  Manipulability of voting rules, Gibbard-Satterthwaite impossibility. Stable matching problem, the Gale-Shapley deferred acceptance algorithm, properties of DA: efficient computability, perfect matching, pairwise stability. Reading: chapter 14 of [COMSOC] (only the relevant portion) [Boardwork] [Scribed lecture notes] [slides on stable matching]
  [Ariel Procaccia's notes on social choice from Harvard]
  [Handwritten notes on stable matching from CS6002 (read only the relevant portion)]
  
• Lecture 24: AI for Problem Solving, Search
  Classical approach for AI, types of decisions: knowledge-based, search. State space search, problem abstraction, a general anatomy of search algorithms. Uninformed search: breadth-first, depth-first, uniform cost. Informed heuristic search: A* search. Reading: chapter 3 of [RN] [Boardwork] [Scribed lecture notes] [slides on search example]