Graphical Model Theory for Wireless Sensor Networks Page: 4 of 17
This report is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to Digital Library by the UNT Libraries Government Documents Department.
The following text was automatically extracted from the image on this page using optical character recognition software:
3.1 Overview of the Junction Tree Algorithm
JUNCTIONTREE performs exact inference in probability models, and operates on the graphical
representation of a joint pdf. Following is an overview of this algorithm, which consists of five main
subroutines. The MORALIZE, TRIANGULATE, and CONSTRUCTJT subroutines are graph-theoretic operations
that construct the inference engine (the junction tree), while the INTRODUCEEVIDENCE and
PROPAGATEPOTENTIALS subroutines use the junction tree to answer probabilistic queries.
Input graph G with nodes X and edges E; Distributions p(X); Evidence XE = XE
MORALIZE (only if G is directed)
Input G; Output moral graph GM
Input moral graph G; Output triangulated graph GT
Input cliques C and separator cardinalities ISI of GT;
Output JT a junction tree of cliques of GT
Initialize clique potentials Vg(C) , separator potentials # (S) on GT
InputXE = XE Output posterior clique potentials y(C) on cliques of GT
Start at root clique
For each child of clique,
Input clique, COLLECTEVIDENCE(child)
Output updated clique potentials y * (XC)
For each parent of clique,
Input clique, DISTRIBUTEEVIDENCE(parent)
Output updated clique potentials y * *(XC )
Output p(XF XE)
This algorithm constructs an inference engine, in the form of a junction tree of clique potentials, then
performs inference by achieving local consistency between adjoining clique potentials in the junction tree.
Because of properties of the junction tree, when this algorithm terminates, the clique potentials equal pdfs
conditioned on the evidence, from which inferential queries can be answered locally.
PROPAGATEPOTENTIALS adjusts the clique potentials to achieve this mutual consistency.
PROPAGATEPOTENTIALS also describes the message-passing necessary between cliques in the junction tree.
The calls to COLLECTEVIDENCE and DISTRIBUTEEVIDENCE are recursive - these subroutines repeatedly call
themselves so long as a clique in the junction tree has children or a parent. The recursive calls ensure that
all cliques send a message to parents only after they have received messages from all children. Messages
are passed once "inward" from the leaves to the root, then once "outward" from the root to the leaves (there
exist shorter sequences of message passing that yield the same result).
The MORALIZE, TRIANGULATE, and CONSTRUCTJT subroutines are graph-theoretic operations that
guarantee that local consistency will result in global consistency, i.e., that PROPAGATEPOTENTIALS will
result in all the potentials proportional to the local marginal probabilities, as desired. These subroutines are
described directly in graph-theoretic terms - adjacency matrices afford a more efficient representation of
graphs in implementation.
Constructing the Inference Engine: Moralization
MORALIZE converts a directed graphical representation to an undirected graphical representation (that
encodes no more conditional independence assumptions, and possibly fewer). This step is therefore only
necessary if G is directed.
Here’s what’s next.
This report can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Report.
Davis, William B. Graphical Model Theory for Wireless Sensor Networks, report, December 8, 2002; Berkeley, California. (digital.library.unt.edu/ark:/67531/metadc781369/m1/4/: accessed February 22, 2019), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT Libraries Government Documents Department.