johnswentworth comments on Some Rules for an Algebra of Bayes Nets

[johnswentworth]

Here’s a new Bookkeeping Theorem, which unifies all of the Bookkeeping Rules mentioned (but mostly not proven) in the post, as well as all possible other Bookkeeping Rules.

If all distributions which factor over Bayes net $G_1$ also factor over Bayes net $G_2$, then all distributions which approximately factor over $G_1$ also approximately factor over $G_2$. Quantitatively:

$D_{KL}\left(P\right[X\left]||{\prod }_{i}P\right[X_i|X_{p{a}^1\left(i\right)}\left]\right)\ge D_{KL}\left(P\right[X\left]||{\prod }_{i}P\right[X_i|X_{p{a}^2\left(i\right)}\left]\right)$

where $p{a}^j\left(i\right)$ indicates parents of variable $i$ in $G_j$.

Proof: Define the distribution $Q\left[X\right]:={\prod }_{i}P\left[X_i|X_{p{a}^1\left(i\right)}\right]$. Since $Q\left[X\right]$ exactly factors over $G_1$, it also exactly factors over $G_2$: $Q\left[X\right]={\prod }_{i}Q\left[X_i|X_{p{a}^2\left(i\right)}\right]$. So

$D_{KL}\left(P\right[X\left]||{\prod }_{i}P\right[X_i|X_{p{a}^1\left(i\right)}\left]\right)=D_{KL}\left(P\right[X\left]||Q\right[X\left]\right)$

$=D_{KL}\left(P\right[X\left]||{\prod }_{i}Q\right[X_i|X_{p{a}^2\left(i\right)}\left]\right)$

Then by the factorization transfer rule (from the post):

$\ge D_{KL}\left(P\right[X\left]||{\prod }_{i}P\right[X_i|X_{p{a}^2\left(i\right)}\left]\right)$

which completes the proof.