Transcript PPT
CSE 473 Artificial Intelligence Review Logistics • Problem Set due at midnight • Exam next Wed 8:30—10:30 Regular classroom Closed book Cover all quarter’s material Emphasis on material not covered on midterm • Even more emphasis on material not on any PS © Daniel S. Weld 2 Abalone © Daniel S. Weld 3 Defining AI human-like vs. rational Systems that Systems that think like humans think rationally thought vs. behavior Systems that act Systems that act like humans rationally © Daniel S. Weld 4 Goals of this Course • To introduce you to a set of key: Paradigms & Techniques • Teach you to identify when & how to use Heuristic search Constraint satisfaction Machine learning Logical inference Bayesian inference Policy construction © Daniel S. Weld 5 Theme I • Problem Spaces & Search © Daniel S. Weld 6 Learning as Search © Daniel S. Weld 7 SUPPLE – Adapting UIs © Daniel S. Weld 8 Adapting to Device Characteristics Func Interface Spec + Hierarchy of State vars + Methods © Daniel S. Weld Device Model Custom Interface Rendering Screen size Available widgets Interaction modes 9 Interface Adaptation as Search Func Interface Spec © Daniel S. Weld + Device Model Custom Interface Rendering 10 Theme II • In the knowledge lies the power • Adding knowledge to search? © Daniel S. Weld 11 Heuristics • How to generate? • Admissibility? © Daniel S. Weld 12 Constraint Satisfaction? • How to Specify? SEND + MORE -----MONEY • Why Effective? © Daniel S. Weld 13 Backjumping (BJ) • Similar to BT, but more efficient when no consistent instantiation can be found for the current var • Instead of backtracking to most recent var… BJ reverts to deepest var which was c-checked against the current var Q Q Q BJ Discovers (2, 5, 3, 6) inconsistent with x6 No sense trying other values of x5 © Daniel S. Weld Q Q 14 Shuttle Repair Scheduling © Daniel S. Weld 15 Probabilistic Representations • How encode knowledge here? © Daniel S. Weld 16 Theme III Importance of Representation • Features in ML • Reformulation © Daniel S. Weld 17 Propositional. Logic vs. First Order Ontology Syntax Objects, Facts (P, Q) Properties, Relations Variables & quantification Atomic sentences Sentences have structure: terms Connectives father-of(mother-of(X))) Semantics Truth Tables Interpretations (Much more complicated) Inference Algorithm DPLL, GSAT Fast in practice Unification Forward, Backward chaining Prolog, theorem proving NP-Complete Semi-decidable Complexity © Daniel S. Weld 18 Nested Quantifiers: Order matters! x y P(x,y) y x P(x,y) Every dog has a tail d t has(d,t) © Daniel S. Weld ? t d has(d,t) 19 Logical Inference as Search © Daniel S. Weld 20 Why is Learning Possible? Experience alone never justifies any conclusion about any unseen instance. Learning occurs when PREJUDICE meets DATA! Learning a “FOO” © Daniel S. Weld 22 • • • • • Uncertainity Joint Distribution Prior & Conditional Probability Bayes Rule [Conditional] Independence Bayes Net Burglary Earthquake Radio Alarm Nbr1Calls © Daniel S. Weld e,b e,b e,b e,b Pr(B=t) Pr(B=f) 0.05 0.95 Pr(A|E,B) 0.9 (0.1) 0.2 (0.8) 0.85 (0.15) 0.01 (0.99) Nbr2Calls 24 Dynamic Bayesian Network State Estimation © Daniel S. Weld 25 Specifying a MDP S = set of states set (|S| = n) A = set of actions (|A| = m) Pr = transition function Pr(s,a,s’) represented by set of m n x n stochastic matrices (factored into DBNs) each defines a distribution over SxS R(s) = bounded, real-valued reward fun represented by an n-vector © Daniel S. Weld 26 Finding a Policy • Value Iteration • Policy Iteration • Modified Policy Iteration © Daniel S. Weld 27 Bellman Backup Qn+1(s,a) Max Vn Vn a1 Vn Vn+1(s) s a2 Vn a3 Vn Vn Vn © Daniel S. Weld 28 Q-Learning ( s) U Q(a, ( s) s)for ( R( svisited ) U states, ( s ) Utried ( s)) actions •U Maintain •beAs execute actions, do backup on per-action basis comes Q(a, s) Q(a, s) ( R( s) max Q(a, s) Q(a, s)) a • Or compute weighted average over all future states (not just immediate successor) • Do updates at end of epoch • Approximating Q function © Daniel S. Weld 29 And More • • • • Specific search & CSP algorithms Adversary Search Inference in Propositional & FO Logic Specific Learning Algorithms DT Induction, Ensembles, Naïve Bayes • EM, DBNs • Lots of details © Daniel S. Weld 30