
COS 402  Fall 2017


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.
Oct 5^{th} 19:30 
garden theater, showing of ExMachina, Q&A + discussion with Profs.
Hasson (PNI) & Hazan on AI
(Enrichment activity;
attendance is encouraged but not mandatory.)
Number 
Topic / hype title 
Reading:
class material 
Optional Reading 
Problem sets 
Date of class 
Lecturer 

Learning from
examples, induction













1 
State
of the art 
NorvigChomesky
debate


9/15 
Hazan 

2 
Decision
trees, symbolic computation (medical diagnosis) Max
information gain rule How
to build decision trees, Overfitting 
Slides lec 2 
Book
5 chapters 18.2 
9/20 
Hazan 

3 
Statistical
learning, sample complexity,

Slides lec 3 
Book
5 chapters 13 

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 chapter 4.2 
9/27 
Hazan 

5 
More
on optimization: mathematical
optimization, convexity, intro to convex analysis, example: learning SVM with SGD

Book
6 chapters 2.1,3.1 Book
5 chapter 14.1 
Book
6 chapter 2 Book
5 chapter 14 Book
7, chapters 3.13.2 
9/29 
Hazan 

6 
Stochastic
optimization: Stochastic
estimation of the gradient, stochastic gradient descent 
Book
6 chapter 3.4 Book
5 chapter 14.3 


10/4 
Hazan 
7 
Intro
to Deep Learning: Deep
nets. Nonconvex optimization. Training via backpropagation algorithm. 


10/6 
Arora 

8 
Vision
via Deep Nets: Neural nets for image recognition. Convolutional architectures. Deep nets. Regularization strategies. 
Draft of book on Deep Learning by
Goodfellow, Bengio, Courville. 
Recognizing Digits. (Due Oct 18) 
10/11 
Arora 









Language &
communication, NLP













9 
Language
Models: Intro Introduction+history Markovian language models. ngrams. Smoothing 
10/13 
Arora 

10 
Word
embeddings Word2vec,
PMI, etc. Using word embeddings to solve analogies
and other tasks. 
Optional
readings 1.
by T. Landauer and S. Dumais , 2. by P.
Turney and P. pantel , 3. by Sanjeev
Arora 
10/18 
Arora 

11 
Collaborative
filtering, latent factor models. 


10/20 
Hazan 

12 
Logic: Background
on logic, Formal
definitions, derivation, verification 
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

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


11/22 
Arora 

19 
Reinforcement
learning, MDP: Define
RL, MDP Markov
chains, Markov Reward processes, Ergodic
theory reminder, Bellman equation 
Book by
Sutton and Barto 
11/29 
Hazan 

20 
Dynamic
programming The
Bellman equation Policy
iteration 

12/1 
Hazan 

21 
Algorithm
for RL Qlearning,
function approximation 

12/6 
Hazan 

22 
Guest
lecture, deep learning 



12/8 
Seung 
23 
Exploration
 MAB problem UCB,
EXP3 algorithms & analysis 
Book by
Sutton and Barto, ch2 

12/13 
Li 

24 
Ask
us anything 



12/15 
Arora+Hazan 




We'll
post additional optional reading as the course progresses.
Motivation: Some discussion and collaboration
enhances your educational experience, but too much collaborationin the
extreme case, copying each other's solutions is unethical and detrimental,
and also leave you illprepared 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.
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.