# CS代写 Inference by enumeration – cscodehelp代写

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