We use probabilistic graphical models to model some probability distribution 𝐏. This section introduces ways to compare the probability independencies induced by the graphical model and the modeled probability distribution. Or even between 2 different probabilistic graphical models.

Terminology for Comparing Independencies

• model 𝐴 is a(n) (I-Map | D-Map | P-Map | Minimal I-Map | Maximal D-Map) of model 𝐵

we use the statement above to explain the terms below:

In most models:

• the REMOVAL of edges typically INCREASES the number of independencies
• the ADDITION of edges typically REDUCES the number of independencies

Formal Definitions

Click here to expand...

Term	Description
Independence Map (I-Map)	if a graphical model 𝐆 is an I-Map of distribution 𝐏, then every independence (conditional and marginal) in 𝐆 also exists in 𝐏 (denoted as 𝐈(𝐆) ⊆ 𝐈(𝐏)) a fully connected DAG 𝐆 is an I-Map for any distribution 𝐏, since 𝐈(𝐆) = ∅ ⊆ 𝐈(𝐏) for all 𝐏
Dependence Map (D-Map)	if a graphical model 𝐆 is a D-Map of distribution 𝐏, then every independence (conditional and marginal) in 𝐏 also exists in 𝐆 (denoted as 𝐈(𝐏) ⊆ 𝐈(𝐆)) an unconnected DAG 𝐆 is a D-Map for any distribution 𝐏, since 𝐈(𝐏) ⊆ 𝕌 = 𝐈(𝐆) for all 𝐏
Minimal I-Map	graphical model 𝐆 is a Minimal I-Map for 𝐏 if the removal of any single edge makes it not an I-Map a distribution 𝐏 may have several Minimal I-Maps, each corresponding to a specific node-ordering
Maximal D-Map	graphical model 𝐆 is a Maximal D-Map for 𝐏 if an addition of any single edge makes it not a D-Map
Perfect Map (P-Map)	graphical model 𝐆 is a P-Map for distribution 𝐏 if 𝐈(𝐆) = 𝐈(𝐏) in other words: if 𝐆 is a P-Map, then 𝐆 is also an I-Map and D-Map if 𝐆 is both an I-Map and a D-Map, then 𝐆 is also a P-Map
Independence Equivalence (I-Equivalence)	two graphical models 𝐆𝟏 and 𝐆𝟐 are I-Equivalent if 𝐈(𝐆𝟏) = 𝐈(𝐆𝟐)

Examples

Click here to expand...

suppose, we are given 2 distributions: 𝐏𝟏 and 𝐏𝟐

• distribution 𝐏𝟏 has independence, 𝐈(𝐏𝟏) = {(𝐼⊥𝐷)}
• distribution 𝐏𝟐 has no independence, 𝐈(𝐏𝟐) = {∅}

suppose, we are given 2 graphical models (DAGs in this case): 𝐆_𝑎 and 𝐆_𝑏

from the DAGs, we can observe:

• 𝐆_𝑎- 𝐈(𝐆_𝑎) = {(𝐼⊥𝐷)}
• 𝐆_𝑏 - 𝐈(𝐆_𝑏) = {∅}

therefore, we can say the following:

• 𝐆_𝑎 is an I-Map of 𝐏𝟏 because 𝐼 and 𝐷 are independent in both 𝐆_𝑎 and 𝐏𝟏

• 𝐆_𝑎 is not the I-Map of 𝐏𝟐 because 𝐏𝟐 fails to satisfy the independence between I and D

• 𝐆_𝑎 is a P-Map of 𝐏𝟏 because 𝐈(𝐆_𝑎) = 𝐈(𝐏𝟏)

• 𝐆_𝑎 is not a P-Map of 𝐏𝟐 because 𝐈(𝐆_𝑎) ≠ 𝐈(𝐏𝟐)

• 𝐆_𝑏 is an I-Map of both 𝐏𝟏 and 𝐏𝟐 because the independence in 𝐆_𝑏 is ∅. Since ∅ is a subset of every set, both 𝐏𝟏 and 𝐏𝟐 satisfy the independence implied in 𝐆_𝑏

• 𝐆_𝑏 is not a P-Map of 𝐏𝟏 because 𝐈(𝐆_𝑏) ≠ 𝐈(𝐏𝟏)

• 𝐆_𝑏 is a P-Map of 𝐏𝟐 because 𝐈(𝐆_𝑏) = 𝐈(𝐏𝟐)

• 𝐆_𝑎 and 𝐆_𝑏 are not I-Equivalent because their set independencies are not equivalent (i.e. 𝐆_𝑎‘s independencies {(𝐼⊥𝐷)} does not equal 𝐆_𝑏‘s independencies {∅})

Relation to Gibbs Distribution

Click here to expand...

Graphical Models

a probability distribution 𝐏(𝐗) is a Gibbs Distribution over a graphical model 𝐆 if it can be written as

• 𝐏(𝐗) = (1/𝘡) * ∏_𝑐∊𝐶 [ 𝜙_𝑐(𝐗_𝑐) ]

where the variables in each potential function 𝜙_𝑐form a clique in 𝐆

Theorem 1: Factorization Implies Conditional Independencies

If 𝐏(𝐗) is a Gibbs Distribution for 𝐆, then 𝐆 is an I-Map for probability distribution 𝐏(𝐗), i.e. 𝐈(𝐆) ⊆ 𝐈(𝐏)

proof:

suppose:

• A, B, and C are disjoint sets of variables
• A is connected to B
• C is connected to B
• B separates A from C

then we can write

𝐏(A, B, C) = (1/𝘡) * 𝜙_𝑐1(A,B) * 𝜙_𝑐2(B,C)

Theorem 2: Conditional Independencies Implies Factorization

If 𝐏(𝐗) is a positive distribution and 𝐆 is an I-Map for 𝐏(𝐗), then 𝐏(𝐗) is a Gibbs Distribution that factorizes over graphical model 𝐆