In mlindsk/jti: Junction Tree Inference

knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>",
  message = FALSE,
  warnings = FALSE,
  fig.path = "man/figures/README-",
  out.width = "100%"
)

jti: Junction Tree Inference

About

The jti package (pronounced 'yeti') is a memory efficient implementaion of the junction tree algorithm (JTA) using the Lauritzen-Spiegelhalter scheme. Why is it memory efficient? Because we use a for the potentials which enable us to handle large and complex graphs where the variables can have an arbitrary large number of levels. The jti package is a big part of the software paper .

Installation

Current stable release from CRAN:

install.packages("jti")

Development version (see README.md for new features):

devtools::install_github("mlindsk/jti", build_vignettes = FALSE)

Libraries

library(jti)
library(igraph)

Setting up the network

el <- matrix(c(
  "A", "T",
  "T", "E",
  "S", "L",
  "S", "B",
  "L", "E",
  "E", "X",
  "E", "D",
  "B", "D"),
  nc = 2,
  byrow = TRUE
)

g <- igraph::graph_from_edgelist(el)
plot(g)

We use the asia data; see the man page (?asia)

Compilation

Checking and conversion

cl <- cpt_list(asia, g)
cl

Compilation

cp <- compile(cl)
cp
# plot(get_graph(cp)) # Should give the same as plot(g)

After the network has been compiled, the graph has been triangulated and moralized. Furthermore, all conditional probability tables (CPTs) has been designated to one of the cliques (in the triangulated and moralized graph).

Example 1: sum-flow without evidence

jt1 <- jt(cp)
jt1
plot(jt1)

Query probabilities

query_belief(jt1, c("E", "L", "T"))
query_belief(jt1, c("B", "D", "E"), type = "joint")

It should be noticed, that the above could also have been achieved by

jt1 <- jt(cp, propagate = "no")
jt1 <- propagate(jt1, prop = "full")

That is; it is possible to postpone the actual propagation.

Example 2: sum-flow with evidence

e2  <- c(A = "y", X = "n")
jt2 <- jt(cp, e2) 
query_belief(jt2, c("B", "D", "E"), type = "joint")

Notice that, the configuration (D,E,B) = (y,y,n) has changed dramatically as a consequence of the evidence. We can get the probability of the evidence:

query_evidence(jt2)

Example 3: max-flow without evidence

jt3 <- jt(cp, flow = "max")
mpe(jt3)

Example 4: max-flow with evidence

e4  <- c(T = "y", X = "y", D = "y")
jt4 <- jt(cp, e4, flow = "max")
mpe(jt4)

Notice, that T, E, S, B, X and D has changed from "n" to "y" as a consequence of the new evidence e4.

Example 5: specifying a root node and only collect to save run time

cp5 <- compile(cpt_list(asia, g) , root_node = "X")
jt5 <- jt(cp5, propagate = "collect")

We can only query from the variables in the root clique now but we have ensured that the node of interest, "X", does indeed live in this clique. The variables are found using get_clique_root.

query_belief(jt5, get_clique_root(jt5), "joint")

Example 6: Compiling from a list of conditional probabilities

• We need a list with CPTs which we extract from the asia2 object
  • the list must be named with child nodes
  • The elements need to be array-like objects

cl  <- cpt_list(asia2)
cp6 <- compile(cl)

Inspection; see if the graph correspond to the cpts

plot(get_graph(cp6)) 

This time we specify that no propagation should be performed

jt6 <- jt(cp6, propagate = "no")

We can now inspect the collecting junction tree and see which cliques are leaves and parents

plot(jt6)
get_cliques(jt6)
get_clique_root(jt6)
leaves(jt6)
unlist(parents(jt6))

That is; - clique 2 is parent of clique 1 - clique 3 is parent of clique 4 etc.

Next, we send the messages from the leaves to the parents

jt6 <- send_messages(jt6)

Inspect again

plot(jt6)

Send the last message to the root and inspect

jt6 <- send_messages(jt6)
plot(jt6)

The arrows are now reversed and the outwards (distribute) phase begins

leaves(jt6)
parents(jt6)

Clique 2 (the root) is now a leave and it has 1, 3 and 6 as parents. Finishing the message passing

jt6 <- send_messages(jt6)
jt6 <- send_messages(jt6)

Queries can now be performed as normal

query_belief(jt6, c("either", "tub"), "joint")

Example 7: Fitting a decomposable model and apply JTA

We use the ess package (on CRAN), found at https://github.com/mlindsk/ess, to fit an undirected decomposable graph to data.

library(ess)

g7  <- ess::fit_graph(asia, trace = FALSE)
ig7 <- ess::as_igraph(g7)
cp7 <- compile(pot_list(asia, ig7))
jt7 <- jt(cp7)

query_belief(jt7, get_cliques(jt7)[[4]], type = "joint")

mlindsk/jti documentation built on April 15, 2022, 6:51 a.m.