MAP is the problem of finding a most probable instantiation of a set of
variables in a Bayesian network given some evidence. Unlike computing posterior
probabilities, or MPE (a special case of MAP), the time and space complexity of
structural solutions for MAP are not only exponential in the network treewidth,
but in a larger parameter known as the "constrained" treewidth. In practice,
this means that computing MAP can be orders of magnitude more expensive than
computing posterior probabilities or MPE. This paper introduces a new, simple
upper bound on the probability of a MAP solution, which admits a tradeoff
between the bound quality and the time needed to compute it. The bound is shown
to be generally much tighter than those of other methods of comparable
complexity. We use this proposed upper bound to develop a branch-and-bound
search algorithm for solving MAP exactly. Experimental results demonstrate that
the search algorithm is able to solve many problems that are far beyond the
reach of any structure-based method for MAP. For example, we show that the
proposed algorithm can compute MAP exactly and efficiently for some networks
whose constrained treewidth is more than 40.

该论文介绍了一种新的、简单的 MAP 解的概率上限，并使用该上限提出了一种分支定界搜索算法，能够准确高效地解决一些网络的 MAP 问题，这些网络的约束树宽度超过了 40。