Junction Tree Algorithm

Inference Control

Used in controlling exact inference.

class pybbn.pptc.inferencecontroller.InferenceController

Bases: JoinTreeListener

Inference controller.

static apply(bbn)

Sets up the specified BBN for probability propagation in tree clusters (PPTC).

Parameters:

bbn – BBN graph.

Returns:

Join tree.

static apply_from_serde(join_tree)

Applies propagation to join tree from a deserialzed join tree.

Parameters:

join_tree – Join tree.

Returns:

Join tree (the same one passed in).

evidence_retracted(join_tree)

Evidence is retracted.

Parameters:

join_tree – Join tree.

evidence_updated(join_tree)

Evidence is updated.

Parameters:

join_tree – Join tree.

static reapply(join_tree, cpts)

Reapply propagation to join tree with new CPTs. The join tree structure is kept but the BBN node CPTs are updated. A new instance/copy of the join tree will be returned.

Parameters:
  • join_tree – Join tree.

  • cpts – Dictionary of new CPTs. Keys are id’s of nodes and values are new CPTs.

Returns:

Join tree.

Potential Initialization

Used to initialize potentials.

class pybbn.pptc.potentialinitializer.PotentialInitializer

Bases: object

Potential initializer.

static init(bbn)

Initializes the BBN potentials.

Parameters:

bbn – BBN graph.

static reinit(jt)

Reinitialize potentials of BBN nodes in join tree.

Parameters:

jt – Join tree.

Returns:

None.

Moralization

Moralization of a directed acyclic graph.

class pybbn.pptc.moralizer.Moralizer

Bases: object

Graph moralizer for a DAG.

static moralize(dag)

Moralizes a DAG.

Parameters:

dag – DAG.

Returns:

Moralized (undirected) graph.

Triangulation

Triangulates a moralized graph.

class pybbn.pptc.triangulator.NodeClique(node, neighbors, weight, edges)

Bases: object

Node clique.

__init__(node, neighbors, weight, edges)

Ctor.

Parameters:
  • node – BBN node.

  • neighbors – BBN nodes (neighbors).

  • weight – Weight.

  • edges – Edges.

get_bbn_nodes()

Gets all the BBN nodes in this node clique.

Returns:

Array of BBN nodes.

class pybbn.pptc.triangulator.Triangulator

Bases: object

Triangulator. Triangulates an undirected moralized graph and produces cliques in the process.

static duplicate(g)

Duplicates a undirected graph.

Parameters:

g – Undirected graph.

Returns:

Undirected graph.

static generate_cliques(m)

Generates a list of node cliques.

Parameters:

m – Graph.

Returns:

List of NodeCliques.

static get_edges_to_add(n, m)

Gets edges to add.

Parameters:
  • n – BBN node.

  • m – Graph.

Returns:

Array of edges.

static get_weight(n, m)

Gets the weight of a BBN node. The weight of a node is the product of the its weight with all its neighbors’ weight.

Parameters:
  • n – BBN node.

  • m – Graph.

Returns:

Weight.

static is_subset(cliques, clique)

Checks if the specified clique is a subset of the specified list of cliques.

Parameters:
  • cliques – List of cliques.

  • clique – Clique.

Returns:

A boolean indicating if the clique is a subset.

static select_node(m)

Selects a clique from the specified graph. Cliques are sorted by number of edges, weight, and id (asc).

Parameters:

m – Graph.

Returns:

Clique.

static triangulate(m)

Triangulates the specified moralized graph.

Parameters:

m – Moralized undirected graph.

Returns:

Array of cliques.

Transformation

Transforms the cliques found from triangulation into a junction tree.

class pybbn.pptc.transformer.Transformer

Bases: object

Transformer. Transforms a list of cliques into a join tree.

static get_sep_sets(cliques)

Gets all pair-wise separation-sets.

Parameters:

cliques – Array of cliques.

Returns:

Array of separation sets sorted descendingly by mass followed by cost (asc) and id (asc).

static transform(cliques)

Transforms the cliques into a join tree.

Parameters:

cliques – List of cliques.

Returns:

Join tree.

Initialization

Initializes a junction tree.

class pybbn.pptc.initializer.Initializer

Bases: object

Initializes the join tree.

static get_clique(node, join_tree)

Gets the parent clique associated with the specified BBN node.

Parameters:
  • node – BBN node.

  • join_tree – Join tree.

Returns:

Parent clique.

static initialize(join_tree)

Starts the initialization.

Parameters:

join_tree – Join tree.

Returns:

Join tree.

Propagation

Propagates evidences in a junction tree.

class pybbn.pptc.propagator.Propagator

Bases: object

Evidence propagator.

static collect_evidence(join_tree, start)

Collects evidence.

Parameters:
  • join_tree – Join tree.

  • start – Start clique.

static distribute_evidence(join_tree, start)

Distributes evidence.

Parameters:
  • join_tree – Join tree.

  • start – Start clique.

static propagate(join_tree)

Propagates evidence.

Parameters:

join_tree – Join tree.

Returns:

Join tree.

Evidence Distribution

Distributes evidences.

class pybbn.pptc.evidencedistributor.EvidenceDistributor(join_tree, start_clique)

Bases: object

Evidence distributor. Passes messages using breadth-first-search (BFS). Messages are passed from the start clique to the far remote cliques.

__init__(join_tree, start_clique)

Ctor.

Parameters:
  • join_tree – Join tree.

  • start_clique – Start clique.

start()

Starts the evidence distribution.

Evidence Collection

Collects evidences.

class pybbn.pptc.evidencecollector.EvidenceCollector(join_tree, start_clique)

Bases: object

Evidence collector. Passes messages using depth-first-search (DFS). Messages are passed from the far remote cliques back to the start clique.

__init__(join_tree, start_clique)

Ctor.

Parameters:
  • join_tree – Join tree.

  • start_clique – Start clique.

start()

Starts the evidence collection.