## 4 Shannon Entropy and Kullback-Leibler Divergence
### Gaussian BNs
One way to do this is to compute a lower and an upper bound for \(\operatorname{tr}(\Sigma_{\mathcal{B}^{\prime}}^{-1}\Sigma_{\mathcal{B}})\), which can serve as an interval estimate, and take their geometric mean as an approximate point estimate. A lower bound is given by [PERSON] [53] (Result 10.39):  
\[\operatorname{tr}(\Sigma_{\mathcal{B}^{\prime}}^{-1}\Sigma_{\mathcal{B}}) \geqslant\log\det(\Sigma_{\mathcal{B}^{\prime}}^{-1}\Sigma_{\mathcal{B}})+N= -\log\det(\Sigma_{\mathcal{B}^{\prime}})+\log\det(\Sigma_{\mathcal{B}})+N, \tag{21}\]  
which conveniently reuses the values of \(\det(\Sigma_{\mathcal{B}})\) and \(\det(\Sigma_{\mathcal{B}^{\prime}})\) we have from (13). For an upper bound, [PERSON] [53] (Result 10.59) combined with [PERSON] [53] (Result 14.15) gives  
\[\operatorname{tr}(\Sigma_{\mathcal{B}^{\prime}}^{-1}\Sigma_{\mathcal{B}}) \leqslant\operatorname{tr}(\Sigma_{\mathcal{B}^{\prime}}^{-1})\operatorname{ tr}(\Sigma_{\mathcal{B}})=\operatorname{tr}\left((C_{\mathcal{B}^{\prime}}C_{ \mathcal{B}^{\prime}}^{\mathrm{T}})^{-1}\right)\operatorname{tr}(C_{\mathcal{B}}C_ {\mathcal{B}}^{\mathrm{T}})=\|C_{\mathcal{B}^{\prime}}^{-1}\|_{F}^{2}\|C_{ \mathcal{B}}\|_{F}^{2}\,, \tag{22}\]a function of \(C_{\mathcal{B}}\) and \(C_{\mathcal{B}^{\prime}}\) that can be computed in \(O\big{(}2N^{2}\big{)}\) time. Note that, as far as the point estimate is concerned, we do not care about how wide the interval is: we only need its geometric mean to be an acceptable approximation of \(\operatorname{tr}(\Sigma_{\mathcal{B}^{\prime}}^{-1}\Sigma_{\mathcal{B}})\). **Example 9** (Approximate KL). : _From Example 7, we have that \(\operatorname{tr}(\Sigma_{\mathcal{B}^{\prime}}^{-1}\Sigma_{\mathcal{B}})=57.087\), \(\det(\Sigma_{\mathcal{B}^{\prime}})=0.475\) and \(\det(\Sigma_{\mathcal{B}})=0.132\). The lower bound in (21) is then_  
\[-\log\det(\Sigma_{\mathcal{B}^{\prime}})+\log\det(\Sigma_{\mathcal{B}})+4=5.281\]  
_and the upper bound in (22) is_  
\[\|C_{\mathcal{B}^{\prime}}^{-1}\|_{F}^{2}\|C_{\mathcal{B}}\|_{F}^{2}=17.496 \cdot 19.272=337.207.\]  
_Their geometric mean is \(42.199\), which can serve as an approximate value for \(\operatorname{KL}(\mathcal{B}\parallel\mathcal{B}^{\prime})\)._  
If we are comparing two GBNs whose parameters (but not necessarily network structures) have been learned from the same data, we can sometimes approximate \(\operatorname{KL}(\mathcal{B}\parallel\mathcal{B}^{\prime})\) using the local distributions \(X_{i}\mid\Pi_{X_{i}}^{\mathcal{B}}\) and \(X_{i}\mid\Pi_{X_{i}}^{\mathcal{B}^{\prime}}\) directly. If \(\mathcal{B}\) and \(\mathcal{B}^{\prime}\) have compatible partial orderings, we can define a common total node ordering for both such that  
\[\operatorname{KL}\big{(}\mathcal{B}\big{\|}\,\mathcal{B}^{\prime} \big{)} =\operatorname{KL}\Big{(}X_{(1)}\mid\{X_{(2)},\ldots,X_{(N)}\} \cdots X_{N}\,\Big{\|}\,X_{(1)}\mid\{X_{(2)},\ldots,X_{(N)}\}\cdots X_{N}\Big{)}\] \[=\operatorname{KL}\Big{(}X_{(1)}\mid\Pi_{X_{(1)}}^{\mathcal{B}} \cdot\ldots\cdot X_{(N)}\mid\Pi_{X_{(N)}}^{\mathcal{B}}\,\Big{\|}\,X_{(1)}\mid \Pi_{X_{(1)}}^{\mathcal{B}^{\prime}}\cdot\ldots\cdot X_{(N)}\mid\Pi_{X_{(N)}}^ {\mathcal{B}^{\prime}}\Big{)}.\]  
By \"compatible partial orderings\", we mean two partial orderings that can be sorted into at least one shared total node ordering that is compatible with both. The product of the local distributions in the second step is obtained from the chain decomposition in the first step by considering the nodes in the conditioning other than the parents to have associated regression coefficients equal to zero.