A sum-product algorithm with polynomials for computing exact derivatives of the likelihood in Bayesian networks

Alexandra Lefebvre, Grégory Nuel
Proceedings of the Ninth International Conference on Probabilistic Graphical Models, PMLR 72:201-212, 2018.

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 this Paper

BibTeX
@InProceedings{pmlr-v72-lefebvre18a, title = {A sum-product algorithm with polynomials for computing exact derivatives of the likelihood in Bayesian networks}, author = {Lefebvre, Alexandra and Nuel, Gr\'{e}gory}, booktitle = {Proceedings of the Ninth International Conference on Probabilistic Graphical Models}, pages = {201--212}, year = {2018}, editor = {Kratochvíl, Václav and Studený, Milan}, volume = {72}, series = {Proceedings of Machine Learning Research}, month = {11--14 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v72/lefebvre18a/lefebvre18a.pdf}, url = {https://proceedings.mlr.press/v72/lefebvre18a.html}, 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.} }
Endnote
%0 Conference Paper %T A sum-product algorithm with polynomials for computing exact derivatives of the likelihood in Bayesian networks %A Alexandra Lefebvre %A Grégory Nuel %B Proceedings of the Ninth International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2018 %E Václav Kratochvíl %E Milan Studený %F pmlr-v72-lefebvre18a %I PMLR %P 201--212 %U https://proceedings.mlr.press/v72/lefebvre18a.html %V 72 %X 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.
APA
Lefebvre, A. & Nuel, G.. (2018). 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, in Proceedings of Machine Learning Research 72:201-212 Available from https://proceedings.mlr.press/v72/lefebvre18a.html.

Related Material