The Finite Model Theory of Bayesian Networks: Descriptive Complexity

1 Introduction

There is a rich literature on "relational" Bayesian networks, where constructs from first-order logic are used to represent populations with repetitive patterns [Getoor and Taskar, 2007; De Raedt, 2008; De Raedt et al., 2010]. A relational specification is often viewed as a template that can be grounded into a finite propositional Bayesian network.

It is only natural to ask what is the expressivity of Bayesian network specifications based on predicates and quantifiers. That is, to ask what can and what cannot be modeled by these specifications, and at what computational costs. To address these questions, we are inspired by the well-known theory of descriptive complexity as developed within finite model theory [Ebbinghaus and Flum, 1995; Grädel et al., 2007]. It does not seem that the descriptive complexity of Bayesian networks has been investigated in previous work; as the topic is novel, most of this paper consists of building a framework in which to operate.

One should expect "relational" Bayesian network specifications to exhibit properties that cannot be matched by propositional networks - much as first-order logic goes beyond propositional logic. The power of relational probabilistic specifications has been already noted in connection with lifted inference algorithms [Jaeger, 2014; Van den Broeck, 2011], but has not been characterized in terms of descriptive complexity.

1 This paper is an abridged and corrected version of a paper selected from ECSQARU 2017 [Cozman and Maua, 2017]; some novel results appear here. The original paper was entitled "The Descriptive Complexity of Bayesian Network Specifications".

We define precisely what we mean by "Bayesian network specifications" in Section 2, and present some necessary background in Section 3. We then move to our main results in Sections 4 and 5. We show that Bayesian network specifications that employ first-order quantification capture the complexity class PP. That is, a language is in PP if and only if its strings encode valid inferences in a Bayesian network specified with predicates and first-order quantifiers. This is a much stronger statement than PP-completeness. And then we look at specifications that allow quantification over predicates, and show that such "second-order" Bayesian networks capture complexity classes in the hierarchy PP NP...NP . It does not seem that previous results on descriptive theory have reached this latter complexity classes.

Intuitively, these results can be interpreted as follows: suppose we have a (physical, social, economic) phenomenon that can be simulated by a probabilistic Turing machine in polynomial time: given an input, the machine will run for a number of steps that is polynomial in the length of the input, and the machine will stop with the output following the same distribution produced by the phenomenon. Our results show that the phenomenon can also be modeled by a Bayesian network specification based on predicates and first-order quantification in the sense that, given the input as evidence, an inference with the network will produce the same probabilities over the output as the phenomenon. But what happens if the phenomenon is so complex that it requires even more computation to be simulated? For instance, what happens if the phenomenon requires a polynomial time probabilistic Turing machine with another nondeterministic Turing machine as oracle? This phenomenon cannot be modeled by a "relational" Bayesian network specification, unless widely accepted assumptions about complexity classes collapse. However, our results show that this phenomenon can be modeled by a Bayesian network specification that allows quantification over predicates.

We further comment on the significance of these results in the concluding Section 6.

2 Specifying Bayesian Networks with Logical Constructs

To make any progress, we must precisely define what are the "relational" Bayesian networks we contemplate. Our strategy, described in this section, is to adopt a proposal by Poole [2010] to mix probabilistic assessments and logical equivalences [Cozman and Mauá, 2015].

2.1 Preliminaries

First, to recap: a Bayesian network is a pair consisting of a directed acyclic graph G whose nodes are random variables, and a joint probability distribution P over the variables in G, so that G and P satisfy the Markov condition (a random variable is independent of its nondescendants given its parents). The Markov condition induces a factorization of joint probabilities [Koller and Friedman, 2009].

In this paper every random variable is binary with values 0 and 1, respectively signifying false and true.

We only consider textual specifications, mostly relying on formulas of function-free first-order logic with equality (denoted by FFFO). That is, most formulas we use are wellformed formulas of first-order logic with equality but without functions, containing predicates from a finite relational vocabulary, negation (¬), conjunction (∧), disjunction (∨), implication (⇒), equivalence (⇔), existential quantification (∃) and universal quantification (∀).

First-order theories are interpreted as usual [Enderton, 1972], using domains, that are just sets, and interpretations that associate predicates with relations (an interpretation can be viewed as a truth assignment for every grounding of every predicate). A pair domain/interpretation is a structure. We only deal with finite domains in this paper.

Throughout the paper it will be convenient to view each grounded predicate r(d1, . . . , dk), for a fixed vocabulary/domain, as a random variable over interpretations. That is, given a domain D, we understand r(d1, . . . , dk) as a function over all possible interpretations of the vocabulary, so that r(d1, . . . , dk)(I) yields 1 if r(d1, . . . , dk) is true in interpretation I, and 0 otherwise.

For instance, say we have two unary predicates r and s, and we are given a domain D = {a, b}. Then we have groundings {r(a), r(b), s(a), s(b)}, and there are 24 possible interpretations. Each interpretation assigns true or false to r(a), and similarly to each grounding. So r(a) can be viewed as a random variable over the possible interpretations.

2.2 Relational Bayesian Network Specifications

A relational Bayesian network specification, abbreviated RELBN, is a directed acyclic graph where each node is a predicate (from a finite relational vocabulary), and where

1. each root node r of arity k is associated with a probabilistic assessment (α is a rational in [0, 1]):

1. while each non-root node s of arity k is associated with a formula (called the definition of s)

where φ(x1, . . . , xk) is a formula in FFFO with free variables x1, . . . , xk.

Given a domain, a RELBN can be grounded into a unique Bayesian network, as follows.

• First, produce every grounding of the predicates.
• Second, associate with each grounding r(d1, . . . , dk) of a root predicate the grounded assessment

• Third, associate with each grounding s(d1, . . . , dk) of a non-root predicate the grounded definition

and replace universal/existential quantification in φ by conjunction/disjunction over the domain. Thus φ(d1, . . . , dk) becomes a (possibly very large!) propositional expression containing groundings.

• Finally draw a graph where each grounded predicate is a node, and where edges are obtained as follows. Add an edge into each grounded non-root predicate s(d1, . . . , dk) from each grounding of a predicate that appears in the grounded definition of s(d1, . . . , dk) given by φ(d1, . . . , dk).

Consider, as an example, the following model of asymmetric friendship, where an individual is always a friend of herself, and where two individuals are friends if they are both fans (of a writer, say) or if there is some "other" reason for it:

Figure 1 depicts the Bayesian network induced by domain D = {a, b, c}.

For a given RELBN τ and a domain D, denote by τ(D) the Bayesian network obtained by grounding τ with respect to D. The set of all relational Bayesian network specifications is denoted by B(FFFO).

3 A bit of Descriptive Complexity

We review some relevant concepts from finite model theory and computational complexity [Grädel, 2007; Papadimitriou, 1994].

ComplexityClasses We consider input strings in the alphabet {0, 1}; that is, a string is a sequence of 0s and 1s. A language is a set of strings; a complexity class is a set of languages. A language is decided by a Turing machine if the machine accepts each string in the language, and rejects each string not in the language. The complexity class NP contains each language that can be decided by a nondeterministic Turing machine with a polynomial time bound. If a Turing machine is such that, whenever its transition function maps to a non-singleton set, the transition is selected with uniform probability within that set, then the Turing machine is a probabilistic Turing machine. The complexity class PP is the set of languages that are decided by a probabilistic Turing machine in polynomial time, with an error probability strictly less than 1/2 for all input strings. This complexity class can be equivalently defined as follows: a language is in PP iff there is a polynomial nondeterministic Turing machine such that a string is in the language iff more than half of the computation paths of the machine end in the accepting state when the string is the input.

An oracle Turing machine M L, where L is a language, is a Turing machine with additional tapes, such that it can write a string ℓ to a tape and obtain from the oracle, in unit time, the decision as to whether ℓ ∈ L or not. If a set of languages A is defined by a set of Turing machines M (that is, the languages are decided by these machines), then define AL to be the set of languages that are decided by {M L : M ∈ M}. If A and B are sets of languages, A B = ∪x∈BAx . The polynomial hierarchy contains classes Σpk , where Σp0 is P and Σpk = NPΣpk-1 for k > 0 (note that Σp1 = NP).

Capturing a Complexity Class If a formula φ(x1, . . . , xk) has free logical variables x1, . . . , xk, then structure A is a model of φ(d1, . . . , dk) iff φ(x1, . . . , xk) is true in structure A when the logical variables x1, . . . , xk are replaced by elements d1, . . . , dk of the domain.

There is an isomorphism between structures A1 and A2 when there is a bijective mapping g between the domains such that if r(d1, . . . , dk) is true in A1, then r(g(d1), . . . , g(dk)) is true in A2, and moreover if r(d1, . . . , dk) is true in A2, then r(g-1 (d1), . . . , g-1 (dk)) is true in A1 (where g-1 denotes the inverse of g). A isomorphism-closed set of structures is a set of structures such that if a structure is in the set, all structures that are isomorphic to it are also in the set.

We assume that every structure is written as a string, encoded as follows for a fixed vocabulary where the maximum predicate arity is K [Grädel, 2007, Section 3.1.5]. Suppose the domain contains elements d1, . . . , dN. To encode interpretations with respect to the domain, we start by ordering the elements of the domain, say d1 < d2 < · · · < dN. This linear ordering is assumed for now to be always available; for the logical languages we consider later, the ordering itself can be defined with a formula. The ordering starts by encoding the domain. To do so, the string begins with N symbols 1 followed by one symbol 0. We take some order for the predicates, r1, . . . , rn. We then append, in this order, the encoding of the interpretation of each predicate. Focus on predicate ri of arity k. Using the linear ordering on the domain, we can enumerate lexicographically all k-tuples over the domain (all N k tuples). We then encode the interpretation of ri by N k symbols followed by N K -N k symbols 0; the jth first symbol (up to the N k th symbol) is 1 if the jth k-tuple belongs to the interpretation, and 0 otherwise. Thus we have n blocks of N K symbols and an initial block of N + 1 symbols, for a total of (N + 1) + nN K symbols in the string.

The data complexity of logical language L is the complexity of deciding whether an input structure satisfies a fixed sentence in L.

Logical language L captures complexity class C if and only if: first, for every sentence φ of L, the data complexity of L is in C and, second, for each isomorphism-closed set of finite structures S, for a non-empty vocabulary V, such that these structures are strings of a language in C, there is a sentence φ in L, with vocabulary V, such that S is exactly the set of all models of φ.

Note that descriptive complexity is distinct from data complexity. For example, the data complexity of FFFO is within polynomial bounds, but it is not the case that FFFO captures polynomial complexity: 2-colorability of a given graph (a graph can be encoded as a structure) can be checked in polynomial time, but 2-colorability cannot be expressed in FFFO.

Existential Second-Order Logic A formula φ in existential function-free second-order logic is a formula of the form

where φ′ is a sentence of FFFO containing predicates r1, . . . , rm. The set of such formulas is denoted ESO. Note that again we have equality (=) in the language. Here a structure A is a pair domain/interpretation, but the interpretation does not touch predicates that are existentially quantified (that is, if φ contains predicates r1, . . . , rm and s1, . . . , sM, but r1, . . . , rm are all existentially quantified, then a model for φ contains an intepretation for s1, . . . , sM).

As an example, consider a formula in ESO that is only satisfied if it is possible to find a domain, to be interpreted as a set of vertices, such that it is possible to partition the set of vertices into two subsets: if two vertices are connected by an edge, they are in distinct subsets. Here is the formula [Grädel, 2007]:

Fagin's Theorem The most celebrated result in descriptive complexity is Fagin's theorem: ESO captures NP [Fagin, 1976]. Or, in more detail:

Theorem 1. Let S be an isomorphism-closed set of finite structures of some non-empty finite vocabulary. Then S is in complexity class NP if and only if S is the class of finite models of a sentence in ESO.

Fagin's theorem offers a definition of NP that is not tied to any computational model; rather, it is tied to the expressivity of ESO. Note that it is not surprising that NP contains the problem of deciding whether an input structure is a model of a fixed ESO sentence; the surprising part of Fagin's theorem is that every language in NP can be exactly encoded by an ESO sentence.

4 B(FFFO) Captures PP

Suppose we have an isomorphism-closed set of finite structures S, of some non-empty vocabulary V. Once encoded, they form a language. Fagin's theorem focuses on languages that belong to NP, while here we wish to look at languages that belong to PP.

We show that any language of structures in PP can be "decided" by some RELBN τ on an extended vocabulary V ′ consisting of V plus some additional predicates. Clearly the question is whether it is possible to generate such a RELBN; however, a preliminary question is how exactly to accept/reject an input structure when we already have some RELBN.

Note that if we have a given structure A, we have a domain D and consequently we can produce a Bayesian network τ(D). We denote by Pτ(D) the probability measure encoded by the Bayesian network τ (D). Note also that each grounding of a predicate in V appears in τ(D) as a random variable; this random variable is set to true or false by the interpretation in A. The evidence E induced by A is just the set of these assignments to random variables corresponding to groundings of predicates in V.

We adopt the following scheme to accept/reject an input structure A using a given RELBN τ whose vocabulary contains V:

• We assume that τ contains two distinguished predicates of zero arity, A and B. The predicate A is the conditioned predicate, while B is the conditioning predicate.
• We assume that if Pτ(D)(A = 1|B = 1, E) > 1/2, then A is accepted; otherwise, A is rejected.

With the proper context in place, here is the main result:

Theorem 2. Let S be an isomorphism-closed set of finite structures of some non-empty finite vocabulary. Then S is in complexity class PP if and only if S is the class of finite structures that are accepted by a fixed RELBN with fixed conditioned and conditioning predicates.

This offers a definition of PP that is not tied to any computational model. In short, there is always a polynomial-time probabilistic Turing machine TM and a triplet (τ, A, B) such that both TM and (τ, A, B) can decide the same language S of structures.

5 Moving to Second-Order

Suppose we have a specification that follows the syntax of RELBN, except for the fact that one logical definition contains, in its right hand side, a formula in ESO. We denote this set of specifications by 1ESOBNs; that is, they are similar to relational Bayesian network specifications, except that one logical definition is not in FFFO but rather in ESO. We can actually extend this to 2ESOBNs and any other number of second-order definitions, until we reach second-order Bayesian network specifications, where arbitrary second-order formulas can be used.

What kind of complexity class is captured by specifications in 1ESOBNs? We adopt a strategy for acceptance/rejection by 1ESOBNs that mimicks our previous strategy for acceptance/rejection by RELBNs. That is, we have an input structure on a vocabulary V, and we assume that there is a conditioned predicate A and a conditioning predicate B in the 1ESOBN; we also assume that quantified predicates are not in V. The decision as to whether to accept or reject the input structure is based on whether the probability of A given B and E (the evidence conveyed by the input structure) is larger than 1/2.

We have: 2

Theorem 3. Let S be an isomorphism-closed set of finite structures of some non-empty finite vocabulary. Then S is in complexity class PP NP if and only if S is the class of finite structures that are accepted by a fixed 1ESOBN with fixed conditioned and conditioning predicates.

By allowing an increasing number of existential secondorder logical definitions, we can produce increasingly more complex alternation of quantifiers (by negating an existential definition so as to obtain a universal one whenever necessary). That is, with a kESOBN, where we can use k logical definitions based on existential second-order logic, we can write down formulas in Σ1k ; that is, formulas that consist of a FFFO formula preceded by k blocks of quantifiers, each block either existential or universal, and the first block existential. Now Σ1k captures the complexity class Σpk in the polynomial hierarchy [Stockmeyer, 1977]. Hence we can extend the previous theorem so as to allow k logical definitions based on ESO, with the result that the oracle machine decides Σpk . Thus we can capture various classes in the counting polynomial hierarchy [Wagner, 1986]:

Theorem 4. Let S be an isomorphism-closed set of finite structures of some non-empty finite vocabulary. Then S is in complexity class PPΣpk if and only if S is the class of finite structures that are accepted by a fixed kESOBN with fixed conditioned and conditioning predicates.

6 Conclusion: A Finite Model Theory of Bayesian Networks?

We have introduced a theory of descriptive complexity for Bayesian networks, a topic that does not seem to have received due attention so far. To summarize, we have shown that relational Bayesian network specifications capture PP, and we have indicated how we can go beyond PP in our modeling tools. Specifically, we added existential second-order quantification to capture complexity classes PPΣpk . Our results can be extended in a variety of directions, for instance to various fixpoint logics that are the basis of logic programming [Ebbinghaus and Flum, 1995; Libkin, 2004].

2 In the original version of this paper we argued that secondorder Bayesian network specifications capture PP NP , failing to state the restriction to a single second-order formula [Cozman and Maua, 2017]. We correct that mistake here.

These results can be better appreciated by taking a broader perspective. For several decades now, there has been significant study of models that arise from combinations of probability and logic [Abadi and Halpern, 1994; Gaifman, 1964]. However, by dealing with domains of arbitrary cardinality, and with logics that both include too many constructs (for instance, functions) and exclude valuable techniques (for instance, independence relations), these previous investigations arrive at results that are often too weak - for instance, almost always obtaining undecidability or very high computational complexity. By focusing on modular tools such as Bayesian networks, and by focusing on finite domains, we are able to obtain much sharper results, nailing down specific complexity classes such as PP and PP NP . In fact, the purpose here is to initiate a "finite model theory of Bayesian network specifications" that can pin down the expressivity and complexity of Bayesian networks, not only when they are propositional objects, but particularly when they are specified using logical constructs.

Our results are also interesting from a point of view centered on complexity theory. There has been little work on capturing counting/probabilistic classes; the most significant previous results capture #P using counting [Saluja and Subrahmanyam, 1995]. We offer a more concrete modeling language that captures PP, and we move into the counting hierarchy with classes PPΣpk - we are not aware of any similar result in the literature. Our results show that classes in the counting hierarchy can be tied to the expressivity of modeling tools, not to any particular computational model (much as Fagin's theorem does for NP).

Acknowledgements

The first author is partially supported by CNPq, grant 308433/2014-9. The second author is partially supported by CNPq grants 303920/2016-5 and 420669/2016-7. This paper was partially funded by FAPESP grants 2016/18841-0, 2016/01055-1, and 2015/21880-4.