What makes Bayesian Networks decomposable into joint trees?
-
16-10-2019 - |
Pergunta
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.
Solução
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:
- Labeling: Mapping each potential $\phi$ to its scope $d(\phi)$ (variables that defined it).
- Combination: Two potentials $\phi$ and $\psi$ are combined through combination operator $\phi \otimes \psi$ (in BNs $\otimes$ is the multiplication of CPTs).
- Marginalization: The usual projection operator (this corresponds to summing up irrelevant variables in BNs).
where the axioms are:
- Commutative Semigroup: it is clear that the set of CPTs represent a commutative semigroup under the combination operator.
- Labeling: for two potentials $\phi$ and $\psi$, $d(\phi \otimes \psi)=d(\phi) \cup d(\psi)$
- Marginalization: $d(\phi^{\downarrow x})=x$ where $x\subseteq d(\phi)$
- Transitivity: $(\phi^{{\downarrow y}})^{\downarrow x}=\phi^{\downarrow x}$ where $x\subseteq y\subseteq d(\phi)$
- 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$
- 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.