Certified Parameter Tuning When Exact Inference Is Out of Reach

A Bayesian network, or more generally a probabilistic graphical model, is a large table-driven probability model whose numbers are usually elicited from experts or estimated from sparse data. A common practical question is parameter tuning: what is the smallest change to those numbers that makes the model agree with a requirement such as "given these symptoms, the probability of disease $h$ should be at least 0.95"? The tools that answer this question well differentiate exact inference with respect to every parameter, then use the derivatives to find the required change. Exact inference, however, becomes infeasible on densely connected models. The obvious fix is to tune through a fast approximate engine such as loopy belief propagation. That fix can make the threshold hold for the approximation while it fails for the true model, and nothing in the procedure will reveal the failure.

We propose to tune against a quantity that is both differentiable and guaranteed to lie below the true posterior. That quantity is the ratio of a variational lower bound on $Pr(h, \mathbf{e})$ to a tree-decomposition upper bound on $Pr(\mathbf{e})$. Each bound can be computed by message passing and differentiated by backpropagation. Pushing this certified lower bound past the threshold gives a parameter change that provably satisfies the requirement in the true model, even though the true posterior is never computed. Complexity theory says the method cannot be complete, so it will sometimes fail to find changes that exist. It is sound by construction. The empirical question is how often it succeeds and at what cost in model disturbance relative to exact tuning.

Core Claim

Multi-parameter tuning on networks too wide for exact compilation can be made sound: whenever the method declares success, the true model meets the constraint. The method optimizes a differentiable certified lower bound on the target posterior. When the bound is too loose, it is tightened by conditioning on a few variables, chosen by the bound's own derivatives. Concretely, let $\theta$ be the network parameters and $\theta_0$ the original values. Let $M(\theta)$ be any mean-field lower bound on $\log Pr(h,\mathbf{e})$, and let $U(\theta)$ be an upper bound on $\log Pr(\mathbf{e})$ obtained by splitting the model's factors across tractable subgraphs and summing their exact log-partition functions. We solve

$$ \min_{\theta}\; D(\theta, \theta_0) \quad \text{subject to} \quad L(\theta) = \exp\big(M(\theta) - U(\theta)\big) \ge T, $$

where $D$ is the log-odds disturbance distance of Sensitivity Analysis in Bayesian Networks: From Single to Multiple Parameters and $T$ is the target probability. Because $L(\theta) \le Pr(h \mid \mathbf{e};\theta)$ at every iterate, any feasible point is a certified solution. This holds at every iterate, not just at convergence: the mean-field value is a lower bound for any variational distribution, and the subgraph bound holds for any valid split of the factors.

What is new is the target of the gradient. Prior work differentiates either exact inference or an uncertified approximation. We differentiate a two-sided certificate, so the tuned model's guarantee holds for the true model.

Why This Gap Exists

The exact derivative machinery is mature. A Differential Approach to Inference in Bayesian Networks represents the evidence probability as a polynomial compiled into an arithmetic circuit, a graph of sums and products that yields all parameter derivatives in one backward pass. It also solves single-parameter tuning in constant time after compilation. A Differential Semantics for Jointree Algorithms and Making Sensitivity Analysis Computationally Efficient show that junction-tree message passing computes the same derivatives. Chan and Darwiche extend tuning to multiple parameters with the log-odds distance. All of these methods supply the objective and the derivative idea we reuse, and all of them stop where exact inference stops. Compiling Bayesian Networks Using Variable Elimination pushes that boundary far by exploiting determinism. Even so, high treewidth without local structure, as in Ising-like grids or dense diagnostic networks, still exhausts memory.

Two papers constrain the design. The Computational Complexity of Sensitivity Analysis and Parameter Tuning proves that tuning is $NP^{PP}$-complete, and that it stays hard on polytrees and in restricted variants. The consequence is that simplifying the graph cannot rescue completeness, and any polynomial method must give up either soundness or completeness. We choose to keep soundness. Hardness of parameter estimation in graphical models shows that the inverse map from marginals to parameters is NP-hard even in realizable cases. This warns that gradient methods on these landscapes have no global guarantees, so we claim only that feasible points are sound, not that they are optimal.

Two papers supply the mechanism. Empirical Risk Minimization of Graphical Model Parameters Given Approximate Inference, Decoding, and Model Structure and Learning Graphical Model Parameters with Approximate Marginal Inference backpropagate through truncated loopy belief propagation, mean field, and tree-reweighted propagation in order to fit parameters to labeled data. They optimize prediction loss, not posterior constraints. Their gradients are gradients of the approximation, with no statement about the true model. We take their differentiation technique and replace the objective with a certified bound.

Research Program

The first component builds the certificate. For Bayesian networks with evidence and for the pairwise UAI models, we write the model as a factor graph. The lower bound $M$ comes from structured mean field: a fully factorized distribution, or one that is tractable over chains, fitted to the clamped model with $h$ and $\mathbf{e}$ fixed. The upper bound $U$ splits the log-factors across a weighted collection of tractable subgraphs, each solved exactly by variable elimination at low treewidth. The split weights are optimized alongside $\theta$, since any valid split gives a bound. Both bounds are differentiated end to end with respect to $\theta$, using the unrolling of the Stoyanov and Domke papers or implicit differentiation at fixed points. We compare the two differentiation schemes on gradient stability.

The second component tightens the bound. When $L(\theta)$ stalls below $T$, we condition on a small set $C$ of variables, which turns the certificate into a sum over branches:

$$ L_C(\theta) = \frac{\sum_{c} \exp M_c(\theta)}{\sum_{c} \exp U_c(\theta)}. $$

Here $M_c$ and $U_c$ are the bounds with $C$ clamped to $c$. The bound remains valid, and it becomes exact as $C$ grows to a cutset, a set of variables whose removal leaves a tractable graph. We choose the next variable to condition on by the derivative of the gap $U - M$ with respect to each variable's single-node marginal. This uses sensitivity to decide where certification effort goes, much as Expert System Consultation Control Strategy used gradients to decide which question to ask.

The third component is the optimizer. We parameterize each CPT row in log-odds, so the disturbance $D$ is smooth. We then solve the constrained problem with an augmented Lagrangian, warm-started from the ranking of parameters by first-order sensitivity, as Chan and Darwiche do for choosing which CPTs to tune.

The fourth component is analysis. We characterize when the method must fail. If the gap between the bounds exceeds $\log(1/T)$ for every reachable parameter setting with a given conditioning budget, then certification is impossible within that budget. We measure this gap as a function of coupling strength. This yields an empirical map of the regime where certified tuning is practical, set alongside the worst-case hardness of Kwisthout and van der Gaag.

Baselines

The naive reference point is single-parameter tuning with derivatives from loopy belief propagation. It applies Darwiche's closed-form single-parameter solution, but uses approximate rather than exact derivatives and then accepts the result. It represents what a practitioner would try first. We count how often it returns an answer and how often that answer is true under exact evaluation.

The strongest competitor in the high-treewidth regime is uncertified multi-parameter tuning through unrolled loopy belief propagation. It uses the differentiation of the Stoyanov paper, with the same log-odds objective and the same augmented Lagrangian, but applies the constraint to the belief-propagation posterior. It is the strongest competitor because it uses the same gradient information our method uses, at lower cost, and it will usually reach smaller disturbances because its constraint is not conservative. No reported result was found on Lacuna for query-constrained tuning through belief propagation. The Stoyanov paper reports only that training through ten iterations of belief propagation reduced test loss by "an order of magnitude" on its synthetic models, which is a learning result rather than a tuning result. Our method beats this competitor if it reaches a zero false-success rate under exact checking while staying within a stated factor of its disturbance and success rate. A competitor with many false successes loses on the criterion that matters.

The gold standard where it exists is exact multi-parameter tuning on a compiled circuit or junction tree, following Chan and Darwiche. On the fire/alarm example they report a disturbance distance of 0.995 for the best single-parameter change versus 0.445 for a multi-parameter change within one CPT. We reproduce that example as a sanity check. On networks that compile, this baseline gives the optimal disturbance, and we report our excess disturbance relative to it.

The key ablation keeps every other component fixed and replaces the certificate $L$ with the belief-propagation point estimate, which isolates the effect of certification. A second ablation conditions on randomly chosen variables rather than gradient-chosen ones, which isolates the sensitivity-guided tightening. All methods receive the same evidence and target queries, the same wall-clock budget per query, and the same number of optimizer restarts.

Why not just…?

Why not just tune through loopy belief propagation and accept the answer? When belief propagation is accurate, this works, and it is cheaper. The danger lies where accuracy is unknown. The Stoyanov and Domke papers show that belief-propagation parameters can be tuned to compensate for the engine's biases, so the threshold may be met by the approximation while the true posterior stays below it. This is a real threat to our method's usefulness on weakly coupled models. The ablation settles it: we sweep coupling strength on grids small enough for exact evaluation and report where belief-propagation tuning starts producing false successes. If it never does on realistic networks, our contribution narrows to a guarantee that costs disturbance, and we will say so.

Why not just compile the network exactly and use Chan and Darwiche? Wherever compilation succeeds, one should do exactly that. The Chavira and Darwiche paper reports gains such as 17 seconds down to 82 milliseconds on st-3-2, and circuits up to 5,000 times smaller on deterministic networks. Our claim is limited to models without such local structure, and we use compilable networks only to measure how far our solutions sit from the exact optimum.

Why not just search with finite differences or importance-reweighted samples? Finite differences need repeated inference runs per parameter, which Making Sensitivity Analysis Computationally Efficient calls prohibitive on realistic networks even when exact inference is available. Sample-based reweighting in the style of Detecting and diagnosing prior and likelihood sensitivity with power-scaling gives estimates with no one-sided guarantee, and it degrades under determinism, according to Approximate Inference in Probabilistic Graphical Models with Determinism. We include a sampling-based tuner with the same time budget and report its false-success rate.

Why not just thin the graph to bounded treewidth first? Kwisthout and van der Gaag show that tuning stays $NP^{PP}$-complete on polytrees, so thinning does not remove the hardness. It also changes the model whose posterior we were asked to constrain. A constraint met on a thinned approximation carries no guarantee for the original model, which is the same flaw as tuning through belief propagation.

Proposed Experiments

The first experiment validates the method where exact inference is still feasible. We use alarm, pigs, water, and munin from the Chavira and Darwiche study, together with the pregnancy diagnostic model, for which Chan and Darwiche raised a positive-test probability to 95% by adjusting two rates. We pose random evidence sets and thresholds that require changes to several CPTs. Every returned solution is checked by exact circuit evaluation, and we report success rate, false-success rate, and excess disturbance over the exact optimum.

The second experiment is a controlled sweep. We use Ising-style grids with side lengths running from sizes solvable by variable elimination up to sizes that are not, and we vary coupling strength. This traces the bound gap and the certification rate as treewidth and coupling grow, and it compares the false-success rates of our method and the belief-propagation tuner where exact checking remains possible.

The third experiment is the target regime. We use the high-treewidth UAI competition models: the 14-model set of Learning to Condition: A Neural Heuristic for Scalable MPE Inference and the 25-model Promedas, pedigree, and grid set of Learning to Guide Local Search for MPE Inference in Probabilistic Graphical Models. These papers report MPE search results, not tuning results, so they provide the models but not a number to beat. Here exact checking is unavailable, so we report certification rate, disturbance, the number of conditioned variables needed, and runtime. On the subset where long exact runs with cutset conditioning finish, we spot-check soundness.

Three outcomes would decide the proposal. It succeeds if certified tuning reaches a substantial fraction of the success rate of uncertified belief-propagation tuning on the UAI models, at bounded extra disturbance. It is supported if belief-propagation tuning shows non-trivial false-success rates on the strongly coupled grids. It fails, and the idea should be abandoned or reframed, if either the bound gap makes certification essentially impossible at realistic coupling strengths, or belief-propagation tuning turns out to be almost never wrong where we can check.