Introduction: From Sets to Distributions
Traditional logic typically evaluates whether a single assignment of values to variables satisfies a formula. Team semantics generalizes this by considering sets of assignments, known as teams. This shift enables the formalization of dependencies, such as functional dependence, where the value of one variable determines another.
Probabilistic team semantics extends this framework further by replacing sets with probability distributions over assignments. This allows for the simultaneous reasoning of logical and probabilistic dependencies, such as conditional independence.
Despite its potential, the relative expressive power of different probabilistic atoms—such as marginal identity versus conditional independence—has remained poorly understood. This paper classifies these logics and establishes their computational complexity.
Theoretical Framework and Methods
The authors utilize several techniques to map the landscape of probabilistic logics:
- Logical Translations: Establishing lower bounds on expressivity by defining one dependency atom through another.
- Closure Properties: The introduction of "scaled union closure" for marginal identity logic ($FO(\approx)$). By demonstrating that atoms like functional dependence violate this property, the authors prove strict separations between logics.
- Reduction to Real Arithmetic: Propositional versions of these logics are translated into the first-order theory of the reals. This leverages decidability results from algebraic geometry to find complexity bounds.
The Expressivity Hierarchy
A central contribution of the work is the establishment of a clear hierarchy of expressive power: $$FO(\approx) < FO(\approx^*) \leq FO(\perp\perp_c)$$ Here, $\approx$ denotes marginal identity, $\approx^*$ denotes multiset equivalence (marginal distribution equivalence), and $\perp\perp_c$ represents conditional independence.
The authors identify that while marginal identity requires distributions to be identical, multiset equivalence only requires the multisets of probabilities to match. Surprisingly, this "weaker" condition is sufficient to define functional dependence, making $FO(\approx^*)$ strictly more expressive than $FO(\approx)$. In fact, they prove that $FO(\approx^*)$ is equivalent to a logic containing both marginal identity and functional dependence atoms ($FO(\approx, =(\cdot))$).
Decidability and Complexity Results
The paper addresses the long-standing "implication problem" for conditional independence: determining if a set of independence statements logically entails another. While this remains an open problem for general discrete distributions, the authors prove it is decidable in EXPSPACE when restricted to binary distributions.
Furthermore, the transition from standard team semantics to the probabilistic realm significantly increases computational complexity. For propositional logic, satisfiability moves from "alternating exponential time" to double exponential space (2-EXPSPACE). Specifically, $QPL(\perp\perp_c, \sim)$ is in 2-EXPSPACE, while the version with only marginal identity is in 2-AEXPTIME.
Conclusion and Future Directions
While the paper clarifies much of the hierarchy, the question of whether $FO(\approx^*)$ is strictly less expressive than $FO(\perp\perp_c)$ remains open. The authors conjecture a divergence in the probabilistic case, unlike in non-probabilistic team semantics where they are equivalent. Future work may also explore "entropy atoms," incorporating fundamental information-theoretic measures directly into the logic to provide more nuanced detection of dependencies.
Summary updated