Polynomial-time probabilistic reasoning with partial observations via implicit learning in probability logics

Brendan Juba

Abstract

Standard approaches to probabilistic reasoning require an explicit model of the distribution in question. However, the empirical learning of probability distributions from partial observations is a problem for which efficient algorithms are generally not known. This work explores the use of bounded-degree fragments of the "Sum-of-Squares" (SoS) logic as a probability logic. Prior research has demonstrated that refutability for such fragments can be decided in polynomial time. We propose using these fragments to answer queries regarding whether a distribution satisfies specific constraints and bounds on expected values. We demonstrate that these constraints can be implicitly learned from partial observations in polynomial time. Furthermore, we show that this logic is expressive enough to derive useful bounds in probabilistic analysis and capture significant polynomial-time fragments of resolution.

Introduction: The Bottleneck of Explicit Modeling

In the field of artificial intelligence, reasoning under uncertainty is typically framed as a probabilistic challenge. Whether determining if a specific attribute correlates with a medical outcome or predicting system behavior, the standard workflow involves building a Probabilistic Graphical Model (such as a Bayesian Network or Markov Logic Network) to represent the entire distribution.

However, this "model-first" approach faces two significant hurdles:

  1. Partial Observations: Real-world data is rarely complete. We often deal with latent variables or missing attributes that obscure the true distribution.
  2. The Structure Learning Bottleneck: Learning the "blueprint" or structure of a distribution from partial data is computationally expensive. Algorithms like Expectation-Maximization (E-M) often fail to scale, and finding the optimal network structure is frequently NP-hard.

This paper proposes a shift in perspective: Can we reason about probabilities directly from data without ever constructing a full model? By utilizing Sum-of-Squares (SoS) logic, we can bypass the structure-learning phase and answer queries through implicit learning.

Methodology: Reasoning via Sum-of-Squares Logic

The core of this approach is the interpretation of the Sum-of-Squares hierarchy as a probability logic. Unlike traditional probability logics that rely on linear programming to find bounds, this framework extends reasoning to handle polynomial inequalities regarding moments and support.

Semidefinite Programming (SDP)

The reasoning problem is reformulated as a "moment problem." By employing Semidefinite Programming (SDP) relaxations, the system can determine if a set of constraints is consistent with any valid probability distribution. This allows the algorithm to check the feasibility of a query without needing to define the distribution's full parameters.

Implicit Learning from Partial Data

The "implicit" nature of this learning is the paper's primary innovation. Instead of attempting to fill in missing data points to reconstruct a model, the algorithm uses partial examples to "witness" constraints. By applying Hoeffding’s Inequality, the system ensures that the empirical constraints derived from a finite sample of partial observations remain valid for the true underlying distribution. This allows the boundaries of what must be true to be learned directly within the reasoning process.

Expressiveness and Computational Complexity

A common concern with tractable logic fragments is their expressiveness. This work addresses this by situating SoS logic within the broader context of automated theorem proving:

  • Simulation of Resolution: The paper proves (Theorem 4) that SoS relaxations can simulate "space-bounded treelike resolution." This confirms that the logic is at least as powerful as many standard automated reasoning techniques used in practice.
  • Analytic Power: The logic is capable of deriving complex analytic inequalities, such as Cauchy-Schwarz, which are essential for rigorous probabilistic analysis.
  • Polynomial-Time Guarantees: The main result (Theorem 9) establishes that for bounded-degree fragments, the algorithm can accept or refute queries in polynomial time relative to the number of attributes and the size of the proof. This provides a clear computational trade-off: by limiting the degree of the polynomials (the "depth" of the reasoning), we ensure efficiency.

Limitations and Future Directions

While the SoS framework offers a powerful alternative to traditional modeling, several challenges remain:

  • Independence Constraints: The logic currently struggles to represent independence between variables. Expressing independence requires quadratic constraints in the primal optimization problem, which currently compromises polynomial-time efficiency.
  • Marginalization Limits: The tractable fragments are generally limited to inferring values for marginal distributions involving a small, constant number of variables, unless the relationships are captured by low-degree polynomials.
  • Propositional Scope: The current framework is propositional. Future research may extend this to First-Order Logic—reasoning about objects and relations—potentially through relational linear programming or propositionalization techniques.
  • The Testability Gap: The requirement for constraints to be "testable" (verifiable from partial data) is strict. Developing methods to leverage more "hidden" or non-testable information remains an open area of study.

Conclusion

By moving away from the requirement of an explicit "blueprint," this work demonstrates that robust probabilistic reasoning is possible even with messy, partial data. The use of Sum-of-Squares logic provides a mathematically rigorous and computationally efficient path to answering complex queries, bridging the gap between statistical learning and formal logic.

Summary updated

Abstract

Standard approaches to probabilistic reasoning require that one possesses an explicit model of the distribution in question. But, the empirical learning of models of probability distributions from partial observations is a problem for which efficient algorithms are generally not known. In this work we consider the use of bounded-degree fragments of the "sum-of-squares" logic as a probability logic. Prior work has shown that we can decide refutability for such fragments in polynomial-time. We propose to use such fragments to answer queries about whether a given probability distribution satisfies a given system of constraints and bounds on expected values. We show that in answering such queries, such constraints and bounds can be implicitly learned from partial observations in polynomial-time as well. It is known that this logic is capable of deriving many bounds that are useful in probabilistic analysis. We show here that it furthermore captures useful polynomial-time fragments of resolution. Thus, these fragments are also quite expressive.
BibTeX
@inproceedings{juba2019polynomial,
  author = {Brendan Juba},
  title = {{Polynomial-time probabilistic reasoning with partial observations via implicit learning in probability logics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33017866},
}
Figure