Given a Bayesian Network $N$, one can build a junction/joint tree $JT$ over $N$ by applying series of steps (namely, moralisation,triangulation..etc). Then we can use $JT$ to answer queries over $N$.

My question is: what makes BN decomposable into $JT$? The structure (along with the CPTs) must exhibit certain conditions otherwise any graphical model is decomposable.


I found the answer in valuation algebra more specifically in this paper .
They assume the set of functions (i.e. tables/relations/potentials/probability distributions) form a commutative semigroup. There are six axioms that the graphical model/representation should obey in order to use local computations (and thus joint trees). The valuation algebra has three operations:

  1. Labeling: Mapping each potential $\phi$ to its scope $d(\phi)$ (variables that defined it).
  2. Combination: Two potentials $\phi$ and $\psi$ are combined through combination operator $\phi \otimes \psi$ (in BNs $\otimes$ is the multiplication of CPTs).
  3. Marginalization: The usual projection operator (this corresponds to summing up irrelevant variables in BNs).

where the axioms are:

  1. Commutative Semigroup: it is clear that the set of CPTs represent a commutative semigroup under the combination operator.
  2. Labeling: for two potentials $\phi$ and $\psi$, $d(\phi \otimes \psi)=d(\phi) \cup d(\psi)$
  3. Marginalization: $d(\phi^{\downarrow x})=x$ where $x\subseteq d(\phi)$
  4. Transitivity: $(\phi^{{\downarrow y}})^{\downarrow x}=\phi^{\downarrow x}$ where $x\subseteq y\subseteq d(\phi)$
  5. Combination: $(\phi \otimes \psi)^{\downarrow z}=\phi \otimes \psi^{\downarrow{z\cap y}}$ where $d(\phi)=x,d(\psi)=y$ and $x\subseteq z\subseteq x\cup y$
  6. Domain: $\phi^{\downarrow x}=\phi$

The axioms are clearly satisfied by the nature of multiplication and marginalization over BN CPTs. Really do not know why axiom 6 is there. Sorry for abusing some of the notations.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.