KTBNInference.h File Reference

Exact inference for k-order dynamic Bayesian networks: Murphy's interface algorithm, extended to interventions. More...

#include <map>
#include <memory>
#include <set>
#include <string>
#include <variant>
#include <vector>
#include <agrum/agrum.h>
#include <agrum/base/graphs/algorithms/triangulations/defaultTriangulation.h>
#include <agrum/base/variables/discreteVariable.h>
#include <agrum/KTBN/KTBN.h>
#include <unordered_map>
#include <unordered_set>
#include <agrum/KTBN/inference/KTBNInference_tpl.h>

Include dependency graph for KTBNInference.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	gum::KTBNInference< GUM_SCALAR >
	Exact inference on a gum::KTBN with observations and interventions, by the interface algorithm. More...
struct	gum::KTBNInference< GUM_SCALAR >::_Series_
	A cached marginal time-series for one base: owned variable descriptors paired with their marginals, indexed by slice (single entry for an atemporal base). Descriptors are owned so tensors get a stable per-slice name rather than the reused ring-slot name they came from. More...
struct	gum::KTBNInference< GUM_SCALAR >::_Slot_
	One node of a window template: a base (index into baseNames) at a lag behind the window's current slice. lag == ATEMPORAL marks an atemporal base, which sits in every interface and never ages. More...
struct	gum::KTBNInference< GUM_SCALAR >::_Window_
	A compiled window: the junction tree of \(H_t = I_{t-1} \cup V_t\), rooted at the clique holding \(I_t\), plus everything needed to fill and message-pass it. Built once; windows 0..k-2 are the initial ones, window k-1 is the repeating one, re-entered from slice k-1 on. More...

Namespaces
namespace	gum
	gum is the global namespace for all aGrUM entities

Variables
template class GUM_PUBLIC_KTBN	gum::KTBNInference< double >

Detailed Description

Exact inference for k-order dynamic Bayesian networks: Murphy's interface algorithm, extended to interventions.

KTBNInference answers queries on a gum::KTBN under any mix of observations \(V[t]=v\) (soft or hard) and hard interventions \(do(V[t]=v)\), returning \(P(\text{target}[t] \mid \text{obs}, do(\cdot))\) for every declared target at every slice.

The algorithm

Murphy's interface algorithm (Dynamic Bayesian Networks: Representation, Inference and Learning, 2002, §3.4), generalised from order-1 DBNs to order k. The forward interface \(I_t\) is the set of node occurrences at slices \(\leq t\) still coupled to the future; it d-separates past from future, so a distribution over \(I_t\) is all that crosses one slice boundary. At order k, \(I_t\) spans the last \(k-1\) slices – exactly what the KTBN's ring of k variable objects holds.

Inference runs on a chain of windows: window t covers \(H_t = I_{t-1} \cup V_t\), compiled once (at construction) into a junction tree by moralising its families, forcing \(I_{t-1}\) and \(I_t\) each into a clique, and triangulating. Time-homogeneity means every window from \(t=k-1\) on has the same shape, so one junction tree serves the whole repeating part, re-entered each step with fresh potentials; only the \(k-1\) initial windows get their own trees. A slice's variables are ring slots \((t-\delta) \bmod k\), so advancing is a relabelling, never an allocation – the model is never unrolled.

Within a window, Shafer-Shenoy message passing (collect then distribute, no division) combines potentials; neighbouring windows exchange \(m_t\) forward and \(r_t\) backward over their shared interface. Cost per slice is \(O(K^{w})\), w the fixed window's triangulation width – independent of the horizon.

Observations vs. interventions

An observation is conditioning: it revises the whole network, ancestors included, so information flows both ways. An intervention \(do(V[t]=v)\) is surgery: V[t] is cut from its causes and its CPT replaced by a point mass, so the effect only reaches descendants. Both may be combined, and a node may carry both.

Cost

With no observations the backward messages are provably uniform, so makeInference() runs a single forward sweep holding one window at a time: memory is independent of the horizon. Once any observation exists, exact smoothing needs the future, so the engine also runs backward, retaining one interface message per slice – \(O(T \cdot |I|)\), never whole windows.

Author

Seth AGUILA & Anis KHACEF

Definition in file KTBNInference.h.