Robustness Guarantees for Credal Bayesian Networks via Constraint Relaxation over Probabilistic Circuits
This work addresses robustness guarantees for decision-making in uncertain environments, offering a scalable solution but is incremental as it builds on existing credal network and probabilistic circuit methods.
The paper tackles the problem of quantifying worst-case performance guarantees for decision functions under distributional shifts using credal Bayesian networks, developing a method that provides a guaranteed upper bound on maximum marginal probability in linear time and shows near-tight results with improved scalability in experiments.
In many domains, worst-case guarantees on the performance (e.g., prediction accuracy) of a decision function subject to distributional shifts and uncertainty about the environment are crucial. In this work we develop a method to quantify the robustness of decision functions with respect to credal Bayesian networks, formal parametric models of the environment where uncertainty is expressed through credal sets on the parameters. In particular, we address the maximum marginal probability (MARmax) problem, that is, determining the greatest probability of an event (such as misclassification) obtainable for parameters in the credal set. We develop a method to faithfully transfer the problem into a constrained optimization problem on a probabilistic circuit. By performing a simple constraint relaxation, we show how to obtain a guaranteed upper bound on MARmax in linear time in the size of the circuit. We further theoretically characterize this constraint relaxation in terms of the original Bayesian network structure, which yields insight into the tightness of the bound. We implement the method and provide experimental evidence that the upper bound is often near tight and demonstrates improved scalability compared to other methods.