AND/OR cutset conditioning
Robert Mateescu, Rina Dechter · International Joint Conference on Artificial Intelligence · 2005
Cutset conditioning is one of the methods of solving reasoning tasks for graphical models, especially when space restrictions make inference (e.g., jointree-clustering) algorithms infeasible. The w-cutset is a natural extension of the method to a hybrid algorithm that performs search on the conditioning variables and inference on the remaining problems of induced width bounded by w. This paper takes a fresh look at these methods through the spectrum of AND/OR search spaces for graphical models. The resulting AND/OR cutset method is a strict improvement over the traditional one, often by exponential amounts.