DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación
Contribución de congreso (ConferenceOutput)
Approximating the maximum weighted decomposable graph problem with applications to probabilistic graphical models
Trabajo presentado en International Conference on Probabilistic Graphical Models (PGM 2018), celebrada en Praga (República Checa), del 11 al 14 de septiembre de2018, 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 treewidth 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, This work has been partially supported by the Basque Government through the BERC 2014-2017
and the ELKARTEK programs, and by the Spanish Ministry of Economy and Competitiveness
MINECO: BCAM Severo Ochoa excellence accreditation SVP-2014-068574 and SEV-2013-0323,
and through the project TIN2017-82626-R funded by (AEI/FEDER, UE)., Peer reviewed
Proyecto:
MINECO / Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016 SVP-2014-068574
,
MINECO / Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016 SEV-2013-0323
,
MINECO / Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016 TIN2017-82626-R