Recursive Best-First AND/OR Search for Optimization in Graphical Models
Abstract
Best-first search algorithms, despite their better time efficiency than depth-first search, are largely ignored in practice primarily due to their inherently enormous memory requirements. We address this by developing RBFAOO, a recursive best-first AND/OR search algorithm with overestimation for optimization in graphical models. RBFAOO operates in linear space while avoiding excessive node re-expansions through a small overestimation parameter delta. We demonstrate that RBFAOO is very effective for pure MAP inference in graphical models.
Cite
Text
Kishimoto and Marinescu. "Recursive Best-First AND/OR Search for Optimization in Graphical Models." Conference on Uncertainty in Artificial Intelligence, 2014.Markdown
[Kishimoto and Marinescu. "Recursive Best-First AND/OR Search for Optimization in Graphical Models." Conference on Uncertainty in Artificial Intelligence, 2014.](https://mlanthology.org/uai/2014/kishimoto2014uai-recursive/)BibTeX
@inproceedings{kishimoto2014uai-recursive,
title = {{Recursive Best-First AND/OR Search for Optimization in Graphical Models}},
author = {Kishimoto, Akihiro and Marinescu, Radu},
booktitle = {Conference on Uncertainty in Artificial Intelligence},
year = {2014},
pages = {400-409},
url = {https://mlanthology.org/uai/2014/kishimoto2014uai-recursive/}
}