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 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 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-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.
Code (1)
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Incremental Inference on Higher-Order Probabilistic Graphical Models Applied to Constraint Satisfaction Problems
Probabilistic graphical models (PGMs) are tools for solving complex probabilistic relationships. However, suboptimal PGM structures are primarily used in practice. This dissertation presents three contributions to the PG…
Land Cover ClassificationLeafy Spurge Dataset: Real-world Weed Classification Within Aerial Drone Imagery
Invasive plant species are detrimental to the ecology of both agricultural and wildland areas. Euphorbia esula, or leafy spurge, is one such plant that has spread through much of North America from Eastern Europe. When p…
On Neural Networks as Infinite Tree-Structured Probabilistic Graphical Models
Deep neural networks (DNNs) lack the precise semantics and definitive probabilistic interpretation of probabilistic graphical models (PGMs). In this paper, we propose an innovative solution by constructing infinite tree-…
Gaussian ProcessesMixed Nondeterministic-Probabilistic Automata: Blending graphical probabilistic models with nondeterminism
Graphical models in probability and statistics are a core concept in the area of probabilistic reasoning and probabilistic programming-graphical models include Bayesian networks and factor graphs. In this paper we develo…
Probabilistic ProgrammingPURGE: Projected Unlearning via Retain-Guided Erasure
We propose PURGE, a machine unlearning algorithm built on a simple but an under-exploited observation: continual learning (CL) and machine unlearning (MU) which are fundamentally dual problems. CL tries to learn new task…
Continual Learning