## 4 Shannon Entropy and Kullback-Leibler Divergence
### Discrete BNs
In order to compute the \(\pi_{ikj}(\mathcal{B})\), we need to transform \(\mathcal{B}\) into its junction tree and use belief propagation to compute the joint distribution of \(X_{i}\cup\Pi^{\mathcal{B}^{\prime}}_{X_{i}}\). As a result, \(\mathrm{H}(\mathcal{B},\mathcal{B}^{\prime})\) does not decompose at all: each \(\pi_{ikj}(\mathcal{B})\) can potentially depend on the whole BN \(\mathcal{B}\). Algorithmically, to compute \(\mathrm{KL}(\mathcal{B}\,\|\,\mathcal{B}^{\prime})\) we:  
1. Transform \(\mathcal{B}\) into its junction tree. 2. Compute the entropy \(\mathrm{H}(\mathcal{B})\). 3. For each node \(X_{i}\): 1. Identify \(\Pi^{\mathcal{B}^{\prime}}_{X_{i}}\), the parents of \(X_{i}\) in \(\mathcal{B}^{\prime}\). 2. Obtain the distribution of the variables \(\{X_{i},\Pi^{\mathcal{B}^{\prime}}_{X_{i}}\}\) from the junction tree of \(\mathcal{B}\), consisting of the probabilities \(\pi_{ikj}(\mathcal{B})\). 3. Read the \(\pi_{ik|j}(\mathcal{B}^{\prime})\) from the local distribution of \(X_{i}\) in \(\mathcal{B}^{\prime}\). 4. Use the \(\pi_{ikj}(\mathcal{B})\) and the \(\pi_{ik|j}(\mathcal{B}^{\prime})\) to compute (10). The computational complexity of this procedure is as follows: \[\underbrace{O\Big{(}N(w(1+l^{w})+l^{w-1})+|\Theta|\Big{)}}_{\text{create the junction tree of $B$ and computing $\mathrm{H}(\mathcal{B})$}}+\underbrace{O(N^{lc}(Nwl^{w}+|\Theta|))}_{\text{ produce the $\pi_{ikj}(\mathcal{B})$}}+\underbrace{O(|\Theta|)}_{\text{compute $\mathrm{H}(\mathcal{B},\mathcal{B}^{\prime})$}}=\\ O\Big{(}N^{2}wl^{w+c}+N(w+wl^{w}+l^{w-1})+(Nl^{c}+2)|\Theta|\Big{)}.\] (11)  
As noted in [PERSON] et al. (2021), computing the \(\pi_{ikj}(\mathcal{B})\) requires a separate run of belief propagation for each configuration of the \(\Pi^{\mathcal{B}^{\prime}}_{X_{i}}\), for a total of \(\sum_{i=1}^{N}|^{\Pi^{\mathcal{B}^{\prime}}_{X_{i}}}|\) times. If we assume that the DAG underlying \(\mathcal{B}^{\prime}\) is sparse, we have that \(|\Pi^{\mathcal{B}^{\prime}}_{X_{i}}|\leqslant c\) and the overall complexity of this step becomes \(O(Nl^{c}\cdot(Nwl^{w}+|\Theta|))\), \(N\) times that listed in Section 3.4. The caching scheme devised by [PERSON] et al. (2021) is very effective in limiting the use of belief propagation, but it does not alter its exponential complexity. **Example 5** (KL between two discrete BNs). : _Consider the discrete BN \(\mathcal{B}\) from Figure 2 top. Furthermore, consider the BN \(\mathcal{B}^{\prime}\) from Figure 2 bottom. We constructed the global distribution of \(\mathcal{B}\) in Example A1; we can similarly compose the global distribution of \(\mathcal{B}^{\prime}\), shown below.__Since both global distributions are limited in size, we can then compute the Kullback-Leibler divergence between \(\mathcal{B}\) and \(\mathcal{B}^{\prime}\) using (7)._  
\[\operatorname{KL}\bigl{(}\mathcal{B}\,\big{\|}\,\mathcal{B}^{ \prime}\bigr{)}=-0.013\log 0.013-0.016\log 0.016-0.022\log 0.022-0.016\log 0.016-\] \[0.072\log 0.072-0.013\log 0.013-0.029\log 0.029-0.079\log 0.079-\] \[0.033\log 0.033-0.144\log 0.144-0.054\log 0.054-0.139\log 0.139-\] \[-0.062\log 0.062-0.04\log 0.04-0.025\log 0.025-0.243\log 0.243=0. 687\]  
_In the general case, when we cannot use the global distributions, we follow the approach described in Section 4.1. Firstly, we apply (8) to write_  
\[\operatorname{KL}\bigl{(}\mathcal{B}\,\big{\|}\,\mathcal{B}^{ \prime}\bigr{)}=\operatorname{H}(\mathcal{B})-\operatorname{H}\bigl{(} \mathcal{B},\mathcal{B}^{\prime}\bigr{)};\]  
_we have from Example A3 that \(\operatorname{H}(\mathcal{B})=2.440\). As for the cross-entropy \(\operatorname{H}(\mathcal{B},\mathcal{B}^{\prime})\), we apply (10):_  
1. _We identify the parents of each node in_ \(\mathcal{B}^{\prime}\)_:_ \[\Pi_{X_{1}}^{\mathcal{B}^{\prime}}=\{\varnothing\},\qquad\Pi_{X_{2}}^{ \mathcal{B}^{\prime}}=\{X_{1},X_{4}\},\qquad\Pi_{X_{3}}^{\mathcal{B}^{\prime}} =\{X_{1}\},\qquad\Pi_{X_{4}}^{\mathcal{B}^{\prime}}=\{X_{3}\}.\]
2.