Graphical model
Encyclopedia
A graphical model is a probabilistic model for which a graph
denotes the conditional independence
structure between random variable
s. They are commonly used in probability theory
, statistics
—particularly Bayesian statistics
—and machine learning
.
s and Markov network
s. Both families encompass the properties of factorization and independences, but they differ in the set of independences they can encode and the factorization of the distribution that they induce.
, the model represents a factorization of the joint probability
of all random variables. More precisely, if the events are
then the joint probability satisfies
where
is the set of parents of node 
. In other words, the joint distribution
factors into a product of conditional distributions. Any two nodes are conditionally independent
given the values of their parents. In general, any two sets of nodes are conditionally independent given a third set if a criterion called d-separation holds in the graph. Local independences and global independences are equivalent in Bayesian networks.
This type of graphical model is known as a directed graphical model, Bayesian network
, or belief network. Classic machine learning models like hidden Markov models, neural networks
and newer models such as variable-order Markov model
s can be considered special cases of Bayesian networks.
.
, speech recognition
, computer vision
, decoding of low-density parity-check codes, modeling of gene regulatory network
s, gene finding and diagnosis of diseases, and graphical models for protein structure
.
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
denotes the conditional independence
Conditional independence
In probability theory, two events R and B are conditionally independent given a third event Y precisely if the occurrence or non-occurrence of R and the occurrence or non-occurrence of B are independent events in their conditional probability distribution given Y...
structure between random variable
Random variable
In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...
s. They are commonly used in probability theory
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
, statistics
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
—particularly Bayesian statistics
Bayesian statistics
Bayesian statistics is that subset of the entire field of statistics in which the evidence about the true state of the world is expressed in terms of degrees of belief or, more specifically, Bayesian probabilities...
—and machine learning
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
.
Types of graphical models
Generally, probabilistic graphical models use a graph-based representation as the foundation for encoding a complete distribution over a multi-dimensional space and a graph that is a compact or factorized representation of a set of independences that hold in the specific distribution. Two branches of graphical representations of distributions are commonly used, namely, Bayesian networkBayesian network
A Bayesian network, Bayes network, belief network or directed acyclic graphical model is a probabilistic graphical model that represents a set of random variables and their conditional dependencies via a directed acyclic graph . For example, a Bayesian network could represent the probabilistic...
s and Markov network
Markov network
A Markov random field, Markov network or undirected graphical model is a set of variables having a Markov property described by an undirected graph. A Markov random field is similar to a Bayesian network in its representation of dependencies...
s. Both families encompass the properties of factorization and independences, but they differ in the set of independences they can encode and the factorization of the distribution that they induce.
Bayesian network
If the network structure of the model is a directed acyclic graphDirected acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
, the model represents a factorization of the joint probability
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
of all random variables. More precisely, if the events are
then the joint probability satisfieswhere
is the set of parents of node . In other words, the joint distributionJoint distribution
In the study of probability, given two random variables X and Y that are defined on the same probability space, the joint distribution for X and Y defines the probability of events defined in terms of both X and Y...
factors into a product of conditional distributions. Any two nodes are conditionally independent
Conditional independence
In probability theory, two events R and B are conditionally independent given a third event Y precisely if the occurrence or non-occurrence of R and the occurrence or non-occurrence of B are independent events in their conditional probability distribution given Y...
given the values of their parents. In general, any two sets of nodes are conditionally independent given a third set if a criterion called d-separation holds in the graph. Local independences and global independences are equivalent in Bayesian networks.
This type of graphical model is known as a directed graphical model, Bayesian network
Bayesian network
A Bayesian network, Bayes network, belief network or directed acyclic graphical model is a probabilistic graphical model that represents a set of random variables and their conditional dependencies via a directed acyclic graph . For example, a Bayesian network could represent the probabilistic...
, or belief network. Classic machine learning models like hidden Markov models, neural networks
Neural Networks
Neural Networks is the official journal of the three oldest societies dedicated to research in neural networks: International Neural Network Society, European Neural Network Society and Japanese Neural Network Society, published by Elsevier...
and newer models such as variable-order Markov model
Variable-order Markov model
Variable-order Markov models are an important class of models that extend the well known Markov chain models. In contrast to the Markov chain models, where each random variable in a sequence with a Markov property depends on a fixed number of random variables, in VOM models this number of...
s can be considered special cases of Bayesian networks.
Markov random field
A Markov random field, also known as a Markov network, is a model over an undirected graph. A graphical model with many repeated subunits can be represented with plate notationPlate notation
Plate notation is a method of representing variables that repeat in a graphical model. Instead of drawing each repeated variable individually, a plate or rectangle is used to group variables into a subgraph that repeat together, and a number is drawn on the plate to represent the number of...
.
Other types
- A factor graphFactor graphIn probability theory and its applications, a factor graph is a particular type of graphical model, with applications in Bayesian inference, that enables efficient computation of marginal distributions through the sum-product algorithm...
is an undirected bipartite graphBipartite graphIn the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
connecting variables and factors. Each factor represents a probability distribution over the variables it is connected to. Graphs are converted into factor graph form to perform belief propagationBelief propagationBelief propagation is a message passing algorithm for performing inference on graphical models, such as Bayesian networks and Markov random fields. It calculates the marginal distribution for each unobserved node, conditional on any observed nodes...
. - A clique tree or junction tree is a treeTree (graph theory)In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
of cliquesClique (graph theory)In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
, used in the junction tree algorithm. - A chain graph is a graph which may have both directed and undirected edges, but without any directed cycles (i.e. if we start at any vertex and move along the graph respecting the directions of any arrows, we cannot return to the vertex we started from if we have passed an arrow). Both directed acyclic graphs and undirected graphs are special cases of chain graphs, which can therefore provide a way of unifying and generalizing Bayesian and Markov networks.
- An ancestral graphAncestral graphAn ancestral graph is a graph with three types of edges: directed edge, bidirected edge, and undirected edge such that it can be decomposed into three parts: an undirected subgraph, a directed subgraph, and directed edges pointing from the undirected subgraph to the directed subgraph.An ancestral...
is a further extension, having directed, bidirected and undirected edges. - A conditional random fieldConditional random fieldA conditional random field is a statistical modelling method often applied in pattern recognition.More specifically it is a type of discriminative undirected probabilistic graphical model. It is used to encode known relationships between observations and construct consistent interpretations...
is a discriminative modelDiscriminative modelDiscriminative models are a class of models used in machine learning for modeling the dependence of an unobserved variable y on an observed variable x...
specified over an undirected graph. - A restricted Boltzmann machine is a generative modelGenerative modelIn probability and statistics, a generative model is a model for randomly generating observable data, typically given some hidden parameters. It specifies a joint probability distribution over observation and label sequences...
specified over an undirected graph.
Applications
The framework of the models, which provides algorithms for discovering and analyzing structure in complex distributions to describe them succinctly and extract the unstructured information, allows them to be constructed and utilized effectively. Applications of graphical models include information extractionInformation extraction
Information extraction is a type of information retrieval whose goal is to automatically extract structured information from unstructured and/or semi-structured machine-readable documents. In most of the cases this activity concerns processing human language texts by means of natural language...
, speech recognition
Speech recognition
Speech recognition converts spoken words to text. The term "voice recognition" is sometimes used to refer to recognition systems that must be trained to a particular speaker—as is the case for most desktop recognition software...
, computer vision
Computer vision
Computer vision is a field that includes methods for acquiring, processing, analysing, and understanding images and, in general, high-dimensional data from the real world in order to produce numerical or symbolic information, e.g., in the forms of decisions...
, decoding of low-density parity-check codes, modeling of gene regulatory network
Gene regulatory network
A gene regulatory network or genetic regulatory network is a collection of DNA segments in a cell whichinteract with each other indirectly and with other substances in the cell, thereby governing the rates at which genes in the network are transcribed into mRNA.In general, each mRNA molecule goes...
s, gene finding and diagnosis of diseases, and graphical models for protein structure
Graphical models for protein structure
Graphical models have become powerful frameworks for protein structure prediction, protein–protein interaction and free energy calculations for protein structures...
.
Books and book chapters
A more advanced and statistically oriented book A computational reasoning approach, where the relationships between graphs and probabilities were formally introduced.Other
- [ftp://ftp.research.microsoft.com/pub/tr/tr-95-06.pdf Heckerman's Bayes Net Learning Tutorial]
- A Brief Introduction to Graphical Models and Bayesian Networks
- Sargur Srihari's lecture slides on probabilistic graphical models