Probability

Today

Random Variables
Joint and Marginal Probabilities
Conditional Probabilities
Product Rule, Chain Rule, Bayes Rule
Inference
Independence

Inference in Ghostbusters

A ghost is in the grid somewhere
Sensor readings tell how close a square is to the ghost

On the ghost: red
1 or 2 away: orange
3 or 4 away: yellow
5+ away: green

Sensors are noisy, but we know

$P(color|distance)$

$pred(red\|3)$	$pred(orange\|3)$	$pred(yellow\|3)$	$pred(green\|3)$
0.05	0.15	0.50	0.30

Uncertainty

General situation:

Observed variables (evidence): Agent knows certain things about the state of the world (e.g., sensor readings or symptoms)
Unobserved variables: Agent needs to reason about other aspects (e.g. where an object is or what disease is present)
Model: Agent knows something about how the known variables relate to the unknown variables

Probabilistic reasoning gives us a framework for managing our beliefs and knowledge

0.11	0.11	0.11
0.11	0.11	0.11
0.11	0.11	0.11

0.17	0.10	0.10
0.09	0.17	0.10
0.01	0.09	0.17

0.01	0.01	0.03
0.01	0.05	0.05
0.01	0.05	0.81

Random Variables

A random variable is some aspect of the world about which we (may) have uncertainty

$R =$ Is it raining?
$T =$ Is it hot or cold?
$D =$ How long will it take to drive to work?
$L =$ Where is the ghost?

We denote random variables with capital letters
Like variables in a CSP, random variables have domains

$R \in \{false, true\}$ (often written as $\{-r, +r\}$ )
$T \in \{hot, cold\}$
$D \in [0, \infty)$
$L \in \mbox{ possible locations}$ , maybe $\{(0,0), (0,1), \dots\}$

Probability Distributions

Associate a probability with each value

Temperature

$P(T)$

$T$	$P$
hot	0.5
cold	0.5

Weather

$P(W)$

$W$	$P$
sun	0.6
rain	0.1
fog	0.3
meteor	0.0

Probability Distributions

Unobserved random variables have distributions
A distribution is a TABLE of probabilities of values
A probability (lower case value) is a single number $P(W=rain)=0.1$
Must have: $\forall x \mbox{ } P(X=x) \geq 0$ and $\sum_x P(X=x)=1$

Shorthand Notation:

$\begin{equation} \begin{aligned} P(hot) &= P(T=hot) \nonumber \\ P(cold) &= P(T=cold) \nonumber \\ P(rain) &= P(W=rain) \nonumber \\ \end{aligned} \end{equation}$ OK, if all domains entries are unique

Joint Distributions

A joint distribution over a set of random variables: $X_1,X_2,\dots,X_n$
Joint distribution specifies a real number for each assignment (or outcome): $\begin{equation} \begin{aligned} & P(X_1,\dots,X_n)\nonumber \\ & P(X_1=x_1,\dots,X_n=x_n)\nonumber \end{aligned} \end{equation}$

Must obey: $\begin{equation} \begin{aligned} & P(x_1,x_2,\dots,x_n) \geq 0 \nonumber \\ & \sum_{x_1,\dots,x_n} P(x_1,x_2,\dots,x_n) = 1 \nonumber \end{aligned} \end{equation}$

Size of distribution if n variables with domain sizes d?

For all but the smallest distributions, impractical to write out !!

$T$	$W$	$P$
hot	sun	0.4
hot	rain	0.1
cold	sun	0.2
cold	rain	0.3

Probabilistic Models

A probabilistic model is a joint distribution over a set of random variables

Probabilistic models:

(Random) variables with domains
Assignments are called outcomes
Joint distributions: say whether assignments (outcomes) are likely
Normalized: sum to 1.0
Ideally: only certain variables directly interact

Constraint satisfaction problems:

Variables with domains
Constraints: state whether assignments are possible
Ideally: only certain variables directly interact

$T$	$W$	$P$
hot	sun	0.4
hot	rain	0.1
cold	sun	0.2
cold	rain	0.3

$T$	$W$	$P$
hot	sun	T
hot	rain	F
cold	sun	F
cold	rain	T

Events

An event is a set E of outcomes:

$\begin{equation} P(E) = \sum_{(x_1,\dots,x_n)\in E} P(x_1,\dots,x_n) \nonumber \end{equation}$

From a joint distribution, we can calculate the probability of any event

Probability that it is hot AND sunny?
Probability that it is hot?
Probability that it is hot OR sunny?

Typically, the events we care about are partial assignments, like $P(T=hot)$

$T$	$W$	$P$
hot	sun	0.4
hot	rain	0.1
cold	sun	0.2
cold	rain	0.3

Quiz: Events

$P(+x, +y)$

$P(+x)$

$P(-y \mbox{ OR } +x)$

$X$	$Y$	$P$
+x	+y	0.4
+x	-y	0.1
-x	+y	0.2
-x	-y	0.3

Marginal Distributions

Marginal distributions are sub-tables which eliminate variables
Marginalization (summing out): Combine collapsed rows by adding

$T$	$W$	$P$
hot	sun	0.4
hot	rain	0.1
cold	sun	0.2
cold	rain	0.3

$T$	$P$
hot	0.5
cold	0.5

$W$	$P$
sun	0.6
rain	0.4

Quiz: Marginal Distributions

$X$	$Y$	$P$
+x	+y	0.2
+x	-y	0.3
-x	+y	0.4
-x	-y	0.1

$X$	$P$
+x
-x

$Y$	$P$
+y
-y

Conditional Distributions

A simple relation between joint and conditional probabilities

In fact, this is taken as the definition of a conditional probability

$\begin{equation} P(a|b) = \frac{P(a,b)}{P(b)} \nonumber \end{equation}$

$T$	$W$	$P$
hot	sun	0.4
hot	rain	0.1
cold	sun	0.2
cold	rain	0.3

$\begin{equation} P(W=s|T=c) = \frac{P(W=s,T=c)}{P(T=c)} = \frac{P(W=s,T=c)}{P(W=s,T=c)+P(W=r,T=c)} = \frac{0.2}{0.2+0.3} = 0.4 \nonumber \end{equation}$

Quiz: Conditional Distributions

$P(X,Y)$

$X$	$Y$	$P$
+x	+y	0.2
+x	-y	0.3
-x	+y	0.4
-x	-y	0.1

$P(+x|+y)$

$P(-x|+y)$

$P(-y|+x)$

Conditional Distributions

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

$P(W|T=hot)$

$W$	$P$
sun	0.8
rain	0.2

$P(W|T=cold)$

$W$	$P$
sun	0.4
rain	0.6

$T$	$W$	$P$
hot	sun	0.4
hot	rain	0.1
cold	sun	0.2
cold	rain	0.3

Normalization Tricks

$T$	$W$	$P$
hot	sun	0.4
hot	rain	0.1
cold	sun	0.2
cold	rain	0.3

$W$	$P$
sun	0.4
rain	0.6

Normalization Tricks

Why does this work?

Sum of selection is P(evidence)!
$P(T=c)$ in this case

In general: $\begin{equation} P(x_1|x_2) = \frac{P(x_1,x_2)}{P(x_2)} = \frac{P(x_1,x_2)}{\sum_{x_1}P(x_1,x_2)} \nonumber \end{equation}$

Quiz: Normalization Tricks

$P(X|Y=-y)$ ?

To Normalize

(Dictionary) To bring or restore to a normal condition
Procedure:

Step 1: Compute $Z =$ sum over all entries
Step 2: Divide every entry by $Z$

Probabilistic Inference

Probabilistic inference: compute a desired probability from other known probabilities (e.g. conditional from joint)

We generally compute conditional probabilities

$P(\mbox{on time}|\mbox{no reported accidents}) = 0.90$
These represent the agent's beliefs given the evidence

Probabilities change with new evidence:

$P(\mbox{on time}|\mbox{no accidents, 5 a.m.}) = 0.95$
$P(\mbox{on time}|\mbox{no accidents, 5 a.m., raining}) = 0.80$
Observing new evidence causes beliefs to be updated

Inference by Enumeration

Problem Setup:

General Case:

Evidence variables: $E_1,\dots,E_k=e_1,\dots,e_k$
Query variables: $Q$
Hidden variables: $H_1,\dots,H_r$

We want: $P(Q|e_1\dots,e_k)$

Solution:

Step 1: Select the entries consistent with the evidence
Step 2: Sum out $H$ to get joint of Query and evidence $\begin{equation}P(Q,e_1\dots,e_k)=\sum_{h_1,\dots,h_r}P(Q,h_1,\dots,h_r,e_1,\dots,e_k)\end{equation}$
Step 3: Normalize $Z = P(Q,e_1,\dots,e_r)$ $P(Q|e_1\dots,e_r) = \frac{1}{Z}P(Q,e_1,\dots,e_r)$

Inference by Enumeration

$P(W)$ ?

$P(W|winter)$ ?

$P(W|winter,hot)$ ?

summer	hot	sun	0.30
summer	hot	rain	0.05
summer	cold	sun	0.10
summer	cold	rain	0.05
winter	hot	sun	0.10
winter	hot	rain	0.05
winter	cold	sun	0.15
winter	cold	rain	0.20

Inference by Enumeration

Obvious problems:

Worst-case time complexity $\mathcal{O}(d^n)$
Space complexity $\mathcal{O}(d^n)$ to store the joint distribution

Product Rule

Sometimes we have conditional distributions but want the joint

$\begin{equation} \begin{aligned} P(y)P(x|y) &= P(x,y) \nonumber \\ \Rightarrow P(x|y) &= \frac{P(x,y)}{P(y)} \nonumber \\ \end{aligned} \end{equation}$

Product Rule

$\begin{equation} P(y)P(x|y) = P(x,y) \nonumber \end{equation}$

Example:

$W$	$P$
sun	0.8
rain	0.2

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

$D$	$W$	$P$
wet	sun
dry	sun
wet	rain
dry	rain

Chain Rule

More generally, can always write any joint distribution as an incremental product of conditional distributions

$\begin{equation} \begin{aligned} P(x_1,x_2,x_3) &= P(x_1)P(x_2|x_1)P(x_3|x_2,x_1) \nonumber \\ P(x_1,x_2,\dots,x_n) &= \prod_{i}P(x_i|x_1,\dots,x_n) \nonumber \end{aligned} \end{equation}$

This is always true. Why?

Bayes Rule

Two ways to factor a joint distribution over two variables:

$\begin{equation} P(x,y) = P(x|y)P(y) = P(y|x)P(x) \nonumber \end{equation}$

Dividing, we get: $\begin{equation} P(x|y) = \frac{P(y|x)P(x)}{P(y)} \nonumber \end{equation}$
Why is this at all helpful?

Lets us build one conditional from its reverse
Often one conditional is tricky but the other one is simple
Foundation of many systems we’ll see later.

In the running for most important AI equation.

Inference with Bayes Rule

Example: Diagnostic probability from causal probability:

$\begin{equation} P(cause|effect) = \frac{P(effect|cause)P(cause)}{P(effect)} \nonumber \end{equation}$

Example:

M: meningitis, S: stiff neck $\begin{equation} \begin{aligned} P(+m) &= 0.0001 \nonumber \\ P(+s|+m) &= 0.8 \nonumber \\ P(+s|-m) &= 0.01 \nonumber \\ \end{aligned} \end{equation}$

$\begin{equation} \begin{aligned} P(+m|+s) &= \frac{P(+s|+m)P(+m)}{P(+s)} \nonumber \\ &= \frac{P(+s|+m)P(+m)}{P(+s|+m)P(+m)+P(+s|-m)P(-m)} \nonumber \\ &= \frac{0.8\times 0.0001}{0.8\times 0.0001+0.01\times 0.9999} \nonumber \end{aligned} \end{equation}$

Note: posterior probability of meningitis still very small
Note: you should still get stiff necks checked out !! Why?

Quiz: Bayes Rule

Given:

$R$	$P$
sun	0.8
rain	0.2

What is $P(W|dry)$ ?

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

Ghostbusters Revisited

Let us say we have two distributions:

Prior distribution over ghost location: $P(G)$

Let us say this is uniform

Sensor reading model: $P(R|G)$

Given: we know what our sensors do
$R =$ reading color measured at $(1,1)$
e.g. $P(R=yellow|G=(1,1)) = 0.1$

We can calculate the posterior distribution $P(G|r)$ over ghost locations given a reading using Bayes' rule: $\begin{equation} P(g|r) \propto P(r|g)P(g) \nonumber \end{equation}$