MAP is the problem of finding a most probable instantiation of a set of variables given evidence. MAP has always been perceived to be significantly harder than the related problems of computing the probability of a variable instantiation Pr, or the problem of computing the most probable explanation (MPE). This paper investigates the complexity of MAP in Bayesian networks. Specifically, we show that MAP is complete for NP^PP and provide further negative complexity results for algorithms based on variable elimination. We also show that MAP remains hard even when MPE and Pr become easy. For example, we show that MAP is NP-complete when the networks are restricted to polytrees, and even then can not be effectively approximated. Given the difficulty of computing MAP exactly, and the difficulty of approximating MAP while providing useful guarantees on the resulting approximation, we investigate best effort approximations. We introduce a generic MAP approximation framework. We provide two instantiations of the framework; one for networks which are amenable to exact inference Pr, and one for networks for which even exact inference is too hard. This allows MAP approximation on networks that are too complex to even exactly solve the easier problems, Pr and MPE. Experimental results indicate that using these approximation algorithms provides much better solutions than standard techniques, and provide accurate MAP estimates in many cases.

研究了贝叶斯网络中 MAP 问题的复杂性，发现即使 MPE 和 Pr 可以轻松计算，MAP 仍然很难。为了找到一个接近最优解的算法，提出了一种通用的 MAP 近似框架，并给出了两个具体的实现，用于对那些即使 Pr 和 MPE 都难以计算的网络进行近似。实验结果表明，这些算法比标准技术提供更好的解决方案，并在许多情况下提供准确的 MAP 估计。

MAP解释的复杂性结果和逼近策略