13 Bayes Nets

Review: Probabilistic Inference

• probabilistic inference

• computing beliefs using inference by enumeration

• general case:

• evidence variables \(E_1, E_2, \dots, E_k\)
• query variables: \(Q\)
• hidden variables \(H_1, H_2, \dots, H_r\)
• we want \(P(Q | e_1, e_2, \dots, e_k)\)

step 1: select the entries that are consistent with the evidence step 2: sum out all the hidden variables (\(h_1, h_2, \dots, h_r\)) to get the joint of query and evidence - summing out will collapse everything into the joint probability - \(P(Q, E_1 \dots E_k) = \sum_{H_1 \dots H_r} P(Q, H, E_1 \dots E_k)\)

we want to know the prob of \(W\)

S	T	W	P
Summer	Hot	sun	0.3
Summer	Hot	rain	0.05
Summer	Cold	sun	0.1
Summer	Cold	rain	0.05
Winter	Hot	sun	0.1
Winter	Hot	rain	0.05
Winter	Cold	sun	0.15
Winter	Cold	rain	0.2

P(W)

• add up the rows where it's sunny
• add the rows where it's rainy
• and that's our distribution

	P
S
R

P(W | Winter)

• remove the first four rows (no winter)
• sum over sun, sum over rain, sum over hot, sum over cold

obvious problems

• worst case runtime complexity \(O(d^n)\)
• etc.

Review the product rule

\(P(y)P(x|y) = P(x, y)\)

Probabilistic models

• we can think of joint distributions as our models, so we'll build on that today as probabilistic models
• the big weather table is a model — summer being hot/cold, and so on
• it's not necessarily a perfect representation: it doesn't include autumn/fall, and maybe temperature isn't discrete but continuous

• we could add more variables, or have each variable take a different domain

• there's a really famous quote: "all models are wrong but some are useful"

• what decisions do I have to make to convince myself and others that this is a useful model of the world?

• what do we do with these probabilistic models? we can use them for prediction

• e.g. you know it's raining and you know there's traffic, so you want the probability of making it on time

Independence

• two variables can be independent

they are independent if: - \(\forall x, y: P(x, y) = P(x)P(y)\), or - \(\forall x, y: P(x|y) = P(x)\)

we can write \(X \perp Y\)

• how is this different from the chain rule or the product rule?

if they are dependent then: - \(\forall x, y: P(x, y) = P(x)P()\)

example: independence?

\(P(T, W)\)

T	W	P
Hot	Sun	0.4
Hot	Sun	0.1
Cold	Rain	0.2
Cold	Rain	0.3

\(P(T)\)

T	P
Hot	0.5
Cold	0.5

\(P(W)\)

W	P
sun	0.6
rain	0.4

so $P(T)P(W) = $ #=: 0.5 * 0.6 \(\neq 0.4\), so not independence

\(P2(T, W)\)

T	W	P
Hot	Sun	0.3
Hot	Sun	0.2
Cold	Rain	0.3
Cold	Rain	0.2
- ^this one is independent

example: coin flips

\(P(X_1)\)

H	0.5
T	0.5

• exactly the same table across all the \(N\) coin flips
• we can test by multiplying the prob of H by the prob of H for all \(X_n\) in the first row — it gives the same probabilities for each marginal value
• this lets us avoid writing out the whole distribution

Conditional independence

• something more general than independence
• we sometimes want to know how some variables interact — e.g. how traffic affects me showing up to work. these things are somewhat connected, and it'd be nice to focus only on the events we know are related, so we can use smaller pieces of the table without storing the entire thing

running example: \(P(\text{toothache}, \text{cavity}, \text{catch})\) - if I have a cavity, the probability the probe catches in it doesn't depend on whether I have a toothache - \(P(+catch | +cavity, +toothache) = P(+catch | +cavity)\) - so toothache and catch are relatively independent - we can factor the distribution into the cavity–catch relationship to simplify the model - whether or not your tooth hurts shouldn't affect whether the probe catches the cavity - the relationship between toothache and catch is mediated by cavity - there are assumptions we can make about each of these - if your tooth hurts, it's probably likely to be a cavity

• this is the idea behind conditional independence; the forms are all equivalent, based on the definition of conditional independence and the definition of the conditional distribution
• conditional independence lets us split the distribution into two smaller cases, e.g. \(P(\text{toothache} | \text{cavity})\) vs \(P(\text{catch} | \text{cavity})\)
• full independence is incredibly rare; conditional independence is a weaker assumption — it only requires knowing a cavity was present, and it pushes us to model variables that are related in some way

definition: \(\forall x, y, z: P(x, y|z) = P(x|z)P(y|z)\)

domain: traffic, umbrella, raining

• maybe having an umbrella doesn't necessarily mean there's traffic
• traffic and umbrella are conditionally dependent — they're not totally independent, but given rain they should be independent

domain: smoke, fire, alarm

• all of these are related in some way, but there may be ways they're not completely dependent on each other
• the fire and the alarm are connected given there is smoke

chain rule (again)

\(P(x_1, x_2, \dots, x_n) = P(x_1) P(x_2 | x_1) P(x_3 | x_1, x_2) \cdots P(x_n | x_1, \dots, x_{n-1})\)

# chain rule: P(a, b, c) = P(a) P(b|a) P(c|a,b)
p_a = 0.6
p_b_given_a = 0.3
p_c_given_ab = 0.5
p_a * p_b_given_a * p_c_given_ab =>

ghostbusters example: chain rule

• each sensor depends only on where the ghost is
• so the two sensors are conditionally independent given the ghost position

two-square grid: - \(T\): top square is red - \(B\): bottom square is red - \(G\): ghost is on top

are these independent? - no — the top and bottom readings are both caused by the ghost - but if we already know where the ghost is (e.g. told the ghost is on top), then whether you get a red reading on one square doesn't affect the reading on the other - so this is just another example of conditional independence and dependence

• in general you'd have to write down every single combination, but what we're trying to do is split distributions
• you can imagine having this big table; you can store just the distributions and compute back the joint one

Bayes nets

• a Bayes net is a joint distribution

two problems with joint distribution tables as our probabilistic models: - unless there are only a few variables, the joint is way too big to represent explicitly — we can instead encode the conditional distributions we talked about - it's hard to learn anything empirically about more than a few variables at a time

• Bayes nets are a graphical representation of these relative distributions

insurance example

• each circle is a node, and a node is a random variable
• say we have two cars and want to price insurance — we have all this data around the car
• from an insurance company's side, we want to know: are any of these variables independent?
• companies believe their own model is best — this is their model of whether someone is likely to get into an accident

• maybe weather isn't related; we could still include it, but wouldn't represent it per customer

• take the variable Age and the variable Accident — they're related in some way. e.g. older people might be more risk-averse, which affects risk. people might see them as related

• if we wanted to write this out as a joint distribution, every column is the list of variables — but this graphical representation lets us write the same thing in a simpler, nicer form

example: bayes net: car

• battery age, battery dead, battery meter, alternator broken, fan belt broken
• no oil, no gas, fuel line blocked
• starter broken
• these can tell you something about why the car won't start
• there are things you don't observe too — e.g. you might not observe whether the fuel line is blocked, and you can try to reason it out
• we can do some sort of diagnostic in the graphical model; it encodes the same information

nodes and arcs

• the variables we're dealing with in the tables are called nodes
• they can be observed or unobserved (weather, etc.)
• the connections between the nodes are the interactions / arcs / arrows

• by drawing the arrow (and not drawing the variable) we can write down the conditional independence, because of the way the interactions are drawn

• e.g. the cavity model: probe catching the cavity — we're conditionally independent, with an arrow from cavity to toothache

• another way to think about it: the arrows mean causation. this isn't true in general, but for now imagine it — a cavity means you have a toothache; if you have a cavity, the dental probe catches
• in general these arrows do not imply causality
• but they help you reason about which direction things should be looking

coin flips example

• \(N\) independent coin flips \(X_1, X_2, \dots, X_n\)
• this Bayes net encodes independence — since they're all independent, it's a set of unconnected nodes

traffic example

• \(R\): rain
• \(T\): traffic

model 1: independence - rain and traffic are completely independent from each other - (and we've reasoned why rain and traffic might actually be correlated)

model 2: rain causes traffic - an arc between \(R\) and \(T\)

causal graphical model

variables: - \(T\): Traffic - \(R\): it rains - \(L\): low pressure - \(D\): Roof Drips - \(B\): ballgame - \(C\): Cavity (haha)

• rain affects traffic: an arrow from \(R\) pointing at \(T\)
• if the pressure is low, that causes clouds and eventually rain: \(L\) points at \(R\)
• with rain the roof would drip: \(R\) points at \(D\)
• the ballgame can get cancelled due to rain, and the ballgame can affect traffic: \(R\) points to \(B\), \(B\) points to \(T\)
• cavity is completely independent — nothing points to \(C\)

another example network

• \(B\): Burglary
• \(A\): Alarm goes off
• \(M\): Mary calls
• \(J\): John calls
• \(E\): Earthquake happens

what it takes to build a bayes net

• a set of nodes, one per variable \(X\)
• a directed acyclic graph
• a conditional distribution for each node
• a collection of distributions over \(X\), one for each combination of parents values
  • \(P(X | a_1, \dots, a_n)\)
• CPT: conditional probability table
• description of a noisy "causal" process

A Bayes net = topology (graph) + local conditional probabilities

• the fact that there are no cycles means there is an ordering
• \(P(x_1, x_2, x_3) = P(x_1) P(x_2 | x_1) P(x_3 | x_1, x_2) \dots\)

• now \(P(x_2)\) would be dependent on not just \(x_1\) but also \(x_3\) if the graph was cyclic, so we have to make sure they're introduced one at a time

• Bayes nets implicitly encode these distributions as a product of local conditional distributions

• to see what probability a BN gives to a full assignment, multiply all the relevant conditionals together
• \(P(x_1, x_2, \dots, x_n) = \prod_{i=1}^{n} P(x_i | \text{parents}(X_i))\)
• example (cavity):
• \(P(+cavity, +catch, -toothache) = P(\text{toothache}|\text{cavity}) \cdot P(\text{catch}|\text{cavity})\)

how big is a bayes net?

• \(2^n\) over \(N\) boolean variables
• \(d^n\) over \(d\)-ary variables
• how big is an \(N\)-node net if nodes have up to \(k\) parents?
• \(O(N \cdot 2^{k+1})\)
• both give you the power to calculate \(P(X_1, X_2, \dots, X_n)\)

• BN's huge

• so far: how a Bayes net encodes a joint distribution

• next: how to answer queries about that distribution
• after that: how to answer numerical queries

bye!