A Sum-Product Algorithm with Polynomials for Computing Exact Derivatives of the Likelihood in Bayesian Networks
Abstract
We consider a Bayesian network with a parameter $\theta$. It is well known that the probability of an \emph{evidence} conditional on $\theta$ (the likelihood) can be computed through a sum-product of potentials. In this work we propose a polynomial version of the sum-product algorithm based on generating functions for computing both the likelihood function and all its exact derivatives. For a unidimensional parameter we obtain the derivatives up to order $d$ with a complexity $\mathcal{O} (C \times d^2)$ where $C$ is the complexity for computing the likelihood alone. For a parameter of $p$ dimensions we obtain the likelihood, the gradient and the Hessian with a complexity $\mathcal{O} (C \times p^2)$. These complexities are similar to the numerical method with the main advantage that it computes exact derivatives instead of approximations.
Cite
Text
Lefebvre and Nuel. "A Sum-Product Algorithm with Polynomials for Computing Exact Derivatives of the Likelihood in Bayesian Networks." Proceedings of the Ninth International Conference on Probabilistic Graphical Models, 2018.Markdown
[Lefebvre and Nuel. "A Sum-Product Algorithm with Polynomials for Computing Exact Derivatives of the Likelihood in Bayesian Networks." Proceedings of the Ninth International Conference on Probabilistic Graphical Models, 2018.](https://mlanthology.org/pgm/2018/lefebvre2018pgm-sumproduct/)BibTeX
@inproceedings{lefebvre2018pgm-sumproduct,
title = {{A Sum-Product Algorithm with Polynomials for Computing Exact Derivatives of the Likelihood in Bayesian Networks}},
author = {Lefebvre, Alexandra and Nuel, Grégory},
booktitle = {Proceedings of the Ninth International Conference on Probabilistic Graphical Models},
year = {2018},
pages = {201-212},
volume = {72},
url = {https://mlanthology.org/pgm/2018/lefebvre2018pgm-sumproduct/}
}