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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Simon Streicher, Johan A. Du Preez
Formato:	article
Lenguaje:	EN
Publicado:	IEEE 2021
Materias:	Probabilistic graphical model probabilistic reasoning belief propagation cluster graph sudoku constraint-satisfaction problem Electrical engineering. Electronics. Nuclear engineering TK1-9971
Acceso en línea:	https://doaj.org/article/8db894f4a89a4f99b9f59e778cd426a1
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:8db894f4a89a4f99b9f59e778cd426a1
record_format	dspace
spelling	oai:doaj.org-article:8db894f4a89a4f99b9f59e778cd426a12021-11-18T00:03:33ZStrengthening Probabilistic Graphical Models: The Purge-and-Merge Algorithm2169-353610.1109/ACCESS.2021.3124760https://doaj.org/article/8db894f4a89a4f99b9f59e778cd426a12021-01-01T00:00:00Zhttps://ieeexplore.ieee.org/document/9598901/https://doaj.org/toc/2169-3536Probabilistic 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.Simon StreicherJohan A. Du PreezIEEEarticleProbabilistic graphical modelprobabilistic reasoningbelief propagationcluster graphsudokuconstraint-satisfaction problemElectrical engineering. Electronics. Nuclear engineeringTK1-9971ENIEEE Access, Vol 9, Pp 149423-149432 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Probabilistic graphical model probabilistic reasoning belief propagation cluster graph sudoku constraint-satisfaction problem Electrical engineering. Electronics. Nuclear engineering TK1-9971
spellingShingle	Probabilistic graphical model probabilistic reasoning belief propagation cluster graph sudoku constraint-satisfaction problem Electrical engineering. Electronics. Nuclear engineering TK1-9971 Simon Streicher Johan A. Du Preez Strengthening Probabilistic Graphical Models: The Purge-and-Merge Algorithm
description	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.
format	article
author	Simon Streicher Johan A. Du Preez
author_facet	Simon Streicher Johan A. Du Preez
author_sort	Simon Streicher
title	Strengthening Probabilistic Graphical Models: The Purge-and-Merge Algorithm
title_short	Strengthening Probabilistic Graphical Models: The Purge-and-Merge Algorithm
title_full	Strengthening Probabilistic Graphical Models: The Purge-and-Merge Algorithm
title_fullStr	Strengthening Probabilistic Graphical Models: The Purge-and-Merge Algorithm
title_full_unstemmed	Strengthening Probabilistic Graphical Models: The Purge-and-Merge Algorithm
title_sort	strengthening probabilistic graphical models: the purge-and-merge algorithm
publisher	IEEE
publishDate	2021
url	https://doaj.org/article/8db894f4a89a4f99b9f59e778cd426a1
work_keys_str_mv	AT simonstreicher strengtheningprobabilisticgraphicalmodelsthepurgeandmergealgorithm AT johanadupreez strengtheningprobabilisticgraphicalmodelsthepurgeandmergealgorithm
_version_	1718425237910978560

Strengthening Probabilistic Graphical Models: The Purge-and-Merge Algorithm

Ejemplares similares