Polynomial-Time Probabilistic Reasoning with Partial Observations via Implicit Learning in Probability Logics

Brendan Juba

Abstract

Traditional probabilistic reasoning often relies on a two-step pipeline: learning an explicit model, such as a Bayesian or Markov Network, and then performing inference. However, structure learning is frequently a computational bottleneck, particularly when dealing with partial observations. This paper introduces a framework that bypasses explicit model construction by treating the Sum-of-Squares (SoS) proof system as a probability logic. By leveraging Semidefinite Programming (SDP), the proposed method allows for implicit learning from partially observed data and enables probabilistic querying in polynomial time.

Introduction

In the field of artificial intelligence, reasoning under uncertainty typically requires a well-defined joint distribution. The standard approach involves learning the parameters and structure of a graphical model from data before answering queries. This process faces two significant hurdles: first, structure learning from partial data (where some values are missing) is often intractable, with algorithms like Expectation-Maximization (EM) prone to local optima. Second, even with a known model, exact inference is only efficient for specific architectures, such as those with low tree-width.

This research asks a fundamental question: Is it possible to reason directly from partial observations without ever building an explicit model of the full distribution? The author proposes a solution rooted in the intersection of optimization theory and formal logic, utilizing the Sum-of-Squares hierarchy to perform "implicit learning."

Methodology

SoS as a Probability Logic

The core of the framework is the Sum-of-Squares (SoS) hierarchy, originally a tool for polynomial optimization. In this context, SoS is repurposed as a logic of "pseudo-expectations." Instead of searching the space of all possible distributions, the algorithm searches for a "moment matrix"—a collection of values representing the expected products of variables—that satisfies a set of polynomial inequalities. If such a matrix exists, it serves as a certificate that a valid distribution could exist under the given constraints.

Reasoning via Semidefinite Programming (SDP)

The reasoning engine is reduced to a Semidefinite Programming feasibility problem. Determining whether a distribution satisfies a set of logical or algebraic constraints becomes a matter of checking the feasibility of an SDP. Because SDPs can be solved in polynomial time, this approach provides a computationally efficient path to probabilistic inference.

Implicit Learning from Partial Observations

Rather than using data to parameterize a model, the paper introduces a method to integrate empirical evidence directly into the SDP. The data provides estimates of "moments" (the expected values of specific monomials). Even when data is masked (partially observed), the author defines "testable" constraints—rules that can be verified despite missing values. These empirical moments act as additional constraints within the SDP, effectively allowing the system to learn the underlying distribution's properties implicitly during the reasoning process.

Theoretical Insights and Expressiveness

Bypassing the Model

A key insight of this work is that answering a probabilistic query does not require a full joint distribution. Instead, one only needs to prove a "refutation": showing that no distribution exists which satisfies both the background knowledge and the empirical evidence while contradicting the query.

Logical and Analytic Power

The paper demonstrates that SoS logic is remarkably expressive. It is shown to simulate significant fragments of classical logic systems, including Resolution and Polynomial Calculus. Specifically, a degree-$(s+1)$ SoS relaxation can simulate a level-$s$ resolution refutation. Furthermore, because it is based on polynomials, the logic naturally incorporates fundamental analytic inequalities, such as Cauchy-Schwarz and Hölder, which are vital for bounding variances and probabilities.

Key Results

Theorem 11: The Main Guarantee

The central theoretical contribution is Theorem 11, which establishes the reliability of the SDP approach. It proves that if a distribution satisfies the constraints, the SDP will be feasible. Conversely, if a "testable" set of constraints leads to a contradiction (an SoS refutation), the SDP will correctly identify the system as infeasible.

Computational Complexity

The paper guarantees that the entire pipeline—incorporating partial observations, adding empirical constraints, and solving the resulting query—runs in polynomial time relative to the number of attributes and the size of the proof. This marks a significant improvement over traditional methods that struggle with the exponential complexity of structure learning.

Limitations and Future Work

Despite its theoretical strengths, the framework has several limitations:

  • Independence Constraints: Representing independence between variables remains difficult. Independence is a quadratic constraint (e.g., $E[XY] = E[X]E[Y]$), which introduces non-convexity into the optimization problem, potentially making it intractable for standard SDP solvers.
  • Marginal Limits: The current tractable fragments are limited to inferring values for marginal distributions involving a small, constant number of variables.
  • Propositional Scope: The work is currently confined to propositional logic. Future research may extend these techniques to First-Order Logic by exploiting symmetries in relational data or using independently quantified expressions.
  • Testability Thresholds: The reliance on "testable" constraints assumes a certain level of data quality. Handling noisier or more heavily masked data remains an open challenge for the framework.

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 decide 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 key 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