Introduction to Machine

Learning

Introduction to Machine Learning Amo G. Tong 1

Lecture 15
Graphical Models

• Introduction
• Representation

• Some materials are courtesy of Vibhave Gogate, Eric Xing and Bishop.
• All pictures belong to their creators.

Introduction to Machine Learning Amo G. Tong 2

A Joint Distribution
• Machine learning: studying a set of random variables {𝑣1 , … , 𝑣𝑛 }.
• They can be input data, parameters or target value.
• The joint distribution over {𝑣1 , … , 𝑣𝑛 }.

Introduction to Machine Learning Amo G. Tong 3

A Joint Distribution
• Machine learning: studying a set of random variables {𝑣1 , … , 𝑣𝑛 }.
• They can be input data, parameters or target value.
• The joint distribution over {𝑣1 , … , 𝑣𝑛 }.

• Regression with 𝑛 features: 𝑓 𝑥1 , … , 𝑥𝑛 = 𝑦, 𝑦 ∈ 𝑅

• Classification with 𝑛 features: 𝑓 𝑥1 , … , 𝑥𝑛 = 𝑦, 𝑦 ∈ {0,1}
• Pr[𝑦|𝑥1 , … , 𝑥𝑛 ]

• Tasks: learn the parameters or infer the probabilities

Introduction to Machine Learning Amo G. Tong 4

Why Graphical Models?
• If you are interested in a joint distribution,
𝑥 𝑦 𝑧 Pr
• Choice one: full joint distribution (table) 0 1 1 0.15
• 𝑥 ∈ 0,1 , 𝑦 ∈ 0,1 , 𝑧 ∈ {0,1} 0 0 1 0.08
• Assign each combination a probability (sum=1) 1 0 1 0.05
1 1 1 0.11
0 1 0 0.20
0 0 0 0.06
1 0 0 0.20
1 1 0 0.15

Introduction to Machine Learning Amo G. Tong 5

Why Graphical Models?
• If you are interested in a joint distribution,
𝑥 𝑦 𝑧 Pr
• Choice one: full joint distribution (table) 0 1 1 0.15
• 𝑥 ∈ 0,1 , 𝑦 ∈ 0,1 , 𝑧 ∈ {0,1} 0 0 1 0.08
• Assign each combination a probability (sum=1) 1 0 1 0.05
• (Good) We can infer everything regarding the task. 1 1 1 0.11
• E.g.
0 1 0 0.20
• Pr[𝑥 = 0] = 0.15 + 0.08 + 0.2 + 0.06
0 0 0 0.06

Test 1 1 0 0 0.20
1 1 0 0.15
Pr 𝑥 = 0 𝑧 = 1 =?

Introduction to Machine Learning Amo G. Tong 6

Why Graphical Models?
• If you are interested in a joint distribution,
𝑥 𝑦 𝑧 Pr
• Choice one: full joint distribution (table) 0 1 1 0.15
• 𝑥 ∈ 0,1 , 𝑦 ∈ 0,1 , 𝑧 ∈ {0,1} 0 0 1 0.08
• Assign each combination a probability (sum=1) 1 0 1 0.05
• (Good) We can infer everything regarding the task. 1 1 1 0.11
• (Bad) Sometimes we do not need every entry. 0 1 0 0.20
• (Bad) The table cannot show any information besides 0 0 0 0.06
the probabilities. E.g. structures, prior knowledge
1 0 0 0.20
1 1 0 0.15

• Choice two: (probabilistic) graphical models

Introduction to Machine Learning Amo G. Tong 7

Graphical Models
The graphical models:

• Provide a simple and systematic way to visualize the

structure of the variables.

• Provide insights, such as conditional independence, by the

shape of the graphs.

• Complex learning or inference can be done via graphical

manipulations.

• Customized to different special models, e.g., Bayesian

network, Markov models, …

Introduction to Machine Learning Amo G. Tong 8

Graphical Models
• Nodes: a random variable or a group of variables
• Edges: the relationship between the variables.

• Directed edges give causality relationships (Bayesian

Network or Directed Graphical Model):

• Undirected edges simply give (physical or symmetric)

correlations between variables (Markov Random Field or
Undirected Graphical model)
𝑎 𝑏

𝑑
𝑐

Introduction to Machine Learning Amo G. Tong 9

Bayesian Network (Notes)
• One of the most important recent advancements in machine learning in the recent 30
years.
• Judea Pearl: Turing award 2011 for this contributions to Bayesian network

• Generalizes simple Bayesian methods such Naïve Bayes and logistic regression.

• Represent exponential terms in a compact way.

• Explores the conditional probability.

Introduction to Machine Learning Amo G. Tong 10

Outline
• Representation
• Conditional independence

Introduction to Machine Learning Amo G. Tong 11

Probability Theory The whole probability theory is built on
these two simple questions, with some
• Rules for joint distribution.
math operations (summation and
integrations, …).
• Product rule
The main part of probabilistic (statistical)
Pr[𝑥, 𝑦] = Pr 𝑦 Pr[𝑥|𝑦]
machine learning is to repeatedly use these
• Sum rule two equations in a smart way.
Pr 𝑥 = ෍ Pr[𝑥, 𝑦] = ෍ Pr 𝑥 𝑦 Pr[𝑦]
𝑦 𝑦
Relates the information regarding Pr[𝑥, 𝑦] to Pr[𝑥]
• Marginal independence:
Pr[𝑥|𝑦] = Pr[𝑥]
• Conditional independence:
Pr[𝑥, 𝑦|𝑧] = Pr[𝑥|𝑧] Pr[𝑦|𝑧]

Introduction to Machine Learning Amo G. Tong 12

Graph Terminology
• DAG: directed acyclic graph 𝑎
𝑐
𝑏
𝑎 𝑏
• Parent: 𝑑
𝑐

• Child:
𝑒

• Descendants: the descendants of 𝑠 are the nodes 𝑡 where there is a directed

path from 𝑠 to 𝑡.

Introduction to Machine Learning Amo G. Tong 13

Representation

Representation

𝑦 = 𝑎𝑥 + 𝑏 Conjunction of constraints.
Graph Model?

Introduction to Machine Learning Amo G. Tong 14

Representation: Distribution to Graph
• Nodes: a random variable or a group of variables
• Edges: the relationship between the variables.

• A full joint distribution can be decomposed into a chain.

• Pr[𝑎, 𝑏, 𝑐] = Pr[𝑐|𝑎, 𝑏]Pr[𝑎, 𝑏] = Pr[𝑐|𝑎, 𝑏]Pr[𝑎|𝑏]Pr[𝑏]
• (General form) Pr 𝑣1 , … , 𝑣𝑛 = Pr 𝑣1 𝑣2 , … , 𝑣𝑛 … Pr 𝑣𝑛−1 𝑣𝑛 Pr[𝑣𝑛 ]

Introduction to Machine Learning Amo G. Tong 15

Representation: Distribution to Graph
• Nodes: a random variable or a group of variables
• Edges: the relationship between the variables.

• A full joint distribution can be decomposed into a chain.

• Pr[𝑎, 𝑏, 𝑐] = Pr[𝑐|𝑎, 𝑏]Pr[𝑎, 𝑏] = Pr[𝑐|𝑎, 𝑏]Pr[𝑎|𝑏]Pr[𝑏]
• (General form) Pr 𝑣1 , … , 𝑣𝑛 = Pr 𝑣1 𝑣2 , … , 𝑣𝑛 … Pr 𝑣𝑛−1 𝑣𝑛 Pr[𝑣𝑛 ]
• The decomposition is not unique.
• Pr 𝑎, 𝑏, 𝑐 = Pr 𝑐 𝑎, 𝑏 Pr 𝑎 𝑏 Pr 𝑏 = Pr 𝑏 𝑎, 𝑐 Pr 𝑎 𝑐 Pr 𝑐

Cause and effect:

𝑎: call 911, 𝑏: alarm, 𝑐: burglary
Which order you want to use?

Introduction to Machine Learning Amo G. Tong 16

Representation: Distribution to Graph
• Nodes: a random variable or a group of variables
• Edges: the relationship between the variables.

• A full joint distribution can be decomposed into a chain.

• Pr[𝑎, 𝑏, 𝑐] = Pr[𝑐|𝑎, 𝑏]Pr[𝑎, 𝑏] = Pr[𝑐|𝑎, 𝑏]Pr[𝑎|𝑏]Pr[𝑏]
• (General form) Pr 𝑣1 , … , 𝑣𝑛 = Pr 𝑣1 𝑣2 , … , 𝑣𝑛 … Pr 𝑣𝑛−1 𝑣𝑛 Pr[𝑣𝑛 ]
• The decomposition is not unique.
• Pr 𝑎, 𝑏, 𝑐 = Pr 𝑐 𝑎, 𝑏 Pr 𝑎 𝑏 Pr 𝑏 = Pr 𝑏 𝑎, 𝑐 Pr 𝑎 𝑐 Pr 𝑐
• We can enforce certain structures.
Cause and effect:
• Pr 𝑎, 𝑏, 𝑐 = Pr[𝑎] Pr[𝑏] Pr[𝑐]
𝑎: call 911, 𝑏: alarm, 𝑐: burglary
Independence and Which order you want to use?
conditional independence

Introduction to Machine Learning Amo G. Tong 17

Representation: Distribution to Graph
• Nodes: a random variable or a group of variables
• Edges: the relationship between the variables.

• Given a chain, draw a graph.

• Pr[𝑎, 𝑏, 𝑐] = Pr[𝑐|𝑎, 𝑏]Pr[𝑎, 𝑏] = Pr[𝑐|𝑎, 𝑏]Pr[𝑎|𝑏]Pr[𝑏]
• Step 1: draw a node for each variables.
• Step 2: for each term Pr[𝑥|𝑦1 , … , 𝑦𝑘 ], draw an edge (𝑦𝑖 , 𝑥) for each 𝑦𝑖 .

𝑎 𝑏

Introduction to Machine Learning Amo G. Tong 18

Representation: Distribution to Graph
• Nodes: a random variable or a group of variables
• Edges: the relationship between the variables.

• Given a chain, draw a graph.

• Step 1: draw a node for each variables.
• Step 2: for each term Pr[𝑥|𝑦1 , … , 𝑦𝑘 ], draw an edge (𝑦𝑖 , 𝑥) for each 𝑦𝑖 .

Test 2

Draw the graph corresponding

𝐏𝐫[𝒂, 𝒃, 𝒄] = 𝐏𝐫 𝒄 𝒃 𝐏𝐫 𝒃 𝐏𝐫[𝒂]
to the given decomposition.

Introduction to Machine Learning Amo G. Tong 19

Representation: Graph to Distribution

𝑎 𝑏 𝑎 𝑐

𝑐 𝑏

Pr[𝑎, 𝑏, 𝑐] = Pr[𝑐|𝑎, 𝑏]Pr[𝑎|𝑏]Pr[𝑏] Pr[𝑎, 𝑏, 𝑐] = Pr[𝑏|𝑎, 𝑐]Pr[𝑐|𝑎]Pr[𝑎]

𝑎 𝑏
For each node 𝑎, Pr[𝑎|𝑎’parents].

It must be a DAG: Bayesian Network

𝑐

Introduction to Machine Learning Amo G. Tong 20

Representation: Graph to Distribution

𝑎 𝑏 𝑎 𝑐

𝑐 𝑏

Pr[𝑎, 𝑏, 𝑐] = Pr[𝑐|𝑎, 𝑏]Pr[𝑎|𝑏]Pr[𝑏] Pr[𝑎, 𝑏, 𝑐] = Pr[𝑏|𝑎, 𝑐]Pr[𝑐|𝑎]Pr[𝑎]

𝑎 𝑏
For each node 𝑎, Pr[𝑎|𝑎’parents].

It must be a DAG: Bayesian Network

Test 3 𝑐

Pr 𝑎, 𝑏, 𝑐 =? ?

Introduction to Machine Learning Amo G. Tong 21

Representation: Graph to Distribution

𝑎 𝑏 𝑎 𝑐

𝑐 𝑏

Pr[𝑎, 𝑏, 𝑐] = Pr[𝑐|𝑎, 𝑏]Pr[𝑎|𝑏]Pr[𝑏] Pr[𝑎, 𝑏, 𝑐] = Pr[𝑏|𝑎, 𝑐]Pr[𝑐|𝑎]Pr[𝑎]

𝑎 𝑏 task Model (parameters)

For each node 𝑎, Pr[𝑎|𝑎’parents].

𝑐

Pr 𝑎, 𝑏, 𝑐 =? ? It must be a DAG: Bayesian Network

Introduction to Machine Learning Amo G. Tong 22

Representation: Graph to Distribution
• Pr[𝑥6 |𝑥4 ]
• Pr[𝑥7 |𝑥4 , 𝑥5 ]
• Pr[𝑥4 |𝑥1 , 𝑥2 , 𝑥3 ]
• Pr[𝑥5 |𝑥1 , 𝑥3 ]
• Pr[𝑥1 ]
• Pr[𝑥2 ] Organize it layer by layer
• Pr[𝑥3 ]
Topological Order

• Pr[𝑥6 |𝑥4 ] Pr[𝑥7 |𝑥4 , 𝑥5 ] Pr[𝑥5 |𝑥1 , 𝑥3 ]Pr[𝑥4 |𝑥1 , 𝑥2 , 𝑥3 ] Pr[𝑥1 ]Pr[𝑥2 ]Pr[𝑥3 ]

DAG? Missing links? Layer by layer?

Introduction to Machine Learning Amo G. Tong 23

Bayesian Network
A table or a density
Pr[𝑎|𝑏] function (e.g, Gaussian)
Pr[𝑏]
𝑎 𝑏

What information can we infer

𝑐 from the network structure?

Pr[𝑐|𝑎, 𝑏]

• A Bayesian network consists of:

• A graph structure specifying the relationships we have.
• The distribution for each relationship. (some parameters 𝜃)

Introduction to Machine Learning Amo G. Tong 24

Conditional Independence
𝑎
𝑐
𝑏

Conditional Independence
𝑒

Is 𝑎 independent of 𝑏?
Is 𝑎 independent of 𝑏 given 𝑐?

Introduction to Machine Learning Amo G. Tong 25

Conditional Independence: Example: Naïve Bayes

𝑥1 𝑥2 𝑥𝑛

• Given 𝑦, 𝑥1 is deductively determined.

• 𝑥𝑖 is independent of 𝑥𝑗 given y.

Introduction to Machine Learning Amo G. Tong 26

Conditional Independence: Example: Naïve Bayes
• Naïve Bayes: 𝑥1 , … , 𝑥𝑛 , 𝑦
• Given the class value, the value of 𝑥𝑖 is independent from 𝑥𝑗

𝑦
• missing link: independence

𝑥1 𝑥2 𝑥𝑛

• Given 𝑦, 𝑥1 is deductively determined.

• 𝑥𝑖 is independent of 𝑥𝑗 given y.

Introduction to Machine Learning Amo G. Tong 27

Conditional Independence: Example: Naïve Bayes
• 𝑎 is independent of 𝑏 given 𝑐
• a ⊥ 𝑏|𝑐 (𝑐 can be an empty variable)
• Pr[𝑎, 𝑏|𝑐] = Pr[𝑎|𝑐]Pr[𝑏|𝑐]

• From graph we know a representation of the joint distribution.

• Pr[𝑥1 , … , 𝑥𝑛 , 𝑦] = Pr[𝑥1 |𝑦] … Pr[𝑥𝑛 |𝑦]Pr[𝑦]
• How to prove Pr 𝑥1 , … , 𝑥𝑛 𝑦 = Pr 𝑥1 𝑦 … Pr 𝑥𝑛 𝑦 ?
• Divide both sides by Pr[𝑦]. 𝑦

Prove using algebra. 𝑥1 𝑥2 𝑥𝑛

Introduction to Machine Learning Amo G. Tong 28

Conditional Independence: General Rules
• Simple case: 𝑥 is independent of other variables 𝑎
conditioned on 𝑥’ parents. 𝑐
𝑏
• General: Given a Bayesian network, and three sets
𝐴, 𝐵, 𝐶 of variables, if 𝐴 is independent of 𝐵 given 𝐶? 𝑑
• Pr[𝐴|𝐵, 𝐶] = Pr[𝐴|𝐶]
• Pr[𝐵|𝐴, 𝐶] = Pr[𝐵|𝐶]
• Pr[𝐴, 𝐵|𝐶] = Pr[𝐴|𝐶]Pr[𝐵|𝐶]
𝑒

• Proving using algebra is tedious in general.

• d-separation: look at the graph

Introduction to Machine Learning Amo G. Tong 29

Conditional Independence: d-separation
• General: Given a Bayesian network, and three sets 𝐴, 𝐵, 𝐶 of variables, if 𝐴 is
independent of 𝐵 given 𝐶?

• Information is carried by paths.

• If a path from 𝑎 and 𝑏 is active, there are information “exchanged” between 𝑎 and 𝑏.
• Given 𝐶, path can be “blocked”.
𝑦

𝑥1 𝑥2 𝑥𝑛

Introduction to Machine Learning Amo G. Tong 30

Conditional Independence: d-separation
• General: Given a Bayesian network, and three sets 𝐴, 𝐵, 𝐶 of variables, if 𝐴 is
independent of 𝐵 given 𝐶?

• Information is carried by paths.

• If a path from 𝑎 and 𝑏 is active, there are information “exchanged” between 𝑎 and 𝑏.
• Given 𝐶, path can be “blocked”.
𝑦

𝑥1 𝑥2 𝑥𝑛

• Idea: to determine if 𝐴 is independent of 𝐵 given 𝐶, check the paths between each 𝑎

in 𝐴 and 𝑏 in 𝐵.

Introduction to Machine Learning Amo G. Tong 31

Conditional Independence: d-separation: Path
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡

𝑎
Paths from a to c
𝑐
a→b→d←c 𝑏
a→b→d→e←c
a→b→e←c 𝑑
a→b→e←d←c

𝑒
(Type 1: causal chains, Type 2: common cause, Type 3 : common effect)

Introduction to Machine Learning Amo G. Tong 32

Conditional Independence: d-separation: Causal Chain
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡

Burglary Self-protection
Alarm
Earthquake Call for help

• Type 1: Causal chain triple

Introduction to Machine Learning Amo G. Tong 33

Conditional Independence: d-separation: Causal Chain
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡

Burglary Self-protection
Alarm
Earthquake Call for help

• Type 1: Causal chain triple

• Burglary(s) → Alarm(r) → Call(t)
• Pr[𝑠, 𝑟, 𝑡] = Pr[𝑠]Pr[𝑟|𝑠]Pr[𝑡|𝑟]
• If 𝑟 is given, 𝑠 and 𝑡 are independent. (causal chain block)

Pr 𝑠, 𝑟, 𝑡 Pr 𝑠 Pr 𝑟 𝑠 Pr 𝑡 𝑟 Pr 𝑠, 𝑟 Pr 𝑡 𝑟
Pr 𝑠, 𝑡 𝑟 = = = = Pr 𝑠|𝑟 Pr 𝑡 𝑟
Pr 𝑟 Pr 𝑟 Pr 𝑟
Introduction to Machine Learning Amo G. Tong 34
Conditional Independence: d-separation: Causal Chain
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡

Burglary Self-protection
Alarm
Rule 1: a path is
Earthquake Call for help
blocked, if it has
a causal chain
• Type 1: Causal chain triple block.
• Burglary(s) → Alarm(r) → Call(t)
• Pr[𝑠, 𝑟, 𝑡] = Pr[𝑠]Pr[𝑟|𝑠]Pr[𝑡|𝑟]
• If 𝑟 is given, 𝑠 and 𝑡 are independent. (causal chain block)

Pr 𝑠, 𝑟, 𝑡 Pr 𝑠 Pr 𝑟 𝑠 Pr 𝑡 𝑟 Pr 𝑠, 𝑟 Pr 𝑡 𝑟
Pr 𝑠, 𝑡 𝑟 = = = = Pr 𝑠|𝑟 Pr 𝑡 𝑟
Pr 𝑟 Pr 𝑟 Pr 𝑟
Introduction to Machine Learning Amo G. Tong 35
Conditional Independence: d-separation: Common Cause
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡

Burglary Self-protection
Alarm
Earthquake Call for help

• Type 2: Common cause triple

• Call(s) ← Alarm(r) → Self-protection(t)

Introduction to Machine Learning Amo G. Tong 36

Conditional Independence: d-separation: Common Cause
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡

Burglary Self-protection
Alarm
Rule 2: a path is
Earthquake Call for help blocked, if it has
a common cause
• Type 2: Common cause triple block.
• Call(s) ← Alarm(r) → Self-protection(t)
• Pr[𝑠, 𝑟, 𝑡] = Pr[𝑡|𝑟]Pr[𝑠|𝑟]Pr[𝑟]
• If 𝑟 is given, 𝑠 and 𝑡 are independent. (common cause block)

Pr 𝑠, 𝑟, 𝑡 Pr[𝑡|𝑟]Pr[𝑠|𝑟]Pr[𝑟]
Pr 𝑠, 𝑡 𝑟 = = = Pr 𝑠|𝑟 Pr 𝑡 𝑟
Pr 𝑟 Pr 𝑟
Introduction to Machine Learning Amo G. Tong 37
Conditional Independence: d-separation: Common Effect
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡

Burglary Self-protection
Alarm
Earthquake Call for help

• Type 3: Common effect triple

• Burglary(s) → Alarm(r) ← Earthquake(t)

Introduction to Machine Learning Amo G. Tong 38

Conditional Independence: d-separation: Common Effect
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡

Burglary Self-protection
Alarm
Earthquake Call for help

• Type 3: Common effect triple

• Burglary(s) → Alarm(r) ← Earthquake(t)
• Pr[𝑠, 𝑟, 𝑡] = Pr[𝑟|𝑠, 𝑡]Pr[𝑠]Pr[𝑡]
• If none of 𝒓 and its descendants is given, 𝑠 and 𝑡 are independent. (common
effect block)
Pr[𝑟|𝑠, 𝑡] Pr[𝑠, 𝑡] Pr[𝑠, 𝑟, 𝑡] Pr[𝑟|𝑠, 𝑡]Pr[𝑠]Pr[𝑡]
Pr[𝑠, 𝑡] = Test 4 = = = Pr[𝑠]Pr[𝑡]
Pr[𝑟|𝑠, 𝑡] Pr[𝑟|𝑠, 𝑡] Pr[𝑟|𝑠, 𝑡]
Introduction to Machine Learning Amo G. Tong 39
Conditional Independence: d-separation: Common Effect
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡

Burglary Self-protection
Alarm
Earthquake Call for help

• Type 3: Common effect triple

• Burglary(s) → Alarm(r) ← Earthquake(t)
• Pr[𝑠, 𝑟, 𝑡] = Pr[𝑟|𝑠, 𝑡]Pr[𝑠]Pr[𝑡]
• If none of 𝒓 and its descendants is given, 𝑠 and 𝑡 are independent. (common
effect block)
Pr[𝑟|𝑠, 𝑡] Pr[𝑠, 𝑡] Pr[𝑠, 𝑟, 𝑡] Pr[𝑟|𝑠, 𝑡]Pr[𝑠]Pr[𝑡]
Pr[𝑠, 𝑡] = = = = Pr[𝑠]Pr[𝑡]
Pr[𝑟|𝑠, 𝑡] Pr[𝑟|𝑠, 𝑡] Pr[𝑟|𝑠, 𝑡]
Introduction to Machine Learning Amo G. Tong 40
Conditional Independence: d-separation: Common Effect
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡

Burglary Self-protection
Alarm
Earthquake Call for help

• Type 3: Common effect triple

• Burglary(s) → Alarm(r) ← Earthquake(t)
• Pr[𝑠, 𝑟, 𝑡] = Pr[𝑟|𝑠, 𝑡]Pr[𝑠]Pr[𝑡]
• If none of 𝒓 and its descendants is given, 𝑠 and 𝑡 are independent. (common
effect block)
• If 𝒓 or its descendants is given, 𝑠 and 𝑡 are not necessarily independent.
(𝑟 enforces some relationship between 𝑠 and 𝑡.)
Introduction to Machine Learning Amo G. Tong 41
Conditional Independence: d-separation: Common Effect
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
Common effect:
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡

𝑠
Burglary 𝑟 𝑡 Self-protection
Alarm
𝒔
Earthquake Call for help
0 0.3
1 0.7
• Type 3: Common Effect Two independent variables
• Burglary(s) → Alarm(r) ← Earthquake(t)
• Pr[𝑠,𝒕 𝑟, 𝑡] = Pr[𝑟|𝑠, 𝑡]Pr[𝑠]Pr[𝑡]
• If 0none
0.4of 𝒓 and its descendants is given, 𝑠 and 𝑡 are independent. (block a
common
1 0.6
effect)
• If 𝒓 or its descendants is given, 𝑠 and 𝑡 are not independent. (𝑟 enforces some
relationship between 𝑠 and 𝑡.)
Introduction to Machine Learning Amo G. Tong 42
Conditional Independence: d-separation: Common Effect
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
Common effect:
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡

𝑠
Burglary 𝑟 𝑡 Self-protection
Joint distribution of 𝑠 and 𝑡
Alarm
𝒔
Earthquake 𝒔 𝒕 Call forAllocate
help 0.3 into two places.
0 0.3 The ratio 4:6 is kept.
0 0.3 0 0.12
1 0.7
• Type 3: Common Effect 1 0.18 Pr[t=0]=0.12+0.28/1=0.4
• Burglary(s) → Alarm(r) ← Earthquake(t) Pr[t=0|s=0]=0.12/(0.12+0.18)=0.4
1
• Pr[𝑠,𝒕 𝑟, 𝑡] = Pr[𝑟|𝑠, 0.7 0
𝑡]Pr[𝑠]Pr[𝑡] 0.28 Pr[t=0|s=1]=0.28/(0.28+0.42)=0.4
• If 0none
0.4of 𝒓 and its descendants
1 is given, 𝑠 and 𝑡 are independent. (block a
0.42
common
1 0.6
effect)
• If 𝒓 or its descendants is given, 𝑠 and 𝑡 are not independent. (𝑟 enforces some
relationship between 𝑠 and 𝑡.)
Introduction to Machine Learning Amo G. Tong 43
Conditional Independence: d-separation: Common Effect
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
Common effect:
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡
𝒔 𝒕 𝒓

𝑠 𝑡 𝑟 Self-protection0 0.12 1 ?
Burglary
Alarm 0 ?
Joint distribution of 𝑠, 𝑡 and 𝑟 0 0.3
Earthquake Call for help 1 0.18 1 ?
Allocate 0.12 into two places. 0 ?
Can3:beCommon
• Type [Link]
0 0.28 1 ?
• Burglary(s) → Alarm(r) ← Earthquake(t) 0 ?
• Pr[𝑠, 𝑟, 𝑡] = Pr[𝑟|𝑠, 𝑡]Pr[𝑠]Pr[𝑡] 1 0.7
1 0.42 1 ?
• 5If none of 𝒓 and its descendants is given, 𝑠 and 𝑡 are independent. (block a
Test
common effect) 0 ?
• If 𝒓 or its descendants is given, 𝑠 and 𝑡 are not independent. (𝑟 enforces some
relationship between 𝑠 and 𝑡.)
Introduction to Machine Learning Amo G. Tong 44
Conditional Independence: d-separation: Common Effect
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
Common effect:
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡
𝒔 𝒕 𝒓

𝑠 𝑡 𝑟 Self-protection0 0.12 1 0.1

Burglary
Alarm 0 0.02
Joint distribution of 𝑠, 𝑡 and 𝑟 0 0.3
Earthquake Call for help 1 0.18 1 0.1
Allocate 0.12 into two places. 0 0.08
Can3:beCommon
• Type [Link]
0 0.28 1 0.2
• Burglary(s) → Alarm(r) ← Earthquake(t) 0 0.08
Pr[t=0]= 1 0.7
• Pr[𝑠, 𝑟, 𝑡] = Pr[𝑟|𝑠, 𝑡]Pr[𝑠]Pr[𝑡]
Pr[t=0|s=0]= 1 0.42 1 0.4
•Pr[t=0|s=1]=
If none of 𝒓 and its descendants is given, 𝑠 and 𝑡 are independent. (block a
common effect) 0 0.02
• If 𝒓 or its descendants is given, 𝑠 and 𝑡 are not independent. (𝑟 enforces some
relationship between 𝑠 and 𝑡.)
Introduction to Machine Learning Amo G. Tong 45
Conditional Independence: d-separation: Common Effect
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
Common effect:
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡
𝒔 𝒕 𝒓

𝑠 𝑡 𝑟 Self-protection0 0.12 1 0.1

Burglary
Alarm 0 0.02
Joint distribution of 𝑠, 𝑡 and 𝑟 0 0.3
Earthquake Call for help 1 0.18 1 0.1
Allocate 0.12 into two places. 0 0.08
Can3:beCommon
• Type [Link]
0 0.28 1 0.2
• Burglary(s) → Alarm(r) ← Earthquake(t) 0 0.08
If 𝒓 is not given, 𝒔 and 𝒕 are independent 1 0.7
• Pr[𝑠, 𝑟, 𝑡] = Pr[𝑟|𝑠, 𝑡]Pr[𝑠]Pr[𝑡]
Pr[t=0]=0.12+0.28=0.4 1 0.42 1 0.4
•Pr[t=0|s=0]=0.12/(0.12+0.18)=0.4
If none of 𝒓 and its descendants is given, 𝑠 and 𝑡 are independent. (block a
common effect) 0 0.02
Pr[t=0|s=1]=0.28/(0.28+0.42)=0.4
• If 𝒓 or its descendants is given, 𝑠 and 𝑡 are not independent. (𝑟 enforces some
relationship between 𝑠 and 𝑡.)
Introduction to Machine Learning Amo G. Tong 46
Conditional Independence: d-separation: Common Effect
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
Common effect:
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡
𝒔 𝒕 𝒓

𝑠 𝑡 𝑟 Self-protection0 0.12 1 0.1

Burglary
Alarm 0 0.02
Joint distribution of 𝑠, 𝑡 and 𝑟 0 0.3
Earthquake Call for help 1 0.18 1 0.1
Allocate 0.12 into two places. 0 0.08
Can3:beCommon
• Type [Link]
0 0.28 1 0.2
• Burglary(s) → Alarm(r) ← Earthquake(t) 0 0.08
But if 𝒓 is given say as 1, 𝒔 and 𝒕 are not 1 0.7
• Pr[𝑠, 𝑟, 𝑡] = Pr[𝑟|𝑠, 𝑡]Pr[𝑠]Pr[𝑡]
independent 1 0.42 1 0.4
•Pr[t=0|r=1]=(0.1+0.1)/(0.1+0.1+0.2+0.4)=0.25
If none of 𝒓 and its descendants is given, 𝑠 and 𝑡 are independent. (block a
common effect) 0 0.02
Pr[t=0|s=0,r=1]=0.1/(0.1+0.1)=0.5
• If 𝒓 or its descendants is given, 𝑠 and 𝑡 are not independent. (𝑟 enforces some
Pr[t=0|s=1,r=1]=0.2/(0.2+0.4)=0.33
relationship between 𝑠 and 𝑡.)
Introduction to Machine Learning Amo G. Tong 47
Conditional Independence: d-separation: Common Effect
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡

Burglary Self-protection
Alarm
Rule3 : a path is
Earthquake Call for help blocked, if it has
a common effect
• Type 3: Common effect triple block.
• Burglary(s) → Alarm(r) ← Earthquake(t)
• Pr[𝑠, 𝑟, 𝑡] = Pr[𝑟|𝑠, 𝑡]Pr[𝑠]Pr[𝑡]
• If none of 𝒓 and its descendants is given, 𝑠 and 𝑡 are independent. (block a
common effect)
• If 𝒓 or its descendants is given, 𝑠 and 𝑡 are not necessarily independent.
(𝑟 enforces some relationship between 𝑠 and 𝑡.)
Introduction to Machine Learning Amo G. Tong 48
Conditional Independence: d-separation: Summary
• General: Given a Bayesian network, and three sets 𝐴, 𝐵, 𝐶 of variables, if 𝐴 is
independent of 𝐵 given 𝐶?
• A path (ignore the direction) between 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵 is composed of triples (𝑠, 𝑟, 𝑡)
𝑠 𝑟 𝑡 𝑠 𝑟 𝑡 𝑠 𝑟 𝑡

• Type 1: Causal chain triple

A path is blocked if any of
𝑠 𝑟 𝑡 Block rule: r is in C. its triple is blocked.
• Type 2: Common cause triple
𝑟 Block rule: r is in C. 𝐴 is independent of 𝐵
𝑠 𝑡
given 𝐶 if all paths from A
• Type 3: Common effect triple
to B are blocked.
𝑠 𝑟 𝑡
Block rule: none of r and its descendants is in C.

Introduction to Machine Learning Amo G. Tong 49

Conditional Independence: d-separation: Practice

𝑎
𝑎⊥𝑑 Test 6
𝑐
𝑏 𝑎 ⊥ 𝑑|𝑏
𝑎⊥𝑐
𝑑 𝑎 ⊥ 𝑐|𝑏
𝑎 ⊥ 𝑐|𝑑
𝑎 ⊥ 𝑐|{𝑑, 𝑒}

Remark: a sufficient condition given by the

structure.

Introduction to Machine Learning Amo G. Tong 50

Inference and Learning
• Two important tasks.
• A set of variables {𝑥1 , … , 𝑥𝑛 }

• Learn (build) a Bayesian network from DATA. 𝑡

• Decide the graph structure. 𝑒
• Learn the distributions.
𝑑

𝑟
• Naïve Bayes is a special case.

Introduction to Machine Learning Amo G. Tong 51

Inference and Learning
• Two important tasks.
• A set of variables {𝑥1 , … , 𝑥𝑛 }

• Probabilistic Inference: the graph and the distributions

are known.
𝑡
• What is the probability of 𝑥 = 𝑡𝑟𝑢𝑒 if (𝑦 = false 𝑎𝑛𝑑 𝑧 =
true)? 𝑒
• What is the joint distribution of (𝑥, 𝑦) if 𝑧 = false? 𝑑
• What is the likelihood of some full assignment?
𝑟

• Analogy: prediction, generalization

Introduction to Machine Learning Amo G. Tong 52

Learning Goal
• What is a Bayesian network?
• Graph structure.
• Distributions given by the structure.

• Transformation between joint distribution and graph.

• d-separation: determine conditional independence according to graph.

Introduction to Machine Learning Amo G. Tong 53