Inference by enumeration
We saw that with our joint distribution table
we can calculate any probability Obvious problems:
1. Worst-casetimecomplexityOpdnqwheredisthelargestarity 2. SpacecomplexityOpdnqtostorethejointdistribution
3. HowtofindthenumbersforOpdnqentries???
These problems effectively stopped the use of probability in AI until the mid 80s
⃝c -Trenn, King’s College London 2
Computational efficiency
To get efficient probabilistic computations, we need two things. 1. (Conditional)independence.
2. Bayesrule.
Will cover these now, in order.
⃝c -Trenn, King’s College London 3
Independence
A and B are independent iff
PpA, Bq “ Can help with the size of the problem.
PpAqPpBq
Why is this interesting?
⃝c -Trenn, King’s College London
4
Independence
PpT oothache, Catch, Cavity, W eatherq
“ PpT oothache, Catch, Cavityq d PpW eatherq
If you store all values naively, this requires 2 ̈ 2 ̈ 2 ̈ 4 “ 32 entries.
You can do it in 31 by leaving one entry empty. This is possible since you know
that the probabilities add up to 1.
Using the independence, you can even reduce the 31 values to 10:
⃝c -Trenn, King’s College London 5
Independence
PpT oothache, Catch, Cavity, W eatherq
“ PpT oothache, Catch, Cavityq d PpW eatherq
If you store all values naively, this requires 2 ̈ 2 ̈ 2 ̈ 4 “ 32 entries.
You can do it in 31 by leaving one entry empty. This is possible since you know
that the probabilities add up to 1.
Using the independence, you can even reduce the 31 values to 10:
You store 7 for the 3 dependent variables and 3 for weather which is independent (note that we’re using the probabilities adding up to 1 trick twice here)
For n independent biased coins, 2n Ñ n
⃝c -Trenn, King’s College London 6
Independence
Absolute independence powerful but rare
Dentistry is a large field with hundreds of variables, none of which are independent. What to do?
Conditional independence
⃝c -Trenn, King’s College London 7
Conditional independence
PpT oothache, Cavity, Catchq has:
Three binary variables.
Thus 23 entries in the joint probability table. But these sum to 1.
So 23 ́ 1 independent entries
That’s 7 independent entries
⃝c -Trenn, King’s College London 8
Conditional independence
But, wait! There’s more!
If I have a cavity, the probability that the probe catches in it doesn’t depend on whether I have a toothache:
P pcatch|toothache, cavityq “ P pcatch|cavityq (1) The same independence holds if I haven’t got a cavity:
P pcatch|toothache, ␣cavityq “ P pcatch|␣cavityq (2) Catch is conditionally independent of Toothache given Cavity
We write
PpCatch|T oothache, Cavityq “ PpCatch|Cavityq Catch K T oothache|Cavity
⃝c -Trenn, King’s College London
9
Conditional independence
Equivalent statements:
PpT oothache|Catch, Cavityq “ PpT oothache, Catch|Cavityq “
PpT oothache|Cavityq
PpT oothache|Cavityq d PpCatch|Cavityq
⃝c -Trenn, King’s College London
10
Conditional independence
Write out full joint distribution using chain rule:
PpT oothache, Catch, Cavityq
“ PpT oothache|Catch, Cavityq d PpCatch, Cavityq
“ PpT oothache|Catch, Cavityq d PpCatch|CavityqPpCavityq “ PpT oothache|Cavityq d PpCatch|Cavityq d PpCavityq
2 + 2 + 1 = 5 independent numbers Equations 1 and 2 remove 2.
⃝c -Trenn, King’s College London 11
Conditional independence
In most cases, the use of conditional independence reduces the size of the representation of the joint distribution from exponential in n to (close to) linear in n.
Conditional independence is our most basic and robust form of knowledge about uncertain environments.
Can often make conditional independence statements when little else is known.
⃝c -Trenn, King’s College London 12