## 4 Shannon Entropy and Kullback-Leibler Divergence
### Discrete BNs  
For discrete BNs, \(\operatorname{H}(\mathcal{B})\) does not decompose into orthogonal components. As pointed out in [PERSON] and [PERSON] (2016) (Section 8.4.12),  
\[\operatorname{H}\left(X_{i}\ |\ \[PERSON]^{\mathcal{B}}_{X_{i}}\right)= \sum_{j=1}^{q_{i}}\operatorname{P}\left(\[PERSON]^{\mathcal{B}}_{X_{i}}=j\right) \operatorname{H}\left(X_{i}\ |\ \[PERSON]^{\mathcal{B}}_{X_{i}}=j\right)\quad\text{where}\\ \operatorname{H}\left(X_{i}\ |\ \[PERSON]^{\mathcal{B}}_{X_{i}}=j\right)=- \sum_{k=1}^{r_{i}}\pi_{ik|j}(\mathcal{B})\log\pi_{ik|j}(\mathcal{B}). \tag{9}\]  
If we estimated the conditional probabilities \(\pi_{ik|j}(\mathcal{B})\) from data, the \(\operatorname{P}\left(\Pi^{\mathcal{B}}_{X_{i}}=j\right)\) are already available as the normalising constants of the individual conditional distributions \(\{\pi_{ik|j}(\mathcal{B}),j=1,\dots,q_{i}\}\) in the local distribution of \(X_{i}\). In this case, the complexity of computing \(\operatorname{H}\left(X_{i}\ |\ \Pi^{\mathcal{B}}_{X_{i}}\right)\) is linear in the number of parameters: \(O(|\Theta|)=\sum_{i=1}^{N}O(|\Theta_{X_{i}}|)\). In the general case, we need exact inference to compute the probabilities \(\operatorname{P}\left(\Pi^{\mathcal{B}}_{X_{i}}=j\right)\). Fortunately, they can be readily extracted from the junction tree derived from \(\mathcal{B}\) as follows:  
1. Identify a clique containing both \(X_{i}\) and \(\Pi^{\mathcal{B}}_{X_{i}}\). Such a clique is guaranteed to exist by the family preservation property ([PERSON], 2016) (Definition 10.1). 2. Compute the marginal distribution of \(\Pi^{\mathcal{B}}_{X_{i}}\) by summing over the remaining variables in the clique. Combining the computational complexity of constructing the junction tree from Section 3.4 and that of marginalisation, which is at most \(O\left(l^{w-1}\right)\) for each node as in (2), we have  
\[\underbrace{O(Nw+wl^{w}N)}_{\text{create the junction tree}}+ \underbrace{O\left(Nl^{w-1}\right)}_{\text{compute the $\operatorname{P}\left(\Pi^{\mathcal{B}}_{X_{i}}=j \right)$}}+\underbrace{O(|\Theta|)}_{\text{compute H}(\mathcal{B})}=\\ O\left(N(w(1+l^{w})+l^{w-1})+|\Theta|\right),\]  
which is exponential in the maximum clique size \(w\). (The maximum clique size in a junction tree is proportional to the _treewidth_ of the BN the junction tree is created from, which is also used in the literature to characterise computational complexity in BNs.) Interestingly, we do not need to perform belief propagation, so computing \(\operatorname{H}(\mathcal{B})\) is more efficient than other inference tasks. **Example 4** (Entropy of a discrete BN). : _For reasons of space, this example is presented as Example A3 in Appendix B._  
The Kullback-Leibler divergence has a similar issue, as noted in [PERSON] and [PERSON] (2016) (Section 8.4.2). The best and most complete explanation of how to compute it for discrete BNs is in [PERSON] et al. (2021). After decomposing \(\mathrm{KL}(\mathcal{B}\,\|\,\mathcal{B}^{\prime})\) following (8) to separate \(\mathrm{H}(\mathcal{B})\) and \(\mathrm{H}(\mathcal{B},\mathcal{B}^{\prime})\), [PERSON] et al. (2021) show that the latter takes the form  
\[\mathrm{H}\big{(}\mathcal{B},\mathcal{B}^{\prime}\big{)}=\sum_{i=1}^{N}\sum_{j \in\mathcal{V}\text{at}\big{(}\Pi^{\mathcal{B}^{\prime}}_{X_{i}}\big{)}}\left[ \sum_{k=1}^{r_{i}}\pi_{ikj}(\mathcal{B})\log\pi_{ik|j}(\mathcal{B}^{\prime})\right] \tag{10}\]  
where:  
* \(\pi_{ikj}(\mathcal{B})=\mathrm{P}\big{(}X_{i}=k,\Pi_{X_{i}}(\mathcal{B}^{ \prime})=j\big{)}\) is the probability assigned by \(\mathcal{B}\) to \(X_{i}=k\) given that the variables that are parents of \(X_{i}\) in \(\mathcal{B}^{\prime}\) take value \(j\);
* \(\pi_{ik|j}(\mathcal{B}^{\prime})=\mathrm{P}\big{(}X_{i}=k\mid\Pi_{X_{i}}( \mathcal{B}^{\prime})=j\big{)}\) is the \((k,j)\) element of the CPT of \(X_{i}\) in \(\mathcal{B}^{\prime}\).