Global Sensitivity Analysis for MAP Inference in Graphical Models

Jasper De Bock, Cassio Polpo de Campos, Alessandro AntonucciNeurIPS 2014 · OpenReview

Overview

This paper introduces an exact, efficient algorithm to determine how "robust" a graphical model's most likely prediction (MAP) is to changes in its underlying parameters. By allowing all parameters to vary simultaneously—a "global" sensitivity analysis—the authors provide a measure ($\epsilon^*$) that strongly correlates with actual prediction accuracy across both facial recognition and standard machine learning benchmarks.

The Challenge of Parameter Sensitivity

Probabilistic Graphical Models (PGMs), like Bayesian Networks and Markov Random Fields, are workhorses for reasoning under uncertainty. However, they rely on numerical parameters (probabilities or weights) that are often "best guesses" derived from noisy data or subjective expert opinions.

The core question is: How much can these parameters wiggle before the model changes its mind?

Most existing research focuses on local sensitivity (changing one parameter at a time) or quantitative sensitivity (how much the output probability changes). This paper tackles global qualitative sensitivity: if we perturb all parameters at once, does the model still pick the same "most likely" configuration (the MAP inference)? Understanding this is crucial for high-stakes decision-making where we need to know if a conclusion is a solid result or a fragile artifact of slightly imprecise tuning.

Methodology

The authors propose an exact algorithm to verify the robustness of a MAP configuration.

  1. The Robustness Criterion: They define a model as "robust" if the MAP configuration remains the unique winner across all possible models within a specified "perturbation region."
  2. The "Second Best" Trick: The authors prove that checking for global robustness can be reduced to a comparison between the best MAP configuration and the second-best MAP configuration.
  3. Efficiency: The computational complexity of this check is roughly equivalent to the cost of performing the original MAP inference multiplied by the number of variables. In PGM terms, it is exponential in the "treewidth" of the graph, making it practical for many real-world architectures.
  4. Perturbation Types: They specialize the approach for two common PGM types:
  5. Markov Random Fields (MRFs): Using "rectangular" perturbations (adding/subtracting a small value $\Delta$ from factors).
  6. Bayesian Networks (BNs): Using "$\epsilon$-contamination," which models the true distribution as a mix of the estimated model and an unknown "noise" distribution.

Experimental Validation

The authors validated their approach on two distinct fronts:

  • Facial Action Unit (AU) Recognition: Using the CK+ (Cohn-Kanade) dataset. This involves predicting which facial muscles are moving (e.g., "cheek raiser" or "lip corner puller") based on 68 landmark positions on the face.
  • General Classification: They tested the algorithm on 18 different datasets from the UCI Machine Learning Repository, ranging from medical data (breast cancer, hypothyroid) to physical objects (autos, sonar).
Robustness across different emotions and facial examples

Key Insights and Results

  • Global > Local: The paper argues that local sensitivity analysis is insufficient. Small, simultaneous changes across multiple parameters can have "synergetic effects" that flip a model's decision, even if no single change is large enough to do so on its own.
  • Robustness as a Proxy for Accuracy: A major discovery is that the critical perturbation threshold ($\epsilon^*$)—the maximum amount of "wiggle room" before the MAP flips—is a powerful indicator of whether the model is actually right.
  • The "Surprise" Factor: In the facial expression experiments, the model was highly robust when identifying "surprise" (which has very distinct muscle movements) but much less robust when identifying "anger." This matches human intuition: some signals are clearer and more "stable" than others.
Correlation between robustness and prediction error
  • Strong Correlation: In the benchmarks, there was a clear, monotonic relationship between the robustness measure ($\epsilon^*$) and the average accuracy of the classifier (often measured inversely by Hamming distance). Instances where the model was "sure" (highly robust) were significantly more likely to be classified correctly.
  • Diagnostic Value: The algorithm calculates the exact threshold $\epsilon^*$, providing a "second-order" confidence score for every prediction the model makes.
  • Performance: Because the algorithm's complexity scales similarly to standard MAP inference, it can be integrated into existing PGM pipelines with minimal overhead.

Limitations and Future Work

  • Discrete Focus: The current work is limited to discrete PGMs. Extending this to continuous variables or hybrid models remains an open challenge.
  • "What Now?": While the paper provides an excellent way to detect a lack of robustness, it doesn't yet offer a formal method for fixing it. Future work could involve using these robustness insights to actively improve classification accuracy or to guide the elicitation of more precise parameters from experts.
  • Worst-Case Complexity: While efficient for many graphs, the algorithm still hits the "treewidth" bottleneck common in PGMs, meaning it may struggle with extremely dense, highly connected networks.

Summary updated

Abstract

We study the sensitivity of a MAP configuration of a discrete probabilistic graphical model with respect to perturbations of its parameters. These perturbations are global, in the sense that simultaneous perturbations of all the parameters (or any chosen subset of them) are allowed. Our main contribution is an exact algorithm that can check whether the MAP configuration is robust with respect to given perturbations. Its complexity is essentially the same as that of obtaining the MAP configuration itself, so it can be promptly used with minimal effort. We use our algorithm to identify the largest global perturbation that does not induce a change in the MAP configuration, and we successfully apply this robustness measure in two practical scenarios: the prediction of facial action units with posed images and the classification of multiple real public data sets. A strong correlation between the proposed robustness measure and accuracy is verified in both scenarios.
BibTeX
@inproceedings{bock2014global,
  author = {Jasper De Bock and Cassio Polpo de Campos and Alessandro Antonucci},
  title = {{Global Sensitivity Analysis for MAP Inference in Graphical Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=BkWo0vWdbB},
}
Figure