Pregovor-biosfera-i-ekologichni-faktori-obobshtenie-4016.jpeg

# Lecture 15: Bayesian Networks ## Reasoning Under Uncertainty ### What is uncertainty? * Things we did not account for * Limited computational power * Principles are non-existent, unknown, or too costly to represent * **Bayesian Networks** are a tool/language for reasoning under uncertai...

# Lecture 15: Bayesian Networks ## Reasoning Under Uncertainty ### What is uncertainty? * Things we did not account for * Limited computational power * Principles are non-existent, unknown, or too costly to represent * **Bayesian Networks** are a tool/language for reasoning under uncertainty ### Bayes' Rule $$ P(A|B) = \frac{P(A)P(B|A)}{P(B)} $$ * We have some hypothesis, A, and some evidence, B * $P(A)$ is our prior belief without evidence * $P(B|A)$ tells us how well the evidence supports the hypothesis * Normalization constant: $P(B) = \sum_i P(B|A_i)P(A_i)$ ### Example **Question**: You have a test for a disease that is 99% accurate. 1% of the population has the disease. You test positive. What is the probability you have the disease? #### Intuition * The test is 99% accurate, so there is a 99% chance you have the disease. #### Bayes Rule * A = You have the disease * B = You test positive * $P(A|B) = \frac{P(A)P(B|A)}{P(B)}$ * $P(A|B) = \frac{0.01 \cdot 0.99}{0.01 \cdot 0.99 + 0.99 \cdot 0.01} = 0.5$ ## Bayesian Networks ### Bayesian Network * A directed acyclic graph (DAG) where nodes represent random variables and edges represent dependencies. * Each node has a conditional probability distribution $P(X_i | Parents(X_i))$ that quantifies the effect of the parents on the node. * A node is conditionally independent of its non-descendants given its parents. ### Example * A = Burglary * B = Earthquake * C = Alarm * D = John calls * E = Mary calls #### Diagram The diagram shows a Bayesian network with 5 nodes: A, B, C, D, and E. * A and B are parent nodes of C. * C is a parent node of D and E. * There are arrows pointing from A to C, B to C, C to D, and C to E. #### Joint Probability $$ P(A, B, C, D, E) = P(A)P(B)P(C|A, B)P(D|C)P(E|C) $$ ### How to Build? 1. Choose the variables. 2. Choose an ordering of variables $X_1,..., X_n$. 3. For $i = 1$ to $n$: * Add $X_i$ to the network * Choose parents $Parents(X_i)$ from $X_1,..., X_{i-1}$ such that $$ P(X_i | Parents(X_i)) = P(X_i | X_1,..., X_{i-1}) $$ ### Example * Weather affects whether I have a headache * Whether I have a headache affects whether I study #### Diagram The diagram shows a Bayesian network with 3 nodes: Weather, Headache, and Study. * Weather is a parent node of Headache. * Headache is a parent node of Study. * There are arrows pointing from Weather to Headache, and from Headache to Study. #### Joint Probability $$ P(W, H, S) = P(W)P(H|W)P(S|H) $$ ### Size of Bayesian Networks * Consider $n$ binary variables * Unconstrained joint distribution requires $O(2^n)$ parameters * Bayesian networks require $O(n2^k)$ parameters, where $k$ is the maximum number of parents * We want shallow dependencies! ### Conditional Independence * $X$ is conditionally independent of $Y$ given $Z$ if $$ P(X|Y, Z) = P(X|Z) $$ * Also written as $X \perp\!\!\!\!\perp Y | Z$ ### Example * A = Burglary * B = Earthquake * C = Alarm * D = John calls * E = Mary calls #### Conditional Independence * John calls is conditionally independent of Mary calls given the alarm * Burglary is conditionally independent of earthquake * Alarm is conditionally independent of John calls given Burglary and Earthquake ### D-Separation #### Definition * A path between two nodes $X$ and $Y$ is d-separated by a set of nodes $Z$ if any of the following conditions hold: 1. The path contains a chain $A \rightarrow B \rightarrow C$ or a fork $A \leftarrow B \rightarrow C$ where $B$ is in $Z$ 2. The path contains a v-structure $A \rightarrow B \leftarrow C$ where $B$ is not in $Z$ and no descendant of $B$ is in $Z$ * If all paths between $X$ and $Y$ are d-separated by $Z$, then $X$ and $Y$ are conditionally independent given $Z$ #### Example 1 * $X \perp\!\!\!\!\perp Y | Z$? Yes The diagram shows a Bayesian network with 3 nodes: X, Y, and Z. * There is a chain X -> Z -> Y. #### Example 2 * $X \perp\!\!\!\!\perp Y | Z$? No The diagram shows a Bayesian network with 3 nodes: X, Y, and Z. * There is a fork X Y. #### Example 3 * $X \perp\!\!\!\!\perp Y | Z$? No * $X \perp\!\!\!\!\perp Y | \emptyset$? Yes The diagram shows a Bayesian network with 3 nodes: X, Y, and Z. * There is a v-structure X -> Z