CSE 471/598 Lecture Notes (Fall 2007)

Motto: A day spent staring at the powerpoint slides and listening to the .WAV files by yourself
can save as much as 75 min in the class with Rao

• Week 1: Intro; Intelligent agent design [[nifty 2001 2001 ]] [R&N Ch 1, Ch 2]
  • Audio of [Aug 20, 2007]. The nifty presentation. Free-ranging discussion of AI accomplishments. Definitions of AI.
  • Audio of [Aug 22, 2007]. Rational agents. Behaviors and performance metrics. Environment types and their impact on agent design.

• Week 2: Problem Solving Agents [R&N Ch 3 3.1--3.5]
  • Audio of [Aug 27, 2007]. Agent Design Architectures; Defining goal metrics; Qn of background knowledge; Start of Problem Solving Agents.
  • Audio of [Aug 29, 2007]. Basic search algorithms, their properties, case-study of bfs, dfs, depth limited search and IDDFS.

• Week 3: Weighted graph search; A* begin [R&N Ch 4 4.1-4.2]
  • Audio of [Sep 5, 2007].IDDFS properties; How to search when all goals are at the same depth; How to handle cycles in the search graph; uniform cost search & its optimality; Iterative Deepening Uniform Cost Search; Informing uniform cost search-->A* search start.

• Week 4: A* continued [R&N Ch 4 4.1-4.2]
  • Audio of [Sep 10, 2007]. Dijkstra vs. Uniform cost search, (optimal sub-structure), Discussion of admissibility, informedness and monotonicity of heuristics; example of A* search; properties (time, space etc) of A* search; IDA* search; viewing heuristics as optimal solutions to abstractions of the real problem.
  • Audio of [Sep 12, 2007]. Understanding that informedness is a coarse characterization; idea of f-contours and the fact that more informed heuristics are only guaranteed to expand fewer nodes below f=f*; A* formal proof of optimality; Puzzle heuristics and how to verify their admissibility (and how it is important not to include blank tile).

• Week 5: CSPs (and local search) [R&N Ch 5.1--5.3; Ch 4 4.3]
  • Audio of [Sep 17, 2007]. Constraint satisfaction problems. What are they. How are they different from normal search. Why is SAT a CSP problem. How are constraints represented (legal vs. illegal partial assignments). Types of constraints (ninary vs. n-ary). How are CSPs solved and why only depth-first search makes any sense. Heuristics for CSP search: Most-constrained variable, least-constraining value. Forward checking, dynamic variable ordering.
  • Audio of [Sep 19, 2007]. Discussion on constraint graphs, canonicity of boolean and binary CSP formulations, shortcomings of chronological backtracking (and the need for dependency directed backtracking), local search--hill climbing, goodness functions and neighborhoods, strategies for making hill-climbing asymptotically complete, state of the art in SAT/CSP, a discussion on where hard-problems live in CSP (and phase transition phenomenon).

• Week 6: KR and Prop logic [R&N Ch 7 7.1-7.6]
  • Audio of [Sep 26, 2007].Logics. Ideas of entailment and inference. Characterizing KB senetences in terms of their possible worlds. Propositional logic--syntax and semantics. Inference rules for propositional logic. Resolution rule in propositional logic, and using it in forward and backward fashion. Yin-and-Yang connection between inference and search.

• Week 7: Prop logic to Prob. Prop. Logic [R&N ch 7 7.1, 7.3--7.6] [k-consistency discussion from Ch 5 5.2 (pp 145)]
  • Audio of [Oct 1st, 2007]. Types of logics classified in terms of their ontological and epistemological commitments. A long discussion on fuzzy vs. probablilistic logic. Model theory and proof theory for Propositional logic. Resolution rule and using it in forward and backward direction. Example of using resolution refutation.
  • Audio of [Oct 3rd, 2007]. Discussion of project 2 code; discussion of k-consistency, and its relation to inference; comparison between forward checking and consistency enforcement; Davis-putnam procedure for solving SAT problems (and its use of unit resolution); A discussion of the state of the art in SAT solvers.

• Week 8: Prob. Prop. Logic [Ch 7 7.6][ch 13 13.1--13.5]
  • Audio of [Oct 8th, 2007]. Theorem proving with modus ponens; theorem proving with resolution; control strategies for resolution (linear input form; set of support etc). Pearl example and the need for modeling exceptions and likelihoods.
  • Audio of [Oct 10th, 2007]. Blog discussion on qns. including "parameterized" probability distributions; and PROBABILITY vs. STATISTICS; Game plan for probabilistic reasoning; review of elementary probability and use of joint distributions to answer any probabilistic query; the idea of Marginalization and the idea of normalization. (This class also has a lot of discussion about model learning vs. model use and how learning requires bias--with the famous "GAVAGAI example").

• Week 9: Prob. Prop. Logic [ch 13 13.1--13.5]
  • Audio of [Oct 15, 2007]. Assessment of joint vs. conditional probabilites; assessment of causal conditional probabilities being more attractive alternative. Reasoning with Bayes Rule (and conditional probablities); Bayes nets as a way of specifying and using conditional independence assertions.
  • Audio of [Oct 17, 2007]. Review of bayes network semantics, d-separation; discussion of blog questions on how bayes network topology constrains the joint distributions that can be modeled; ideas of i-map, d-map and perfect map; discussion on causality and to what extent logic/bayes network model it; admitting that we get to focus on assessement of probablities only because the harder part--topology--is available from experts (for domains where there are human experts), procedures for construction bayes networks (using human expert help); using hidden variables to make bayes nets sparse (and thus reduce the number of probabilities that need to be assessed); use of templated distributions to further reduce parameters that need to be assessed. Pathfinder as an example.

• Week 10: Inference in Bayes Networks [ch 13 13.1--13.5]
  • Audio of [Oct 22, 2007]. Types of inference with bayes networks-- posterior of a single query variable given evidence, MPE, MAP. Complexity of inference, and its relation to topology of the network. Singly vs. multiply connected networks (and converting multiply connected networks to singly connected networks by merging nodes). Exact vs. approximate inference. Rejection sampling vs. Likelihood weighting; brute-force enumeration vs. variable elimination.

• Week 11: First-order logic [ch 8 and 9]
  • Audio of [Oct 29, 2007]. Expressiveness limitations of Prop logic, and how FOPC handles them. Quantifications and their *rough* relation to conjunctions/disjunctions. Functions and how they lead to unbounded number of objects (and there by unbounded translation of quantified statements). Difference between First vs. higher order logics in terms of quantifiers. (non)Connection to Goedel's theorem. Properties of quantifiers. Importance of quantifer order (and the Jessica Alba effect). Model-theoretic semantics for FOPC. Tarskian Interpretations vs. Herbrand Interpretations.
  • Audio of [Oct 31, 2007]. Herbrand universe, Herbrand base, model-theoretic semantics of FOPC; universal instantiation and existential introduction as new inference rules; Generalized modus-ponens as a way of combining modus ponens and universal instantiation; Need for unification (and the procedure for unification), example of backward-chaining inference with GMP--the apartment pet!

• Week 12: FOPC Resolution Thm Proving; Situation Calculus-->Planning. [9.5; 10.3; 11.1,11.2,11.4,11.5]
  • Audio of [Nov 5, 2007]. Project 4 (prolog project) discussion; Discussion on logic programming and prolog; Resolution theorem proving, conversion to CNF--and skolemization; doing resolution refutation theorem proving. A short discussion on how existential proofs can be bad news if you want to do planning as theorem proving.
  • Audio of [Nov 7, 2007]. Situation Calculus as a way of representing and reasoning with time. Need for frame axioms--the representational and computational issues. STRIPS assumption and state variable models of planning. Progression and Regression models.

• Makeup class: Planning: Progression, Regression--Reachability Heuristics.[R&N 11.2,11.4]
  • (This makeup class is also available as a Google Video ) Audio of [Nov 9, 2007]. Progression, regression, comparison of search spaces; subgoal interactions and hardness of planning; reachability heuristics; planning graphs; level heuristics; relaxed plan heuristics.

• Week 13: Markov Decision Processes
  • Audio of [Nov 14, 2007]. Wrap-up of planning graphs (redundancy in the PGs, level-off for PGs, bi-level PGs), relative utility of PG heuristics for progression vs. regression. Partial satisfaction planning and Markov-decision processes. The MDP model--and contrasting it to problem-solving agent model. Discussion on the relation between stochasticity and multi-agency (in terms of laziness of modeling). Policies as solutions to MDPs.

• Week 14: Markov Decision Processes
  • Audio of [Nov 19, 2007]. A bit of discussion on Money and Utilities (Expected monitory value, The Compleat MDP lecture (Policies, policy evaluation based on behaviors, defining values of behaviors in terms the immediate rewards. Optimal value and Optimal Policy functions. Bellman and his equation. Value and Policy iteration. Demo of value iteration.)

  • Audio of [Nov 21, 2007]. More discussion of value and policy iteration; discussion of partially observable markov decision processes. Approximate methods for policy generation--envelope extension; real-time dynamic programming; Special cases of RTDP--RTA* and Min-Max search. Doing Min-Max search and the idea behind Alpha-beta pruning.

• Week 15: Learning (18.1-18.3; 20.5)
  • Audio of [Nov 26, 2007]. Part 1. More on alpha-beta pruning; limited depth gametree search and evaluation functions. Quiescence search and Horizon effect. Current state of the art in Games. Part 2. Learning start. Dimensions of learning, inductive learning. Speedup vs. knowledge level learning. Relation between the size of the hypothesis space and sample complexity of learning. Evaluating hypotheses in terms of false positives and false negatives. Types of biases.

  • Audio of [Nov 28, 2007]. Discussion of blog questions on the nature or learning as a computational problem; derivation of the relation between sample complexity and the size of the hypothesis space. The general view of learning as searching through the space of hypotheses. Types of search strategies used (hint: all). Decision tree learning. Information gain heuristic and why it makes sense. How greedy decision tree learners can be defeated by problems that have inter-attribute interactions. How learning algorithms are evaluated (learning curves and the idea of m-fold cross validation). Decision trees on Russell domain vs. majority functions. Classification as learning of decision surfaces. How perceptrons learn hyperplanes. How perceptrons have complementary tradeoffs w.r.t decision trees.

• Week 16: Swan Song

  • Audio of [Dec 2, 2007]. Discussion on the contrast between linguistically explainable vs. not explainable learned hypotheses. Networks of linear threshold units and their properties. Single layer LTU networks (perceptrons). Learning weights in perceptrons. Max margin classifiers as an optimizing version of perceptrons. Two paths out from perceptrons--multi-layer neural networks (and backpropagation); linear separation in higher dimensional spaces (and kernel learning). Interactive review.