## 4 Shannon Entropy and Kullback-Leibler Divergence
### Gaussian BNs
Combining (17), (13) and (18), the expression in (14) becomes \[\operatorname{KL}\bigl{(}\mathcal{B}\,\|\,\mathcal{B}^{\prime} \bigr{)}=\\ \frac{1}{2}\Bigg{[}\|C_{\mathcal{B}^{\prime}}^{-1}C_{\mathcal{B} }^{*}\|_{F}^{2}+(C_{\mathcal{B}^{\prime}}^{-1}(\mu_{\mathcal{B}^{\prime}}^{*}- \mu_{\mathcal{B}}^{*}))^{\mathsf{T}}C_{\mathcal{B}^{\prime}}^{-1}(\mu_{\mathcal{ B}^{\prime}}^{*}-\mu_{\mathcal{B}}^{*})-N+2\log\frac{\prod_{i=1}^{N}C_{ \mathcal{B}^{\prime}}[i;i]}{\prod_{i=1}^{N}C_{\mathcal{B}}[i;i]}\Bigg{]}.\] (19) The overall complexity of (19) KL is \[\underbrace{O\Bigl{(}2N^{2}+2N\Bigr{)}}_{\text{compute $\mu_{\mathcal{B}},\mu_{ \mathcal{B}^{\prime}}\,C_{\mathcal{B}}$, $C_{\mathcal{B}}$}}+\underbrace{O\Bigl{(}2N^{2}+N^{3}\Bigr{)}}_{\text{ compute $\|C_{\mathcal{B}^{\prime}}^{-1}C_{\mathcal{B}}\|_{F}^{2}$}}+\underbrace{O\Bigl{(}N^{2}+2N \Bigr{)}}_{\text{compute the quadratic form}}+\\ \underbrace{O(2N)}_{\text{compute $\det(\Sigma_{\mathcal{B}}),\,\det(\Sigma_{ \mathcal{B}^{\prime}})$}}=O\Bigl{(}N^{3}+5N^{2}+6N\Bigr{)};\] (20) while still cubic, the leading coefficient suggests that it should be about 5 times faster than the variant of (15) using the spectral decomposition. **Example 8** (Sparse KL between two GBNs). : _Consider again the two GBNs from Example 7. The corresponding matrices_  
\[C_{\mathcal{B}}= \begin{array}{c}X_{1}\\ X_{2}\\ X_{4}\\ X_{3}\\ X_{4}\\ X_{3}\\ \end{array}\begin{pmatrix}0.894&0&0&0\\ 0&0.774&0&0\\ 1.341&2.014&1.049&0\\ 1.610&2.416&1.258&0.948\\ \end{pmatrix} ,\quad C_{\mathcal{B}^{\prime}}= \begin{array}{c}X_{1}\\ X_{3}\\ X_{4}\\ X_{2}\\ \end{array}\begin{pmatrix}0.894&0&0&0\\ 1.163&0.548&0&0\\ 0.715&0&0.707&0\\ 2.647&0.657&0&1.049\\ \end{pmatrix} \end{array}\]  
_readily give the determinants of \(\Sigma_{\mathcal{B}}\) and \(\Sigma_{\mathcal{B}^{\prime}}\) following (13):_  
\[\det(C_{\mathcal{B}}) =(0.894\cdot 0.774\cdot 1.049\cdot 0.948)^{2}=0.475,\] \[\det(C_{\mathcal{B}^{\prime}}) =(0.894\cdot 0.548\cdot 0.707\cdot 1.049)^{2}=0.132.\]  
_As for the Frobenius norm in (17), we first invert \(C_{\mathcal{B}^{\prime}}\) to obtain_  
\[C_{\mathcal{B}^{\prime}}^{-1}= \begin{array}{c}X_{1}\\ X_{3}\\ X_{4}\\ X_{2}\\ \end{array}\begin{pmatrix}1.118&0&0&0\\ -2.373&1.825&0&0\\ -1.131&0&1.414&0\\ -1.334&-1.144&0&0.953\\ \end{pmatrix} ;\]  
_then we reorder the rows and columns of \(C_{\mathcal{B}}\) to follow the same node ordering as \(C_{\mathcal{B}^{\prime}}\) and compute_  
\[\left\| \begin{pmatrix}1.118&0&0&0\\ -2.373&1.825&0&0\\ -1.131&0&1.414&0\\ -1.334&-1.144&0&0.953\\ \end{pmatrix}\begin{pmatrix}0.894&0&0&0\\ 1.610&0.948&1.258&2.416\\ 1.341&0&1.049&2.014\\ 0&0&0&0.774\\ \end{pmatrix} \right\|_{F}^{2}=57.087\]  
_which, as expected, matches the value of \(\operatorname{tr}(\Sigma_{\mathcal{B}^{\prime}}^{-1}\Sigma_{\mathcal{B}})\) we computed in Example 7. Finally, \(C_{\mathcal{B}^{\prime}}^{-1}(\mu_{\mathcal{B}^{\prime}}^{*}-\mu_{\mathcal{B}}^ {*})\) in (18) is_  
\[ \begin{pmatrix}1.118&0&0&0\\ -2.373&1.825&0&0\\ -1.131&0&1.414&0\\ -1.334&-1.144&0&0.953\\ \end{pmatrix}\begin{bmatrix}2.400\\ 6.220\\ 4.620\\ 11.324\\ \end{bmatrix} - \begin{pmatrix}2.400\\ 12.1276\\ 8.848\\ 1.800\\ \end{bmatrix}\end{pmatrix} = \begin{pmatrix}0\\ -11.056\\ -5.459\\ 16.010\\ \end{pmatrix} .\]  
_The quadratic form is then equal to \(408.362\), which matches the value of \(\left(\mu_{\mathcal{B}^{\prime}}-\mu_{\mathcal{B}}\right)^{\mathrm{T}}\Sigma_ {\mathcal{B}^{\prime}}^{-1}(\mu_{\mathcal{B}^{\prime}}-\mu_{\mathcal{B}})\) in Example 7. As a result, the expression for \(\operatorname{KL}(\mathcal{B}\,\|\,\mathcal{B}^{\prime})\) is the same as in (16)._  
We can further reduce the complexity (20) of (19) when an approximate value of KL is suitable for our purposes. The only term with cubic complexity is \(\operatorname{tr}(\Sigma_{\mathcal{B}^{\prime}}^{-1}\Sigma_{\mathcal{B}})=\|C _{\mathcal{B}^{\prime}}^{-1}C_{\mathcal{B}}^{*}\|_{F}^{2}\). reducing it to quadratic complexity or lower will eliminate the leading term of (20), making it quadratic in complexity.