Bayesian Networks Artificial Intelligence PDF

Bayesian networks Artificial intelligence Kristóf Karacs PPKE-ITK Recap n What is intelligence? n Agent model n Problem solving by search ¨ Non-informed, informed search strategies ¨ Search in two player games n Planning n Constraint satisf...

Bayesian networks Artificial intelligence Kristóf Karacs PPKE-ITK Recap n What is intelligence? n Agent model n Problem solving by search ¨ Non-informed, informed search strategies ¨ Search in two player games n Planning n Constraint satisfaction problems 1 Outline n Uncertainty vs. probability n Bayes’ rule n Independence… n Combining evidence n Bayesian Networks ¨ Connections ¨ Independence Sources and types of uncertainty n Lack of exact knowledge ¨ Environment of agent n not fully observable n noisy measurements ¨ e.g. “He may have found it.” n P( ) < 1 n Lack of exact concept definitions ¨ Categorical uncertainty ¨ e.g. “Peter is young.” n P( ) = 1, and we still do not know his age 2 Approaches to probability n Frequentist ¨ probability: frequency of positive cases ¨ assumes infinite sampling ¨ objective n Bayesian ¨ probability: based on agent’s experience / belief ¨ assumes a prior distribution ¨ subjective Motivation n For N propositional variables ¨ To calculate every possible probability joint probability distributions are needed ¨ There are 2N joint probabilities n Solution: exploit independencies in the domain 3 Bayes’ rule n Commutativity ¨ P(A Ù B) = P(B Ù A) ¨ P(A) * P(B | A) = P(B) * P(A | B) P(B | A) = P(A | B) * P(B) / P(A) n Example ¨ P(disease | symptom) = P(symptom | disease) * P(disease) / P(symptom) ¨ High fever (HF), diphtheria (D) ¨ P(D | HF) = P(HF | D) * P(D) / P(HF) Bayes’ rule n E - evidence n Hi - hypotheses P ( E | H i ) P ( Hi ) P ( E | Hi ) P ( Hi ) P ( Hi | E ) = = P(E) n å P( E | Hk ) P ( Hk ) k =1 4 Conditional independence n A and B are conditionally independent given C iff ¨ P(A Ù B | C) = P(A | C) * P(B | C) ¨ P(A | B,C) = P(A | C) ¨ P(B | A,C) = P(B | C) n Examples C ¨ Toothache (T), spot (X), cavity (C) T X Conditional independence n A and B are conditionally independent given C iff ¨ P(A Ù B | C) = P(A | C) * P(B | C) ¨ P(A | B,C) = P(A | C) ¨ P(B | A,C) = P(B | C) n Examples B ¨ Toothache (T), spot (X), cavity (C) ¨ Engine (E), radio (R), battery (B) E R 5 Conditional independence n A and B are conditionally independent given C iff ¨ P(A Ù B | C) = P(A | C) * P(B | C) ¨ P(A | B,C) = P(A | C) ¨ P(B | A,C) = P(B | C) n Examples F B ¨ Toothache, spot, cavity ¨ Engine (E), radio (R), battery (B), fuel (F) E R Everyday probability n Linda is 31 years old, single, outspoken, and very bright. She majored in philosophy. As a student, she was deeply concerned with issues of discrimination and social justice, and also participated in anti-nuclear demonstrations. n Which is more likely? (1) Linda is a bank teller. (2) Linda is a bank teller and is active in the feminist movement. 6 Conjugation fallacy n Amos Tversky and Daniel Kahneman, 1983 n “Extension versus intuitive reasoning: The conjunction fallacy in probability judgment” n 85% of people chose option 2, although P(A) ³ P(A,B) Exercises n Show that (1) P(A) ³ P(A,B) (2) P(A | B) + P(¬A | B) = 1 n Write an expression for P(A | B,C) in terms of P(B | A,C)! 7 Combining evidence n T: toothache X: spot on X-ray C: cavity P (T , X | C ) P ( C ) P (C | T , X ) = P (T , X ) n If T and X are conditionally independent given C, then P (T | C ) P ( X | C ) P ( C ) P (C | T , X ) = P (T , X ) Normalizing factor P ( C | T , X ) + P ( ØC | T , X ) = 1 P (T | C ) P ( X | C ) P ( C ) P ( T | ØC ) P ( X | ØC ) P ( ØC ) + =1 P (T , X ) P (T , X ) P (T | C ) P ( X | C ) P ( C ) + P (T | ØC ) P ( X | ØC ) P ( ØC ) = P ( T , X ) 8  Combining evidence P (T , X | C ) P ( C ) P (C | T , X ) = = P (T , X ) P (T | C ) P ( X | C ) P ( C ) = = P (T , X ) P (T | C ) P ( X | C ) P ( C ) = P (T | C ) P ( X | C ) P ( C ) + P (T | ØC ) P ( X | ØC ) P ( ØC ) Bayesian networks n Set of nodes representing random variables n Set of directed arcs (forming a DAG) expressing direct influence between nodes n Every node A with parents B1, …, Bn has the conditional probabilities P(A | B1, …, Bn) specified B1 … Bn A B1 ® A B2 ® A 9 Causal component n “Sherlock Holmes wakes up to find his lawn wet. He wonders if it has rained or if he left his sprinkler on. He looks at his neighbor Watson’s lawn and he sees it is wet as well. So, he concludes, it must have rained.” S R H W Serial connections n 1. Forward serial connection ¨ Transmit evidence from A to C through unless B is instantiated (its truth value is known) A B C 10 Serial connections n 1. Forward serial connection ¨ Transmit evidence from A to C through unless B is instantiated (its truth value is known) A B C Serial connections n 1. Forward serial connection ¨ Transmit evidence from A to C through unless B is instantiated (its truth value is known) A B C 11 Serial connections n 1. Forward serial connection ¨ Transmit evidence from A to C through unless B is instantiated (its truth value is known) n 2. Backward serial connection ¨ Transmit evidence from C to A through unless B is instantiated (its truth value is known) A B C Serial connections n 1. Forward serial connection ¨ Transmit evidence from A to C through unless B is instantiated (its truth value is known) n 2. Backward serial connection ¨ Transmit evidence from C to A through unless B is instantiated (its truth value is known) A B C 12 Serial connections n 1. Forward serial connection ¨ Transmit evidence from A to C through unless B is instantiated (its truth value is known) n 2. Backward serial connection ¨ Transmit evidence from C to A through unless B is instantiated (its truth value is known) A B C Diverging connection n Transmit evidence through B unless it is instantiated A B C 13 Diverging connection n Transmit evidence through B unless it is instantiated n Knowing about A will tell us something about C A B C Diverging connection n Transmit evidence through B unless it is instantiated n But, if we know B, then knowing about A will not tell us anything new about C, or vice versa A B C 14 Converging connection n Tricky case! n Transmit evidence from A to C only if B or a descendant of B is instantiated A B C Converging connection n Transmit evidence from A to C only if B or a descendant of B is instantiated n Without knowing B, finding A does not tell us anything about C A B C 15 Converging connection n Transmit evidence from A to C only if B or a descendant of B is instantiated n If we see evidence for B, then A and C become dependent (potential for “explaining away”). A B C Converging connection n Transmit evidence from A to C only if B or a descendant of B is instantiated n If we see evidence for B, then A and C become dependent (potential for “explaining away”). D A B C 16 D-separation n Two variables A and B are d-separated iff for every path between them, there is an intermediate variable V such that either ¨ the connection is serial or diverging and V is known ¨ the connection is converging and neither V nor any of its descendants is instantiated n Two variables are d-connected iff they are not d- separated D-separation exercise n No instantiation A n A instantiated n A and D instantiated B C n B instantiated D n B and C instantiated 17 Solution n No instantiation ¨ A, D are d-connected (A-B-D connected, A-C-D connected) ¨ B, C are d-connected (B-A-C connected, B-D-C blocked) n A instantiated ¨ B, C are d-separated (B-A-C blocked, B-D-C blocked) n A and D instantiated ¨ B, C are d-connected (B-A-C blocked, B-D-C connected) n B instantiated ¨ A, D are d-connected (A-B-D blocked, A-C-D connected) n B and C instantiated ¨ A, D are d-separated (A-B-D blocked, A-C-D blocked) Outline n Uncertainty vs. probability n Bayes’ Rule n Conditional independence n Combining evidence n Bayesian Networks ¨ Connections ¨ D-separation 18