Lecture Notes for CSE571 (F12)

Go here for the Fall 2013 Schedule

1. Introduction (2013 version.) (Audio of lecture 2) (Audio of lecture 3 (9/4)) (Audio of lecture 4 (9/9)) (Slide video of lecture 5 (9/11))

   • L1 Lecture of [Aug 27, 2012] Introduction

     
     
     
     
     
     
     
     

   • L2 Lecture of [Aug 29, 2012] A bit more introduction. Start of MDPs.

   
   
   
   
   
   
   
   

2. MDPs

   • L3 Lecture of [Sep 5, 2012] Solving finite horizon MDPs

     
     
     
     
     
     
     
     

   • L4 Lecture of of [Sep 10, 2012] Infinite Horizon MDPs and Value Iteration

     
     
     
     
     
     
     
     
     
     

   • L5 Lecture of [Sep 14, 2012] (makeup for Sep 12) Policy iteration for Infinite Horizon MDPs, why it works. Indefinite Horizon MDPs. Stochastic shortest path MDPs, understanding them as general cases of infinite horizon and finite horizon MDPs.

   
   
   
   
   
   
   
   
   

3. Reinforcement Learning

   • L6 Lecture of [Sep 17, 2012] Reinforcement Learning start. Dimensions of variation. Passive RL. Active RL. Exploration/Exploitation tradeoff
     
     
     
     
     
     
     
     
     
   • L7 Lecture of [Sep 19, 2012] RL Contd. Exploration functions. Discussion on model-free vs. model-based. Passive model-free learning. Temporal difference learning. COmparing TD to montecarlo. Understanding the spectrum of DP vs. sample-based and deep vs. shallow dimensions of RL backups. A long discussion on how RL methods can also be seen as methods for approximately solving MDPs with *known* models. Active model-free learning, and the importance of q-values. Q-learning.
     
     
     
     
     
     
     
     
     

4. Efficient/Approximate Approaches for solving Large-scale MDPs

   
   
   
   
   
   • L8 Lecture of [Sep 24, 2012] Overview of directions for efficiently solving large-scale MDPs (for 30min). LRTDP.
     
     
     
     
     
     
     
     
     
   • L9 Lecture of [Sep 26, 2012] Discussion on LRTDP "all-outcome determinization" heuristic. UCT approach and where and when it works. Determinization-based approaches and FF-Replan.
     
     
     
     
     
     
     
     
     
   • L10 Lecture of [Oct 1st, 2012] Discussion of FF-HOP; Discussion of factored MDP approaches.
     
     
     
     
     
     
     
     
     

5. Partial Observability, conditional plans, and POMDPs (Partially Observable Markov Decision Processes)

   
   
   
   
   
   
   
   
   
   
   • L11 Lecture of [Oct 3rd, 2012] Discussion of dynamics, goal-types and observability dimensions. Discussion that decision-making is hardest with partial knowledge of dynamics and/or observability. The belief state representation. The observation model and how it filters the belief state during execution, and *partitions* it during search. How plans are sequences with no observability and conditional with partial observability or stochastic actions. How partial observability brings to fore the problem of state estimation (and the related problems of prediction and smoothing).
     
     
     
     
     
     
     
     
     
   • L12 Lecture of [Oct 8th, 2012] Recap of the discussion on handling non-deterministic actions and partial observability in terms of belief states. Formal start of POMDP model.
     
     
     
     
     
     
     
     
     
   • L13 Lecture of [Oct 10th, 2012] POMDP model. Acting with it. Deriving its transfer function. Approximate methods (based on online lookup) for POMDP. POMDP relaxations. A quick overview of POMDP value iteration algorithm and where its horrendous complexity comes from.
     
     
     
     
     
     
     
     
     
   • L14 Lecture of [Oct 17th, 2012] Discussion of finite horizon POMDP Value Iteration. Factored methods for belief-space planning.
     
     
     
     
     
     
     
     
     

6. Factored approaches to MDP and RL

7. CSP and SAT

   
   
   
   • L15 Lecture of [Oct 22nd, 2012] Short discussion of non-deterministic propostional conditional planning (15min), followed by start of constraint satisfaction problems.
     
     
     
     
     
     
     
     
     
   • L16 Lecture of [Oct 24th, 2012] Quick overview of CSP search algorithms. Backtracking search. Variable and value ordering heuristics. Forward Checking. Explanation-based learning (of nogoods) and intelligent backtracking. Iterative (local search) algorithms for CSP.
     
     
     
     
     
     
     
     
     
   • L17 Lecture of [Oct 29th, 2012] Preprocessing of CSP problems. Consistency enforcement. K-consistency; strong K-consistency; directional K-consistency. Connection between induced tree width and directional K-consistency.
     
     
     
     
     
     
     
     
     
   • L18 Lecture of [Oct 31st, 2012] A bit more on directional consistency and induced width. Main topic on compiling bounded-length planning problems into SAT problems.
     
     
     
     
     
     
     
     
     

8. Bayes Nets: Representation, Inference and Learning (New: Markov nets: an even quicker intro

   • L19 Lecture of [Nov 7, 2012] Motivating LDA in terms of the need to keep-up with Zhou Dynasty elementary school kids. A short fast-paced introduction to probabilistic graphical models, with specific emphasis on bayes nets.
     
     
     
     
     
     
     
     
     
   • L20 Lecture of [Nov 14, 2012] Inference in Bayes Nets; exact vs. approximate inference. Approximate inference based on sampling from the network. Rejection sampling vs. likelihood weighting. Markov Chain Monte Carlo and Gibbs sampling.
     
     
     
     
     
     
     
     
     
   • L21 Lecture of [Nov 19, 2012] Learning in Bayes Nets. Bayesian Learning as just inference of the posterior of hypothesis distribution. MAP and ML as approximations of Bayes Learning. Application of ML to Bayes Net learning with known topology and complete data.
     
     
     
     
     
     
     
     
     
   • L22 Lecture of [Nov 21, 2012] Bayes Net learning in the case of unknown topology and in the case of incomplete data.
     
     
     
     
     
     
     
     
     
   • L23 Lecture of [Nov 26, 2012] Back to Bayes Learning. Understanding the challenges of bayes learning when the hypothesis space is large (or continuous). Understanding the need for conjugate distributions. Understanding Beta distribution as a 2-D version of Dirichlet (or Dirichlet as the K-dimensional version of Beta). Understanding how beta prior looks for different hyper parameters, and what sort of a constraint it puts on the priors you can express. Computing bayes posterior and understanding graphical model version of bayes learning.
     
     
     
     
     
     
     
     
     

9. Statistical models of Language (text) F13 version

   • L24 Lecture of [Nov 28, 2012] Bayes prediction; bayes learning on multi-parameter networks. Statistical models for text. Positional model and why it is infeasible. Unigram model and its plate model. Brief discussion of bigram model as an extension. Topic model as another extension. Single topic model. Viewing topics as points in the word simplex. Plate model for single topic model. Seeing complete data learning case as the Naive Bayes Classifier. Seeing incomplete data learning as fitting single topics for the documents (and how either MLE or Bayes Learning can be used). Motivating LDA as an extension from single to multiple topics per document.
     
     
     
     
     
     
     
     
     
   • L25 Lecture of [Dec 3, 2012] Bayes learning of unigram and single-topic models. Discussion on naive bayes classifer and why it works well as a classifier even though it is lousy as a generative model. Documents as distribution over topics--the progression of ideas from LSA to PLSA to LDA. LSA and matrix factorization methods. PLSA as providing statistical version of LSA. LDA as bayesian learning of PLSA. Along the way, a whole lot of topics, importance of having documents with more than one topic but not too many topics, and how dirichlet prior can be set to ensure this sparsity.
     
     
     
     
     
     
     
     
     
   • L26 Lecture of [Dec 5, 2012] More discussion of LDA and its connections to LSA and PLSA; discussion of generative vs. discriminative models, and how LDA, being a generative model, can be embedded in other generative models. Discussion of Yuheng's ET-LDA framework for aligning event and tweets as an example of this flexibility. Inference with LDA and collapsed gibbs sampling.
     
     
     
     
     
     
     
     
     
     
     
     
   • L27 Lecture of [Dec 10, 2012] End of LDA. More discussion on generative vs. discriminative models. Discussion on Markov Nets and how they compare to Bayes Nets.