Variational Probabilistic Inference and the QMR-DT Network

Tommi S. Jaakkola, Michael I. Jordan

TL;DR

Exact Bayesian inference in large, densely connected diagnostic networks is notoriously intractable due to exponential state explosion. This paper introduces a deterministic variational approach based on convex duality and Jensen's inequality that transforms complex noisy-OR interactions into decoupled, linear forms—effectively "delinking" evidence nodes. By coupling these variational transformations with exact inference on a small subset of findings, the method provides real-time, highly accurate posterior marginals and likelihood bounds for the massive Quick Medical Reference (QMR-DT) network.

What Problem Does This Paper Address?

The Quick Medical Reference (QMR-DT) belief network is a large bipartite graphical model containing roughly 600 diseases and over 4,000 findings connected via noisy-OR distributions. While negative findings can be absorbed into disease priors in linear time, positive findings dramatically couple parent diseases:

  • Exact inference algorithms (e.g., junction trees) scale exponentially with the moralized graph's maximal clique size, which has a median of 151.5 nodes across standardized diagnostic cases.
  • Heckerman's Quickscore algorithm provides an exact factorization tailored to noisy-OR gates, but its run time scales exponentially with the number of positive findings. For realistic cases with ~36 positive findings, Quickscore would require an estimated average of 50 years per case.
  • Existing approximations (bounded conditioning, heuristic search, stochastic sampling) struggle: sampling methods frequently get trapped in spurious local modes or require excessive compute for clinical real-time diagnosis.

The challenge is designing an algorithm that delivers accurate posterior disease marginals in sub-second runtimes.

Methods

The authors develop a variational framework grounded in convex analysis to simplify the graph:

  • Convex Duality for Upper Bounds: The positive finding likelihood $P(f_i^+ | d) = 1 - e^{-(\theta_{i0} + \sum_j \theta_{ij} d_j)}$ has a concave exponent $f(x) = \log(1 - e^{-x})$. Using convex conjugate duality ($f(x) = \min_\xi \{ \xi x - f^*(\xi) \}$), the authors bound the conditional by an exponential function strictly linear in the disease states $d$.
  • Jensen’s Inequality for Lower Bounds: By viewing normalized combinations of disease inputs as probability distributions, Jensen’s inequality provides a decoupled lower bound that is also linear in the exponent.
  • Graphical "Delinking": Because both upper and lower bounds are linear in disease variables, incorporating them factorizes across diseases—effectively removing ("delinking") finding nodes and simply modulating disease priors.
  • Hybrid Exact/Variational Scheme: Transforming every node decouples the network completely. To balance speed and accuracy, the authors retain a small subset of critical findings for exact computation (via Quickscore) while variationally delinking the rest.
  • The $\delta$-Heuristic for Finding Selection: To decide which findings to treat exactly, the model first optimizes all variational parameters on the fully decoupled graph, then measures $\delta_i$ (the accuracy drop when approximating finding $i$). Findings with the largest $\delta_i$ are selected to be treated exactly.
  • Optimization: Upper bounds are proven strictly convex in variational parameters $\xi$ (optimized without local minima via Newton-Raphson or fixed-point updates). Lower bounds are maximized using the Expectation-Maximization (EM) algorithm.

Datasets

  • Clinicopathologic Conference (CPC) Cases: 48 clinically challenging, multiple-disease patient cases abstracted from the medical literature.
  • 4 Tractable Cases ($\le 20$ positive findings): Allowed full exact inference via Quickscore to serve as a rigorous gold standard.
  • 44 Intractable Cases ($> 20$ positive findings): Evaluated against a surrogate baseline constructed from two independent 400,000-sample runs of likelihood-weighted sampling filtered by the variational bounds (yielding 24 verified consistent cases).

Key Insights and Ideas

  • Law of Large Numbers in Dense Networks: Rather than summing over an astronomical state space, dense connectivity allows variational parameters to act as low-dimensional surrogates for high-dimensional interactions.
  • Variational Bounds as MCMC Diagnostics: Because upper and lower bounds on log-likelihood are mathematically rigorous, the authors discovered they could filter out sampling runs that diverged or trapped in spurious modes, creating a reliable surrogate baseline for otherwise unverifiable cases.
  • Hybridizing Approximation and Exact Methods: Variational methods do not need to replace exact inference entirely; instead, they act as graph simplifiers that peel away complexity until exact algorithms become tractable.

Key Results

  • Drastic Speedups on Tractable Cases:
  • Exact Quickscore: 26.9 seconds average runtime.
  • Variational inference (8 exact findings): 0.11 seconds (>200× faster).
  • Variational inference (12 exact findings): 0.85 seconds (>30× faster) with correlation to true posteriors $>0.98$.
  • Superior Diagnostic Ranking: On tractable cases, to recover the 20 most probable diseases, variational inference needed to inspect only the top 23 candidates, compared to $>50$ for a partially exact baseline and significantly fewer false positives than likelihood-weighted sampling run for over 6 seconds.
  • Scaling to Intractable Cases: On 24 intractable CPC cases, variational inference took 0.29 seconds per case and required reviewing the top 30 candidates to identify the top 20 diseases. In contrast, time-budgeted sampling (8.83 seconds per case) required searching the top 70 candidates.

Limitations and Future Work

  • Numerical Instability of the Exact Subroutine: Quickscore suffers catastrophic loss of numerical precision when evaluating more than ~16 positive findings, causing marginal interval bounds to become vacuous for nearly half of the diseases in large CPC cases.
  • One-Shot Parameter Optimization: In the interest of speed, variational parameters were optimized only once before greedily selecting exact nodes, leaving room for iterative refinement.
  • Future Directions: Combining variational bounds with search-based or bounded-conditioning methods, adopting numerically stable exact inference subroutines, and using variational posteriors to initialize MCMC samplers.

Summary updated

Abstract

We describe a variational approximation method for efficient inference in large-scale probabilistic models. Variational methods are deterministic procedures that provide approximations to marginal and conditional probabilities of interest. They provide alternatives to approximate inference methods based on stochastic sampling or search. We describe a variational approach to the problem of diagnostic inference in the `Quick Medical Reference' (QMR) network. The QMR network is a large-scale probabilistic graphical model built on statistical and expert knowledge. Exact probabilistic inference is infeasible in this model for all but a small set of cases. We evaluate our variational inference algorithm on a large set of diagnostic test cases, comparing the algorithm to a state-of-the-art stochastic sampling method.
BibTeX
@article{jaakkola1999variational,
  author = {Tommi S. Jaakkola and Michael I. Jordan},
  title = {{Variational Probabilistic Inference and the QMR-DT Network}},
  journal = {J. Artif. Intell. Res.},
  year = {1999},
  url = {https://openreview.net/forum?id=OVAP6l9-0Dc},
}

Loading related content...

Figure