The Theory and Practice of MAP Inference over Non-Convex Constraints

In many safety-critical settings, probabilistic ML systems have to make predictions subject to algebraic constraints, e.g., predicting the most likely trajectory that does not cross obstacles. These real-world constraints are rarely convex, nor the densities considered are (log-)concave. This makes computing this constrained maximum a posteriori (MAP) prediction in an efficient and reliable way extremely challenging. In this paper, we first investigate under which conditions we can perform constrained MAP inference over continuous variables exactly and efficiently and devise a scalable message-passing algorithm for this tractable fragment. Then, we devise a general constrained MAP strategy that interleaves partitioning the domain into convex feasible regions with numerical constrained optimization. We evaluate both methods on synthetic and real-world benchmarks, showing our structure aware approach outperforms constraint-agnostic baselines.

In real-world applications, machine-learning predictions often need to satisfy rules or physical constraints. For example, a predicted pedestrian trajectory should not pass through obstacles. A common prediction strategy in machine-learning is to choose the single most likely outcome, known as the maximum a posteriori (MAP) prediction. In this work, we study how to compute these most-likely predictions while ensuring that such rules are never violated. We identify cases in which the optimal prediction can be found efficiently and exactly, and for more general settings we develop an algorithm that can closely approximate the optimal prediction while still guaranteeing that all constraints are satisfied.