Mathematical Foundations of Artificial Intelligence

Books

Required:

• [B] Christopher M. Bishop, Pattern Recognition and Machine Learning.

Recommended:

• [HTF] Trevor Hastie, Robert Tibshirani, Jerome Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd edition), 2009
  
• [KV] Michael J. Kearns and Umesh V. Vazirani, An Introduction to Computational Learning Theory, 1994.
• [M] Tom Mitchell, Machine Learning, 1997.
• [DHS] Richard O. Duda, Peter E. Hart, and David G. Stork, Pattern Classification (2nd edition), 2001.
• [DGL] Luc Devroye, Laszlo Gyorfi, Gabor Lugosi, A Probabilistic Theory of Pattern Recognition, 1996.
• [W] Larry Wasserman, All of Statistics, 2004.
• [A] Ethem Alpaydin, Introduction to Machine Learning, 2004.

• Jeff's Notes (pdf)

Homework

1. due Jan. 27 (Tu) - basic 1
   • [B] 1.3, 1.5, 1.6, 1.7, 1.11, 1.30, 1.31, 1.32, 1.33.
2. due Feb. 3 (Tu)
   • [B] 2.8, 2.14, 2.26, 3.3, 4.5.
3. due Feb. 26 (Th)
   • [B] 8.8, 8.9, 8.10.
   • Prove the following theorem: Let G be an undirected graphical model. Let A,B,C be sets of vertices such that B separates A from C. Then X_A is independent from X_C conditioning on X_B.
4. due Mar. 24 (Tu)
   • [KV1.1] Let C be the class of axis-alligned rectangles in R^n. Show that C is efficiently PAC learnable.
   • Let C be the class of unions of 3 intervals in R. Show that C is efficiently PAC learnable.
   • [KV2.1] Show tht for each k there exists a function that can be represented as a k-decision list, but not by a k-CNF or k-DNF formula.
5. due Apr. 14 (Tu)
   • [B] 12.1, 12.3, 12.5.
6. due Apr. 21 (Tu)
   • [B] 13.2, 13.3, 13.6,

Projects

1. due Feb. 5 (Th) - estimation.
2. due Feb. 15 (Su) - SVM's.
3. due Mar. 3 (Tu) - EM.
4. due Apr. 23 (Th) - MDP's

• Jan. 15 (Th) Introduction.
  • TOPICS: k-NN, generalization error, true error, cross-validation, entropy, decision trees.
  • READING: [M] 3,5.
  
  
• Jan. 20 (Tu) Probability theory review.
  • TOPICS: density, expectation, variance, conditional expectation, covariance, basic densities.
  • READING: [B] 1.
  
  
• Jan. 22 (Th) Bayesian inference.
  • TOPICS: frequentist/bayesian viewpoint, likelihood, Bayes theorem, conjugate priors, maximum likelihood.
  • READING: [B] 2, [HTF] 2.
  
  
• Jan. 27 (Tu) (Linear) regression.
  • TOPICS: curve fitting, regularization, least squares (connection with maximum likelihood).
  • READING: [B] 3, [HTF] 3.
  
  
• Jan. 29 (Th) (Linear) classification.
  • TOPICS: perceptron algorithm.
  • READING: [B] 4, [HTF] 4.
  
  
• Feb. 3 (Th) SVM I.
  • TOPICS: kernel methods.
  • READING: [B] 6.1, 6.2, Andrew Ng's notes.
  
  
• Feb. 5 (Tu) SVM II.
  • TOPICS: SVMs.
  • READING: [B] 7.1, Burges 98, ICML01-tutorial.
  
  
• Feb. 10 (Tu) Neural Networks.
  • TOPICS: neural networks, backpropagation.
  • READING: [B] 5.1,5.2,5.3.
  
  
• Feb. 12 (Th) Graphical models I.
  • TOPICS: directed/undirected graphical models, elimination algorithm.
  • READING: [B] 8, Bayesian networks without tears..
  
  
• Feb. 17 (Tu) Graphical models II.
  • TOPICS: sum-product, max-sum algorithms, belief propagation.
  • READING: [B] 8.
  
  
• Feb. 19 (Th) EM algorithm.
  • TOPICS: mixture models, EM algorithm.
  • READING: [B] 9.
  
  
• Feb. 24 (Tu) Sampling I.
  • TOPICS: sampling from basic distributions, rejection sampling.
  • READING: [B] 11.1.
  
  
• Feb. 26 (Th) Sampling II.
  • TOPICS: MCMC.
  • READING: [B] 11.2, 11.3, 11.4.
  
  
• Mar. 3 (Tu) review
  
  
• Mar. 5 (Th) EXAM
  
  
• Mar. 10 Tu SPRING BREAK
• Mar. 12 Th SPRING BREAK
  
  
• Mar. 17 (Tu) Theory I - PAC.
  • TOPICS: Chernoff bound, union bound, PAC.
  • READING: [KV] 1,2.
  
  
• Mar. 19 (Th) Theory II - VC-dimension.
  • TOPICS: VC dimension.
  • READING: [KV] 3.
  
  
• Mar. 24 (Tu) Theory III - boosting.
  • TOPICS: strong/weak learning, boosting.
  • READING: [KV] 4, Schapire 1, Schapire 2, [HTF] 10.1-10.5.
  
  
• Mar. 26 (Th) Theory IV - membership queries.
  • TOPICS: Fourier transform based algorithms.
  • READING: Mansour's survey article
  
  
• Mar. 31 (Tu) PCA I.
  • TOPICS: PCA, SVD
  • READING: [B] 12.1
  
  
• Apr. 2 (Th) PCA II.
  • TOPICS: ICA
  • READING: [B] 12.4.1
  
  
• Apr. 7 (Tu) Manifold learning.
  • TOPICS/READING: Isomap, LLE, Laplacian Eigenmap.
  
  
• Apr. 9 (Th) Hidden Markov Models I.
  • TOPICS: HMMs, Viterbi algorithm.
  • READING: [B] 13.1, 13.2.
  
  
• Apr. 14 (Tu) Hidden Markov Models II.
  • TOPICS:
  • READING:
  
  
• Apr. 16 (Th) Reinforcement learning I.
  • TOPICS: MDP's, Policy Iteration.
  • READING: Pieter Abbeel course notes
  
  
• Apr. 21 (Tu) Reinforcement learning II.
  • TOPICS: Value Iteration (proof of correctness), POMDP's.
  • READING: [B] 14.
  
  
• Apr. 23 (Th) review
  
  
• Apr. 28 (Tu) EXAM
  

Grading

• Homework: 20%,
• Projects: 20%,
• EXAM 1: 30%,
• EXAM 2: 30%.

Homework/Project Rules

• Homework is collected on the due date, before class.
• No late homework will be accepted without instructor's permission (a permission must be requested at least 24 hours before the due date).
• In the final evaluation everybody's one lowest homework score and one lowest project score will be dropped.
• You may work with other people on the homework, but you must each write up your solutions separately (without any written aid, for example, looking at other people's source code (or written up solution) is forbidden). If you work with other people, indicate who you worked with on your solution.