# Mathematical Foundations of Artificial Intelligence

### Daniel Stefankovic (CSB 620), office hours: Tu, Th 14:30-15:30 TA: Tivadar Papai (CSB 725), office hours: We 17:00-18:00, problem session: We 18:00-19:00

Time: TR 11:05-12:20, Place: CSB 601

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

### 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