## 4 Shannon Entropy and Kullback-Leibler Divergence
### Conditional Gaussian BNs
Two properties of CLGBNs that are apparent from Examples 3 and 12 allow us to compute (26) efficiently:  
* We can reduce \(\mathbf{X}_{G}^{\mathcal{B}}\mid\mathbf{X}_{D}^{\mathcal{B}}\) to \(\mathbf{X}_{G}^{\mathcal{B}}\mid\boldsymbol{\Delta}^{\mathcal{B}}\) where \(\boldsymbol{\Delta}^{\mathcal{B}}=\bigcup_{X_{i}\in\mathbf{X}_{G}}\Delta_{X_{i} }^{\mathcal{B}}\subseteq\mathbf{X}_{D}^{\mathcal{B}}\). In other words, the continuous nodes are conditionally independent on the discrete nodes that are not their parents (\(\mathbf{X}_{D}^{\mathcal{B}}\setminus\boldsymbol{\Delta}^{\mathcal{B}}\)) given their parents (\(\boldsymbol{\Delta}^{\mathcal{B}}\)). The same is true for \(\mathbf{X}_{G}^{\mathcal{B}^{\prime}}\mid\mathbf{X}_{D}^{\mathcal{B}}\). The number of distinct terms in the summation in (26) is then given by \(|Val(\boldsymbol{\Delta}^{\mathcal{B}}\cup\boldsymbol{\Delta}^{\mathcal{B}^{ \prime}})|\) which will be smaller than \(|Val(\mathbf{X}_{D}^{\mathcal{B}})|\) in sparse networks. * The conditional distributions \(\mathbf{X}_{G}^{\mathcal{B}}\mid\mathbf{X}_{D}^{\mathcal{B}}=\delta\) and \(\mathbf{X}_{G}^{\mathcal{B}^{\prime}}\mid\mathbf{X}_{D}^{\mathcal{B}}=\delta\) are multivariate normals (not mixtures). They are also faithful to the subgraphs spanning the continuous nodes \(\mathbf{X}_{G}\), and we can represent them as GBNs whose parameters can be extracted directly from \(\mathcal{B}\) and \(\mathcal{B}^{\prime}\). Therefore, we can use the results from Section 4.2 to compute their Kullback-Leibler divergences efficiently. As a result, (26) simplifies to  
\[\operatorname{KL}\left(\mathbf{X}_{G}^{\mathcal{B}}\mid\mathbf{X }_{D}^{\mathcal{B}}\left\|\mathbf{X}_{G}^{\mathcal{B}^{\prime}}\mid\mathbf{X }_{D}^{\mathcal{B}^{\prime}}\right\|=\right.\] \[\sum_{\delta\in Val(\boldsymbol{\Delta}^{\mathcal{B}}\cup \boldsymbol{\Delta}^{\mathcal{B}^{\prime}})}\operatorname{P}\Big{(}\{ \boldsymbol{\Delta}^{\mathcal{B}}\cup\boldsymbol{\Delta}^{\mathcal{B}^{ \prime}}\}=\delta\Big{)}\operatorname{KL}\left(\mathbf{X}_{G}^{\mathcal{B}} \mid\{\boldsymbol{\Delta}^{\mathcal{B}}\cup\boldsymbol{\Delta}^{\mathcal{B}^ {\prime}}\}=\delta\,\Big{\|}\,\mathbf{X}_{G}^{\mathcal{B}^{\prime}}\mid\{ \boldsymbol{\Delta}^{\mathcal{B}}\cup\boldsymbol{\Delta}^{\mathcal{B}^{\prime}} \}=\delta\Big{)}.\]  
Figure 3: DAGs and local distributions for the CLGBNs \(\mathcal{B}\) (**top**) and \(\mathcal{B}^{\prime}\) (**bottom**) used in Examples 3 and 11–13. where \(\mathrm{P}\Big{(}\{\Delta^{\mathcal{B}}\cup\Delta^{\mathcal{B}^{\prime}}\}=\delta \Big{)}\) is the probability that the nodes \(\Delta^{\mathcal{B}}\cup\Delta^{\mathcal{B}^{\prime}}\) take value \(\delta\) as computed in \(\mathcal{B}\). In turn, (27) reduces to  
\[\underbrace{O\Big{(}Mwl^{w+c}+M(w+wl^{w}+l^{w-1})+(Ml^{c}+2)| \Theta_{\mathbf{X}_{\mathrm{D}}}|\Big{)}}_{\text{compute KL}\left(\mathbf{X}_{ \mathrm{G}}^{B}\left\|\mathbf{X}_{\mathrm{D}}^{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\]0  
because we can replace \(l^{M}\) with \(l^{|Val|(\Delta^{\mathcal{B}}\cup\Delta^{\mathcal{B}^{\prime}})|}\), which is an upper bound to the unique components in the mixture, and because we replace the complexity in (15) with that (20). We can also further reduce the second term to quadratic complexity as we discussed in Section 4.2. The remaining drivers of the computational complexity are:  
* the maximum clique size \(w\) in the subgraph spanning \(\mathbf{X}_{\mathrm{D}}^{B}\);
* the number of arcs from discrete nodes to continuous nodes in both \(\mathcal{B}\) and \(\mathcal{B}^{\prime}\) and the overlap between \(\Delta^{\mathcal{B}}\) and \(\Delta^{\mathcal{B}^{\prime}}\). **Example 13** (Sparse KL between two CLGBNs). : _Consider again the CLGBNs \(\mathcal{B}\) and \(\mathcal{B}^{\prime}\) from Example 12.