Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 1
Encontrada(s) 1 página(s)

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

  • Pérez, Aritz
  • Blum, Christian
  • Lozano, Jose A.
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