Strengthening Probabilistic Graphical Models: The Purge-and-Merge Algorithm
Probabilistic graphical models (PGMs) are powerful tools for solving systems of complex relationships over a variety of probability distributions. However, while tree-structured PGMs always result in efficient and exact solutions, inference on graph (or loopy) structured PGMs is not guaranteed to di...
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | article |
| Langue: | EN |
| Publié: |
IEEE
2021
|
| Sujets: | |
| Accès en ligne: | https://doaj.org/article/8db894f4a89a4f99b9f59e778cd426a1 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| Résumé: | Probabilistic graphical models (PGMs) are powerful tools for solving systems of complex relationships over a variety of probability distributions. However, while tree-structured PGMs always result in efficient and exact solutions, inference on graph (or loopy) structured PGMs is not guaranteed to discover the optimal solutions. It is in principle possible to convert loopy PGMs to an equivalent tree structure, but this is usually impractical for interesting problems due to exponential blow-up. To address this, we developed the “purge-and-merge” algorithm. This algorithm iteratively nudges a malleable graph structure towards a tree structure by selectively <italic>merging</italic> factors. The merging process is designed to avoid exponential blow-up by way of sparse structures from which redundancy is <italic>purged</italic> as the algorithm progresses. We set up tasks to test the algorithm on constraint-satisfaction puzzles such as Sudoku, Fill-a-pix, and Kakuro, and it outperformed other PGM-based approaches reported in the literature. While the tasks we set focussed on the binary logic of CSP, we believe the purge-and-merge algorithm could be extended to general PGM inference. |
|---|