Hi, in this module, I'm going to talk about Bayesian networks,
a new modeling paradigm.
So we have talked about two types of variable based models.
The first was constraint satisfaction problems,
where the objective is to find the maximum weight assignment,
given a factor graph.
Then we talked about Markov networks,
where we used factor graphs to define a joint probability
distribution over assignments.
And we were computing marginal probabilities.
Now I'm going to talk about Bayesian networks, where
we still define a distribution over a set of random variables
using a factor graph.
But now the factors are going to have special meaning.
So Bayesian networks were developed
by Judea Pearl in the mid 1980s, and really have
evolved into the more general notion of generative modeling
that we see today in machine learning.
So quickly, before diving into Bayesian networks,
it's helpful to compare and contrast with Markov networks.
So both are going to define a probability
distribution over assignments to a set of random variables.
But the way that each approaches this is very different.
So if you're defining a Markov network,
you tend to think in terms of specifying
a set of preferences.
And you throw these factors, encoding these preferences
into the Markov network.
So for example, the last time we just threw
in the transition factor and observation factor
for the object tracking example.
So the Bayesian network is going to require
a more coordinated approach.
So in a Bayesian network, the factors
are going to be local conditional distributions,
as we'll see later.
And we really think about a generative process
by which each of these variables is set, based
on other variables, in turn.
So there are many applications of Bayesian networks,
and more generally, generative models.
So I'll just go through a couple of them here.
So the first one is topic modeling,
where the goal is to discover hidden structure
in a large collection of documents.
So an example of topic modeling is Latent Dirichlet Allocation
or LDA.
And the LDA posits that each document
is generated by drawing a mixture of topics
and then generating the words, given those topics.
Another interesting example is this idea
of vision as inverse graphics.
So, much of computer vision today
is taking images and processing them
in some way to generate semantic descriptions, such as object
categories or scene descriptions.
So vision as inverse graphics takes a very different
approach, where we specify, using
laws of physics, a graphics engine
that can generate an image, given
some semantic description-- for example,
a 3D model of an object.
And then, given this model, computer vision
is just inverse graphics, where we're
trying to recover the semantic description using
the image as input.
So this is an example of inference
on this generative model.
So while this idea hasn't really been
able to be scaled past some limited examples,
it's, I think, a very tantalizing idea, nonetheless.
So switching gears a little bit, let's talk
about communication networks.
So in the communication networks,
nodes must send messages, just a sequence of bits to each other.
But these bits can get corrupted along the way, due to physics.
So the idea behind error correcting codes--
in particular, these things called low density parity
codes--
is that the sender sends random parity checks on the data bits.
And then the receiver obtains a noisy version
of both the data and the parity bits.
The Bayesian network defines how the original bits
are related to the noisy bits.
And then the receiver can use Bayesian inference to compute
and recover the original bits.
So this is actually a very effective idea
that's used in practice.
The final example is either controversial or a little bit
grim, which I'll explain later.
So this is the problem of DNA matching.
So there are two use cases of this, one is in forensics.
So, given the DNA found at a crime site,
even if the suspect's DNA is not in the database,
one can still match this DNA against the family members
of a subject.
And here, the Bayesian network is structured along the family
tree and specifies a relationship
between the family member's DNA, using a Mendelian inheritance.
So now, while this technology has actually
been used to solve a number of crime cases,
there's definitely a lot of tricky ethical concerns
about this expanded DNA matching, especially when
an individual's decision to release their own DNA
can impact the privacy of family members.
The second use case is in disaster victim identification.
So after a big airplane crash or some other disaster.
For example, Malaysia Airlines crashed in Ukraine in 2014.
And victims' DNA is found at the crash site
and is matched against the family members,
using the same mechanism as I just described,
to help identify our victims.
And these methods are very scalable,
which allows them to deal with these unfortunate large crash
sites.
So why Bayesian networks?
Well, these days, it's kind of hard
not to think about problems exclusively through the lens
of standard supervised learning, such as, just
train a deep neural network on a pile of data.
Bayesian networks really operate in a very different paradigm,
which offers several advantages that I want to underscore here.
So the first is that it can handle heterogeneously missing
information.
So normally, when you're doing standard supervised learning,
your data is fairly homogeneous.
You have training input and output pairs,
both at training and test time.
But in cases where you have missing information, where
you have auxiliary information, Bayesian networks
can gracefully handle this messiness
in a way that's a little bit more
challenging for traditional supervised methods.
The second is that Bayesian networks
allow you to incorporate prior knowledge much more easily.
So when you have it, for example,
you understand how Mendelian inheritance works on DNA.
Or you understand the laws of physics,
that Bayesian networks provides a nice language
for incorporating this information into your model.
And now, using this model, you can actually
learn from very few samples and extrapolate beyond the training
distribution.
Whereas in contrast, many kind of model,
agnostic, low inductive bias methods,
such as deep neural networks, require much more data
to be effective.
Because you're specifying prior knowledge,
you can also interpret the variables inside the Bayesian
networks.
And this could be useful for understanding why a model is
making a certain decision.
And you can introspect and ask questions
about any of the intermediate variables.
And this just follows from the laws of probability.
Finally, Bayesian networks are an important precursor
to causal models.
So these are beyond the scope of this course.
But they are extremely important, especially
these days.
They allow you to answer questions about interventions.
For example, what would happen if we
give this drug to this patient?
When the counterfactual is, what would have happened
if we have given this drug?
So these questions are extremely tricky and deep,
that standard machine learning, or any methods that
view the world through just the lens of predictions,
are really inadequate to answer.
So we're not going to talk about in this course.
But I highly encourage you to explore this topic on your own.
So finally, Bayesian networks, obviously,
aren't the panacea in many situations.
So often, in these canonical AI applications,
such as vision, speech, and language,
we actually have large data sets.
And we mostly care about prediction.
And it's extremely hard to incorporate prior knowledge
into your models in these very complex domains.
So in these cases, Bayesian networks
haven't been as successful and have largely
been supplanted by deep learning approaches.
But still, having Bayesian networks in your toolkit
will allow you to use it effectively when
you discover the right problem.
So in the remaining modules on Bayesian networks,
I will first introduce Bayesian networks more formally.
And then I'll talk about probabilistic programming,
which is a way to define Bayesian networks using
probabilistic programs.
So this is a really cool way to think about modeling.
Then we'll turn to inference.
I'll talk about what inference means,
computing conditional and marginal probabilities.
We're actually going to reduce the problem
in Bayesian networks to the same problem
of a bit probabilistic inference in Markov networks,
allowing to leverage the stuff that we talked about,
where we talked about Markov networks.
Then we're going to specialize to hidden Markov models, HMMs,
an important special case of Bayesian networks.
We're going to show that the forward backward algorithm can
leverage the chain structure of an HMM,
allowing you to do exact probabilistic inference
efficiently.
Then we're going to talk about particle filtering, which
allows you to do approximate inference and scale up
to HMMs, where variables have larger domains.
Finally, we're going to talk about learning
in Bayesian networks.
We're just going to start with supervised learning, where
all the variables are observed.
And this actually turns out to be quite easy.
You'll be pleasantly surprised.
Then we're going to show you how to guard against overfitting,
using a Laplace smoothing.
And finally, we're going to turn to cases where not all
the variables are observed.
And we introduce the EM algorithm
that will help us learn in such Bayesian elements.
OK, so let's jump in.