Order Statistics for Probabilistic Graphical Models

David B. Smith, Sara Rouhani, Vibhav GogateIJCAI 2017 · OpenReview

TL;DR

This paper introduces the problem of "r-th order statistics" for probabilistic graphical models (PGMs), which involves finding assignments with a specific rank (e.g., the 5th most probable assignment). They prove this problem is NP-hard even for simple models and develop novel pseudo-polynomial time approximation algorithms that outperform traditional sampling methods, especially for less extreme ranks.

What Problem Does This Paper Address?

Probabilistic graphical models (PGMs) are powerful tools for representing complex probability distributions over many variables. While tasks like finding the most probable assignment (MAP estimation) are well-studied, this paper tackles a more general query: finding the r-th most probable assignment. This is akin to asking for the 5th, 10th, or 100th most likely configuration of variables in a system. Such queries are valuable for understanding the shape of a distribution, generating diverse explanations, and enabling interactive model exploration. The authors highlight that existing work on this problem is limited, and they aim to provide both theoretical complexity analysis and practical algorithms.

Methods

The core of the paper's contribution lies in its theoretical analysis and algorithmic development.

  • NP-Hardness Proof: They prove that computing the r-th order statistic is NP-hard, even for "zero-treewidth" models (where variables are independent). This is achieved through a reduction from the well-known Number Partitioning Problem.
  • Pseudo-Polynomial Time Approximation for Zero-Treewidth Models: Leveraging the pseudo-polynomial time algorithms for Number Partitioning, they develop an approximation algorithm for zero-treewidth models. This algorithm is efficient in terms of the magnitude of the numbers involved, rather than just the number of variables.
  • Generalization to Tree-Decompositions: To extend their approach to general graphical models (which can have complex dependencies), they generalize their algorithm to work with tree decompositions. This is a non-trivial extension because r-th order statistics operators are not associative like standard max or sum operations.
  • Rank Variable Elimination (RVE): They introduce a novel algorithm called Rank Variable Elimination (RVE), which adapts the standard Variable Elimination algorithm (used for MAP inference) to handle order statistics. RVE uses "rank potentials" and "binning functions" to group assignments with similar probabilities, allowing it to retain order statistics information that is typically discarded by standard VE.

Datasets

The paper evaluates their algorithms on several benchmark datasets:

  • NLTCS
  • KDD Cup
  • Plants

These datasets are used to learn Chow-Liu trees (a specific type of graphical model) for evaluating the "Infer Rank of an Assignment" query. For the "Infer Assignment given a Rank" query, they use synthetic models with varying numbers of edges.

Key Insights and Ideas

  • The "Long Tail" Problem: The paper reveals that finding assignments with specific ranks is hard, even when variables are independent. This suggests that understanding the full probability distribution, not just the most probable parts, is crucial.
  • Bridging Number Partitioning and PGMs: The reduction from the Number Partitioning Problem to r-th order statistics in zero-treewidth models is a clever theoretical link that enables practical algorithmic solutions.
  • RVE's Novelty: The Rank Variable Elimination algorithm is a significant advancement. By adapting the well-established Variable Elimination framework to track probability ranges (bins) instead of just single values, it can efficiently estimate ranks and find assignments of a given rank.
  • Sampling vs. RVE: The experimental results highlight a key trade-off: sampling methods perform reasonably well for extreme ranks (very high or very low probability) but struggle in the middle of the distribution. RVE, on the other hand, offers more consistent accuracy across the entire rank spectrum, especially for less extreme ranks.

Key Results

  • NP-Hardness: The r-th order statistics problem is proven to be NP-hard, even for models with zero treewidth.
  • Algorithmic Performance: The proposed RVE algorithm significantly outperforms sampling-based methods in terms of accuracy for estimating ranks and finding assignments of a given rank.
  • Accuracy vs. Rank: Sampling methods show higher error for ranks in the middle of the distribution, while RVE's error is more evenly distributed, though it can be higher in densely populated rank ranges.
  • Efficiency: The RVE algorithm's complexity is exponential in the treewidth of the model, but it offers a practical solution for low-treewidth models.

Limitations and Future Work

  • Treewidth Dependency: The RVE algorithm's complexity is exponential in the treewidth, meaning it can become computationally expensive for models with high treewidth.
  • Dynamic Binning: The authors suggest that dynamic binning strategies could be effective in addressing the higher error observed in densely populated rank ranges.
  • Multi-valued Variables: The paper primarily focuses on Boolean variables, and extension to multi-valued variables is mentioned as straightforward but not deeply explored.
  • Quantization Function: The choice of quantization function and its parameters can affect the accuracy and complexity of the RVE algorithm. Further research into optimal quantization strategies could be beneficial.

Summary updated

Abstract

We consider the problem of computing r-th order statistics, namely finding an assignment having rank r in a probabilistic graphical model. We show that the problem is NP-hard even when the graphical model has no edges (zero-treewidth models) via a reduction from the partition problem. We use this reduction, specifically a pseudo-polynomial time algorithm for number partitioning to yield a pseudo-polynomial time approximation algorithm for solving the r-th order statistics problem in zero- treewidth models. We then extend this algorithm to arbitrary graphical models by generalizing it to tree decompositions, and demonstrate via experimental evaluation on various datasets that our proposed algorithm is more accurate than sampling algorithms.
BibTeX
@inproceedings{smith2017order,
  author = {David B. Smith and Sara Rouhani and Vibhav Gogate},
  title = {{Order Statistics for Probabilistic Graphical Models}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  url = {https://openreview.net/forum?id=HJWzQVfdbH},
}
Figure