Probabilistic graphical models encode knowledge in tables of numbers: conditional probabilities in a Bayesian network, or clique "potentials" (non-negative compatibility scores) in a Markov network. When a deployed model gives an answer an expert believes is wrong, for example a diagnosis probability of 0.79 where it should be at least 0.9, the modeller wants the smallest set of edits to those tables that fixes the answer. This inverse problem is called parameter tuning. The theory says it is hopeless in general. It is NP^PP-complete, and it stays that way even on polytrees, the simplest multiply-parented networks where ordinary inference takes linear time (Kwisthout & van der Gaag). The practical tools, meanwhile, give closed-form answers only when a single parameter or a single clique is changed (Darwiche; Chan & Darwiche). Real fixes usually need small coordinated changes spread across many tables, and no method sits in that space.
We propose an algorithm for Markov networks of tractable treewidth, which is exactly the regime where the hardness result still bites. The algorithm tunes many cliques at once. Every iterate is guaranteed to satisfy the target constraint, the size of the edit never increases from one iterate to the next, and the output comes with a cheap certificate of how far it could be from the best possible edit. The mechanism rests on two observations. First, measured in log-potentials, the tuning constraint is a difference of two convex functions, so a convex–concave procedure (repeatedly replacing the troublesome convex term by its tangent line) yields conservative convex subproblems. Second, the tangent it needs is a vector of clique marginals. A single inward/outward jointree pass returns those marginals as the exact derivative of the network polynomial (Park & Darwiche). Hardness is not contradicted. We give up global optimality, and in exchange we get monotone, always-feasible progress and an explicit optimality gap.
Core Claim
Write the Markov network with log-potentials $\eta = (\eta_c)_c$, one entry per clique configuration. Let $L_{y}(\eta) = \log \sum_{x \models y,\mathbf{e}} \exp \sum_c \eta_c(x_c)$ be the log-mass of configurations agreeing with the query value $y$ and evidence $\mathbf{e}$, and let $L_{\bar y}(\eta)$ be the same quantity for configurations that agree with $\mathbf{e}$ but not with $y$. The target $Pr(y\mid\mathbf{e}) \ge \gamma$ is then equivalent to $L_y(\eta) - L_{\bar y}(\eta) \ge \log\frac{\gamma}{1-\gamma}$. Both $L$ terms are log-sum-exp functions of $\eta$, so both are convex, and the constraint set is their difference, which is not convex.
As the edit cost we use the Chan–Darwiche local distance $D_c(\eta_c) = \max(\eta_c - \eta_c^0) - \min(\eta_c - \eta_c^0)$. This is the quantity their global-to-local theorem equates with the global distribution change when only clique $c$ is edited (Chan & Darwiche), and it is convex and piecewise linear in $\eta_c$. At iterate $\eta^k$, the procedure replaces $L_y$ by its tangent. That tangent lies below $L_y$ everywhere, so any point satisfying the linearized constraint also satisfies the true one. The subproblem is:
$$\eta^{k+1} = \arg\min_{\eta} \sum_c D_c(\eta_c) \quad \text{s.t.} \quad L_{\bar y}(\eta) \le L_y(\eta^k) + \mu_y^k \cdot (\eta - \eta^k) - \log\tfrac{\gamma}{1-\gamma},$$
where $\mu_y^k$ is the vector of clique marginals conditioned on $y$ and $\mathbf{e}$ at $\eta^k$, which is exactly $\nabla L_y(\eta^k)$. The subproblem is convex. Each evaluation of $L_{\bar y}$ and its gradient inside the solver costs one jointree pass. The standard convex–concave argument then gives that, once started from a feasible point, all iterates stay feasible and the objective is non-increasing.
The certificate comes from subadditivity. The global distance between the original and tuned networks is at most $\sum_c D_c$, because the maximum of a sum is at most the sum of the maxima, and likewise for the minima. The global distance in turn bounds the change in log-odds of any conditional query. It follows that every feasible tuning must pay at least $\log\frac{\gamma}{1-\gamma} - \log\frac{Pr(y\mid\mathbf{e})}{1-Pr(y\mid\mathbf{e})}$. Comparing our objective with this floor gives a reported optimality ratio at essentially zero cost.
Relation to Prior Work
Four lines of work bear on this proposal, and each plays a different role.
The differential-inference line supplies the gradient engine. Darwiche compiles inference into an arithmetic circuit and reads off all partial derivatives in one backward sweep. Park & Darwiche show the Shenoy–Shafer outward pass computes these same derivatives. Sato gives the matching inside–outside reading of belief propagation. We reuse these results unchanged. None of these papers turns the gradient into a multi-parameter tuning procedure, and all of them solve tuning only for a single parameter.
The single-clique tuning line motivates the gap. Chan & Darwiche give exact minimal changes for one clique and state that disjoint multi-clique tuning is unresolved. Kjærulff & van der Gaag obtain joint sensitivity functions efficiently only when all parameters lie in one clique. Our method is not restricted to one clique, and its single-clique special case must reproduce their closed form.
The complexity results constrain the design. Kwisthout & van der Gaag rule out any polynomial algorithm that is exact and global, even at treewidth one. For that reason we claim only local optimality with a computed gap, and we treat instances where that gap is large as the expected signature of the hardness.
Robustness detection is complementary rather than competing. Liu et al. compute the perturbation radius at which a MAP answer flips, using the best versus second-best assignment, but offer no repair. Robust Inference with Variational Bayes differentiates a mean-field surrogate rather than the true model. Our gradients are exact for the model being tuned.
Research Program
The first component is the algorithm for Markov networks with exact jointrees. It needs a feasible starting point. We obtain one from the best single-clique closed-form fix (Chan & Darwiche), or, when no single clique can reach the target, from a large uniform shift along the gradient direction.
The second component is theory, which we will prove:
- subadditivity of $\sum_c D_c$;
- monotone feasibility of the iterates;
- the lower-bound certificate;
- a characterization of when the procedure is exactly optimal. Our conjecture is that it is exactly optimal when the edited cliques are separated by evidence.
The third component, treated as secondary, is an extension to Bayesian networks. Column normalization breaks the clean difference-of-convex form there, so we will use a sequential convex approximation that explicitly checks feasibility at each step, and we will report it separately. Extending the method to high-treewidth models by differentiating approximate clique-tree sequences such as IBIA is out of scope. We note it only as the natural next step.
Baselines
The naive reference point is the best single-clique edit. For each clique that can reach the target alone, we compute the exact Chan–Darwiche minimal change and keep the cheapest one. This answers whether spreading an edit across cliques buys anything at all. We beat it if the multi-clique objective is strictly smaller on a meaningful fraction of instances, and if we solve the instances where no single clique suffices.
The second baseline is greedy sequential single-clique tuning. It repeatedly applies the cheapest single-clique step toward the target, which is the natural reading of the "tune few parameters" advice in Kwisthout & van der Gaag.
The strongest competitor is generic autodiff optimization. It uses the same exact gradients through the same jointree, minimizes $\sum_c D_c$ plus a penalty or augmented-Lagrangian term for the constraint, and runs projected Adam or a sequential quadratic programming solver. It will receive the same number of jointree passes as our method and a hyperparameter search over penalty weights and step sizes. We beat it if, at equal pass budgets, we match or lower its objective while it returns infeasible or penalty-sensitive solutions.
For ground truth on small instances, we solve the nonconvex program by exhaustive multistart or spatial branch-and-bound. This measures our true optimality gap, and we check it against the cheap certificate.
Two ablations isolate the key ingredients. The first replaces the conservative tangent step with an unguarded linearization, which isolates the feasibility guarantee. The second swaps $D_c$ for squared Euclidean change, which tests whether the distance choice matters for the downstream check described in the decisive checks below.
On reported numbers: the only reported tuning result in the file is the Chan–Darwiche toy network. There, $Pr(\bar a_2\mid a_1)$ is raised from 0.789 to at least 0.9 by reducing a single potential from 2 to 0.533 (Chan & Darwiche). No reported result was found on Lacuna for multi-parameter or multi-clique tuning on any benchmark.
Why not just…?
Why not just run projected gradient descent with autodiff on a penalized objective? This is the real threat, since it uses the same gradient source we do. Its weaknesses are specific. A penalty method gives no feasibility guarantee at any finite penalty. It is sensitive to the penalty weight. The nonsmooth $D_c$ objective slows first-order methods. Our procedure removes the penalty weight entirely and guarantees feasibility at every step. If the tuned autodiff baseline reaches the same objective in the same number of passes with no infeasible outputs, then our contribution shrinks to the certificate and the guarantees, and we will report that. The equal-budget comparison is designed to settle this question.
Why not just tune one parameter or one clique at a time? Single-clique fixes are exact and cheap (Darwiche; Chan & Darwiche). However, they either concentrate a large distortion in one table or fail outright when no single clique carries enough leverage. Greedy chaining of such fixes has no optimality account. Both are included as baselines, and the gap between their cost and our certificate floor quantifies what they leave on the table.
Why not just solve tuning exactly with a global solver? The problem is NP^PP-hard even on polytrees (Kwisthout & van der Gaag). We run such solvers only on small instances, as ground truth, and we plot runtime against clique count to locate the point where they stop being usable.
Why not just differentiate a mean-field or loopy-belief-propagation surrogate? Mean-field derivatives inherit the surrogate's bias under strong coupling (Robust Inference with Variational Bayes). Loopy belief propagation may not converge (IBIA). Either way, a tuning that looks feasible under the surrogate may not be feasible in the true model. In the regime we target, exact inference is affordable, so this compromise is unnecessary.
Proposed Experiments
The sanity check is the Chan–Darwiche four-variable network. Restricted to one clique, our method must reproduce the change from 2 to 0.533. With all cliques allowed, we report whether a lower total distance exists.
The main study uses Markov network and grid instances from the UAI/PIC suites, including the GridBN family, whose treewidth admits exact jointrees. We generate query–evidence–target triples by pushing a posterior to a set margin beyond its current value. For each triple, we report four quantities: the fraction of runs returning a feasible edit; the objective $\sum_c D_c$; the ratio of that objective to the certificate floor; and the number of jointree passes used. The secondary study applies the Bayesian-network extension to Bnlearn networks and Munin, the medical networks that motivated Kjærulff & van der Gaag.
There are three decisive checks. The first is whether the certificate ratio stays near one on evidence-separated edits and grows on tightly coupled ones, as the hardness result predicts. The second is whether our method beats the tuned autodiff baseline on feasibility at equal budget. The third is downstream. On the UCI classifiers used by Liu et al., we check whether tunings that minimize the Chan–Darwiche distance leave unrelated MAP predictions more robust, measured by their critical perturbation radius $\epsilon^*$, than Euclidean-minimal tunings do. This third check is the evidence that the choice of distance matters in practice and not only on paper.
References
- The Computational Complexity of Sensitivity Analysis and Parameter Tuning
- A Differential Approach to Inference in Bayesian Networks
- Sensitivity Analysis in Markov Networks
- A Differential Semantics for Jointree Algorithms
- Inside-Outside Probability Computation for Belief Propagation
- Making Sensitivity Analysis Computationally Efficient
- Global Sensitivity Analysis for MAP Inference in Graphical Models
- Robust Inference with Variational Bayes
- Approximate inference of marginals using the IBIA framework
- IBIA: An Incremental Build-Infer-Approximate Framework for Approximate Inference of Partition Function