Conditional Independence & Distributions in AI: Lecture Notes Outline

Lecture notes for Principles of Artificial Intelligence (COMS 4720/5720) Yan-Bin Jia, Iowa State University Conditional Independence & Distributions Outline I. Conditional independence relations II. Independence within context III. Case Studies * Figures are either from the textbook site or by the instructor.

I. Non-Descendants Property of BNs Non-descendants property: Every variable is conditionally independent of its non-descendants, given its parents. Given the value of Alarm, JohnCalls is independent of Burglary, Earthquake, and Marycalls. ? ??parents(??)) = ? ?? | parents(??) // network parameter interpretation

Illustration ? ??parents(??)) = ? ?? | parents(??) ? The full joint distribution ?(?1, ,??) = ? ??parents(??)) ?=1

Markov Blanket The Markov blanket ?? ? of a node ? consists of its parents, children, and children s parents (excluding ?). ?? ? = Children ? Parents ? ? | ? ? ? ? Children ? ? Parents(?) The Markov blanket of Burglary is {Alarm, Earthquake}. The Markov blanket is represented by the gray area.

Conditional Independence It is implied by the non-descendants property that A node is conditionally independent of all other nodes given its Markov blanket. For any random variable ? such that ? ? and ? ?? ? ? ? | ?? ? ,? = ? ? | ?? ? The Markov blanket of Burglary is {Alarm, Earthquake}. Given Alarm and Earthquake, Burglary is independent of JohnCalls and Marycalls (even though they are its descendants). Markov blanket will be used for inferences over stochastic sampling processes.

D-Separation Q: Is a set of nodes ? conditionally independent of another set ?, given a third set ?? In short, does ? ? ?,?) = ? ? ?) hold? This question can be answered as follows: 1. Start with the ancestral subgraph consisting of ?, ?, ?, and their ancestors (and edges between them). ? ? ? ? ? 2. Replace all directed edges with undirected edges. 3. Add an (undirected) edge between every two nodes that share a common child. The resulting graph is the moral graph of the ancestral subgraph. a. If ? blocks all paths between ? and ? in the moral graph, then ? d-separates ? and ?. In this case, ? is conditionally independent of ?, given ?. (You may check connectivity by removing nodes in ? and their edges.) ?,?,? is conditionally independent of ? given ?. ? is conditionally independent of ? given {?,?}. ? ? ? ? ? Moral graph b. Otherwise, ? and ? are not necessarily conditionally independent, given ?. ? and ? are not necessarily conditionally independent given ?.

Example 1 1. ?={Burglary } ?={Earthquake } ?={ } Q: ? conditionally independent of ? given ?? Ancestral graph: ?,?,? and their ancestors (and edges) Burglary Earthquake Moral graph: also edges between two parents of the same child Burglary Earthquake ? and ? are separated, thus d-separated by ?. Burglary and Earthquake are independent given the empty set.

Example 2 1. ?={Burglary } ?={Earthquake } ?={ Alarm } Q: ? conditionally independent of ? given ?? Ancestral graph Burglary Earthquake Alarm Moral graph Burglary and Earthquake are not necessarily independent given Alarm.

Example 3 3.?={JohnCalls } ?={MaryCalls } ?={ Alarm } Q: ? conditionally independent of ? given ?? JohnCalls and MayCalls are conditionally independent given Alarm. Ancestral graph Burglary Earthquake Alarm Moral graph MaryCalls JohnCalls

II. Efficient Representations The size 2? of the conditional probability table (CPT) for a node with ? parents is the worst-case scenario in which the relationships with the parents are arbitrary. ?1 ?2 ?? ? ?1 ?2 ?? 2? ? Deterministic nodes. Such a node has its value specified exactly by those of its parents, with no uncertainty. Specify deterministic functions in a BN. Mexican Canadian US disjunction NorthAmerican CPT has 3 rows instead of 8.

Independence Within Context Context-specific independence. A variable is conditionally independent of some of its parents given certain values of others. ? DamageRuggedness,Accident) = if (Accident = false) then ?1 else ?2(Ruggedness) // if no accident, damage to // your car does not depend // on ruggedness. distributions function of ruggedness

Noisy-OR Relation Characterizes uncertain relationships. Generalizes logical OR. Fever Cold Flu Malaria (Propositional logic) Malaria Cold Flu A patient could have a cold, but not exhibit a fever. Fever Noisy-OR allows for uncertainty about each of Cold, Flu, Malaria to cause Fever. The causal relationship betwe en a node ? and its parents may be inhibited (i.e., ? =False despite a parent ? =True) List all the possible causes. Inhibition of each parent is independent of inhibition of any other parents.

Causes of Fever Random variables: ?1 Cold,?2 Flu, ?3 Malaria Inhibition probabilities: // no fever; false alarm ?1= ?cold = ? fevercold, flu, malaria) = 0.6 Cold is the only symptom. ?2= ?flu = ? fever cold,flu, malaria) = 0.2 ?3= ?malaria = ? fever cold, flu,malaria) = 0.1 ?? ? ?? | ?? Parents ?? ??= true ? ? parents ?? ? ?? ? = false

Independence of Inhibition ?1 Cold,?2 Flu, ?3 Malaria ?1= ?cold = ? fevercold, flu, malaria) = 0.6 ?2= ?flu = ? fever cold,flu, malaria) = 0.2 ?3= ?malaria = ? fever cold, flu,malaria) = 0.1 Whatever inhibits cold from causing a fever is independent of whatever inhibits flu from causing a fever. Fever is false if and only if all of its parents are inhibited. ? fever cold,flu,malaria) = ? fever cold,flu, malaria) ? fever cold, flu,malaria) = 0.2 0.1 = 0.02 ? fever cold,flu,malaria) = 1 ? fever cold,flu,malaria) = 0.98 From ?1,?2,?3 we can construct the entire CPT: ? ??parents(??)) = 1 ?? ?? Parents true ?? ??=

III. Case Study 1: Car Insurance A car insurance company processes a car insurance application to decide on the annual premium based on the anticipated claims it will pay out for the applicant. input information hidden variables essential for structuring the network so it stays sparse and manageable Goal Give an accurate, well-calibrated distribution over the output variables given the evidence available form the input. claims

Case Study 2: Car Diagnosis * Courtesy of Dr. Jin Tian