On Heuristics for Finding Loop Cutsets in Multiply-Connected Belief Networks
This work addresses a specific computational bottleneck in probabilistic reasoning for AI, but it is incremental as it builds on prior heuristics without achieving a breakthrough.
The paper tackles the problem of finding minimum size loop cutsets in multiply connected belief networks by introducing a new heuristic algorithm, comparing it to an existing method, and providing lower bounds on performance, though it notes no heuristic can guarantee constant difference from optimal.
We introduce a new heuristic algorithm for the problem of finding minimum size loop cutsets in multiply connected belief networks. We compare this algorithm to that proposed in [Suemmondt and Cooper, 1988]. We provide lower bounds on the performance of these algorithms with respect to one another and with respect to optimal. We demonstrate that no heuristic algorithm for this problem cam be guaranteed to produce loop cutsets within a constant difference from optimal. We discuss experimental results based on randomly generated networks, and discuss future work and open questions.