Serving MPE Queries on Tensor Networks by Computing Derivatives

Maurice Wenig, Hanno Barschel, Joachim Giesen, Andreas Goral, Mark Blacher
Proceedings of The 12th International Conference on Probabilistic Graphical Models, PMLR 246:515-527, 2024.

Abstract

Recently, tensor networks have been proposed as a data structure for weighted model counting. Computing a weighted model count is thus reduced to contracting a factorized tensor expression. Inference queries on graphical models, especially PoE (probability of evidence) queries, can be expressed directly as weighted model counting problems. Maximization problems can also be addressed on the same data structure, only the standard sum-product semiring has to be replaced by either the tropical (max-sum) or the Viterbi (max-product) semiring in the computations, that is, the tensor contractions. However, tensor contractions only provide maximal values, but MPE (most probable explanation) queries on graphical models do not ask for the maximal value, but for a state, or even the states, at which the maximal value is attained. In the special case of tropical tensor networks for ground states of spin glasses, it has been observed that the ground state can be obtained by computing a derivative of the tensor network over the tropical semiring. Here, we generalize this observation, provide a generic algorithm for computing the derivatives, and prove its correctness.

Cite this Paper

BibTeX
@InProceedings{pmlr-v246-wenig24a, title = {Serving MPE Queries on Tensor Networks by Computing Derivatives}, author = {Wenig, Maurice and Barschel, Hanno and Giesen, Joachim and Goral, Andreas and Blacher, Mark}, booktitle = {Proceedings of The 12th International Conference on Probabilistic Graphical Models}, pages = {515--527}, year = {2024}, editor = {Kwisthout, Johan and Renooij, Silja}, volume = {246}, series = {Proceedings of Machine Learning Research}, month = {11--13 Sep}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v246/main/assets/wenig24a/wenig24a.pdf}, url = {https://proceedings.mlr.press/v246/wenig24a.html}, abstract = {Recently, tensor networks have been proposed as a data structure for weighted model counting. Computing a weighted model count is thus reduced to contracting a factorized tensor expression. Inference queries on graphical models, especially PoE (probability of evidence) queries, can be expressed directly as weighted model counting problems. Maximization problems can also be addressed on the same data structure, only the standard sum-product semiring has to be replaced by either the tropical (max-sum) or the Viterbi (max-product) semiring in the computations, that is, the tensor contractions. However, tensor contractions only provide maximal values, but MPE (most probable explanation) queries on graphical models do not ask for the maximal value, but for a state, or even the states, at which the maximal value is attained. In the special case of tropical tensor networks for ground states of spin glasses, it has been observed that the ground state can be obtained by computing a derivative of the tensor network over the tropical semiring. Here, we generalize this observation, provide a generic algorithm for computing the derivatives, and prove its correctness.} }
Endnote
%0 Conference Paper %T Serving MPE Queries on Tensor Networks by Computing Derivatives %A Maurice Wenig %A Hanno Barschel %A Joachim Giesen %A Andreas Goral %A Mark Blacher %B Proceedings of The 12th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2024 %E Johan Kwisthout %E Silja Renooij %F pmlr-v246-wenig24a %I PMLR %P 515--527 %U https://proceedings.mlr.press/v246/wenig24a.html %V 246 %X Recently, tensor networks have been proposed as a data structure for weighted model counting. Computing a weighted model count is thus reduced to contracting a factorized tensor expression. Inference queries on graphical models, especially PoE (probability of evidence) queries, can be expressed directly as weighted model counting problems. Maximization problems can also be addressed on the same data structure, only the standard sum-product semiring has to be replaced by either the tropical (max-sum) or the Viterbi (max-product) semiring in the computations, that is, the tensor contractions. However, tensor contractions only provide maximal values, but MPE (most probable explanation) queries on graphical models do not ask for the maximal value, but for a state, or even the states, at which the maximal value is attained. In the special case of tropical tensor networks for ground states of spin glasses, it has been observed that the ground state can be obtained by computing a derivative of the tensor network over the tropical semiring. Here, we generalize this observation, provide a generic algorithm for computing the derivatives, and prove its correctness.
APA
Wenig, M., Barschel, H., Giesen, J., Goral, A. & Blacher, M.. (2024). Serving MPE Queries on Tensor Networks by Computing Derivatives. Proceedings of The 12th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 246:515-527 Available from https://proceedings.mlr.press/v246/wenig24a.html.

Related Material