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 = {Václav Kratochvíl and Milan Studený}, volume = {72}, series = {Proceedings of Machine Learning Research}, address = {Prague, Czech Republic}, month = {11--14 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v72/lefebvre18a/lefebvre18a.pdf}, url = {http://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 %J Proceedings of Machine Learning Research %P 201--212 %U http://proceedings.mlr.press %V 72 %W PMLR %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 PMLR 72:201-212

Related Material