Speeding up approximate MAP by applying domain knowledge about relevant variables
This work addresses the intractable MAP problem in Bayesian networks, but it is incremental as it builds on prior heuristic methods without clear performance gains.
The study investigated whether using domain knowledge to identify relevant variables in Bayesian networks speeds up approximate MAP computation, but found inconclusive results that depend on query specifics like the number of MAP variables.
The MAP problem in Bayesian networks is notoriously intractable, even when approximated. In an earlier paper we introduced the Most Frugal Explanation heuristic approach to solving MAP, by partitioning the set of intermediate variables (neither observed nor part of the MAP variables) into a set of relevant variables, which are marginalized out, and irrelevant variables, which will be assigned a sampled value from their domain. In this study we explore whether knowledge about which variables are relevant for a particular query (i.e., domain knowledge) speeds up computation sufficiently to beat both exact MAP as well as approximate MAP while giving reasonably accurate results. Our results are inconclusive, but also show that this probably depends on the specifics of the MAP query, most prominently the number of MAP variables.