## 4 Shannon Entropy and Kullback-Leibler Divergence
### Conditional Gaussian BNs
The CPTs for \(X_{1}\), \(X_{2}\) and \(X_{3}\) are the same as in \(\mathcal{B}\) and in \(\mathcal{B}^{\prime}\). We then compute \(\operatorname{KL}\left(\mathbf{X}_{D}^{\mathcal{B}}\left\|\,\mathbf{X}_{D}^{ \mathcal{B}^{\prime}}\right\|\right)=0.577\) following Example 5._  
_Secondly, we construct the multivariate normal distributions associated with the components of \(\mathcal{B}^{\prime}\) following Example 3 (in which we computed those of \(\mathcal{B}\)). For \(\{e\}\), we have_  
\[ \begin{bmatrix}X_{4}\\ X_{5}\\ X_{6}\end{bmatrix} \sim N\left( \begin{bmatrix}0.300\\ 1.400\\ 1.140\end{bmatrix} , \begin{bmatrix}0.160&0.000&0.032\\ 0.000&1.690&1.183\\ 0.032&1.183&2.274\end{bmatrix} \right);\]  
_for \(\{f\}\), we have_  
\[ \begin{bmatrix}X_{4}\\ X_{5}\\ X_{6}\end{bmatrix} \sim N\left( \begin{bmatrix}1.000\\ 0.500\\ 0.650\end{bmatrix} , \begin{bmatrix}0.090&0.000&0.018\\ 0.000&2.250&1.575\\ 0.018&1.575&2.546\end{bmatrix} \right).\]  
_Then,_  
\[\operatorname{KL}\left(\mathbf{X}_{\mathrm{G}}^{\mathcal{B}}\mid \mathbf{X}_{\mathrm{D}}^{\mathcal{B}}\left\|\,\mathbf{X}_{\mathrm{G}}^{ \mathcal{B}^{\prime}}\mid\mathbf{X}_{D}^{\mathcal{B}^{\prime}}\right)\right.\] \[=\sum_{x_{1}\in\{a,b\}}\sum_{x_{2}\in\{c,d\}}\sum_{x_{3}\in\{e,f \}}\mathrm{P}\Big{(}\mathbf{X}_{D}^{\mathcal{B}}=\{x_{1},x_{2},x_{3}\}\Big{)}\cdot\] \[=\underbrace{0.040\times 1.721}_{\{a,c,d\}}+\underbrace{0.036 \times 1.721}_{\{b,c,e\}}+\underbrace{0.040\times 2.504}_{\{a,d\}}+\underbrace{0.084 \times 2.504}_{\{b,d\}}+\] \[\qquad\qquad\underbrace{0.16\times 4.303}_{\{a,c,f\}}+ \underbrace{0.144\times 4.303}_{\{b,c,f\}}+\underbrace{0.16\times 6.31}_{\{a,d,f\}}+ \underbrace{0.336\times 6.31}_{\{b,d,f\}}\] \[=4.879\]  
_and \(\operatorname{KL}(\mathcal{B}\left\|\,\mathcal{B}^{\prime}\right\|)= \operatorname{KL}\left(\mathbf{X}_{D}^{\mathcal{B}}\left\|\,\mathbf{X}_{D}^{ \mathcal{B}^{\prime}}\right)+\operatorname{KL}\left(\mathbf{X}_{\mathrm{G}}^{ \mathcal{B}}\mid\mathbf{X}_{D}^{\mathcal{B}}\left\|\,\mathbf{X}_{\mathrm{G}}^{ \mathcal{B}^{\prime}}\mid\mathbf{X}_{D}^{\mathcal{B}^{\prime}}\right)=0.577+4.8 79=5.456\)._  
The computational complexity of this basic approach to computing \(\operatorname{KL}(\mathcal{B}\left\|\,\mathcal{B}^{\prime}\right\rangle\) is  
\[\underbrace{O\Big{(}Mwl^{w+c}+M(w+wl^{w}+l^{w-1})+(Ml^{c}+2)| \Theta_{\mathbf{X}_{D}}|\Big{)}}_{\text{compute }\operatorname{KL}\left(\mathbf{X}_{\mathrm{D}}^{ \mathcal{B}}\left\|\,\mathbf{X}_{D}^{\mathcal{B}^{\prime}}\right\|\right)}+\\ \underbrace{O\Big{(}l^{M}\cdot\Big{(}6(N-M)^{3}+(N-M)^{2}+5(N-M) \Big{)}\Big{)}}_{\text{compute all the }\operatorname{KL}\left(\mathbf{X}_{\mathrm{G}}^{ \mathcal{B}}\mid\mathbf{X}_{D}^{\mathcal{B}}=\mathbf{x}_{D}\left\|\,\mathbf{X} _{\mathrm{G}}^{\mathcal{B}^{\prime}}\mid\mathbf{X}_{D}^{\mathcal{B}^{\prime}}= \mathbf{x}_{D}\right)}, \tag{27}\]  
which we obtain by adapting (11) and (15) to follow the notation \(|\mathbf{X}_{D}|=M\) and \(|\mathbf{X}_{\mathrm{G}}|=N-M\) we established in Section 3.3. The first term implicitly covers the cost of computing the \(\mathrm{P}\left(\mathbf{X}_{D}^{\mathcal{B}}=\mathbf{x}_{D}\right)\), which relies on exact inference like the computation of \(\operatorname{KL}\left(\mathbf{X}_{D}^{\mathcal{B}}\left\|\,\mathbf{X}_{D}^{ \mathcal{B}^{\prime}}\right)\). The second term is exponential in \(M\), which would lead us to conclude that it is computationally unfeasible to compute \(\operatorname{KL}(\mathcal{B}\left\|\,\mathcal{B}^{\prime}\right\rangle\) whenever we have more than a few discrete variables in \(\mathcal{B}\) and \(\mathcal{B}^{\prime}\). Certainly, this would agree with [PERSON] and [PERSON] [PERSON] and [PERSON] (2012), who reviewed various scalable approximations of the KL divergence between two Gaussian mixtures. However, we would again disregard the fact that BNs are sparse models.