Ranked Programming

Tjitze RienstraIJCAI 2019 · DOI

TL;DR

This paper introduces "Ranked Scheme," a novel programming language that extends probabilistic programming with "ranking theory" to handle a different kind of uncertainty: degrees of surprise rather than probabilities. This allows for more intuitive modeling of situations where outcomes are either normal or exceptionally surprising, offering a computationally simpler alternative to traditional probabilistic approaches.

What Problem Does This Paper Address?

Traditional probabilistic programming languages (PPLs) are excellent for modeling uncertainty that can be quantified with probabilities. However, many real-world scenarios involve uncertainty that isn't strictly probabilistic. For instance, in fault diagnosis, we might know that components normally work but exceptionally fail, without precise probabilities for these failures. Similarly, sensor data is usually correct but can be exceptionally wrong. Ranking theory, an alternative to probability theory, measures uncertainty using "ranks" (integers from 0 to infinity) representing degrees of surprise. This paper addresses the gap of applying this ranking-theoretic uncertainty to the powerful framework of probabilistic programming, enabling more natural and efficient reasoning in these non-probabilistic uncertainty scenarios.

Methods

The core contribution is the development of "Ranked Scheme," a programming language built upon the Scheme dialect. It extends Scheme with new "R-expressions" that manipulate ranking functions. Key R-expressions include:

  • !x: Represents a value x with absolute certainty (rank 0).
  • (nrm K1 exc r K2): A ranked choice expression. It normally yields a value from ranking function K1 (rank 0), but exceptionally (with rank r) yields a value from K2. This is the central mechanism for expressing ranked uncertainty.
  • (observe p K): Implements ranking-theoretic conditionalization, analogous to conditioning in probabilistic programming. It updates the ranking function K based on a predicate p.
  • ($ K1 K2 ... Kn): A ranked procedure call, generalizing regular Scheme procedure calls to work with ranking functions.
  • (rlet* ((v1 exp1) ... (vn expn)) body): A ranked let* expression, allowing for sequential binding of variables to ranking functions and building complex dependencies.

The semantics of these expressions are defined denotationally, mapping each R-expression to a ranking function over Scheme values. The implementation leverages Scheme's "promise" objects for lazy evaluation, representing ranking functions as lazily-linked lists of (value, rank, next_promise) triples. This "least-surprising-first" execution strategy computes only the necessary finite-ranked values.

Datasets

Not discussed in the paper. The paper focuses on introducing a new language and demonstrating its capabilities through examples rather than empirical evaluation on standard datasets.

Key Insights and Ideas

  • Ranking Theory as a Complement to Probability: The paper convincingly argues that ranking theory offers a distinct and valuable perspective on uncertainty, particularly for scenarios where "normal" vs. "exceptional" is more relevant than precise probabilities.
  • Ranked Programming as a Generalization: By adapting the PPL methodology to ranking theory, the authors create a framework that is as flexible and powerful as PPLs but computationally simpler for certain types of uncertainty.
  • Computational Simplicity: The use of integer ranks and the "least-surprising-first" execution strategy can lead to more efficient inference compared to full probabilistic inference, especially when only a few "normal" outcomes are of interest.
  • Intuitive Modeling of Exceptions: The (nrm K1 exc r K2) construct provides a direct and intuitive way to model situations where something is usually true but can exceptionally be false (or vice-versa), with the rank r quantifying the degree of exception.
  • Unified Framework: Ranked Scheme allows seamless integration of ranked uncertainty with regular Scheme code, making it a practical tool for building complex models.

Key Results

The paper presents a functional implementation of Ranked Scheme and demonstrates its utility through several examples:

  • Ranking Networks: A car diagnosis example shows how ranking networks can be constructed and queried, analogous to Bayesian networks.
  • Boolean Circuit Diagnosis: A circuit diagnosis scenario illustrates how to find the most likely explanations for faulty behavior using ranked inference.
  • Ranked Hidden Markov Models (HMMs): A toy HMM example demonstrates how to infer hidden states (weather) from observable emissions (umbrella presence) using ranks.
  • Ranked Automata for Spelling Correction: An example shows how to adapt automata for spelling correction, where ranks correspond to Levenshtein distances.

These examples showcase the language's ability to model diverse problems involving non-probabilistic uncertainty and perform inference.

Limitations and Future Work

  • Limited Empirical Evaluation: The paper primarily focuses on the language design and illustrative examples. A more extensive empirical evaluation comparing Ranked Scheme's performance and expressiveness against probabilistic approaches on a wider range of benchmarks is needed.
  • Handling of Infinite Ranks: While the implementation handles finite ranks efficiently, the paper acknowledges that infinite sets of finitely-ranked values can still pose challenges. The semantics are extended with ∞ for impossible events, but practical handling of very large finite rank sets might require further optimization.
  • Comparison with Other Uncertainty Formalisms: The paper briefly mentions other uncertainty formalisms like Dempster-Shafer and possibility measures. A more in-depth comparison of Ranked Scheme's strengths and weaknesses against these alternatives would be beneficial.
  • Future Work: The authors suggest exploring the use of Ranked Scheme for other applications and further investigating its theoretical properties and computational efficiency. They also mention that ranked programming generalizes nondeterministic programming, hinting at potential connections to other areas of AI.

Summary updated

BibTeX
@inproceedings{rienstra2019ranked,
  author = {Tjitze Rienstra},
  title = {{Ranked Programming}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/798},
}

Loading related content...

Figure