COS 402 - Fall 2017 Machine Learning and Artificial Intelligence

---

Course Summary (notice change from previous years)

This course will survey the aspects of intelligence exhibited in biological systems and algorithmic approaches to mimic it. Material will include theoretical and applicative treatment of inductive learning, reinforcement learning, artificial neural networks, natural language processing and knowledge representation.

In comparison to previous years - we will cover new topics (natural language processing, optimization, and deep learning), and will require more mathematical background for topics we cover.

---

Administrative Information

Professors: Sanjeev Arora (Rm 407, CS Bldg) and Elad Hazan (Rm 409)
Office hours:
Arora - Tue 15:00-16:00
Hazan - Thu 15:00-16:00

Lead Faculty Preceptor: Dr. Xiaoyan Li . Room 104, 221 Nassau St;
Office Hours: 10:00-12:00 Fridays

TA: Karan Singh, Room 416 COS building
Office Hours: Mon 16:30-17:30, Wed 13:00-14:00

Lectures: Tue + Thu, 11:00-12:20 in computer science building, room 104.

---

Movie

Oct 5^th 19:30 - garden theater, showing of --Ex-Machina--, Q&A + discussion with Profs. Hasson (PNI) & Hazan on AI

(Enrichment activity; attendance is encouraged but not mandatory.)

---

Tentative Schedule

Number	Topic / hype title	Reading: class material	Optional Reading (enrichment / extra)	Problem sets	Date of class	Lecturer
	Learning from examples, induction
1	Introduction to AIML: Basic questions of AI, history of AI review, State of the art	Slides lec 1 The crow	Norvig-Chomesky debate		9/15	Hazan
2	Symbolic AI: Decision trees, symbolic computation (medical diagnosis) Max information gain rule How to build decision trees, Overfitting	Slides lec 2 Book 3 chapters 3.1-3.5	Book 5 chapters 18.2	DecisionTrees	9/20	Hazan
3	Why "learning from examples" works: Generalization Theory, Statistical learning, sample complexity, proof of learnability of finite hypothesis class,	Slides lec 3 Book 5 chapters 2.1,2.2	Book 5 chapters 1-3 Book 3 chapter 7		9/22	Hazan
4	Learning via efficient optimization.     Sample complexity of python programs -> optimization SVMs / linear classification The perceptron, margin, proof of convergence	Slides lec 4 Book 5 chapters 3.1,3.2	Book 5 chapter 4.2	Decision Trees - implementation	9/27	Hazan
5	More on optimization: mathematical optimization, convexity, intro to convex analysis, constrained optimization, Gradient Descent + proof of convergence example: learning SVM with SGD	Slides lec 5 Book 6 chapters 2.1,3.1 Book 5 chapter 14.1	Book 6 chapter 2 Book 5 chapter 14 Book 7, chapters 3.1-3.2	Learning theory	9/29	Hazan
6	Stochastic optimization: Stochastic estimation of the gradient, stochastic gradient descent Special guest: Dr. Yoram Singer	Slides lec 6 Book 6 chapter 3.4 Book 5 chapter 14.3			10/4	Hazan
7	Intro to Deep Learning: Deep nets. Non-convex optimization. Training via backpropagation algorithm.	Slides lec 7	Intro Chapter on Deep Nets by Michael Nielsen		10/6	Arora
8	Vision via Deep Nets: Neural nets for image recognition. Convolutional architectures. Deep nets. Regularization strategies.	Slides lec 8	Draft of book on Deep Learning by Goodfellow, Bengio, Courville. (comprehensive but advanced) Optional readings 1 and 2	Recognizing Digits. (Due Oct 18)	10/11	Arora
	Language & communication, NLP
9	Language Models: Intro Introduction+history Markovian language models. n-grams. Smoothing	Slides lec 9	up to Section 3.2, by Michael Collins		10/13	Arora
10	Word embeddings Word2vec, PMI, etc. Using word embeddings to solve analogies and other tasks.	Slides lec 10	Optional readings 1. by T. Landauer and S. Dumais ,  2. by P. Turney and P. pantel ,  3. by Sanjeev Arora	optimization and NN Written Assignment	10/18	Arora
11	Recommender systems Collaborative filtering, latent factor models.	Slides lec 11			10/20	Hazan
12	Logic: Background on logic, Formal definitions, derivation, verification Resolution algorithm	Slides lec 12	R&N (Book 8)  Section 7.3, 7.4. Skim through 7.5.1 and 7.5.2 (related to what we did, but more detailed)		10/25	Arora
13	Midterm				10/27
	Knowledge representation
14	Knowledge Representation and Reasoning: Bayesian Networks Marginalization	Slides lec 13	Chapter 2 from Bayesian Artificial Intelligence; A survey due to Kevin Murphy	Movie Embedding Due Nov. 15th	11/8	Arora
15	Bayes nets: Definition of probabilistic Bayesian nets Modeling via Bayes nets Inferences	Slides lec 14	Bayesian Networks witout tears by Eugene Chamiak	.	11/10	Arora
16	Markov Chain Monte Carlo: The sampling problem, simple sampling methods, Markov chains, stationarity, ergodicity The MCMC algorithm	Slides lec 15	Lectures 12 and 13 from the course stochastic simulation.		11/15	Hazan
17	Hidden Markov Models Temporal models, application to text tagging Viterbi decoding algorithms	Slides lec 16	Lecture notes by Percy Liang And by Michael Collins	Bayesian networks, due Nov 29	11/17	Hazan
	Reinforcement learning
18	Game playing Search, A^* heuristic	Slides lec 17			11/22	Arora
19	Reinforcement learning, MDP: Define RL, MDP Markov chains, Markov Reward processes, Ergodic theory reminder, Bellman equation	Slides lec 18	Book by Sutton and Barto course by David Silver	MCMC	11/29	Hazan
20	Dynamic programming The Bellman equation value iteration Policy iteration	Slides lec 19			12/1	Hazan
21	Algorithm for RL Q-learning, function approximation       TD learning, policy gradient	Slides lec 20		RL	12/6	Hazan
22	Guest lecture, deep learning				12/8	Seung
23	Exploration - MAB problem UCB, EXP3 algorithms & analysis	Slides lec 22	Book by Sutton and Barto, ch2 article by Auer,Cesa-Bianchi,Freund and Schapire		12/13	Li
24	Ask us anything				12/15	Arora+Hazan

---

Textbook and readings

(NOTICE: there is no necessary textbook for the course. All material will be self-contained, or based on freely available books)

Recommended:

1. Review of probability/statistics needed for machine learning. Sections 3.1-3.8 of draft of Deep Learning by Goodfellow, Bengio, Courville.
2. Explanation of Gradients and Local optima from Khan Academy.
3. Machine Learning, by Tom Mitchell

Advanced further references:

4. Convex Optimization by Stephen Boyd and Lieven Vandenberghe
5. Understanding Machine Learning: From Theory to Algorithms, by Shai Shalev-Shwartz and Shai Ben-David
6. Online convex optimization and relationship to machine learning.
7. Convex optimization: algorithms and complexity by Sebastien Bubeck
8. Artificial Intelligence: A Modern Approach, by Stuart Russell and Peter Norvig
   
   

We'll post additional optional reading as the course progresses.

Python Tutorials

• An interactive python tutorial from LearnPython.com
• Tutorial for Python 2.7 from python.org
• Tutorial for Python 3 from python.org

---

Collaboration policy

Motivation: Some discussion and collaboration enhances your educational experience, but too much collaboration---in the extreme case, copying each other's solutions--- is unethical and detrimental, and also leave you ill-prepared for the exams, which count for 50% of the grade. 

? OK:
discussion with others about the material in this course, including HW (if attempted alone first), in which case names of all discussants should be noted for each problem separately.  Comparing and discussing the results of experiments.

? NOT OK:
No copying of any sort from any student (past, present or future), from the web, from prior year solutions, from any other course or source. Do not take notes on any solution that may have been arrived at during discussion; instead try to reconstruct it independently later when you write it down. Consulting any kind of website, blog, forum, mailing list or other service for discussing, purchasing, downloading or otherwise obtaining or sharing homework solutions is strictly forbidden (except for piazza and the class mailing list).

Deviations from this policy will result in university disciplinary action. 

---

Late policy

Exercises: 10% off for every day (24 hours) late. Exercises not accepted more than 4 days late.
Special circumstances: please send letter from residential college dean.