English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/197657
logo share SHARE   Add this article to your Mendeley library MendeleyBASE
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:


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

AuthorsPérez, Aritz; Blum, Christian ; Lozano, Jose A.
KeywordsMaximum weighted graph
Decomposable graphs
Bounded maximum clique size
Decomposable models
Issue DateSep-2018
PublisherMassachusetts Institute of Technology
CitationProceedings of Machine Learning Research 72: 320-331 (2018)
AbstractIn 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
DescriptionTrabajo presentado en International Conference on Probabilistic Graphical Models (PGM 2018), celebrada en Praga (República Checa), del 11 al 14 de septiembre de2018
Appears in Collections:(IIIA) Artículos
Files in This Item:
File Description SizeFormat 
Approximating_maximum.pdf498,9 kBAdobe PDFThumbnail
Show full item record
Review this work

WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.