Strengthening Probabilistic Graphical Models: The Purge-and-Merge Algorithm
Simon Streicher, Johan A. du Preez · IEEE Access · 2021
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 [1, p391]. 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 [1, p336]. To address this, we developed the “purge-and-merge” algorithm. This algorithm iteratively nudges a malleable graph structure towards a tree structure by selectively merging factors. The merging process is designed to avoid exponential blow-up by way of sparse structures from which redundancy is purged as the algorithm progresses. We set up tasks to test the algorithm on constraint-satisfaction puzzles such as Sudoku, Fill-apix, and Kakuro, and it outperformed other PGM-based approaches reported in the literature [2]–[4]. 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.