12 Probability

part 1-2 we've finished search and solving stuff, planning in RL
part 3: probabilistic reasoning
part 4: Machine Learning

in the lectures we have predetermined probabilities as we go on computation will become more challenging

Now doing part 3

Probability

Today

random variables
joint and marginal distributions
conditional distributions
product rule, chain rule, etc

Inference in Ghostbusters

goal is to find the ghost hidden in the grid
we don't have any info, but when we pick a square, a sensor tells us how far away we are from the ghost
green 5 or more squares away
yellow 3-4 squares
orange 1-2 squares
red, caught the ghost
sensors are noisy but we know $P(\text{color} \mid \text{distance})$

p(red\|3)	p(orange\|3)	p(yellow\|3)	p(green\|3)

demo of ghostbuster: no probability

how do we do that when we have massive amounts of data and we are trying to make a decision?

general situation
observed variables (evidence): the agent knows certain things about the state of the world (sensor readings or symptoms)
unobserved variables: agent needs to reason about other aspects (where the ghost is or what disease is present)
model: agent knows something about how the known variables relate to the unknown variables
probabilistic reasoning and inference gives us a framework for managing our beliefs and knowledge

go back and forth between the variables and unobserved variables

a random variable is some aspect of the world about which we (may) have uncertainty
$R$: is it raining
binary, yes or no
$T$: is it hot or cold?
binary, hot or cold
$D$: how long will it take to drive to work?
all positive real values
$L$: where is the ghost
all locations on the lattice

what do probability distributions do?

they let us assume a probability for any outcome that the variable can take

$T = \text{hot} \to p = 0.5$
$T = \text{cold} \to p = 0.5$

and so on.

we may not know what the assignment of the variable is, we can find an probability.

for example the T-p table above show the possible values that the variable $T$ can take

$P(T = \text{cold}) = 0.5$

when you're dealing with multiple random variables, it can get confusing, so make sure that they can't have the same values

$P(T = \text{hot})$ is not $P(W = \text{hot})$

we can't use $P(\text{hot})$ anymore

they have some constraints

for all possible values of a random variable

\[\forall x \; P(X = x) \geq 0$$ $$\sum_{x} P(X = x) = 1\]

A joint distribution over a set of RV $X_1, X_2, X_3, \dots, X_n$, specifies a real number for each assignment or outcome

still obeys the same rules

all values must be nonnegative, and the sum of probabilities of events must sum to 1

what's the size of the distributions of $n$ variables with size $d$?
a probabilistic model is a joint distribution over a set of rv
probabilistic models
random variables with domains
assignments are called outcomes
joint distribution

marginal distributions

sub tables where we eliminate random variables

looks at a subset of them

we can get that by summing together the relevant rows to reduce the variables in other columns

lets compute the conditional probability

$P(a|b) = \frac{P(a, b)}{P(b)}$

$P(+x \mid +y) =$ #=: 0.2 / (0.2 + 0.4)

conditional distributions are probability distributions over some variables given fixed values of others

give some examples

how do we read $P(W = s \mid T = c) = \frac{P(W = s, T = c)}{P(T = c)}$

$= P(W = s \mid T = c) / (P(W = s, T = c) + P(W = r, T = c))$

to normalize we just have to divide by the total probabilities that $W$ can take.

look at the rows where $T = c$

normalize the selection so $T = c$

with that we get this conditional probability distribution.

Why does this work?

we are going to put this all together in order to do probabilistic inference

want to compute a conditional probability from a joint probability

$P(\text{being on time} \mid \text{no reported accidents})$

we generally compute conditional probabilities
these represent the agents beliefs given the evidence

probabilities change with new evidence,

$P(\text{on time} \mid \text{no accidents}) = 0.9$ $P(\text{on time} \mid \text{no accidents}, 5am) = 0.95$ etc.

general case
evidence variables: $E_1, E_2, E_3, \dots$
Query var: $Q$
Hidden variables, $H_1, H_2, H_3, \dots$

Example

variables: arrival time, reported accidents

how do we compute those variables

we select the entries consistent with the evidence
sum out $H$ to get the joint of the Query and the evidence
Normalize: $1/Z$

$P(W)$?

sum up the rows where W = sunny, add those rows tg sum the rows where W = rain, add those rows up $P(\text{sun})$ = 0.3, 0.1, 0.1, 0.15 ... $P(\text{rain})$ = ...

$P(W \mid \text{winter})$

filter out all the cases where $S$ is winter, then we sum over the rows of $W$ that are the same $W$ value.

$P(\text{sun} \mid \text{winter}) =$ #=: 0.25 / 0.5 ... $P(\text{rain} \mid \text{winter}) =$ #=: 0.25 / 0.5

this algo is really helpful

obvious problems - worst case time complexity $O(d^n)$ - space complexity $O(d^n)$ to store the joint distribution

Product rule

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

we can compute the probabilites of what we do know from what we dont know.

between two rv it's going to be the product behind the other conditional variable, we can rearrange the terms to get back to the function above.

we have our marginal distribution $P(W)$ and we have the joint distribution $P(D|W)$ and we want $P(D, W)$

we can multiply the corresponding rows to generate the new table.

the chain rule

can (almost) always write any joint distribution as an incremental product of conditional distributions

$P(x_1, x_2, x_3) = P(x_1)P(x_2|x_1)P(x_3|x_1,x_2)$ $P(x_1, x_2, \dots, x_n) = \prod_i P(x_i | x_1, x_2, \dots, x_{i-1})$

bayes rule

we can factor a joint distribution over two variables

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

dividing we can get

$P(x|y) = \frac{P(y|x)}{P(y)} P(x)$

why is this helpful?

lets build one conditional from its reverse

one setting where bayes rule is applied in the medical setting is good

most of the time it's applied incorrectly

$P(\text{cause} \mid \text{effect}) = \frac{P(e|c)P(c)}{P(e)}$

example $M$ = meningitis, $S$ = stiff neck

# Bayes: P(+m|+s) = P(+s|+m)P(+m) / P(+s)
p_m = 0.0001
p_s_given_m = 0.8
p_s_given_not_m = 1
# P(+s) = P(+s|+m)P(+m) + P(+s|-m)P(-m)
p_s = p_s_given_m * p_m + p_s_given_not_m * (1 - p_m)
(p_s_given_m * p_m) / p_s =>

$P(+m | +s) = 0.008$

$P(W)$

R	P
sun	0.8
rain	0.2

$P(D|W)$

D	W	P
wet	sun	0.1
dry	sun	0.9
wet	rain	0.7
dry	rain	0.3

want to calculate $P(W, \text{dry})$

Ghostbusters revisited

lets say we have two distros
prior distributions over ghost location