Introduction to Probabilistic

Graphical Models: Terminology

and Examples
Prof. Nicholas Zabaras
Center for Informatics and Computational Science
[Link]
University of Notre Dame
Notre Dame, IN, USA

Email: nzabaras@[Link]
URL: [Link]

December 23, 2017

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 1
 Contents
 Introduction, Types of Graphical Models, Joint Distribution of Random Variables and
Graphs, Applications of PGMs

 Graph Terminology, Directed Acyclic Graphs, Trees and Polytrees, Cliques and
Maximal Cliques, Conditional Probability Tables,

 Examples: Naïve Bayes Classifiers, Markov and Hidden Markov Models, Medical
Diagnosis – The Alarm Network, The QMR Network, Inference Problems, Back to
Naïve Bayes Classifier

 Example: Genetic Linkage Analysis

 Kevin Murphy, Machine Learning: A probabilistic Perspective, Chapter 10

 Chris Bishop, Pattern Recognition and Machine Learning, Chapter 8
 Jordan, M. I. (2007). An introduction to probabilistic graphical models. In preparation (Chapter 2) – Also review
article entitled `Graphical Models’
 Video Lectures on Machine Learning, Z. Gahramani, C. Bishop and others.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 2

 Introduction
 Key problems in probabilistic modeling of complex high-dimensional
problems include the following:

 Once we observe multiple correlated variables, how can we

compactly represent the joint distribution 𝑝(𝒙|𝜽)?

 How can we use 𝑝(𝒙|𝜽) to efficiently infer one set of variables

given another?

 How can we learn the parameters 𝜽 of this distribution with limited

data?

 Frey, B. (1998). Graphical Models for Machine Learning and Digital Communication. MIT Press.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 3

 Probabilistic Graphical Models
 Probabilistic graphical models (probability theory + graph theory)
have several useful properties:

 Provide a simple way to visualize the structure of an existent

probabilistic model or design and motivate new models

 Insights into the conditional independence properties of the

model, can be obtained by inspection of the graph (without
knowing the parametric form of the distributions).

 Graph based algorithms: Complex computations, required to

perform inference and learning in sophisticated models, can be
expressed in terms of efficient graphical manipulations, in which
underling mathematical expressions are carried along implicitly
 message passing algorithms that don’t require enumerating
all settings of all variables in the model.
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 4
 Probabilistic Graphical Models
 Combination of probability theory and basic graph theory
 Benefits of a graphical representation of probability
distributions:
 Gain insights into your model
 Wonderful way for generating new models
 Graph based algorithms and computation
 All developments are nothing else but applications of the sum
and product rules of probability!

 Whittaker, J. (1990). Graphical Models in Applied Multivariate Statistics. Wiley.

 Lauritzen, S. L. (1996). Graphical Models. Oxford University Press.
 Jensen, F. V. (1996). An Introduction to Bayesian Networks. UCL Press.
 Castillo, E., J. M. Gutierrez, and A. S. Hadi (1997). Expert Systems and Probabilistic Network Models. Springer.
 Jordan, M. I. (1999). Learning in Graphical Models. MIT Press.
 Cowell, R. G., A. P. Dawid, S. L. Lauritzen, and D. J. Spiegelhalter (1999). Probabilistic Networks and Expert
Systems. Springer.
 Jordan, M. I. (2007). An Introduction to Probabilistic Graphical Models. In preparation.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 5

 Probabilistic Graphical Models
 The graph structure informally specifies which parts of system are
directly dependent

 The graph encodes conditional independence assumptions

 Local functions at each node specify how parts interact

 Local functions at each node are factors in the joint probability

distribution

 Bayesian networks: PGMs based on directed acyclic graphs.

 Markov networks (Markov random fields): PGM with undirected

graph

 K. Murphy (1998). A Brief Introduction to Graphical Models and Bayesian Networks (online tutorial)
 D. Koller and N. Friedman (2009), Probabilistic Graphical Models, Principles and Techniques (Chapters 1 and 2)
 S. Russell, P. Norvig, AI: A Modern Approach (Chapter 13, Quantifying Uncertainty)
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 6
 Graphical Models
 Although the 1st-order Markov assumption is useful defining
distributions on 1d sequences, how can we define distributions on
arbitrary collections of variables ?

 Graphical models (GM) represent a joint distribution by making CI

assumptions and efficiently address this problem.

 The nodes in the graph represent random variables, and the (lack of)
edges represent CI assumptions.

 There are several kinds of graphical models, depending on whether

the graph is

 Directed,

 Undirected, or

 Some combination.
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 7
Three Main Types of Graphical Models

Factor Graph Undirected Directed Graph

Graph

 Nodes represent random variables and edges statistical dependencies

between two variables.

 These are three models for the joint probability distribution.

 Here we discuss directed probabilistic graphical models.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 8
 Joint Distributions
 Consider a set of random variables {𝑋1, 𝑋2, . . . , 𝑋𝑉 }
 Assume for simplicity of presentation that they are
discrete.
 We can ask many questions for such an ensemble:
 is one subset of variables conditionally independent of
another subset of variables given a third subset?
 how do we compute conditional probabilities?
 All such queries can be answered once we know the joint
probability 𝑃(𝑋1 = 𝑥1, 𝑋2 = 𝑥2, . . . , 𝑋𝑉 = 𝑥𝑉).
 Questions regarding independence can be answered by
factoring the joint probability distribution.
 Questions regarding conditional probabilities can be
answered by marginalization & normalization operations.
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 9
 Applications of PGMs
 Bio-informatics

 Medical Diagnosis

 Computer Vision

 Speech Recognition

 Most areas of Machine Learning and Computational Statistics

 Error-Control Codes

 Natural Language Processing

 Complex interconnected engineering systems

 Many more.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 10

 DGMs: Terminology
 A graph comprises nodes (vertices) connected by links (also
known as edges).
 Node: represents a random variable (or group of random
variables)
 Edges: express probabilistic relationships (statistical
dependencies) between these variables.

 The graph captures the way in which the joint distribution over
all of the random variables can be decomposed into a product
of factors each depending only on a subset of the variables.

 A graph representation abstracts out the conditional

independence relations between the variables from the actual
probabilistic distributions.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 11

 Graph Terminology
 A graph 𝐺 = 𝒱, ℰ consists of nodes or vertices, 𝒱 = {1, . . . , 𝑉 }, and
edges, ℰ = 𝑠, 𝑡 : 𝑠, 𝑡 ∈ 𝒱 .

 We represent the graph by its adjacency matrix, in which we write

𝐺(𝑠, 𝑡) = 1 to denote 𝑠, 𝑡 ∈ ℰ, that is, if 𝑠 → 𝑡 is an edge in the
graph.

 If 𝐺(𝑠, 𝑡) = 1 iff 𝐺(𝑡, 𝑠) = 1, we say the graph is undirected,

otherwise it is directed.

 𝐺(𝑠, 𝑠) = 0 implies that there are no self loops.

A DAG on 5 nodes, An undirected

numbered in graph, with the
topological order. Node following maximal
1 is the root, nodes 4 cliques:
and 5 are the leaves. {1, 2, 3},
{2, 3, 4},
{3, 5}.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 12

Terminology for Directed Graphs
 The parents of a node 𝑠 is the set 𝑝𝑎 𝑠 ≜ 𝑡: 𝐺 𝑡, 𝑠 = 1 .

 6  {2,5}
X 6  {X 2 , X 5}

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 13

Terminology for Directed Graphs
 The children of a node 𝑠 is the set 𝑐ℎ 𝑠 ≜ 𝑡: 𝐺 𝑠, 𝑡 = 1 .
 Family of a node is the node and its parents, 𝑓𝑎𝑚(𝑠) = {𝑠} ∪ 𝑝𝑎(𝑠).

 Root is a node with no parents.

 Leaf is a node with no children.

 Ancestors of a node 𝑡 are the parents, grand-parents,

etc., i.e. the set of nodes that connect to 𝑡 via a trail:
𝑎𝑛𝑐(𝑡) = {𝑠 ∶ 𝑠 𝑡}

 Descendants of a node 𝑠 are the children, grand-children, etc, i.e. the

set of nodes that can be reached via trails from 𝑠:
𝑑𝑒𝑠𝑐(𝑠) = {𝑡 ∶ 𝑠 𝑡}

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 14

 Directed Acyclic Graphs
 For any graph, we define the neighbors of a node as the set of all
immediately connected nodes, 𝑛𝑏𝑟(𝑠) = {𝑡 ∶ 𝐺(𝑠, 𝑡) = 1 ∨ 𝐺(𝑡, 𝑠) =
1}.

 For an undirected graph, we write 𝑠 ∼ 𝑡 to indicate that 𝑠 and 𝑡 are

neighbors (so (𝑠, 𝑡) ∈ ℰ is an edge in the graph).

 Degree of a node is the number of neighbors. For directed graphs, the

in- and out-degree count the number of parents & children.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 15

 Directed Acyclic Graphs
 Define a cycle to be a series of nodes such that we can get back to
where we started by following edges, 𝑠1 − 𝑠2 · · · −𝑠𝑛 − 𝑠1, 𝑛 ≥ 2.

 If the graph is directed, we speak of a directed cycle (Fig. b). In Figs.

(a,c), there are no directed cycles, but in Fig. (a) 1 → 2 → 4 → 3 →
1 is an undirected cycle.

 A directed acyclic graph or DAG is a directed graph with no directed

cycles (a and c are DAGs).

(a)
(b)
(c)

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 16

 Trees and Polytrees
 For a DAG, a topological ordering is a numbering of the nodes such
that parents have lower numbers than their children. For the DAG
shown, can use (1, 2, 3, 4, 5), or (1, 3, 2, 5, 4).
 A path or trail 𝑠 𝑡 is a series of directed edges leading
from 𝑠 to 𝑡.
 An undirected tree is an undirected graph with no
cycles (single path between any pair of nodes).
 A directed tree is a DAG in which every
node has at most one parent.
 A polytree is a DAG with nodes having more
than one parent, and whose
underlying undirected graph
is a tree (i.e. single path between
any two nodes ignoring the
direction of the arrows).

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 17

 Undicted and Directed Trees
 UNDIRECTED TREES: In the case of an undirected graph, a tree is
defined as a graph in which there is one, and only one, path between
any pair of nodes. Such graphs therefore do not have loops.

 DIRECTED TREES: In the case of directed graphs, a tree is defined

such that there is a single node, called the root, which has no parents,
and all other nodes have one parent. If we convert a directed tree into
an undirected graph, we see that “the moralization step” (marrying the
parents) will not add any links as all nodes have at most one parent,
and as a consequence the corresponding “moralized graph” will be an
undirected tree.

An undirected tree (left) and a directed tree (right)

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 18

 Trees and Polytrees
 Note that a distribution represented as a directed tree can easily be
converted into one represented by an undirected tree, and vice versa.

 POLYTREE: If there are nodes in a directed graph that have more

than one parent, but there is still only one path (ignoring the direction
of the arrows) between any two nodes, then the graph is a called a
polytree.

 Such a graph will have more than one node with the property of
having no parents, and furthermore, the corresponding moralized
undirected graph will have loops.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 19

 Cliques and Maximal Cliques
 A (node-induced) subgraph GA is the graph created by using the
nodes in A and their corresponding edges, 𝐺𝐴 = (𝒱𝐴, ℰ𝐴).
 For an undirected graph, a clique is a set of nodes that are all
neighbors of each other.
 A maximal clique is a clique which cannot be made any larger
without losing the clique property.

 {1, 2} is a clique but it

is not maximal, since
we can add 3 and
still maintain the
clique property.

 The maximal cliques

are {1, 2, 3},
{2, 3, 4},
{3, 5}.
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 20
Directed and Undirected Graphs
Directed Graph

Directed graphical model

Corresponding Moralized Undirected Graph

Undirected graphical model

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras)

 PGM: The Chain rule

𝑃 𝑿1:7 = 𝑃 𝑋1 𝑃 𝑋2 𝑋1 𝑃 𝑋3 𝑋1
𝑃 𝑋4 𝑋2 𝑃 𝑋5 𝑋2 , 𝑋3 𝑃 𝑋6 𝑋3 , 𝑋5
𝑃 𝑋7 𝑋4 , 𝑋5 , 𝑋6

 So, knowledge regarding the conditional distribution is enough for

defining the joint PDF in a Bayes net.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras)

 Conditional Probability Tables
𝑃 𝑿1:7 = 𝑃 𝑋1 𝑃 𝑋2 𝑋1 𝑃 𝑋3 𝑋1
𝑃 𝑋4 𝑋2 𝑃 𝑋5 𝑋2 , 𝑋3
𝑃 𝑋6 𝑋3 , 𝑋5
𝑃 𝑋7 𝑋4 , 𝑋5 , 𝑋6

 Consider that the variables are discrete and we use tables with 𝐾
entries to represent it.

 𝑃 𝑋1 will have 𝐾 entries

 𝑃 𝑋2 𝑋1 will have 𝐾 2 entries

 𝑃 𝑋5 𝑋2 , 𝑋3 will have 𝐾 3 entries

 𝑃 𝑋7 𝑋4 , 𝑋5 , 𝑋6 will have 𝐾 4 entries.

 It is obvious that this will quickly become intractable.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras)

Conditional Probability Distribution
𝑃 𝑿1:7 = 𝑃 𝑋1 𝑃 𝑋2 𝑋1 𝑃 𝑋3 𝑋1
𝑃 𝑋4 𝑋2 𝑃 𝑋5 𝑋2 , 𝑋3
𝑃 𝑋6 𝑋3 , 𝑋5
𝑃 𝑋7 𝑋4 , 𝑋5 , 𝑋6

 One solution is to replace each CPT with conditional probability

distribution (CPD).

 In such case, the number of parameters is reduced significantly

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras)

Example: Naive Bayes Classifiers
 NBC assumes the
features are conditionally
independent given the
class label.

 We can write the joint

distribution as:

𝑃 𝑦, 𝐱 = 𝑃 𝑦 ෑ 𝑃 𝑥𝑖 𝑦
𝑖=1
 The naive Bayes assumption is quite naive and hence,
the accuracy is compromised.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras)

Example: Naive Bayes Classifiers
 One way to capture correlation between the features is to
use tree-augmented naive Bayes classifier (TAN).

 The reason to use a tree, as opposed to a generic graph,

is two-fold:
 is easy to find the optimal tree structure using the Chow-Liu
algorithm
 it is easy to handle missing features in a tree-structured model

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras)

Example: Markov and Hidden Markov Model

𝑋1 𝑋2 𝑍𝑇

Markov model

𝑍1 𝑍2 𝑍𝑇

𝑋1 𝑋2 𝑋𝑇

Hidden Markov model

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras)
Markov and Hidden Markov Models
 Consider a 1st-order Markov chain as a DAG. The assumption that
𝑥𝑡−1 captures everything we need to know about 𝒙1:𝑡−1 , is strong.

 We can relax it a little by adding a dependence from 𝑥𝑡−2 to 𝑥𝑡 as well;

this is called a 2nd order Markov chain:

T
p ( x1:T )  p ( x1 , x2 ) p ( x3 | x1 , x2 ) p ( x4 | x2 , x3 ). . .  p ( x1 , x2 ) p ( xt | xt 1 , xt 2 )
t 3

 These models cannot capture long range correlations and the number
of parameters increases with the order of the chain.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 28

Markov and Hidden Markov Models
 An alternative approach is to assume that there is an underlying
hidden process, that can be modeled by a 1st-order Markov chain, and
that the data is a noisy observation of this process.

 The result is known as a hidden Markov model or HMM.

 Here 𝑧𝑡 is known as a hidden variable at time 𝑡, and 𝑥𝑡 is the observed
variable.
 The CPD 𝑝(𝑧𝑡|𝑧𝑡−1 ) is the transition model, and the CPD 𝑝(𝑥𝑡|𝑧𝑡) is
the observation model.
 We are interested to estimate 𝑝(𝑧𝑡|𝒙1: 𝑡, 𝜽). This is called the state
estimation problem.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 29

Medical Diagnosis – The Alarm Network
 Here we are interested to model the relationships between variables
measured in an intensive care unit (breathing rate of a patient, blood
pressure, etc). The alarm network represents these dependencies
with 37 variables & 504 parameters.

 Probabilistic
Expert
System: This
model was
created by
hand.

 Beinlich, I., H. Suermondt, R. Chavez, and G. Cooper (1989). The ALARM monitoring system: A case study with two
probabilistic inference techniques for belief networks. In Proc. of the Second European Conf. on AI in Medicine, pp.
247–256.
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 30
 Medical Diagnosis – The QMR Model
 A different medical diagnosis network is the quick medical reference
(QMR) network designed to model infectious diseases.
 The QMR model is a bipartite graph structure, with diseases (causes)
at the top and symptoms at the bottom. All nodes are binary. We can
write the distribution as follows:
p (v , h)   p (hs ) p (vt | hpa ( t ) )
s t
 ℎ𝑠 represent the hidden nodes (diseases), and 𝑣𝑡 represent the visible
nodes (symptoms, findings).
 The CPD for ℎ𝑠 are Bernoulli
distributions (prior probability of
each disease)
 Representing p (vt | hpa ( t ) ) using
CPTs requires many parameters
since the fan-in (# of parents) of
many leaf nodes is very high.
 Neal, R. (1992). Connectionist learning of belief networks. Artificial Intelligence 56, 71–113.
 Shwe, M., B. Middleton, D. Heckerman, M. Henrion, E. Horvitz, H. Lehmann, and G. Cooper (1991). Probabilistic
diagnosis using a reformulation of the internist-1/qmr knowledge base. Methods. Inf. Med 30(4), 241–255.
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 31
Medical Diagnosis – The Noisy OR Model
 A natural alternative to using CPTs is to use logistic regression:
p (vt  1 | hpa t  )  sigm( wtT hpa t  )
 This is known as a sigmoid belief net.
 An alternative CPD, known as the noisy-OR model is used next.
 In the noisy-OR model if a parent is on, then the child will usually also
be on but occasionally the links from parents to child may fail
independently at random.
 Even if the parent is on, the child may be off.
 Let 𝜃𝑠𝑡 = 1 − 𝑞𝑠𝑡 be the probability that the 𝑠 → 𝑡 link fails (ℎ𝑠 =
1 but 𝑣𝑡 = 0) so 𝑞𝑠𝑡 = 1 − 𝜃𝑠𝑡 = 𝑝(𝑣𝑡 = 1|ℎ𝑠 = 1, 𝒉−𝑠 = 0) is the
probability that s can activate 𝑡 on its own.
 The only way for the child to be off is if all the links from all parents are
on fail independently at random.
 Neal, R. (1992). Connectionist learning of belief networks. Artificial Intelligence 56, 71–113.
 Tommi S. Jaakkola and Michael I. Jordan, Variational methods and the QMR-DT database, Journal of Articial
Intelligence Research 10 (1999) 291-322
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 32
Medical Diagnosis – The Noisy OR Model
 Thus
p (vt  0 | h)  
s pa ( t )
 st( h 1)
s

 Obviously 𝑝(𝑣𝑡 = 1|𝒉) = 1 − 𝑝(𝑣𝑡 = 0|𝒉).

 If we observe that 𝑣𝑡 = 1 but all its parents are off, then this
contradicts the model. Such a data case would get probability zero
under the model even though someone may exhibit a symptom
without having any of the specified diseases.
 To handle this, we add a dummy leak node ℎ0, which is always on; this
represents all other causes not included in the QMR model.
 The parameter 𝑞0𝑡 = 1 − 𝜃0𝑡 is the probability that the background
leak can cause the effect on its own. The modified CPD becomes
p (vt  0 | h)   0t 
s pa ( t )
 st( h 1)
s

 If we define 𝑤𝑠𝑡 = log(𝜃𝑠𝑡), we can rewrite the CPD as logistic

regression model:  
p (vt  1 | h)  1  exp  w0t   hs wst 
 s 
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 33
Medical Diagnosis – The Noisy OR Model
 Bipartite models with noisy-OR CPDs are called BN2O models. One
can set the 𝜃𝑠𝑡 parameters based on domain expertise.

 It is also possible to learn them from data.1,2

 Noisy-OR have been used in human causal learning,3 and binary

classification settings.4

Example of the Noisy-OR:

CPD for 2 parents augmented
with leak node. We have
omitted the t subscript.

1. Neal, R. (1992). Connectionist learning of belief networks. Artificial Intelligence 56, 71–113.
2. Meek, C. and D. Heckerman (1997). Structure and parameter learning for causal independence and causal
interaction models. In UAI, pp. 366–375.
3. Griffiths, T. and J. Tenenbaum (2005). Structure and strength in causal induction. Cognitive Psychology 51, 334–
384.
4. Yuille, A. and S. Zheng (2009). Compositional noisy-logical learning. In Intl. Conf. on Machine Learning.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 34

Medical Diagnosis – Inference Problems
 Given some observations of the findings, typical inference problems
of interest include the following:

𝑃(𝑑𝑖 |𝑓𝑗): Hard to calculate

𝑃(𝑓𝑗|𝑑𝑖): Easy to calculate

 What are the marginal posterior probabilities over the diseases?

 What is the most likely setting over the underlying disease

variables?

 Which test should we carry out next (which finding to observe) in

order to get the most information about the underlying diseases?

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 35

 Medical Diagnosis - Classification
 Given observed symptoms (evidence - 𝑓1: blood pressure=high, 𝑓2:
shortness of breath=false, etc.), what is the most likely cause
(disease)? *
d  arg max p (d | f1:N )
d

 This classification problem can be addressed with supervised learning

techniques: approximating 𝑝(𝑑|𝑓1: 𝑁) with a function using a training
data set (𝑑, 𝑓1: 𝑁) pairs.

 Support Vector Machines (SVMs)

 Neural networks, etc.
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 36
 Generative Model + Bayes Rule
 A causal model can also be built using Bayes’ rule:

p ( f1:N | d ) p (d ) p ( f1:N | d ) p( d )
p (d | f1:N )  
p( f )  p( f1:N | d ') p(d ')
d'

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 37

 Naïve Bayes Classifier
 Given the cause, we assume the effects (findings) to be independent:
Fi  Fj | D  d
p (d | f1:N )  p ( f1:N | d ) p (d )
  p( f j | d ) p(d )
j

 This model is often used even when the features are not independent.
p ( D  cancer | F1  fever , F2  high press.,...)  p ( fever | cancer ) p (high press. | cancer )... p( D  cancer )

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 38

 Naïve Bayes Classifier
 The model is often used for classification.
Xi  X j | C

p (C , X1:N )  p (C ) p ( X j | C )
j

 If all variables are binary, for n features, we need 2n+1 parameters to

specify the model.
 In making classification decisions, we will need to compute:
p (C  c1 , x1:N ) p (C  c1 ) p ( x j | C  c1 )
2 

p (C  c , x1:N ) p (C  c ) j p ( x j | C  c 2 )
2

 Note that if the conditional independence relation is not valid for two
correlated features 𝑘 and 𝑙, the multiplicative term in the Eq. above
double counts the evidence 𝑘 and 𝑙 provide.
 The naïve Bayes model is degraded as the number of features
increases.
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 39
 Genetic Linkage Analysis
 This is a historically very early application of DGMs.

 A “pedigree graph” is a DAG that represents the relationship between

parents and children that can be converted to a DGM.

 Probabilistic inference can be performed on the resulting DGM.

 We want to model the transmission of a
certain property, say blood type, from parent Individuals
to child. with the
 The blood type of a person is an observable disease
quantity that depends on his genetic
makeup. Such properties are called
phenotypes.
o Circles: Females
 The genetic makeup of a person is called  Squares: Males
genotype.

 For a biology background on inheritance, see KhanAcademy lectures here

 Albers, C., M. Leisink, and H. Kappen (2006). The Cluster Variation Method for Efficient Linkage Analysis on Extended
Pedigrees. BMC Bioinformatics 7.
 Siepel, A. and D. Haussler (2003). Combining phylogenetic and hidden markov models in biosequence analysis. In Proc.
7th Intl. Conf. on Computational Molecular Biology (RECOMB).
 Fishelson, M. and D. Geiger (2002). Exact genetic linkage computations for general pedigrees. BMC Bioinformatics 18.
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 40
 Genetic Linkage Analysis
 The human genetic material consists of 22 pairs of autosomal
chromosomes and a pair of the sex chromosomes (X and Y).
 Each chromosome contains a set of genetic material consisting of
genes that determine a person's properties.
 A region of the chromosome that is of interest is called a locus; a locus
can have several variants called alleles.
 In each autosomal pair, one chromosome is the paternal chromosome,
inherited from the father, and the other is the maternal chromosome,
inherited from the mother.
 For genes in an autosomal pair, a person has two copies of the gene,
one on each copy of the chromosome. Thus, one of the gene's alleles
is inherited from the person's mother, and the other from the person's
father.
 The region containing the gene that encodes a person's blood type is
a locus. This gene comes in three variants, or alleles: A, B, and 0.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 41

 Genetic Linkage Analysis
 A person's genotype is denoted by an ordered pair and with three
choices for each entry in the pair, there are 9 possible genotypes.

 The blood type phenotype is a function of both copies of the gene.

E.g., if the person has an A allele and an 0 allele, her observed blood
type is A. If he has two 0 alleles, his observed blood type is 0.

Genotype (9 possible)
AA,AB,AO,BO,BB,OO
Phenotype
A,B,AB,O

 For each person we assign two variables: one representing the

person's genotype, and the other the phenotype.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 42

 Penetrance Model
 For each person i and location (locus) j along the genome, we create
three nodes: the observed marker Xij (blood type, or fragment of DNA
m p
that can be measured), and two hidden alleles, ij G , G ij , one
inherited from i’s mother (maternal allele) and the other from i’s father
m p
(paternal allele). Together, the ordered pair Gij Gij , Gij constitute 𝑖’s
hidden genotype at locus j.
G pi j X i j
G mi j
Gpi j
X i j G mi j Add Gijm X ij , Gijp X ij arcs
representing the fact that
genotypes cause phenotypes
Z ijp Z ijm (observed manifestations of
genotypes).
Genotype (9 possible)
Xij AA,AB,AO,BO,BB,OO
Phenotype
paternal allele
(genotype)
Gijp phenotype Gijm maternal allele
A,B,AB,O
(genotype)
 The CPD p( X | G , G ) is called the penetrance model (Mendel’s law).
ij
m
ij
p
ij

Suppose 𝑋𝑖𝑗 ∈ {𝐴, 𝐵, 𝑂, 𝐴𝐵} represents person 𝑖’s observed bloodtype,

and G , G A, B, O is their genotype. We represent the penetrance model
m
ij
p
ij

with a deterministic CPD.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 43
 Mendelian Inheritance
p( X ij | Gijm , Gijp )
 For example, A dominates O,
so if a person has genotype
AO or OA, their phenotype
will be A.
 In addition, we add arcs from
i’s mother and father into 𝑮𝑖𝑗 ,
reflecting the Mendelian
inheritance of genetic
material from one’s parents.
G pi X G mi Gpi X G mi
 More precisely, let 𝜇(𝑖) be 𝑖’s j i j j j i j j

mother. Then
Gijm G m(i ) j or G p(i ) j Z ijp Z ijm
i.e. , i’s maternal allele is a
copy of one of its mother’s Xij
m
two alleles. Let Z ij a hidden
variable that specifies the Gijp Gijm
choice.
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 44
 Inheritance and Founder Models
 We can model this using m m p m
Gijm G m(i ) j if Z ijm m
the following CPD, known p (Gij | G ( i ) j , G ( i ) j , Z ij )
Gijm G p(i ) j if Z ijm p
as the inheritance model:
G pi X G mi Gpi X G mi
 We can define similarly j i j j j i j j

p (Gijp | G m(i ) j , G p(i ) j , Z ijp )

Z ijp Z ijm

 Next we specify the prior

Xij
for the root nodes,
p (Gijp ), p(Gijm ) .This founder Gijp Gijm
model represents the
overall prevalence of haplotype at locus i of person i
difference kinds of alleles in Gijp , Gijm , Z ijp , Z ijm
the population.

 We usually assume independence between the loci for these

founder alleles. Finally, we need to specify priors for the switch
variables that control the inheritance process.
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 45
 Recombination Model
m
 ij are spatially correlated, G p
Z
X G mi Gpi X i j G mi
i j i j j j j
since adjacent sites on the
genome are inherited
together. Model this by Z ijp Z ijm
imposing a two-state
Markov chain on the 𝑍’s, Xij
where the probability of
Gijp Gijm
switching state at locus j is
given by
𝜃𝑗 = 1/2 (1 − 𝑒 −2𝑑𝑗 ), Z ijp Z ip, j 1
where 𝑑𝑗 is the distance Z ijm Z im, j 1
between loci j and j + 1 Z ijm / p
(recombination model)
p
G
 The resulting DGM is a series ofij
replicated pedigree DAGs,
augmented with switching 𝑍
variables, which are linked using
Xij Gijm
Markov chains.
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 46
 Genetic Linkage Analysis
 In linkage analysis, the task is identifying the location of disease genes
from pedigree data using some number of pedigrees (where a large
fraction of the individuals exhibit a disease phenotype).

 Available data: (a) phenotype information for many individuals in the

pedigree, (b) genotype information for loci whose location in the
chromosome is known.

 Using the inheritance model, we can evaluate the likelihood of these

observations under different hypotheses about the location of the
disease gene relative to the known loci.

 By repeated calculation of the probabilities in the network for different

hypotheses, we pinpoint the area linked to the disease.

 We can then focus in areas as small as 1/10,000 of the genome.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 47

 Genetic Linkage Analysis
 We use the model to determine where along the genome a given
disease causing gene is assumed to lie (genetic linkage)
 Suppose all the parameters of the model, including the distance
between all the marker loci, are known. The only unknown is the
location of the disease-causing gene. If there are 𝐿 marker loci, we
construct 𝐿 + 1 models: in model ℓ, we postulate that the disease
gene comes after marker ℓ, for 0 < ℓ < 𝐿 + 1. We can estimate the
Markov switching parameter 𝜃መℓ and hence the distance dℓ between
the disease gene and its nearest known locus.
 We pick the model with highest likelihood 𝑝 𝒟 𝜃መℓ ). Computing the
likelihood requires marginalizing out all the hidden Z and G variables.
 Exact methods for this task are based on the variable elimination
algorithm whereas approximate methods are based on variational
inference.
 Albers, C., M. Leisink, and H. Kappen (2006). The Cluster Variation Method for Efficient Linkage Analysis on
Extended Pedigrees. BMC Bioinformatics 7.
 Fishelson, M. and D. Geiger (2002). Exact genetic linkage computations for general pedigrees. BMC
Bioinformatics 18.
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 48
 Genetic Linkage Analysis
 Suppose we only have one
locus, corresponding to
blood type. Drop the j index
and suppose we observe xi
= A.
 Inverse Problem: There are
3 possible genotypes: 𝑮𝑖 is
(A,A), (A,O) or (O,A). The
genotype->phenotype
mapping is many-to-one
and we want to solve the
The founder (root) nodes have no parents and hence do no need
inverse problem. switching variables.

 We can use the blood types of relatives to help disambiguate the

evidence. Information flows from the other xi ’s up to their 𝑮𝑖 ’s, then
across to i’s 𝑮𝑖 via the pedigree DAG. Thus we can combine our local
evidence 𝑝(𝑥𝑖 |𝑮𝑖 ) with an informative prior, 𝑝(𝑮𝑖 |𝒙−𝑖 ), conditioned on
the other data, to get a less entropic local posterior, 𝑝(𝐺𝑖 |𝒙) ∝
𝑝(𝑥𝑖 |𝐺𝑖)𝑝(𝐺𝑖 |𝒙−𝑖 ).
Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 49
Genetic Counseling and Prediction
 In genetic counseling/prediction, one takes a phenotype with known
loci and a set of observed phenotype and genotype data for some
individuals in the pedigree to infer the genotype & phenotype for
another person in the pedigree (e.g. a planned child).

 The genetic data can consist of direct measurements of the relevant

disease loci (for some individuals) or measurements of nearby loci,
which are correlated with the disease loci.

Probabilistic Graphical Models, University of Notre Dame (Spring 2018, N. Zabaras) 50