CSE 471/598 Lecture Notes (Spring 2012)

Thanks to the unexpected generosity of Youtube folks, I am now able to
link streaming videos of lectures..

• Intro; Intelligent agent design [R&N Ch 1, Ch 2] (sound).

  • L1 [Jan 5, 2012] Video (~4gig) and Audio of the lecture. Administrivia; the space odyssey son et lumeire; Using it as a vehicle to do an interactive overview of AI developments; Definitions of AI--and why thinking humanly, thinking rationally and acting humanly do not quite provide the right fit as general definitions for AI enterprise.

  • L2 [Jan 10, 2012] Video (~4gig) and Audio of the lecture. Rational agency; performance metrics; percept/action/goal/environment types; agent designs and how they motivate the course topics.

• Atomic (Problem Solving) Agents [R&N Ch 3 3.1--3.5]

  • L3 [Jan 12, 2012] Video (~4gig) and Audio of the lecture. Atomic, propositional and relational representations--their tradeoffs (and how functions can allow representation of infinite state spaces compactly.). Atomic agent design. How search is at the heart--and child-generator, goal-test functions are needed. Blind vs. Informed search. Before continuing to single state search algorithms, thinking of the effect of enviornment accessibility. Multiple-initial state search or belief-state search. Without sensing (conformant planning) and with sensing (contingent planning; the medicate problem).

  • L4 [Jan 17, 2012] Video (~4gig) and Audio of the lecture. Exploration/exploitation tradeoffs. Setting state-spaces for atomic agents. Search for single-state atomic agents. World state vs. Search node difference. Viewing search algorithms in terms of their queuing functions. Dept-First/Breadth-first searches and how they differ in optimiality vs. space consumption.

  • L5 [Jan 19, 2012] Video (~4gig) and Audio of the lecture. A discussion of the uniform search tree model. A slow and comprehensive discussion of blind search strategies BFS, DFS, Depth limited DFS and IDDFS and their tradeoffs. A discussion on graph vs. tree search. A discussion on handling duplicate expansions with closed list vs. ancestor checking.

• Informed Search

  • L6 [Jan 20, 2012; for the class of 1/24] Video (~2.5 gig), (Compressed video ~1gig) and Audio of the lecture. Search on graphs with non-uniform cost edges. Optimality and completeness conditions. Aside on how cost variance can hurt badly; and Will Cushing's paper. Informing uniform cost search with a heuristic estimate of cost-to-go (i.e, cost of the optimal path from the node to the goal). h* vs. h0 vs. reasonable heuristics. Admissibility condition on heuristics. Informedness of heuristics. How to get heuristics from problem relaxations. Straightline distance vs. manhattan distance for travel in Manhattan. Misplaced tiles vs. sum of manhattan distances of misplaced tiles in sliding tile puzzle. Getting more informed heuristics by considering "tighter" relaxations (i.e., don't relax away all constraints). Pattern database heuristics and how they show that time spent computing a less relaxed but costlier heuristic can be more than madeup in total search time.

  • L7 [Jan 26, 2012] Video (~2.5 gig) and Audio More discussion on admissibility of heuristics (for example (1) that admissibility it is only sufficient but not a necessary condition for optimality (2) you only get admissibility if you relax (rather than tighten) constraints of the problem--circumscribing vs. inscribing circles). Proof of A* optimality. Viewing A* as doing focused progress to goal. How the "inconsistency" of a heuristic can interfere with this view as f won't monotonically increase. How pathmax correction helps restore monotonic increase of f-values of expanded nodes. Properties of A*--completeness, optimality, time (which is exponential in the relative error) and space. Improving A* space consumption using IDA*--which does tree cutoff using f-values (rather than d-values as IDDFS does), and does *depth-first search* in each iteration.

    • A 11min example walk through explaning A*/IDA* on a graph (just 15mb flash file--runs with vlc viewer)

• Propositional/State-variable models and Planning (Chapter 10.1--3)

  • L8 [Jan 31, 2012] Video (~2.5 gig) and Audio Admissibility/informedness refresher. Realizing that max of admissible heuristics is admissible. Start of search with propositional state models. Initial and goal state descriptions, action descriptions, progression, how to make progression work with A* search (and a brief discussion of set-difference heuristic). Start of regression. Understand why regression is harder in atomic space. Understanding a goal state can be regressed over an action.

  • L9 [Feb 2, 2012] Video (~2.5 gig) and Audio Progression example, regression and regression example; comparison of progression and regression search spaces. Digression on the complexity of planning problems. Heuristics for planning. Set difference heuristic and its informedeness and admissibility. Connection between informedness/admissibility and +ve and -ve interactions. Motivation for planning graph heuristics.

    ---

    *********Up to and including lecture 9 for the Test on 2/9 Thursday******* Here is a 46mb video that gives exam solutions Khan academy style.. and here is just the word with solutions if you are too impatient (note that only the video is self-contained). *********Up to and including lecture 9 for the Test on 2/9 Thursday*******

    ---

  • L10 [Feb 3, 2012] (Recorded for Feb 7th) Video (~2.5 gig) and Audio All about planning graph heuristics. Viewing planning graphs as tools for approximate projection/reachability analysis. Growing planning graphs. The concepts of proposition lists, action lists, mutual exclusions (and propagating them). Using planning graphs--h-sum, h-level, h-max, h-relaxed-plan. Why computing feasible relaxed plans can be done back-track free, but computing an optimal one is still NP-complete. How h-level can be extended to -ve interactions, but when you try extending h-relaxed-plan, then you are doing full planning (and how Graphplan actually did this). How planning graph heuristics are used in progression (where you need to compute a PG for each node), and regression (where you just need one planning graph grown from init state); how despite this apparently huge heuristic computation advantage regression planners using PG heuristics don't do as well as progression planners.

• Knowledge Representation and Propositional Logic; Satisfiability and CSP; Solving SAT problems (Chapter 7 and parts of Chapter 6--6.1;6.3;6.4)

  • L11 [Feb 14, 2012] Video (~2.5 gig) and Audio Knowledge-based agents. Syntax and Semantics of logics. Understanding semantics in terms of sets of worlds where the KB is true. Types of logics and their ontological/epistemological commitments--understanding t/f/unknown vs. degrees of belief epistemological commitment. Understanding the difference between degree of truth (fuzzy logic) vs. degree of belief (probabilistic logic). Undestanding entailment in terms of set-subset relation between the worlds where the KB (and the theorem to be proved) hold. Model-theoretic vs. Proof-theoretic ways of computing entailment. Propositional logic--syntax, semantics. Entailment computation using truth tables. Understanding the relation between the "unsolvability" of KB&~alpha and KB |= alpha. Connection between satisfiability and theorem proving.

  • L12 [Feb 16, 2012] Video (~2.5 gig) and Audio Inference rules for propositional logic; showing their soundness. Showing that they are not complete. Showing it is easy to get inference rules that are complete but not sound. Resolution as a sound and complete inference. Forward resolution vs. Resolution Refutation. Converting propositional KB to clausal form. Example of propositional theorem proving using resolution. Understanding theorem proving as search--but since any proof is considered as good as any other, length of proof doesn't matter. The search algorithm and using it to realize the asymmetry between theorems that hold (and so lead to an empty clause) and those that don't which have to fall out of the loop. Realizing that if we use First Order Logic, then the equivalent compilation to propositional logic is infinite sized and so "falling out of the loop" is not possible--thus the *semi-decidability* result there. Set-of-support and linear-input-form heuristics for propositional resolution.

  • L13 [Feb 21, 2012] Video (~2.5 gig) and Audio Noting that if A is not provable, it doesn't mean that ~A is provable. Discussion on the tractable sub-classes of propositional inference. Running resolution to completion can take exponential time, but running modus-ponens or unit-resolution to completion only takes polynomial time (but they are not complete--i.e., there are theorem that hold but can't be proved just with UR or MP). Recognizing that if your KB is horn clauses (i.e., at most one positive literal per clause when converted to clausal form), then just running modus-ponens will get you completeness.
    Focusing directly on satisfiability problems. The applications of SAT. Realizing that SAT is NP-Complete. Notions of K-SAT problems--and realizing that 1-SAT is easy, and 3-SAT is NP-Complete. 2-SAT turns out to be polynomial.
    Notion of constraint graphs--and realizing that if the constraint graph for SAT is a normal graph, then we have 2-SAT on hands.
    Searching for solutions for SAT problems. Noting that (1) the search space is finite (2^n possible models where n is the number of propositions) (2) that all solutions are at the leaf level (!) (3) that all solutions are considered equally good (4) that we have to be brain-dead to use anything other than depth-first search for looking for solutions--no IDDFS!(5) that we need not branch on which variable to set (6) but the order in which we set variables *does* affect the efficiency of search --the infamous calling "Rao and Bill-Gates to a party at your home" example (7) That the intuition is to branch on the most-constrained variable first.

  • L14 [Feb 23, 2012] Video (~2.5 gig) and Audio Basic SAT solver as a recursive procedure. Improving it with forward checking (unit-resolution). Realizing, along the way that we can use a SAT solver to do theorem proving, and a theorem prover can in turn be used during SAT solving to prune partial assignments. Model finding (Search) and theoremproving (inference) thus go hand-in-hand like yin and yang.
    Variable ordering heuristics and using "most constrained or constraining variable first" idea. (The paris metaphor--the critical decision you want to make first is the flight you are going to take). How SATZ implements this idea as "pick the variables that leads to most derived unit clauses".
    Pure literal elimination idea
    Hillclimbing search for SAT, and comparing hill-climbing search to systematic search (e.g. understanding that a hill-climbing based sat solver can not be used to prove theorems--since that involves showing there are no models.
    Understanding where hard SAT problems live. The discussion on the fascinating phenomenon of phaset transition in SAT.

• Handling uncertainty: Propositional probabilistic logic

  • L15 [Feb 28, 2012] Video (~2.5 gig) and Audio Review of the kinds of knowledge we can represent and queries we can ask in propositional logic. Modeling "Pearl" scenario, and the queries we can handle. Considering moderling "real pearl" scenario, and the kind of plausible reasoning--including "explaining away" that we would like to be able to support.
    Omniscient and eager approach for modeling. Understanding the four difficulties with it: we may not know all exceptions; we may not have the patience to write them all down; we may not have enough memory to hold all exceptions and we may not have the computational power to reason with all of them. The qualification and ramification problems and the "potato in the tail pipe example."
    Ignorant and lazy approach where we consider likelihoods. Nonmonotonic reasoning, certainty factors and fuzzy logic as possible alternatives. Focusing on probablistic reasoning.
    Comparing joint probability distribution to "models of a knowledge base". Understanding that the prop logic can only distinguish double exponential number of knowledege states (since a KB on n proposition can have at most 2^(2^n) different sets of models). Understanding that there are infinite number of joint distributions on n variables (and thus probabilistic logic can make finer distinctions in knowledge level compared to prop logic).
    Undrstanding that the analgoy to propositional logic sentences is probabilistic statements (such as P(A)=x; P(A|B)=y), and absolute and conditional indepenences.
    Understanding that getting the probabilities is the biggest bottleneck --as we may need 2^n different numbers. Understanding that we can reduce numbers if independence assertions hold. Realizing that when everything is indepdent of everything, you need only n probabilities. Realizing that the more reasonable scenario is for small sets of variables to be correlated, while they are independent from other sets (the "Worlds theory" of George Costanza).
    Bayes nets as a compact way to represent joint distributions: their topology captures the independences, and their CPTs capture the numbers.

  • L16 [Mar 1, 2012] Video (~2.5 gig) and Audio Understanding that all probabilistic queries can be computed given the joint distribution. Understanding conditional probability definition leads to both the chain rule for decomposing a joint probability into a product of conditional probabilities; and also bayes rule. Understanding that bayes rule allows computing diagnostic probabilities given causal ones and vice versa. Understanding that computation of diagnostic probabilities is very useful in medicine (and car repair etc).
    Understanding that conditional probabilities are easier to assess than joint probabilities. Understanding that conditional independence assertions allow us to get by with fewer assessed probabilities.
    Understanding that Bayesnet topology gives conditional independence assertions. Of particular interest is the local independence assertions--which state that a node is conditionally independent of all its non-descendants given its immediate parents. Understanding that the topology and the CPTs uniquely define a joint probability distribution (which is their "semantics").
    Understanding that both topology and CPTs are *domain knowledge* that needs to be either provided by the domain expert or learned. Understanding one way of developing the network topology when you have a domain expert on hand (which is to introduce nodes in causal order into the network).

  • L17 [Mar 6, 2012] Video of short Bayes Net problem (250meg) Video of lecture (~2.5 gig) and Audio
    Understanding the robustness of causal probabilities for assessment (compared to diagnostic probabilities)
    Understanding the notion of frequentist vs. bayesian (personal) probabilities. Understanding how whatever the CPTs, a Bayes Net defines a consistent joint distribution. assessment.
    Understanding that a bayesnet "factorizes" a joint distribution (such that you can get the joint by multiplying the CPTs).
    Reducing number of probabilities to be assessed by introducing intermeidate variables. Example in automobile diagnosis
    Reducing the number of probabilities to be assessed by using parameterized conditional distributions. Noisy Or distribution.
    Understanding Conditional Independence assertions that hold in a bayes network. The local independence and Markov Blanket independence. D-Sep as a way to decide whether any given conditional independence assertion holds.
    Understanding D-sep in terms of blockage of three types of paths: causal chain paths; common-cause paths and common-effect paths.

  • L18 [Mar 8, 2012] Video of lecture (~2.5 gig) and Audio Discussing another example illustrating on D-Sep approach to testing conditional independence assertions. The question of whether it is possible to write a bayenetwork that satisfies exactly the given set of conditional independence aassertions (the answer, unfortunately is no--which is why we also have markov networks). The fact that in practice we can get by by ensuring that the B.N. captures a subset of the CIAs (so it may be assuming that some things are dependent when they are not--but this only worsens the efficiency and the compactness of the network).
    Inference on bayes nets--simple cases where you can avoid enumerating the full joint. The idea of using normalization along with bayes rule.
    Inference by enumerating full joint. An improvement of the idea which only enumerates the part of the joint that is needed.
    Factor algebra--which also explains in what sense is the joint "factorized" by bayesnets. The similarity between the product of factors operation and the join operation in databases. Variable elimination operation on factors.
    The improved form of inference where the intermediate results are stored and reused using dynamic programming techniques.

  • L19 [Mar 13, 2012] Video of lecture (~2.5 gig) and Audio Deriving D-Sep independence rules on the board for common-effect case (and giving the other two cases as homework ;-).
    Approximate Inference methods. The desirable properties of approximate inference methods--the "consistency" (i.e., they converge to the real probabilities in the limit), and sample efficiency (how many samples they need to reach a certain level of efficiency).
    Understanding "sampling" a variable (and how to simulate a biased coin toss using random number genrators).
    Sampling empty network (when there is no evidence)--how samples approximate the joint (and understanding why it is actually easier than computing the full joint).
    Sampling from a network given evidence. Idea 1: Rejection sampling. Understanding how rejection sampling is very inefficient when the "evidence" is very unlikely (e.g. P(runny nose|Ebola)--where Ebola is very unlikely, but runny nose given Ebola is close to 1).
    Idea 2 for sampling from a network given evidence: Likelihood weighting--where you consider samples with non-0/1 weight.
    Idea 3: Markov-Chain Monte Carlo --start from a network configuration, and sample non-evidence nodes in-turn. When a node is sampled, it is sampled given the configuration of the rest of the network, which is also equal to just the configuration of its markov-blanket (since given MB, everything else in the network has no effect on the node).

• Learning Bayes Nets..

  • L20 [Mar 15, 2012] Video of lecture (~2.5 gig) and Audio Complexity of inference in bayes nets; singly connected networks as tractable subclass. How you can convert a multiply connected one to singly connected network.
    Probability vs. Statistics
    Bayesian learning--which is really no different from bayesian inference--but with hypothesis becoming intermediate variables.
    Understanding Bayesian learning as just updating the posterior over hypothesis space given the data seen.
    Understanding prediction as weighted prediction of data given hypotheses
    Understanding why full bayesian learning, while optimal, is too hard to do (it requires to us keep the entire set of hypotheses around).
    Two ideas for picking a single best hypothesis: MAP (maximum a posteriori), and ML (maximum likelihood).
    Understanding that MAP is what is at play when scientists look for "simple" or "elegant" hyptheses that explain observations.
    Understanding that MAP adds a term proportional to the prior on the hypothesis to the ML, and that for large data case, MAP becomes close to ML as data likelihood dominates hypothesis prior.
    Quick overview of how continuous function optimization is involved in learning parameters by maximizing likelihood.

  • L21 [Mar 27, 2012] Video of lecture (~2.5 gig) and Audio Quick review of Bayesian learning, and its approximation by MAP and ML. An aside on how ML is the only learning that Frequentists (the kind that you learnt in AP Stat) and Bayesians agree on. Understanding that frequentists shudder at considering the hypothesis to be a random variable (and so write P(D; h) rather than P(D|h) for data likelihood.
    Understanding ML approximation of MAP either as large data approximation (where log likelihood dominates log prior) or uniform prior approximation (where we assume that all hypotheses are equally likely).
    Going through Maximum Likelihood parameter learning over single node and multi-node bayes networks, and understanding the steps involved in (a) setting up the data likelihood expression in terms of hypothesis parameters and (b) finding the parameters for which likehood becomes maximum.
    Noticing that for Bayesnets with known topology and complete data (i.e., values of all attributes are known), the likelihood maximization leads conveniently to one equation per parameter.
    Understanding the laplacian smoothing as a way of handling zero counts by assuming "virtual examples" (and seeing how this is the price we pay for ignoring priors ;-).
    Learning beyond known topology and incomplete data cases. Understanding why incomplete data leads to a more cumbersome log likelihood as we have to marginalize over hidden variables (and logs hate sums in their arguments ;-).
    Understanding that for complete data and unknown topology, we have to search over all topologies, but need to be careful as likelihood only increases when you add edges to a network (and so you will wind up always finding completely connected network).
    Understanding that we can handle this by "penalizing" more complex network topologies, and realizing that this is a backdoor way of making up for ignoring prior.

  • L22 [Mar 29, 2012] Video of lecture (~2.5 gig) and Audio Brief review of steps involved in Maximum Likelihood parameter learning. Understanding how it can get hard (parameter entaglement, nonlinear partial derivatives). How you will need gradient ascent methods in that case.
    (short digression) on comparing local search in combinatorial search to gradient ascent in continuous function optimization (understanding how continuity makes "systematic" search impossible).
    Handling unknown topology (but complete data). Motivating it with domains such as Russell Restaurant domain where we have no clear idea of causality.
    Digression on classification tasks as a special case of data modeling tasks where we are particularly interested in predicting only some attributes of the data.
    Reviewing the point about the need for penalizing topologies with more links.
    Naive Bayes Classifiers as the Jean Harlow of topology learners (don't give me a topology--I already *have* a topology).
    Understanding Naive Bayes classifier as a special case of complete data/known topology bayes net learning. Understanding why Naive Bays models do well at all (you may get good class prediction even with bad posterior).
    Laplacian smoothing for Naive Bayes classifier
    Handling incomplete data. First considering the case where some attributes somtimes are unknown (null values). Understanding the idea of EM through it.
    Then considering the case of hidden variables--where they are always unknown--and realizing that EM idea works there too--as you can initialize with any parameters first. (The example of homework solutions with one of the problems missing a couple of steps).
    Example of EM on candies being drawn from a bag (where the bag is never observed). Understanding the E step (inference) and M step (likelihood maximization). Seeing that the log-likelihood of data given the network improves as EM iterates.
    Understanding that EM is basically a specialized (non-uniform step-size) gradient ascent procedure.
    Understanding that unlike ML-based learning on complete data, which separates learning and inference, EM interleaves inference and learning. [Note that bayesian inference of course doesn't even differentiate learning and inference ;=)

• General Learning

  • L23 [April 3rd, 2012] Video of lecture (~2.5 gig) and Audio General learning. Starting from classification task and seeing how it can be done by decision trees and decision surfaces in addition to naive bayes.

    Realizing also that in each type, it is possible to go more expressive hypotheses (e.g. topology and hidden variables for Bayes nets; higher order polynomials for decision surfaces etc).

    Understanding that inductive learning involves ranking hypotheses in terms of their fit to training data.

    False positives and false negatives and how the "loss" /"cost" function for learning may give asymmetric costs to them.

    Understanding that what we want to really do is get a hypothesis that fits well to the test data--and that training data is only a stand-in.

    Understanding that training data has to be drawn from the same distribution as test data (the discussion about fair tests).

    Understanding the "bias-variance" tradeoff and the perils of over-fitting. ( if we keep picking more and more expressive hypotheses (or weaker and weaker bias--e.g. going from lines to 2nd order polynomials to 7th order polyonomials etc) we can reduce the training error, but will eventually start increasing the test error due to over-fitting).

    Desiderata for a good learning algorithm--in terms of probably approximately correct learning performance.

    Understanding learner difficulty interms of number of samples needed to reach a certain level of test accuracy, and how different learning algorithms might compare.

    Understanding learning problem difficulty interms of sample complexity of the problem. Realizing that sample complexity of discrete hypothesis spaces (e.g. boolean functions) is proportional to the log of the hypothesis space size. Seeing that this means boolean function learning requires exponential number of samples while conjunctive boolean function learning only requires polynomial number of samples.

  • L24 [April 10th, 2012] Video of lecture (~2.5 gig) and Audio Decision tree learning. The bias for finding "small" decision trees that agree with the training data. Optimal decision tree learning will be hard as there are at least as many decision trees as boolean functions (2^2^n).

    Greedy decision tree induction. Figuring out which attribute to split on. Entropy heuristic, and computing expected entropy after a split.

    Seinfeld-Neuman example and understanding why the greedy splitting on single attributes can give us inoptimal (not the smallest) decision trees.

    Understanding when the data is noisy (we have no more attributes to split on, and we still have both +ve and -ve examples..).

    Undestanding over-fitting and refusing to split on a variable because its entropy is not much lower than 1 (or alternately its information gain is not much higher than 1).

  • L25 [April 12th, 2012] Video of lecture (~2.5 gig) and Audio
    Reviewing decision tree overfitting (and a digression on how "overfitting" delineates the place where learning and compression diverge--lossless compression may have to overfit..).
    Handling high-branching factor attributes in decision trees.
    Evaluating learning algorithms using cross-validation and m-fold cross validation. The idea of learning curves as viewing learning performacne w.r.t the size of training data.
    Performance of decision trees on Russell restaurant domain vs. majority function domain. Understanding why decision trees do badly in the majority function.
    Comparing decision trees and naive bayes learners on russell restaurant domain and spam mail domain. Understanding that decision trees work well when there is a succint explanation for the label that involves only a few of the features, while naive bayes works well when all features take part in the explanation with differing weights.
    (Digression on humans liking simplified (simplistic?) explanations even if the underlying learner had to learn complex/nuanced explanations)
    Learning decision surfaces. Perceptron learning algorithm and modifying weights of the weight vector.
    Understanding perceptron learning as finding the minimum of the weight mean-squared error in the weight space using gradient descent.
    Connection between perceptrons and neurons. The aside about Rosenblatt's perceptron excitement and Minsky/Papert's point that perceptrons can only learn linear decision boundaries. Realizing that not all boolean functions are linearly separable--canonical example being XOR.
    Understanding that to approximate non-linear decision boundaries, you need to stack perceptron units (so the output of one becomes the input of the other). Every continuous function can be approximated by *some* 2-layer network.
    Realizing that while multi-layer neural networks are "expressive" enough to learn any decision boundary, they are hard to train (need too many examples).
    Ending learning with a summary of the tradeoffs between naive bayes classifiers, decision trees and perceptrons.

• Game Trees

  • L26 [April 17th, 2012] Video of lecture (~2.5 gig) and Audio
    First a digression into Thinking Cap on unlabeled examples, via an aside on Civil War ;-) Focus on how unlabeled examples can be exploited by EM ideas. How "randomly made-up" examples won't help since they won't be from the same distribution as the test data.
    Game tree search--understanding it as a search where you also simulate your opponent moves.
    Realizing that the agent would select the move that is maximally advantageous to it. Assuming "perfectly rational" opponent, and thus assuming that the opponent will try to take the move that gives "minimal" advantage to the agent.
    Understanding min-max search on a complete tree where leaf nodes are all terminal game positions.
    Realizing that min-max can be done in a depth-first fashion.
    Recognizing that when doing DFS, min-max will have to keep intermediate estimates on the backed up value of a node, and realizing that these estimates naturally correspond to "upper" (in the case of min-node) and "lower" (in the case of max-node) bounds.
    Alpha-beta pruning as a way of stopping search in certain branches when the bounds show that the unexplored subtree cannot possibly in play (i.e., affect what gets backed up to the root node).
    Alpha-beta example done in the class.
    Here is another alpha-beta pruning example
    Understanding the best case of alpha-beta example where it evaluates a d-depth b-branching tree with just b^{d/2} node evaluations (instead of b^d). Thus in the best case, alpha-beta allows us to double the depth of look-ahead.
    Doing min-max on incompletely expanded trees where the leaf nodes are given valuations based on a heuristic evaluation function.
    Understanding that the depth of the tree doesn't have to be uniform.
    

  • L27 [Apr 19, 2012] Video of lecture (~2.5 gig) and Audio Depth-limited min-max, and evaluation functions to assess the leaf nodes.
    Understanding why going deeper helps improve the accuracy of the estimate of the value of a position. Realizing in particular that it is the existence of shallow traps that helps improve the accuracy of backed up value when you go deeper.
    Understanding quiescence search--which involves going deeper under certain moves when their backed up value seems not to have stabilized.
    Connection between limited depth min-max search and anytime computations needed in online search.
    (A small digression into ergodicity of a domain as a necessary condition for the feasibility of online search).
    Seague into games against nature and discussion of Real Time Dynamic Programming as a way to handle actions with stochastic outcomes (a small digression into over-optimistic, conservative and rational agents).
    Realizing that the analogue of evaluation function in RTDP is the heuristic a la A* search!
    Real-time A* search--which shows that online decision making is important and critical even in non-stochastic, non-adversarial domains.
    The idea of Learning RTA* which caches backed up values at the nodes as more accurate heuristics for those nodes
    Marvelling a bit at how we adapted Game-Tree techniques to single-agent search. A quick mention of Monte Carlo Tree search, which evaluate a node via a set of sample probes starting from that node, and UCT (upper confidence-bound tree search) which keeps bounds about the confidence of the current estimates and adjusts the number of sample probes to reach a level of confidience in all branches.

• First-Order Logic end mid

  • L28 [Apr 24, 2012] Video of lecture (~2.5 gig) and Audio The last class. General discussion. Summary.

  ---

  Recitation Material

  • (Video of) Lisp Recitation lecture by Will Cushing ([Jan 12, 2012])

  • Lisp review lectures (video; Khan academy style ;-)

    • Lecture 1 on the anatomy of lisp

    • Lecture 2 on functions as first-class objects (and connection to project 1)

  Classes remaining (and *tentative* topics--subject to change)

  1. 4/19 Stochastic actions and ; Games against nature..

  2. 4/24 First order logic; end

  3. 5/1 [Semester final for Spring 2012: Tuesday, May 1st 2:30 - 4:20 PM]
  Subbarao Kambhampati
  Last modified: Tue Apr 24 20:59:19 MST 2012