Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Bucket and Mini-bucket Schemes for M Best Solutions over Graphical Models
verfasst von : Natalia Flerova, Emma Rollon, Rina Dechter
Erschienen in: Graph Structures for Knowledge Representation and Reasoning
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The paper focuses on the task of generating the first m best solutions for a combinatorial optimization problem defined over a graphical model (e.g., the
m
most probable explanations for a Bayesian network). We show that the m-best task can be expressed within the unifying framework of semirings making known inference algorithms defined and their correctness and completeness for the m-best task immediately implied. We subsequently describe
elim-m-opt
, a new bucket elimination algorithm for solving the m-best task, provide algorithms for its defining combination and marginalization operators and analyze its worst-case performance. An extension of the algorithm to the mini-bucket framework provides bounds for each of the m best solutions. Empirical demonstrations of the algorithms with emphasis on their potential for approximations are provided.