Compressed Constraints in Probabilistic Logic and Their Revision

Paul SnowUAI 1991

TL;DR

This paper introduces a "compressed" constraint system for probabilistic logic that significantly reduces computational complexity by using a three-valued logic ("true," "false," and "don't care"). This allows for more practical exact solutions to entailment problems that would otherwise be intractable due to an exponential explosion of possible "worlds."

What Problem Does This Paper Address?

Probabilistic logic aims to estimate the probability of a target sentence based on prior beliefs about other source sentences. A standard approach involves constructing a system of linear constraints that represent the relationships between these beliefs. However, a major hurdle is the "proliferation of worlds" – the number of possible truth assignments (worlds) for the source sentences grows exponentially with the number of sentences, making exact methods computationally impractical for even moderately sized problems. This paper addresses this scalability issue by proposing a method to create smaller, "compressed" constraint systems that are equivalent to the original, larger ones.

Methods

The core innovation is the introduction of a three-valued logic, incorporating a "don't care" (d.c.) state, alongside the standard "true" and "false." This allows for the compression of constraint systems. When two "worlds" (truth assignments) differ in only one component, they can be merged into a single "compressed" world represented by a d.c. value. This technique is particularly effective for well-understood inference schemas like modus ponens with a conjunctive antecedent, where the structure of the inference allows for systematic compression. The paper details how to construct these compressed semantic trees and derive the corresponding linear constraint systems, which then can be solved using standard linear programming techniques. The paper also discusses how to perform probabilistic revision with these compressed systems, particularly when dealing with conditional probabilities.

Datasets

Not discussed in the paper. The paper uses a hypothetical example (modus ponens with a conjunctive antecedent) to illustrate its method.

Key Insights and Ideas

  • The "Don't Care" Advantage: Introducing a "don't care" state is a powerful way to merge similar possible worlds, drastically reducing the size of the constraint system without losing information about the target sentence's probability.
  • Schema-Driven Compression: The effectiveness of compression is highly dependent on the structure of the inference problem. Well-defined inference schemas (like modus ponens) lend themselves to systematic and significant compression.
  • Trade-off between Search and Compression: For arbitrary entailments, compression might require a search phase to identify mergeable worlds. This introduces a gamble: the search cost could be high, but if successful, it avoids an impractical linear program.
  • Revision with Compressed Systems: While revision with conditionals is possible, the paper notes that the conceptual ease of calculating exact posterior constraint systems is lost with compressed systems, though point estimates are still readily obtainable.

Key Results

The paper demonstrates that for an inference schema with n antecedents, the compressed system can yield n+2 possible worlds, compared to 2^(n+1) worlds in the uncompressed two-valued system. This leads to a linear system size that is roughly O(n²), a significant improvement over the exponential complexity of the original approach. The paper provides an example where a problem with 16 possible worlds is compressed to 5, effectively halving the size of the linear system.

Limitations and Future Work

The authors acknowledge that compression may not always be possible or may yield only disappointing savings, especially for problems without clear inference schemas (e.g., parity functions). The search required for arbitrary entailments introduces a gamble on computational savings. Furthermore, while revision using point estimates is straightforward with compressed systems, the paper notes that the conceptual ease of calculating exact posterior constraint systems is lost, unlike with uncompressed systems. Future work could explore more systematic ways to handle arbitrary entailments and further refine revision methods for compressed systems.

Summary updated

BibTeX
@inproceedings{snow1991compressed,
  author = {Paul Snow},
  title = {{Compressed Constraints in Probabilistic Logic and Their Revision}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1991},
}
Figure