advertisement

Mid-term Review Chapters 2-5, 7, 13, 14 • Review Agents (2.1-2.3) • Review State Space Search • • • • • • • • Problem Formulation (3.1, 3.3) Blind (Uninformed) Search (3.4) Heuristic Search (3.5) Local Search (4.1, 4.2) Review Adversarial (Game) Search (5.1-5.4) Review Propositional Logic (7.1-7.5) Review Probability & Bayesian Networks (13, 14.1-14.5) Please review your quizzes and old CS-171 tests • At least one question from a prior quiz or old CS-171 test will appear on the mid-term (and all other tests) Review Agents Chapter 2.1-2.3 • Agent definition (2.1) • Rational Agent definition (2.2) – Performance measure • Task environment definition (2.3) – PEAS acronym • Properties of Task Environments – Fully vs. partially observable; single vs. multi agent; deterministic vs. stochastic; episodic vs. sequential; static vs. dynamic; discrete vs. continuous; known vs. unknown • Basic Definitions – Percept, percept sequence, agent function, agent program Agents • An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators • Human agent: eyes, ears, and other organs for sensors; hands, legs, mouth, and other body parts for actuators • Robotic agent: cameras and infrared range finders for sensors; various motors for actuators Agents and environments • Percept: agent’s perceptual inputs at an instant • The agent function maps from percept sequences to actions: [f: P* A] • The agent program runs on the physical architecture to produce f • agent = architecture + program Rational agents • Rational Agent: For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, based on the evidence provided by the percept sequence and whatever built-in knowledge the agent has. • Performance measure: An objective criterion for success of an agent's behavior • E.g., performance measure of a vacuum-cleaner agent could be amount of dirt cleaned up, amount of time taken, amount of electricity consumed, amount of noise generated, etc. Task Environment • Before we design an intelligent agent, we must specify its “task environment”: PEAS: Performance measure Environment Actuators Sensors Environment types • Fully observable (vs. partially observable): An agent's sensors give it access to the complete state of the environment at each point in time. • Deterministic (vs. stochastic): The next state of the environment is completely determined by the current state and the action executed by the agent. (If the environment is deterministic except for the actions of other agents, then the environment is strategic) • Episodic (vs. sequential): An agent’s action is divided into atomic episodes. Decisions do not depend on previous decisions/actions. • Known (vs. unknown): An environment is considered to be "known" if the agent understands the laws that govern the environment's behavior. Environment types • Static (vs. dynamic): The environment is unchanged while an agent is deliberating. (The environment is semidynamic if the environment itself does not change with the passage of time but the agent's performance score does) • Discrete (vs. continuous): A limited number of distinct, clearly defined percepts and actions. How do we represent or abstract or model the world? • Single agent (vs. multi-agent): An agent operating by itself in an environment. Does the other agent interfere with my performance measure? Review State Space Search Chapters 3-4 • Problem Formulation (3.1, 3.3) • Blind (Uninformed) Search (3.4) • Depth-First, Breadth-First, Iterative Deepening • Uniform-Cost, Bidirectional (if applicable) • Time? Space? Complete? Optimal? • Heuristic Search (3.5) • A*, Greedy-Best-First • Local Search (4.1, 4.2) • Hill-climbing, Simulated Annealing, Genetic Algorithms • Gradient descent Problem Formulation A problem is defined by five items: initial state e.g., "at Arad“ actions – Actions(X) = set of actions available in State X transition model – Result(S,A) = state resulting from doing action A in state S goal test, e.g., x = "at Bucharest”, Checkmate(x) path cost (additive, i.e., the sum of the step costs) – c(x,a,y) = step cost of action a in state x to reach state y – assumed to be ≥ 0 A solution is a sequence of actions leading from the initial state to a goal state Tree search vs. Graph search Review Fig. 3.7, p. 77 • Failure to detect repeated states can turn a linear problem into an exponential one! • Test is often implemented as a hash table. 11 Solutions to RepeatedSStates B S B C C C S B S State Space Example of a Search Tree • Graph search faster, but memory inefficient – never generate a state generated before • must keep track of all possible states (uses a lot of memory) • e.g., 8-puzzle problem, we have 9! = 362,880 states • approximation for DFS/DLS: only avoid states in its (limited) memory: avoid infinite loops by checking path back to root. – “visited?” test usually implemented as a hash table 12 Implementation: states vs. nodes • A state is a (representation of) a physical configuration • A node is a data structure constituting part of a search tree • A node contains info such as: – state, parent node, action, path cost g(x), depth, etc. • The Expand function creates new nodes, filling in the various fields using the Actions(S) and Result(S,A)functions associated with the problem. 13 General tree search Goal test after pop General graph search Goal test after pop Breadth-first graph search function B RE ADT H -F IRST-S EARCH ( problem ) returns a solution, or failure node ← a node with S TAT E = problem .I NIT IAL -S TAT E, PAT H -C OST = 0 if problem .G OAL -T EST(node .S TAT E) then return S OL UT ION (node ) frontier ← a FIFO queue with node as the only element explored ← an empty set loop do if E MPT Y ?( frontier ) then return failure node ← P OP ( frontier ) /* chooses the shallowest node in frontier */ add node .S TAT E to explored Goal test before push for each action in problem .A CT IONS (node .S TAT E) do child ← C HILD -N ODE ( problem , node , action ) if child .S TAT E is not in explored or frontier then if problem .G OAL -T EST(child .S TAT E) then return S OL UT ION (child ) frontier ← I NSE RT (child , frontier ) Figure 3.11 Breadth-first search on a graph. Uniform cost search: sort by g A* is identical but uses f=g+h Greedy best-first is identical but uses h function U NIFORM -C OST-S EARCH ( problem ) returns a solution, or failure node ← a node with S TAT E = problem .I NIT IAL -S TAT E, PAT H -C OST = 0 frontier ← a priority queue ordered by PAT H -C OST, with node as the only element explored ← an empty set Goal test after pop loop do if E MPT Y ?( frontier ) then return failure node ← P OP ( frontier ) /* chooses the lowest-cost node in frontier */ if problem .G OAL -T EST(node .S TAT E) then return S OL UT ION (node ) add node .S TAT E to explored for each action in problem .A CT IONS (node .S TAT E) do child ← C HILD -N ODE ( problem , node , action ) if child .S TAT E is not in explored or frontier then frontier ← I NSE RT (child , frontier ) else if child .S TAT E is in frontier with higher PAT H -C OST then replace that frontier node with child Figure 3.14 Uniform-cost search on a graph. The algorithm is identical to the general graph search algorithm in Figure 3.7, except for the use of a priority queue and the addition of an extra check in case a shorter path to a frontier state is discovered. The data structure for frontier needs to support efficient membership testing, so it should combine the capabilities of a priority queue and a hash table. Depth-limited search & IDS Goal test before push When to do Goal-Test? Summary • For DFS, BFS, DLS, and IDS, the goal test is done when the child node is generated. – These are not optimal searches in the general case. – BFS and IDS are optimal if cost is a function of depth only; then, optimal goals are also shallowest goals and so will be found first • For GBFS the behavior is the same whether the goal test is done when the node is generated or when it is removed – h(goal)=0 so any goal will be at the front of the queue anyway. • For UCS and A* the goal test is done when the node is removed from the queue. – This precaution avoids finding a short expensive path before a long cheap path. Blind Search Strategies (3.4) • • • • • • Depth-first: Add successors to front of queue Breadth-first: Add successors to back of queue Uniform-cost: Sort queue by path cost g(n) Depth-limited: Depth-first, cut off at limit l Iterated-deepening: Depth-limited, increasing l Bidirectional: Breadth-first from goal, too. • Review example Uniform-cost search – Slides 25-34, Lecture on “Uninformed Search” Search strategy evaluation • A search strategy is defined by the order of node expansion • Strategies are evaluated along the following dimensions: – – – – completeness: does it always find a solution if one exists? time complexity: number of nodes generated space complexity: maximum number of nodes in memory optimality: does it always find a least-cost solution? • Time and space complexity are measured in terms of – – – – b: maximum branching factor of the search tree d: depth of the least-cost solution m: maximum depth of the state space (may be ∞) (for UCS: C*: true cost to optimal goal; > 0: minimum step cost) Summary of algorithms Fig. 3.21, p. 91 Criterion BreadthFirst UniformCost DepthFirst DepthLimited Iterative Deepening DLS Bidirectional (if applicable) Complete? Yes[a] Yes[a,b] No No Yes[a] Yes[a,d] Time O(bd) O(b1+C*/ε) O(bm) O(bl) O(bd) O(bd/2) Space O(bd) O(b1+C*/ε) O(bm) O(bl) O(bd) O(bd/2) Optimal? Yes[c] Yes No No Yes[c] Yes[c,d] There are a number of footnotes, caveats, and assumptions. See Fig. 3.21, p. 91. Generally the preferred [a] complete if b is finite uninformed search strategy [b] complete if step costs > 0 [c] optimal if step costs are all identical (also if path cost non-decreasing function of depth only) [d] if both directions use breadth-first search (also if both directions use uniform-cost search with step costs > 0) Heuristic function (3.5) Heuristic: Definition: a commonsense rule (or set of rules) intended to increase the probability of solving some problem “using rules of thumb to find answers” Heuristic function h(n) Estimate of (optimal) cost from n to goal Defined using only the state of node n h(n) = 0 if n is a goal node Example: straight line distance from n to Bucharest Note that this is not the true state-space distance It is an estimate – actual state-space distance can be higher Provides problem-specific knowledge to the search algorithm Greedy best-first search • h(n) = estimate of cost from n to goal – e.g., h(n) = straight-line distance from n to Bucharest • Greedy best-first search expands the node that appears to be closest to goal. – Sort queue by h(n) • Not an optimal search strategy – May perform well in practice A* search • Idea: avoid expanding paths that are already expensive • Evaluation function f(n) = g(n) + h(n) • g(n) = cost so far to reach n • h(n) = estimated cost from n to goal • f(n) = estimated total cost of path through n to goal • A* search sorts queue by f(n) • Greedy Best First search sorts queue by h(n) • Uniform Cost search sorts queue by g(n) Admissible heuristics • A heuristic h(n) is admissible if for every node n, h(n) ≤ h*(n), where h*(n) is the true cost to reach the goal state from n. • An admissible heuristic never overestimates the cost to reach the goal, i.e., it is optimistic • Example: hSLD(n) (never overestimates the actual road distance) • Theorem: If h(n) is admissible, A* using TREE-SEARCH is optimal Consistent heuristics (consistent => admissible) • A heuristic is consistent if for every node n, every successor n' of n generated by any action a, h(n) ≤ c(n,a,n') + h(n') • If h is consistent, we have f(n’) = g(n’) + h(n’) (by def.) = g(n) + c(n,a,n') + h(n’) (g(n’)=g(n)+c(n.a.n’)) ≥ g(n) + h(n) = f(n) (consistency) f(n’) ≥ f(n) • i.e., f(n) is non-decreasing along any path. • Theorem: If h(n) is consistent, A* using GRAPH-SEARCH is optimal keeps all checked nodes in memory to avoid repeated states It’s the triangle inequality ! Local search algorithms (4.1, 4.2) • In many optimization problems, the path to the goal is irrelevant; the goal state itself is the solution • • • • • State space = set of "complete" configurations Find configuration satisfying constraints, e.g., n-queens In such cases, we can use local search algorithms keep a single "current" state, try to improve it. Very memory efficient (only remember current state) Random Restart Wrapper • These are stochastic local search methods – Different solution for each trial and initial state • Almost every trial hits difficulties (see below) – Most trials will not yield a good result (sadly) • Many random restarts improve your chances – Many “shots at goal” may, finally, get a good one • Restart a random initial state; many times – Report the best result found; across many trials Random Restart Wrapper BestResultFoundSoFar <- infinitely bad; UNTIL ( you are tired of doing it ) DO { Result <- ( Local search from random initial state ); IF ( Result is better than BestResultFoundSoFar ) THEN ( Set BestResultFoundSoFar to Result ); } RETURN BestResultFoundSoFar; Typically, “you are tired of doing it” means that some resource limit is exceeded, e.g., number of iterations, wall clock time, CPU time, etc. It may also mean that Result improvements are small and infrequent, e.g., less than 0.1% Result improvement in the last week of run time. Local Search Difficulties These difficulties apply to ALL local search algorithms, and become MUCH more difficult as the dimensionality of the search space increases to high dimensions. • Problems: depending on state, can get stuck in local maxima – Many other problems also endanger your success!! Hill-climbing search • "Like climbing Everest in thick fog with amnesia" • Simulated annealing search • Idea: escape local maxima by allowing some "bad" moves but gradually decrease their frequency • Improvement: Track the BestResultFoundSoFar. Here, this slide follows Fig. 4.5 of the textbook, which is simplified. P(accepting a worse successor) Decreases as Temperature T decreases Increases as | E | decreases (Sometimes step size also decreases with T) e^( E / T ) Temperature |E | Temperature T High Low High Medium Low Low High Medium Genetic algorithms (Darwin!!) • A state = a string over a finite alphabet (an individual) • Start with k randomly generated states (a population) • Fitness function (= our heuristic objective function). – Higher fitness values for better states. • Select individuals for next generation based on fitness – P(individual in next gen.) = individual fitness/ population fitness • Crossover fit parents to yield next generation (off-spring) • Mutate the offspring randomly with some low probability fitness = #non-attacking queens probability of being in next generation = fitness/(_i fitness_i) • Fitness function: #non-attacking queen pairs – min = 0, max = 8 × 7/2 = 28 How to convert a fitness value into a probability of being in the next generation. • _i fitness_i = 24+23+20+11 = 78 • P(child_1 in next gen.) = fitness_1/(_i fitness_i) = 24/78 = 31% • P(child_2 in next gen.) = fitness_2/(_i fitness_i) = 23/78 = 29%; etc Review Adversarial (Game) Search Chapter 5.1-5.4 • Minimax Search with Perfect Decisions (5.2) – Impractical in most cases, but theoretical basis for analysis • Minimax Search with Cut-off (5.4) – Replace terminal leaf utility by heuristic evaluation function • Alpha-Beta Pruning (5.3) – The fact of the adversary leads to an advantage in search! • Practical Considerations (5.4) – Redundant path elimination, look-up tables, etc. Games as Search • • Two players: MAX and MIN MAX moves first and they take turns until the game is over – Winner gets reward, loser gets penalty. – “Zero sum” means the sum of the reward and the penalty is a constant. • Formal definition as a search problem: – – – – – – – • Initial state: Set-up specified by the rules, e.g., initial board configuration of chess. Player(s): Defines which player has the move in a state. Actions(s): Returns the set of legal moves in a state. Result(s,a): Transition model defines the result of a move. (2nd ed.: Successor function: list of (move,state) pairs specifying legal moves.) Terminal-Test(s): Is the game finished? True if finished, false otherwise. Utility function(s,p): Gives numerical value of terminal state s for player p. • E.g., win (+1), lose (-1), and draw (0) in tic-tac-toe. • E.g., win (+1), lose (0), and draw (1/2) in chess. MAX uses search tree to determine “best” next move. An optimal procedure: The Min-Max method Will find the optimal strategy and best next move for Max: • 1. Generate the whole game tree, down to the leaves. • 2. Apply utility (payoff) function to each leaf. • 3. Back-up values from leaves through branch nodes: – a Max node computes the Max of its child values – a Min node computes the Min of its child values • 4. At root: Choose move leading to the child of highest value. Two-Ply Game Tree Two-Ply Game Tree Minimax maximizes the utility of the worst-case outcome for Max The minimax decision Pseudocode for Minimax Algorithm function MINIMAX-DECISION(state) returns an action inputs: state, current state in game return arg maxaACTIONS(state) MIN-VALUE(Result(state,a)) function MAX-VALUE(state) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v −∞ for a in ACTIONS(state) do v MAX(v,MIN-VALUE(Result(state,a))) return v function MIN-VALUE(state) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v +∞ for a in ACTIONS(state) do v MIN(v,MAX-VALUE(Result(state,a))) return v Properties of minimax • Complete? – Yes (if tree is finite). • Optimal? – Yes (against an optimal opponent). – Can it be beaten by an opponent playing sub-optimally? • No. (Why not?) • Time complexity? – O(bm) • Space complexity? – O(bm) (depth-first search, generate all actions at once) – O(m) (backtracking search, generate actions one at a time) Static (Heuristic) Evaluation Functions • An Evaluation Function: – Estimates how good the current board configuration is for a player. – Typically, evaluate how good it is for the player, how good it is for the opponent, then subtract the opponent’s score from the player’s. – Othello: Number of white pieces - Number of black pieces – Chess: Value of all white pieces - Value of all black pieces • Typical values from -infinity (loss) to +infinity (win) or [-1, +1]. • If the board evaluation is X for a player, it’s -X for the opponent – “Zero-sum game” Alpha-beta Algorithm • Depth first search – only considers nodes along a single path from root at any time a = highest-value choice found at any choice point of path for MAX (initially, a = −infinity) b = lowest-value choice found at any choice point of path for MIN (initially, b = +infinity) • Pass current values of a and b down to child nodes during search. • Update values of a and b during search: – MAX updates a at MAX nodes – MIN updates b at MIN nodes • Prune remaining branches at a node when a ≥ b Pseudocode for Alpha-Beta Algorithm function ALPHA-BETA-SEARCH(state) returns an action inputs: state, current state in game vMAX-VALUE(state, - ∞ , +∞) return the action in ACTIONS(state) with value v function MAX-VALUE(state,a , b) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v-∞ for a in ACTIONS(state) do v MAX(v, MIN-VALUE(Result(s,a), a , b)) if v ≥ b then return v a MAX(a ,v) return v (MIN-VALUE is defined analogously) When to Prune? • Prune whenever a ≥ b. – Prune below a Max node whose alpha value becomes greater than or equal to the beta value of its ancestors. • Max nodes update alpha based on children’s returned values. – Prune below a Min node whose beta value becomes less than or equal to the alpha value of its ancestors. • Min nodes update beta based on children’s returned values. Alpha-Beta Example Revisited Do DF-search until first leaf a, b, initial values a=− b =+ a, b, passed to kids a=− b =+ Review Detailed Example of Alpha-Beta Pruning in lecture slides. Alpha-Beta Example (continued) a=− b =+ a=− b =3 MIN updates b, based on kids Alpha-Beta Example (continued) a=− b =+ a=− b =3 MIN updates b, based on kids. No change. Alpha-Beta Example (continued) MAX updates a, based on kids. a=3 b =+ 3 is returned as node value. Alpha-Beta Example (continued) a=3 b =+ a, b, passed to kids a=3 b =+ Alpha-Beta Example (continued) a=3 b =+ MIN updates b, based on kids. a=3 b =2 Alpha-Beta Example (continued) a=3 b =+ a=3 b =2 a ≥ b, so prune. Alpha-Beta Example (continued) MAX updates a, based on kids. No change. a=3 b =+ 2 is returned as node value. Review Detailed Example of Alpha-Beta Pruning in lecture slides. Review Propositional Logic Chapter 7.1-7.5 • Definitions: – Syntax, Semantics, Sentences, Propositions, Entails, Follows, Derives, Inference, Sound, Complete, Model, Satisfiable, Valid (or Tautology) • Syntactic Transformations: – E.g., (A B) (A B) • Semantic Transformations: – E.g., (KB |= a) (|= (KB a) • Truth Tables: – Negation, Conjunction, Disjunction, Implication, Equivalence (Biconditional) • Inference: – By Model Enumeration (truth tables) – By Resolution Recap propositional logic: Syntax • Propositional logic is the simplest logic – illustrates basic ideas • The proposition symbols P1, P2 etc are sentences – – – – – If S is a sentence, S is a sentence (negation) If S1 and S2 are sentences, S1 S2 is a sentence (conjunction) If S1 and S2 are sentences, S1 S2 is a sentence (disjunction) If S1 and S2 are sentences, S1 S2 is a sentence (implication) If S1 and S2 are sentences, S1 S2 is a sentence (biconditional) Recap propositional logic: Semantics Each model/world specifies true or false for each proposition symbol E.g. P1,2 P2,2 P3,1 false true false With these symbols, 8 possible models can be enumerated automatically. Rules for evaluating truth with respect to a model m: S is true iff S is false S1 S2 is true iff S1 is true and S2 is true S1 S2 is true iff S1is true or S2 is true S1 S2 is true iff S1 is false or S2 is true (i.e., is false iff S1 is true and S2 is false) S1 S2 is true iff S1S2 is true and S2S1 is true Simple recursive process evaluates an arbitrary sentence, e.g., P1,2 (P2,2 P3,1) = true (true false) = true true = true Recap propositional logic: Truth tables for connectives OR: P or Q is true or both are true. XOR: P or Q is true but not both. Implication is always true when the premises are False! Recap propositional logic: Logical equivalence and rewrite rules • To manipulate logical sentences we need some rewrite rules. • Two sentences are logically equivalent iff they are true in same models: α ≡ ß iff α╞ β and β╞ α You need to know these ! Recap propositional logic: Entailment • Entailment means that one thing follows from another: KB ╞ α • Knowledge base KB entails sentence α if and only if α is true in all worlds where KB is true – E.g., the KB containing “the Giants won and the Reds won” entails “The Giants won”. – E.g., x+y = 4 entails 4 = x+y – E.g., “Mary is Sue’s sister and Amy is Sue’s daughter” entails “Mary is Amy’s aunt.” Review: Models (and in FOL, Interpretations) • Models are formal worlds in which truth can be evaluated • We say m is a model of a sentence α if α is true in m • M(α) is the set of all models of α • Then KB ╞ α iff M(KB) M(α) – E.g. KB, = “Mary is Sue’s sister and Amy is Sue’s daughter.” – α = “Mary is Amy’s aunt.” • Think of KB and α as constraints, and of models m as possible states. • M(KB) are the solutions to KB and M(α) the solutions to α. • Then, KB ╞ α, i.e., ╞ (KB a) , when all solutions to KB are also solutions to α. Review: Wumpus models • KB = all possible wumpus-worlds consistent with the observations and the “physics” of the Wumpus world. Review: Wumpus models α1 = "[1,2] is safe", KB ╞ α1, proved by model checking. Every model that makes KB true also makes α1 true. Wumpus models α2 = "[2,2] is safe", KB ╞ α2 Review: Schematic for Follows, Entails, and Derives Inference Sentences Derives Sentence If KB is true in the real world, then any sentence a entailed by KB and any sentence a derived from KB by a sound inference procedure is also true in the real world. Schematic Example: Follows, Entails, and Derives “Mary is Sue’s sister and Amy is Sue’s daughter.” Inference “An aunt is a sister of a parent.” “Mary is Sue’s sister and Amy is Sue’s daughter.” Representation “An aunt is a sister of a parent.” Mary Sister Sue World Daughter Amy Derives “Mary is Amy’s aunt.” Is it provable? Entails “Mary is Amy’s aunt.” Is it true? Follows Is it the case? Mary Aunt Amy Recap propositional logic: Validity and satisfiability A sentence is valid if it is true in all models, e.g., True, A A, A A, (A (A B)) B Validity is connected to inference via the Deduction Theorem: KB ╞ α if and only if (KB α) is valid A sentence is satisfiable if it is true in some model e.g., A B, C A sentence is unsatisfiable if it is false in all models e.g., AA Satisfiability is connected to inference via the following: KB ╞ A if and only if (KB A) is unsatisfiable (there is no model for which KB is true and A is false) • KB ├ i Inference Procedures A means that sentence A can be derived from KB by procedure i • Soundness: i is sound if whenever KB ├i α, it is also true that KB╞ α – (no wrong inferences, but maybe not all inferences) • Completeness: i is complete if whenever KB╞ α, it is also true that KB ├i α – (all inferences can be made, but maybe some wrong extra ones as well) • Entailment can be used for inference (Model checking) – enumerate all possible models and check whether a is true. – For n symbols, time complexity is O(2n)... • Inference can be done directly on the sentences – Forward chaining, backward chaining, resolution (see FOPC, later) Conjunctive Normal Form (CNF) We’d like to prove: KB | a equivalent to : KB a unsatifiable We first rewrite KB a into conjunctive normal form (CNF). A “conjunction of disjunctions” literals (A B) (B C D) Clause Clause • Any KB can be converted into CNF. • In fact, any KB can be converted into CNF-3 using clauses with at most 3 literals. Example: Conversion to CNF Example: B1,1 (P1,2 P2,1) 1. Eliminate by replacing α β with (α β)(β α). = (B1,1 (P1,2 P2,1)) ((P1,2 P2,1) B1,1) 2. Eliminate by replacing α β with α β and simplify. = (B1,1 P1,2 P2,1) ((P1,2 P2,1) B1,1) 3. Move inwards using de Morgan's rules and simplify. (a b ) a b = (B1,1 P1,2 P2,1) ((P1,2 P2,1) B1,1) 4. Apply distributive law ( over ) and simplify. = (B1,1 P1,2 P2,1) (P1,2 B1,1) (P2,1 B1,1) Example: Conversion to CNF Example: B1,1 (P1,2 P2,1) From the previous slide we had: = (B1,1 P1,2 P2,1) (P1,2 B1,1) (P2,1 B1,1) 5. KB is the conjunction of all of its sentences (all are true), so write each clause (disjunct) as a sentence in KB: KB = … (B1,1 P1,2 P2,1) (P1,2 B1,1) (P2,1 B1,1) … Often, Won’t Write “” or “” (we know they are there) (B1,1 P1,2 P2,1) (P1,2 B1,1) (P2,1 B1,1) (same) Inference by Resolution • KB is represented in CNF – – – – KB = AND of all the sentences in KB KB sentence = clause = OR of literals Literal = propositional symbol or its negation Add the negated goal sentence to KB • Find two clauses in KB, one of which contains a literal and the other its negation • Cancel the literal and its negation • Bundle everything else into a new clause • Add the new clause to KB and keep going • Stop at the empty clause: ( ) = FALSE, you proved it! – Or stop when no more new inferences are possible Resolution = Efficient Implication Recall that (A => B) = ( (NOT A) OR B) and so: (Y OR X) = ( (NOT X) => Y) ( (NOT Y) OR Z) = (Y => Z) which yields: ( (Y OR X) AND ( (NOT Y) OR Z) ) = ( (NOT X) => Z) = (X OR Z) (OR A B C D) ->Same -> (OR ¬A E F G) ->Same -> ----------------------------(OR B C D E F G) (NOT (OR B C D)) => A A => (OR E F G) ---------------------------------------------------(NOT (OR B C D)) => (OR E F G) ---------------------------------------------------(OR B C D E F G) Recall: All clauses in KB are conjoined by an implicit AND (= CNF representation). Resolution Examples • Resolution: inference rule for CNF: sound and complete! * (A B C ) (A) “If A or B or C is true, but not A, then B or C must be true.” (B C ) (A B C ) ( A D E ) “If A is false then B or C must be true, or if A is true then D or E must be true, hence since A is either true or false, B or C or D or E must be true.” (B C D E ) (A B ) (A B ) “If A or B is true, and not A or B is true, then B must be true.” (B B ) B Simplification is done always. * Resolution is “refutation complete” in that it can prove the truth of any entailed sentence by refutation. * You can start two resolution proofs in parallel, one for the sentence and one for its negation, and see which branch returns a correct proof. Only Resolve ONE Literal Pair! If more than one pair, result always = TRUE. Useless!! Always simplifies to TRUE!! No! (OR A B C D) (OR ¬A ¬B F G) ----------------------------(OR C D F G) No! Yes! (but = TRUE) (OR A B C D) (OR ¬A ¬B F G) ----------------------------(OR B ¬B C D F G) Yes! (but = TRUE) No! (OR A B C D) (OR ¬A ¬B ¬C ) ----------------------------(OR D) No! Yes! (but = TRUE) (OR A B C D) (OR ¬A ¬B ¬C ) ----------------------------(OR A ¬A B ¬B D) Yes! (but = TRUE) Resolution example • KB = (B1,1 (P1,2 P2,1)) B1,1 • α = P1,2 KB a P2,1 True! False in all worlds Detailed Resolution Proof Example • In words: If the unicorn is mythical, then it is immortal, but if it is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a mammal, then it is horned. The unicorn is magical if it is horned. Prove that the unicorn is both magical and horned. ( (NOT Y) (NOT R) ) (M Y) (H R) ( (NOT H) G) • • • • • • (R Y) ( (NOT G) (NOT H) ) (H (NOT M) ) Fourth, produce a resolution proof ending in ( ): Resolve (¬H ¬G) and (¬H G) to give (¬H) Resolve (¬Y ¬R) and (Y M) to give (¬R M) Resolve (¬R M) and (R H) to give (M H) Resolve (M H) and (¬M H) to give (H) Resolve (¬H) and (H) to give ( ) • Of course, there are many other proofs, which are OK iff correct. Propositional Logic --- Summary • Logical agents apply inference to a knowledge base to derive new information and make decisions • Basic concepts of logic: – – – – – – – syntax: formal structure of sentences semantics: truth of sentences wrt models entailment: necessary truth of one sentence given another inference: deriving sentences from other sentences soundness: derivations produce only entailed sentences completeness: derivations can produce all entailed sentences valid: sentence is true in every model (a tautology) • Logical equivalences allow syntactic manipulations • Propositional logic lacks expressive power – Can only state specific facts about the world. – Cannot express general rules about the world (use First Order Predicate Logic instead) Review Probability Chapter 13 • Basic probability notation/definitions • Probability model, unconditional/prior and conditional/posterior probabilities, factored representation (= variable/value pairs), random variable, (joint) probability distribution, probability density function (pdf), marginal probability, (conditional) independence, normalization, etc. • Probability axioms, basic probability formulae • Product rule, summation rule, Bayes’ rule, factoring. Syntax •Basic element: random variable •Similar to propositional logic: possible worlds defined by assignment of values to random variables. •Booleanrandom variables e.g., Cavity (= do I have a cavity?) •Discreterandom variables e.g., Weather is one of <sunny,rainy,cloudy,snow> •Domain values must be exhaustive and mutually exclusive •Elementary proposition is an assignment of a value to a random variable: e.g., Weather = sunny; Cavity = false(abbreviated as ¬cavity) •Complex propositions formed from elementary propositions and standard logical connectives : e.g., Weather = sunny ∨ Cavity = false Probability • P(a) is the probability of proposition “a” – – – – E.g., P(it will rain in London tomorrow) The proposition a is actually true or false in the real-world P(a) = “prior” or marginal or unconditional probability Assumes no other information is available • Axioms: – – – – – 0 <= P(a) <= 1 P(NOT(a)) = 1 – P(a) P(true) = 1 P(false) = 0 P(A OR B) = P(A) + P(B) – P(A AND B) • An agent that holds degrees of beliefs that contradict these axioms will act sub-optimally in some cases – e.g., de Finetti proved that there will be some combination of bets that forces such an unhappy agent to lose money every time. – No rational agent can have axioms that violate probability theory. Conditional Probability • P(a|b) is the conditional probability of proposition a, conditioned on knowing that b is true, – – – – – E.g., P(rain in London tomorrow | raining in London today) P(a|b) is a “posterior” or conditional probability The updated probability that a is true, now that we know b P(a|b) = P(a AND b) / P(b) Syntax: P(a | b) is the probability of a given that b is true • a and b can be any propositional sentences • e.g., p( John wins OR Mary wins | Bob wins AND Jack loses) • P(a|b) obeys the same rules as probabilities, – E.g., P(a | b) + P(NOT(a) | b) = 1 – All probabilities in effect are conditional probabilities • E.g., P(a) = P(a | our background knowledge) Random Variables • A is a random variable taking values a1, a2, … am – Events are A= a1, A= a2, …. – We will focus on discrete random variables • Mutual exclusion P(A = ai AND A = aj) = 0 • Exhaustive P(ai) = 1 MEE (Mutually Exclusive and Exhaustive) assumption is often useful (but not always appropriate, e.g., disease-state for a patient) For finite m, can represent P(A) as a table of m probabilities For infinite m (e.g., number of tosses before “heads”) we can represent P(A) by a function (e.g., geometric) Joint Distributions • Consider 2 random variables: A, B – P(a, b) is shorthand for P(A = a AND B=b) a b P(a, b) = 1 – Can represent P(A, B) as a table of m2 numbers • Generalize to more than 2 random variables – E.g., A, B, C, … Z a b… z P(a, b, …, z) = 1 – P(A, B, …. Z) is a table of mK numbers, K = # variables • This is a potential problem in practice, e.g., m=2, K = 20 Linking Joint and Conditional Probabilities • Basic fact: P(a, b) = P(a | b) P(b) – Why? Probability of a and b occurring is the same as probability of a occurring given b is true, times the probability of b occurring • Bayes rule: P(a, b) = P(a | b) P(b) = P(b | a) P(a) by definition => P(b | a) = P(a | b) P(b) / P(a) [Bayes rule] Why is this useful? Often much more natural to express knowledge in a particular “direction”, e.g., in the causal direction e.g., b = disease, a = symptoms More natural to encode knowledge as P(a|b) than as P(b|a) Summary of Probability Rules • Product Rule: – P(a, b) = P(a|b) P(b) = P(b|a) P(a) – Probability of “a” and “b” occurring is the same as probability of “a” occurring given “b” is true, times the probability of “b” occurring. e.g., P( rain, cloudy ) = P(rain | cloudy) * P(cloudy) • Sum Rule: (AKA Law of Total Probability) – P(a) = b P(a, b) = b P(a|b) P(b), where B is any random variable – Probability of “a” occurring is the same as the sum of all joint probabilities including the event, provided the joint probabilities represent all possible events. – Can be used to “marginalize” out other variables from probabilities, resulting in prior probabilities also being called marginal probabilities. e.g., P(rain) = Windspeed P(rain, Windspeed) where Windspeed = {0-10mph, 10-20mph, 20-30mph, etc.} • Bayes’ Rule: - P(b|a) = P(a|b) P(b) / P(a) - Acquired from rearranging the product rule. - Allows conversion between conditionals, from P(a|b) to P(b|a). e.g., b = disease, a = symptoms More natural to encode knowledge as P(a|b) than as P(b|a). Computing with Probabilities: Law of Total Probability Law of Total Probability (aka “summing out” or marginalization) P(a) = b P(a, b) = b P(a | b) P(b) where B is any random variable Why is this useful? Given a joint distribution (e.g., P(a,b,c,d)) we can obtain any “marginal” probability (e.g., P(b)) by summing out the other variables, e.g., P(b) = a c d P(a, b, c, d) We can compute any conditional probability given a joint distribution, e.g., P(c | b) = a d P(a, c, d | b) = a d P(a, c, d, b) / P(b) where P(b) can be computed as above Independence • 2 random variables A and B are independent iff P(a, b) = P(a) P(b) for all values a, b • More intuitive (equivalent) conditional formulation – A and B are independent iff P(a | b) = P(a) OR P(b | a) P(b), for all values a, b – Intuitive interpretation: P(a | b) = P(a) tells us that knowing b provides no change in our probability for a, i.e., b contains no information about a • Can generalize to more than 2 random variables • In practice true independence is very rare – – – • “butterfly in China” effect Weather and dental example in the text Conditional independence is much more common and useful Note: independence is an assumption we impose on our model of the world - it does not follow from basic axioms Conditional Independence • 2 random variables A and B are conditionally independent given C iff P(a, b | c) = P(a | c) P(b | c) • More intuitive (equivalent) conditional formulation – – • for all values a, b, c A and B are conditionally independent given C iff P(a | b, c) = P(a | c) OR P(b | a, c) P(b | c), for all values a, b, c Intuitive interpretation: P(a | b, c) = P(a | c) tells us that learning about b, given that we already know c, provides no change in our probability for a, i.e., b contains no information about a beyond what c provides Can generalize to more than 2 random variables – E.g., K different symptom variables X1, X2, … XK, and C = disease – – P(X1, X2,…. XK | C) = P P(Xi | C) Also known as the naïve Bayes assumption Review Bayesian Networks Chapter 14.1-14.5 • Basic concepts and vocabulary of Bayesian networks. – Nodes represent random variables. – Directed arcs represent (informally) direct influences. – Conditional probability tables, P( Xi | Parents(Xi) ). • Given a Bayesian network: – Write down the full joint distribution it represents. – Inference by Variable Elimination • Given a full joint distribution in factored form: – Draw the Bayesian network that represents it. • Given a variable ordering and some background assertions of conditional independence among the variables: – Write down the factored form of the full joint distribution, as simplified by the conditional independence assertions. Bayesian Networks • Represent dependence/independence via a directed graph – Nodes = random variables – Edges = direct dependence • Structure of the graph Conditional independence relations • Recall the chain rule of repeated conditioning: The full joint distribution The graph-structured approximation • Requires that graph is acyclic (no directed cycles) • 2 components to a Bayesian network – The graph structure (conditional independence assumptions) – The numerical probabilities (for each variable given its parents) Bayesian Network • A Bayesian network specifies a joint distribution in a structured form: Full factorization B A p(A,B,C) = p(C|A,B)p(A|B)p(B) = p(C|A,B)p(A)p(B) After applying conditional independence from the graph C • Dependence/independence represented via a directed graph: − Node − Directed Edge − Absence of Edge = random variable = conditional dependence = conditional independence •Allows concise view of joint distribution relationships: − Graph nodes and edges show conditional relationships between variables. − Tables provide probability data. Examples of 3-way Bayesian Networks A B C Marginal Independence: p(A,B,C) = p(A) p(B) p(C) Examples of 3-way Bayesian Networks Conditionally independent effects: p(A,B,C) = p(B|A)p(C|A)p(A) B and C are conditionally independent Given A A B C e.g., A is a disease, and we model B and C as conditionally independent symptoms given A e.g. A is culprit, B is murder weapon and C is fingerprints on door to the guest’s room Examples of 3-way Bayesian Networks A B Independent Causes: p(A,B,C) = p(C|A,B)p(A)p(B) C “Explaining away” effect: Given C, observing A makes B less likely e.g., earthquake/burglary/alarm example A and B are (marginally) independent but become dependent once C is known Examples of 3-way Bayesian Networks A B C Markov chain dependence: p(A,B,C) = p(C|B) p(B|A)p(A) e.g. If Prof. Lathrop goes to party, then I might go to party. If I go to party, then my wife might go to party. Bigger Example • Consider the following 5 binary variables: – – – – – B = a burglary occurs at your house E = an earthquake occurs at your house A = the alarm goes off J = John calls to report the alarm M = Mary calls to report the alarm • Sample Query: What is P(B|M, J) ? • Using full joint distribution to answer this question requires – 25 - 1= 31 parameters • Can we use prior domain knowledge to come up with a Bayesian network that requires fewer probabilities? Constructing a Bayesian Network: Step 1 • Order the variables in terms of influence (may be a partial order) e.g., {E, B} -> {A} -> {J, M} • P(J, M, A, E, B) = P(J, M | A, E, B) P(A| E, B) P(E, B) ≈ P(J, M | A) P(A| E, B) P(E) P(B) ≈ P(J | A) P(M | A) P(A| E, B) P(E) P(B) These conditional independence assumptions are reflected in the graph structure of the Bayesian network Constructing this Bayesian Network: Step 2 • P(J, M, A, E, B) = P(J | A) P(M | A) P(A | E, B) P(E) P(B) • There are 3 conditional probability tables (CPDs) to be determined: P(J | A), P(M | A), P(A | E, B) – Requiring 2 + 2 + 4 = 8 probabilities • And 2 marginal probabilities P(E), P(B) -> 2 more probabilities • Where do these probabilities come from? – – – Expert knowledge From data (relative frequency estimates) Or a combination of both - see discussion in Section 20.1 and 20.2 (optional) The Resulting Bayesian Network The Bayesian Network from a different Variable Ordering Inference by Variable Elimination • Say that query is P(B|j,m) – P(B|j,m) = P(B,j,m) / P(j,m) = α P(B,j,m) • Apply evidence to expression for joint distribution – P(j,m,A,E,B) = P(j|A)P(m|A)P(A|E,B)P(E)P(B) • Marginalize out A and E Distribution over variable B – i.e. over states {b,¬b} Sum is over states of variable A – i.e. {a,¬a} Inference by Variable Elimination P(A) .05 Disease1 P(B) .02 Disease2 A A B P(C|A,B) t t .95 t f .90 f t .90 f f .005 TempReg B C D C P(D|C) t .95 f .002 Fever What is the posterior conditional distribution of our query variables, given that fever was observed? P(A,B|d) = α Σ c P(A,B,c,d) = α Σ c P(A)P(B)P(c|A,B)P(d|c) = α P(A)P(B) Σ c P(c|A,B)P(d|c) P(a,b|d) = α P(a)P(b) Σ c P(c|a,b)P(d|c) = α P(a)P(b){ P(c|a,b)P(d|c)+P(c|a,b)P(d|c) } = α .05x.02x{.95x.95+.05x.002} α .000903 .014 P(a,b|d) = α P(a)P(b) Σ c P(c|a,b)P(d|c) = α P(a)P(b){ P(c|a,b)P(d|c)+P(c|a,b)P(d|c) } = α .95x.02x{.90x.95+.10x.002} α .0162 .248 P(a,b|d) = α P(a)P(b) Σ c P(c|a,b)P(d|c) = α P(a)P(b){ P(c|a,b)P(d|c)+P(c|a,b)P(d|c) } = α .05x.98x{.90x.95+.10x.002} α .0419 .642 P(a,b|d) = α P(a)P(b) Σ c P(c|a,b)P(d|c) = α P(a)P(b){ P(c|a,b)P(d|c)+P(c|a,b)P(d|c) } = α .95x.98x{.005x.95+.995x.002} α .00627 .096 α 1 / (.000903+.0162+.0419+.00627) 1 / .06527 15.32 Mid-term Review Chapters 2-5, 7, 13, 14 • Review Agents (2.1-2.3 ? 1-2) • Review State Space Search • • • • • • • • Problem Formulation (3.1, 3.3 ? 3.1-3.4) Blind (Uninformed) Search (3.4) Heuristic Search (3.5 ? 3.5-3.7) Local Search (4.1, 4.2) Review Adversarial (Game) Search (5.1-5.4) Review Propositional Logic (7.1-7.5) Review Probability & Bayesian Networks (13, 14.1-14.5) Please review your quizzes and old CS-171 tests • At least one question from a prior quiz or old CS-171 test will appear on the mid-term (and all other tests)