Approximating the maximum weighted decomposable graph problem with applications to probabilistic graphical models

Aritz Pérez, Christian Blum, Jose A. Lozano
Proceedings of the Ninth International Conference on Probabilistic Graphical Models, PMLR 72:320-331, 2018.

Abstract

In this work we deal with the problem of learning a maximum weighted $(k + 1)$-order decomposable graph coarser than a given maximal $k$-order decomposable graph (also known as hypertree of tree-width $k-1$). An Integer Linear Programming formulation for the problem has recently been proposed and used in order to solve instances of the problem with a moderate number of vertices. However, as the problem is known to be NP-hard, it is of practical interest to develop approximate algorithms able to work with a limited amount of computational resources. In this paper we propose an approximate Integer Linear Programming formulation for the problem using a threshold distance which discards the edges that, on average, have a low probability of being contained in the solution. Experiments have been carried out with weighted graphs and probabilistic graphical models. Using the proposed formulation we have obtained results close to the optimum, even when most of the candidate edges were discarded using the distance criterion. The obtained good results indicate that the approximate formulation has important applications for learning probabilistic graphical models using decomposable scores, e.g., BDe.

Cite this Paper

BibTeX
@InProceedings{pmlr-v72-perez18a, title = {Approximating the maximum weighted decomposable graph problem with applications to probabilistic graphical models}, author = {P\'{e}rez, Aritz and Blum, Christian and Lozano, Jose A.}, booktitle = {Proceedings of the Ninth International Conference on Probabilistic Graphical Models}, pages = {320--331}, 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/perez18a/perez18a.pdf}, url = {https://proceedings.mlr.press/v72/perez18a.html}, abstract = {In this work we deal with the problem of learning a maximum weighted $(k + 1)$-order decomposable graph coarser than a given maximal $k$-order decomposable graph (also known as hypertree of tree-width $k-1$). An Integer Linear Programming formulation for the problem has recently been proposed and used in order to solve instances of the problem with a moderate number of vertices. However, as the problem is known to be NP-hard, it is of practical interest to develop approximate algorithms able to work with a limited amount of computational resources. In this paper we propose an approximate Integer Linear Programming formulation for the problem using a threshold distance which discards the edges that, on average, have a low probability of being contained in the solution. Experiments have been carried out with weighted graphs and probabilistic graphical models. Using the proposed formulation we have obtained results close to the optimum, even when most of the candidate edges were discarded using the distance criterion. The obtained good results indicate that the approximate formulation has important applications for learning probabilistic graphical models using decomposable scores, e.g., BDe.} }
Endnote
%0 Conference Paper %T Approximating the maximum weighted decomposable graph problem with applications to probabilistic graphical models %A Aritz Pérez %A Christian Blum %A Jose A. Lozano %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-perez18a %I PMLR %P 320--331 %U https://proceedings.mlr.press/v72/perez18a.html %V 72 %X In this work we deal with the problem of learning a maximum weighted $(k + 1)$-order decomposable graph coarser than a given maximal $k$-order decomposable graph (also known as hypertree of tree-width $k-1$). An Integer Linear Programming formulation for the problem has recently been proposed and used in order to solve instances of the problem with a moderate number of vertices. However, as the problem is known to be NP-hard, it is of practical interest to develop approximate algorithms able to work with a limited amount of computational resources. In this paper we propose an approximate Integer Linear Programming formulation for the problem using a threshold distance which discards the edges that, on average, have a low probability of being contained in the solution. Experiments have been carried out with weighted graphs and probabilistic graphical models. Using the proposed formulation we have obtained results close to the optimum, even when most of the candidate edges were discarded using the distance criterion. The obtained good results indicate that the approximate formulation has important applications for learning probabilistic graphical models using decomposable scores, e.g., BDe.
APA
Pérez, A., Blum, C. & Lozano, J.A.. (2018). Approximating the maximum weighted decomposable graph problem with applications to probabilistic graphical models. Proceedings of the Ninth International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 72:320-331 Available from https://proceedings.mlr.press/v72/perez18a.html.

Related Material