R Graphical Models Tutorial for Beginners

1. Graphical Models in R – Objective

This R Graphical Models tutorial will provide you a detailed overview of Graphical Models. First of all, we discuss what is Graphical Model, what are the real life applications of graphical models. Moreover, we will look at types of Graphical Models- Undirected, Directed Graphical Models, Conditional Independence, Conditional Independence and Separation in Graphs, and Decomposition with directed and undirected graphs are also covered in this Graphical Models Tutorial.

So, let’s start R Graphical Models Tutorial.

R Graphical Models Tutorial for Beginners

R Graphical Models Tutorial for Beginners

2. What is R Graphical Models?

R Graphical model refers to a graph to represent relationships among a set of variables. By a set of nodes (vertices) and edges, we design these models to connect those nodes.
Define a graph G by the following equation:
G = (V, E)
Here:

  • V is a finite set of vertices or nodes
  • E ⊆ V × V is a finite set of edges, links, or arcs

A graphical model encodes conditional independence assumptions between variables. It represents random variables as nodes or vertices. Conditional independence assumptions as missing arcs.
Some other real-life examples of graphical models are:
Some other real-life examples of graphical models are:

  • Road maps – Represent crossings and streets by nodes and edges.
  • Electrical circuits – Represent Electronic components and edges by nodes and edges.
  • Computer networks – Represent computers and connections by nodes and edges.
  • World Wide Web – Represent web pages and links by nodes and edges.
  • Flowcharts – Represent boxes and arrows by nodes and edges.

Read about Graphical data analysis using R Programming Language.
R Graphical models represent a class of probability distribution in terms of a graph. They use combine uncertainty and logical structure into a credible, real world phenomenon. They provide an effective way to connect the dots and reason the unlimited observations and variable available around us.
It is a probabilistic model for which a graph denotes the dependence structure between random variables. They are commonly used in probability theory, statistics—
particularly Bayesian statistics—and machine learning.
To specify the dependencies in a domain under study. The conditional distribution functions that represent the quantitative information about the domain. At the end estimate its need. This approach is tiresome and time-consuming. For example large domains like retail which have 1000 variables.
Let us see if, given an image x ∈ X, how the human pose estimates in image y ∈ Y.
The computation starts with the estimation of different body parts, as follows:
The formula to calculate the body part, for example estimating head, yhead = (u; v; Θ) where:

  • (u; v) center, where: (u; v) ∈ {1,….,M} X {1,….,N};
  • Θ rotation, where: Θ ∈ {0, 45˚, 90˚,…};

As shown in the figure, estimate a head classifier as:

R Graphical Model

R Graphical Models – Classifier

  • With this classifier, check a score and recorded for all positions in the picture.
  • Repeat this process for all the body parts. Repeat the process until the entire image for different body classifiers scans, as shown in the figure in the following slide:

Predict the most precise human pose as:

R Graphical Models

R Graphical Models – Formula 1

  • To capture the uncertainty of a phenomenon given some data we use probability distribution Represent it as::
    R Graphical Models

    R Graphical Models- Formula 2

  • The following slide shows an example of probability distribution graph
  • The graph depicts binary variable, which is y ∈ Y = {0.1}
  • It has 2 values and 1 degree of freedom

In this graph, the conditional probability distribution is:

R Graphical Models

Conditional Probability Distribution in Graphical Model

Graphical Models- Formula.3

Graphical Models- Formula 3

3. Types of R Graphical Models

There are 2 main types of R graphical models:

  • Undirected graphical models (Markow Random Fields (MRFs) – On undirected graphs Markov network based. Markov networks are also called Undirected R Graphical Models.
  • Directed or Bayesian Networks – On directed graphs Bayesian networks based. Hence, they are also called directed R Graphical Models.

Both families encompass the properties of factorization and independences. They differ in the set of independences they can encode and the factorization of the distribution that they induce.

i. Undirected R Graphical Models

An undirected graph is one in which edges have no orientation. The edge (a, b) is identical to the edge (b, a), i.e., they are not ordered pairs, but sets {u, v} (or 2-multi sets) of vertices. The largest number of edges in an undirected graph without a self-loop is n(n – 1)/2.
A graph G is indirect if ∀A, B ∈ V: (A, B) ∈ E ⇒ (B, A) ∈ E
Identify the two ordered pairs (A, B) and (B, A) and represent by only one undirected edge. Undirected R Graphical Models are also called Markov networks.
A Markov random field, also known as a Markov network, is a model over an undirected graph.
These models are useful in modeling a variety of phenomena. Where one cannot ascribe a directionality to the interaction between variables. The undirected models also offer a different and often simpler perspective on directed models. Both in terms of the independence structure and the inference task.
MRF is an undirected conditional independence graph of a probability distribution. PD along with the family of non-negative functions M of the factorization created by the graph.
Suppose that G = (V, E)
Here, vertex set V = {0,1,2,3,4,5,6} and edge set E = {(0,2), (0,4), (0,5), (1,0), (2,1), (2,5), (3,1), (3,6), (4,0), (4,5),(6,3),(6,5)}

a. Undirected Graph Terminology

Let us see few terminologies related to undirected graph:
1. Adjacent Node – A node B ∈ V is adjacent to a node A ∈ V or a neighbor of A.
If and only if (that is, if and only if) there is an edge between them: (A, B) ∈ E.
Two nodes are adjacent if they share a common edge in which case the common edge is to join the two vertices.           The two endpoints of an edge are also said to be next to each other.
2. Set of neighbors – The set of all neighbors of A is neighbors (A) = {B ∈ V | (A,B) ∈ E}. The set neighbors(A) is sometimes also called the boundary of A
3. Degree of node – The degree of the node A (number of incident edges) is deg(A) = | neighbors(A)|. The degree of a node is the number of edges that connect to it, where an edge that connects to the node at both ends (a loop). Count the edge twice. Degree, especially that of a vertex, is usually a measure of immediate adjacency.
4.Closure of node – The boundary of A together with A is the closure of A: closure(A) = neighbors(A) ∪ {A}
5. Connected nodes – Two distinct nodes A, B ∈ V are called connected in G if and only if there exists a sequence C1, . ., Ck, k ≥ 2, of distinct nodes, called a path, with C1 = A, Ck = B, and ∀i, 1 ≤ i < k : (Ci, Ci+1) ∈ E
6. Tree – An undirected graph is singly connected or a tree if and connect only if any pair of distinct nodes is by exactly one path. A tree is a connected graph with no cycles. Connect end 2 vertices by exactly 1 simple path.
7. Subgraph – A subgraph is a subset of a graph’s edges (and associated vertices) that forms a graph. An undirected graph GX = (X, EX) is called a subgraph of G (induced by X). If and only if X ⊆ V and EX = (X×X) ∩ E, that is if it contains a subset of the nodes in G and all corresponding edges
8. Complete graph – The complete graph Kn of order n is a simple graph with n vertices in which every vertex is next to every other. An undirected graph G = (V, E) is complete if and only if its set of edges is complete, that is, if and only if all possible edges are present, or if and only if:  E = V × V − {(A, A) | A ∈ V}
9. Clique – A clique in a graph is a set of pairwise adjacent vertices. Since any subgraph induced by a clique is a complete subgraph, the two terms and their notations are usually used interchangeably. A complete subgraph is called a clique. A clique is maximal if and only if it is not a subgraph of a larger clique, that is, a clique having more nodes

ii. Directed R Graphical Models

A directed graph or digraph is an ordered pair D = (VA) with

  • Vset whose elements are called vertices or nodes, and
  • Aa set of ordered pairs of vertices, called arcs, directed edges, or arrows.

Consider an edge (A, B) and direct it from A towards B.
Directed R graphical models are also called Bayesian networks or Bayes nets (BN).
A Bayesian network is a directed conditional independence graph of a probability distribution. It is along with the family of conditional probabilities of the factorization brought by the graph
A Bayesian network, Bayes network, belief network, Bayes(ian) model is a probabilistic graphical model. It represents a set of random variables and their conditional dependencies via a directed acyclic graph (DAG). For example, it could represent the probabilistic relationships between diseases and symptoms. Given symptoms, the network can use to compute the probabilities of the presence of various diseases.
Suppose, vertex set V = {0,1,2,3,4,5,6} and edge set E = {(0,2), (0,4), (0,5), (1,0), (2,1), (2,5), (3,1), (3,6), (4,0), (4,5), (6,3), (6,5)}.
We can create a directed graph from it.

a. Directed Graph Terminology

Let us see few terms related to the directed graph:
1. Parent and child note – Given an edge, the node that the edge points from is called the parent and the node that the edge points to is called the child. A node B ∈ V is called a parent of a node A ∈ V. A is called the child of B, if and only if there is a directed edge from B to A, that is, if and only if (B, A) ∈ E.
B is called adjacent to A, if and only if it is either a parent or a child of A. Denotes the set of all parents of a                 node  A :
parents(A) = {B ∈ V | (B,A) ∈ E}
Denote the set of its children:
children(A) = {B ∈ V | (A,B) ∈ E}
2. D-connected nodes – Two nodes A, B ∈ V are called d-connected in G, if and only if there is a sequence C1, ., Ck, k ≥ 2, of distinct nodes, called a directed path, with C1 = A, Ck = B, and ∀i, 1 ≤ i< k : (Ci, Ci+1) ∈ E .
x and y are d-connected if there is an unblocked path between them.
For Example:

R Graphical models

Directed Graphs terminologies – D-Connected Nodes

This graph contains one collider, at t. Unblock the path x-r-s-t, hence x and t are d-connected. So is also the path t-u-v-y, hence t and y are d-connected, as well as the pairs u andy, t and v, t, and u, x and s etc…. Yet, x and y are not d-connected; there is no way of tracing a path from x to y without traversing the collider at t.
3. Connected nodes – Two nodes A, B ∈ V are called connected in G, if and only if there is a sequence C1, . ., Ck, k ≥ 2, of distinct nodes, called a path, with C1 = A, Ck = B, and ∀i, 1 ≤ i < k : (Ci, Ci+1) ∈ E ∨ (Ci+1, Ci) ∈ E
4. Polytree – A directed acyclic graph is called singly connected or a polytree if and only if each pair of distinct nodes is connected by exactly one path.
5. Tree – A directed acyclic graph is called a (directed) tree if and only if:
It is a polytree and exactly one node (the root node) has no parents.
Next to learn in R Graphical Models is the Condition independence in Graphs.

4. Conditional Independence in Graphs

In this, each vertex or node represents an attribute to describe the domain in the study. Each edge represents a direct dependence between two attributes.
A graphical model extracts conditional independence relationships between variables from their parametric forms.
In principle, all parts depend on each other. Knowing where the head is put constraints on where the feet
can be. Suppose you want to know if the left foot’s position depends on the torso position given you know the position of the left leg. Conditional independences in the graph state that it does not.
Define conditional independence as :

R Graphical Models

R Graphical Models

Or

R Graphical Models

R Graphical Models

Here, (·⊥⊥ · | ·) depicts a three-place relation.
Some real-life examples of conditional independence are as follows:

  • Speeding fine ⊥⊥ type of car | speed
  • Lung cancer ⊥⊥ yellow teeth | smoker

5. Conditional Independence and Separation in Graphs

Associate conditional independence with separation in graphs. Here, ‘separation’ depends on whether the graph is undirected or directed:
i. Undirected Graph 

  • G = (V, E) Here, X, Y, and Z are three disjoint subsets of nodes.
  • If all paths from a node in X to a node in Y contain a node in Z, then Z u-separates X and Y in G, written as <X | Z | Y>G.
  • A path that contains a node in Z is called blocked (by Z), otherwise, it is called active
  • Thus, separation means that all paths get a block.

ii. Directed Graph 

  • G = (V, E) X, Y, and Z are three disjoint subsets of nodes.
  • X and Y are d-connected if there is an unblocked path between them.
  • X and Y are d-connected and conditioned on a set Z of nodes if there is a collider-tree path between X and Y that traverses no member of Z. If there is no such collider-tree path, then X and Y are d-separated by Z. In other words, Z blocks the every path between X and Y.
  • A path satisfying the above conditions is called active, otherwise, we can say blocked (by Z). Thus, separation means that all paths are blocked.
  • Z d-separates X and Y in G, written <X | Z | Y>G, if there is no path from a node in X to a node in Y along which the following two conditions hold:
  • Every node with converging edges (from its predecessor and its successor on the path) either is in Z or has a descendant in Z
  • Every other node is not in Z.

6. Decomposition or Factorization in Graphs

Conditional independences in graphs is only a path to find a decomposition of a distribution.
To determine it for a given distribution is the same as determining the terms that need in a decomposition of the distribution.
Finding a minimal conditional independence graph is like finding the best decomposition.
In this part, we are going to learn about:

  • Decomposition or factorization wrt undirected graphs
  • Decomposition or factorization wrt directed graphs

7. Decomposition and Undirected Graphs

  • A probability distribution over a set U of attributes is called It can also call factorizable with respect to an undirected graph G = (U, E) and write it as a product of non-negative functions on the maximal cliques of G.
  • M is a family of subsets of attributes, such that the sub graphs of G induced by the sets M ∈ M are the maximal cliques of G.
  • Then, the functions φM: EM → IR+ 0, M∈M:
R Graphical Models

Decomposition and Undirected Graphs – R Graphical Models

  • A possibility distribution πU over U is called decomposable with respect to an undirected graph G = (U, E). If is written as the least of the marginal possibility distributions on the maximal cliques of G, that is, if:
R Graphical Models

Decomposition and Undirected Graphs

The figure represents a decomposition/factorization into four terms for an undirected graph:
These 4 terms correspond to 4 maximal cliques induced by the four sets {A1,A2,A3}, {A3,A5,A6}, {A2,A4} and {A4,A6}.

R Graphical Models

Decomposition Undirected Graphs

R Quiz

8. Decomposition and Directed Graphs

  • A probability distribution pu over a set U of attributes is called It can also call factorizable with respect to a directed acyclic graph G =(U, E). If it is written as a product of the conditional probabilities of the attributes given their parent in G, if:
R Graphical Models

Graphical Model – Product of the Conditional Probabilities

  • A possibility distribution πU over U is called decomposable with respect to a directed acyclic graph G = (U, E). If it is written as the least of conditional probabilities of the attributes given their parent in G, if:
R Graphical Models

Graphical Model – Product of the Conditional Probabilities

  • The figure represents a decomposition/factorization into four terms for a directed graph:
R Graphical Models

Graphical Model – Decomposition and Directed Graphs

So, this was all on R Graphical Models. Hope you like our explanation.

9. Conclusion – R Graphical Models

Hence, in this R Graphical Models tutorial, we discussed the meaning of R Graphicak Models. Moreover, we looked at types of R Graphical Models. Also, we learned about conditional independence and decomposition in graphs. Still, if you have any suggestions or any query related to this R Graphical Models tutorial, you can ask in the comment tab.

Reference for R 

Leave a Reply

Your email address will not be published. Required fields are marked *