Scribd
Upload
5 views18 pages

Advanced Machine Learning Notes

A Bayesian network (BN) is a directed acyclic graph that represents random variables and their dependencies, allowing for simplification of conditional probabilities. It can model real-life problems more effectively than Naive Bayes by capturing complex interdependencies among variables. However, BNs have limitations in representing certain independence assumptions, particularly in cases of bidirectional relationships.

Uploaded by

HK
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views18 pages

Advanced Machine Learning Notes

A Bayesian network (BN) is a directed acyclic graph that represents random variables and their dependencies, allowing for simplification of conditional probabilities. It can model real-life problems more effectively than Naive Bayes by capturing complex interdependencies among variables. However, BNs have limitations in representing certain independence assumptions, particularly in cases of bidirectional relationships.

Uploaded by

HK
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Bayesian network (BN)

A Bayesian network represents random variables and their


dependencies using a directed acyclic graph (DAG). DAG is a
directed graph with no directed cycles. Variables can be positively
dependent, negatively dependent or unrelated. For example, if it
rains, it has a smaller chance in turning the automatic sprinkler on.
In the morning, if the grass is wet, it is because it has rained or the
automatic sprinkler is on.

Bayesian network

In the model above, we consider the wet grass in the morning is


independent on the chance of rain or the chance of turning the
automatic sprinkler on. In a Bayesian network, we join variables
with a directed link in demonstrating dependency.

Let’s start with the joint probability and expand it using the chain
rule.

With the Bayesian network (BN), we can simplify the conditional


probability further. For example, P(S|R, W) becomes P(S|R)
because S is not dependent on W. The general form of the
conditional probability at each node becomes:

Now, we can simplify the data collection by just collecting the


relevant data for each conditional probabilities.

\
let’s make some predictions. The conditional probability P(R|W) for
rain given the grass is wet can be calculated by Bayes’ Theorem
followed by the corresponding marginal probabilities.

Modified from source

The joint probability in the R.H.S. will be expanded with the


conditional probabilities defined in the GM and solved with variable
elimination or some approximation methods that will be discussed
in later articles.

Modified from source

Here are another BN and the joint probability.


According to the graph, the joint probability p can be factorized as

For example, the joint distribution of this example is factorized as

Comparing with Naive Bayes Theorem, we can use a more generic


BN to model some real-life problems better. For example, given
different diseases, a BN can have overlapping findings from many
diseases.
Generative network

BN can be treated as a generative model — a model that can


generate samples. For example, starting from the top parent nodes,
we can sample and generate data according to the conditional
probabilities.

This is the same principle that GAN (Generative Adversary


Network) generates the raw image by first random sampling a latent
variable.
Recap

A BN is a graph with each node represents a variable with one


conditional probability p(x | x_parent) attached — the probability
of x given its parents. We can then factorize the joint probability
according to this GM.
Independence

3 + 4 equals 5 + 2. So even the formulae are different, they are


identical. Given two graphs, they can model the same problem even
they look different. When p is factorized according to the
dependency in the Bayesian network G), we say p factorizes
over G. But G is not necessarily the simplest model for our domain
problem. We may miss some possible independence. However, we
just make the model more complex but the solution remains sound.

Therefore, we can use the independence in determining whether


two graphical models will produce the same result. Let’s
conceptualize the idea of independent a little bit more.
If variables X and Y are independent (X ⊥ Y), then p(X, Y)
= p(X) p(Y). First, let’s introduce the following notation in
representing such independence.

If two variables A and B are independent, knowing A does not


give us any information on B or vice versa.

For the first diagram above, if we know A, then the probability


distribution for B and C will be known and not dependent on any
variable. Therefore, B & C are independent of each other
given A (B ⊥ C | A ∈ I(p)).
We can prove it with the joint distribution probability derived from
the graph.

But if A is unknown, knowing B can give us information


on C through A. Therefore,

The graph above represents a common cause relation. We can argue


such independence in an easier way without math. If the common
cause is known, all its effect will be known without further
information and therefore, they are not dependent on each other.
If A is unknown, since all effects are linked to a common cause,
therefore, all effects are related and therefore not independent.

Let’s consider the second case (v-structure).

B links to C if value A is known. For example, a pedestrian is hurt


(event A) if either the car or the pedestrian runs a red light. By
knowing a pedestrian is hurt, we know the pedestrian is following
the rule if we know the car runs a red light. Therefore B and C are
not independent given A. But if A is unknown, knowing B gives us
no information on C. This graph represents the common effect. If
we don’t know the effect, we know nothing about the possible
causes and they will be independent. But if we know the
effect, B and C will be dependent.
A path in a graph is active if it carries information. In the third case
below (Cascade), if we know A, then C is independent of B. We don’t
need B to figure out C anymore.

Knowing B gives us no extra information on C and therefore, the


path is inactive. But if A is unknown, the path is
active. B and C are d-separated (dependency separated or
directional separated) if all the paths that connect them are inactive.
So depending on what has been observed, we can check whether
two variables are d-separated. This will be much easier in finding
independence without complex math. In fact, the analysis can be
done by dividing the graph into subgraphs with one of the three
structures below.
For example, L is independent of {I, D, S} given G.

To evaluate whether a path is active, we can apply the following


cheat sheet. In checking whether two variables are d-separated, we
determine whether all possible paths between them is blocked. The
cheat sheet below indicates whether a path is blocked under three
different structures. So we can use that to analyze whether there is
an active path between two nodes. In the cheat sheet, the shaded
node represents the variable is observed.

Here is another analysis regarding variable D when C is


observed. D and A are d-separated if C is observed. On the other
hand, all red nodes have an active path with D if C is observed, i.e.
they are not d-separated. (The graph is analyzed by this software.)
This visual analysis allows us to discover conditional dependency
easily without probability theory. As shown later, it can be nasty for
even simple cases. It seems that we spend an awful amount of time
in studying independence. But such analysis is important. Given
some known observations O, we can further prune the graph and
simplify the model significantly to answer the query efficiently. For
example, if C is observed in the graph above, we can drop the blue
nodes for any query on the red nodes.

I-map (independence map)

Conditional independencies allow us to compare BN. Let I(G) be all


conditional independencies implied by the DAG G, and I(p) be all
conditional independencies hold for the joint distribution p. G is
an I-map of a distribution p if I(G) ⊆ I(p). G is a minimal I-map
for p if the removal of a single edge makes it not an I-map. If I(G)
= I(p), G is a perfect map. Finding a perfect map may not be easy,
but we want at least I(G) ⊆ I(p).

In short, if I(G) is an I-map for p, I(p) contains all the


independencies of I(G), i.e. all the independencies in I(G) will not
violate the rules in I(p). So the way we factorize p over G will be
sound. But G is not necessarily the simplest. We may not discover
all the independence. It may be more complex than it could be.

I-map is not unique. I(p) can have many I-map. For a fully
connected graph G (every node is connected to each other), its
independence set will be empty. Therefore, a fully connected G is
always an I-map for any distribution p since I(G) = ∅ ⊆ I(p).

Without proof here, let’s make a few claims.

 Finding a perfect map is not always possible in BN.

 A perfect map may not be unique.

 Two graphics have the same skeleton if they are the same if we
ignore the arrow in the dependency.

To be perfect maps, G and G′ should have the same skeleton and the
same v-structures.
Both BNs below have the same skeleton and v-structure and
therefore the same.

BN examples

Let’s see more BN examples. We can use BN to relate diseases d and


lab findings f. However, the conditional probability p(fᵢ|dⱼ) may
remain too complex because many findings can be caused by many
different diseases. We can simplify the joint probability further
using a noisy-or parameterization below.
Modified from source

Here are the BN examples on the Hidden Markov Model and the
Gaussian Mixture model.

Limitations on BN
BN is a directed acyclic graph. The directed nature of the edge and
the non-acyclic graph behavior make it impossible to model some
independence assumptions together. Some independent
assumptions cannot co-exist in a BN. For example, both BNs below
can fulfill A ⊥ C | {B, D} but not B ⊥ D | {A, C}. If we want both
independence together, it is not easy.

This often happens when the relationship between two variables is


bi-directional. For example, friends may vote similarly. The
influence is bidirectional (not directed). One solution is to introduce
additional variables to the graph but that will increase the
complexity of the model.

Modified from source


Next, we will study another type of graph that can model some
independence that is not possible for BN. Nevertheless, both graphs
will have different types of independence that they cannot
represent. It is provided as an alternative rather than a guarantee
that it works better.

You might also like