Probably Approximately Correct Maximum A Posteriori Inference
This addresses a fundamental bottleneck in probabilistic inference for AI/ML practitioners, offering rigorous guarantees where existing methods are heuristic or intractable.
The paper tackles the intractable problem of maximum a posteriori (MAP) inference in probabilistic models by introducing probably approximately correct (PAC) algorithms that provide provably optimal solutions under computational budgets, with experiments confirming benefits across benchmarks.
Computing the conditional mode of a distribution, better known as the $\mathit{maximum\ a\ posteriori}$ (MAP) assignment, is a fundamental task in probabilistic inference. However, MAP estimation is generally intractable, and remains hard even under many common structural constraints and approximation schemes. We introduce $\mathit{probably\ approximately\ correct}$ (PAC) algorithms for MAP inference that provide provably optimal solutions under variable and fixed computational budgets. We characterize tractability conditions for PAC-MAP using information theoretic measures that can be estimated from finite samples. Our PAC-MAP solvers are efficiently implemented using probabilistic circuits with appropriate architectures. The randomization strategies we develop can be used either as standalone MAP inference techniques or to improve on popular heuristics, fortifying their solutions with rigorous guarantees. Experiments confirm the benefits of our method in a range of benchmarks.