Okay, back to the topic at hand.

First things first, if I sound a bit weird today, that's not because I'm sick or anything.

So I'm not infectious.

You can talk to me.

I was just stupid enough to spend the last two days in a recording studio doing backing

vocals which involves lots of shouting and now my vocal cords are fried.

I will get through this somehow, but I'm going to sound a bit different.

So last time we talked about inference in Bayesian networks mostly.

The naive way of doing this is pretty clear.

We have our standard formula for enumeration which is basically just normalizing the marginalization

over our unknown variables and plugging in our query variables and our evidence.

We know how to compute the full joint probability distribution in Bayesian networks basically

by just multiplying all of the conditional probability tables for the relevant entries

and then we plug things in.

In the general worst case that will give you a complexity of something like n times

2 to the n which is not exactly ideal.

We can optimize things relatively easily by just noticing that there's lots of variables

which we don't need in the first place potentially and then we end up with this algorithm which

literally just takes the formula we have for inference by enumeration and steps through

it step by step.

That gives us a complexity as mentioned earlier of something like n times 2 to the n which

is not exactly ideal.

One way to improve things is by noticing that what we do in this algorithm is basically

just traverse an arithmetic expression tree in a depth first manner and doing that depth

first is not exactly ideal because in that case we end up basically computing the same

things over and over again and the natural way to improve things therefore is to basically

just trade time complexity by space complexity by hashing intermediate values.

That is a process called variable elimination where instead of basically doing this whole

expression from left to right and recursively and then just summing up things every time

I have to do marginalization instead we take the same order of random variables that we

already have and instead do it from right to left and every time we compute any kind

of expression we introduce a factor for that.

That factor has certain dependencies i.e. the variables that are not yet necessarily

known with respect to their value at that particular point and then we just store those

somewhere for retrieval in the future when we need it.

We went over one example how that works and noticeably if you have a big network then

that can speed things up massively.

In some cases it's known to happen that it's sped up certain inference tasks by a factor

of over a thousand.

In general if we have the kind of Bayesian network where it happens to be the case that

between any two variables you only ever have one directed path anyway we call that a poetry

and for poetry doing variable elimination turns out to yield an algorithm that runs

in polynomial time which is basically the best thing we can hope for for these kinds

of tasks anyway.

The bad news is that in the worst case if we don't have a poetry we end up with something

that is even harder than NP which is basically the worst case you can hope for.

So in that case usually what you do is you just throw exactitude out the window in the

first place and instead of trying to compute the exact probabilities of various events

you do things like Monte Carlo tree search and just estimate as good as you can.

So much about that and as mentioned Bayesian networks are pretty much the most general