Facets of Distribution Identities in Probabilistic Team Semantics

Miika Hannula, Åsa Hirvonen, Juha Kontinen, Vadim Kulikov, Jonni Virtema

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.

A probabilistic team represented as a distribution over assignments.

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.

A Bayesian network illustrating complex dependencies and conditional independence.

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

Abstract

We study probabilistic team semantics which is a semantical framework allowing the study of logical and probabilistic dependencies simultaneously. We examine and classify the expressive power of logical formalisms arising by different probabilistic atoms such as conditional independence and different variants of marginal distribution equivalences. We also relate the framework to the first-order theory of the reals and apply our methods to the open question on the complexity of the implication problem of conditional independence.
BibTeX
@inproceedings{hannula2019facets,
  author = {Miika Hannula and Åsa Hirvonen and Juha Kontinen and Vadim Kulikov and Jonni Virtema},
  title = {{Facets of Distribution Identities in Probabilistic Team Semantics}},
  booktitle = {JELIA},
  year = {2019},
  doi = {10.1007/978-3-030-19570-0\_20},
}
Figure