ISIPTA 2023

# Markov Conditions and Factorization in Logical Credal Networks

Fabio Gagliardi Cozman
Universidade de São Paulo  Brazil

###### Abstract

We examine the recently proposed language of Logical Credal Networks, in
particular investigating the consequences of various Markov conditions. We
introduce the notion of structure for a Logical Credal Network and show that a
structure without directed cycles leads to a well-known factorization result.
For networks with directed cycles, we analyze the differences between Markov
conditions, factorization results, and specification requirements.

###### keywords:

Logical credal networks, probabilistic logic, Markov condition, factorization.

##  1 Introduction

This paper examines Logical Credal Networks, a formalism recently introduced
by Qian et al. [16] to combine logical sentences, probabilities and
independence relations. The have proposed interesting ideas and evaluated the
formalism in practical scenarios with positive results.

The central element of a Logical Credal Network (LCN) is a collection of
constraints over probabilities. Independence relations are then extracted
mostly from the logical content of those inequalities. This scheme differs
from previous proposals that extract independence relations from explicitly
specified graphs [1, 7, 8]. Several probabilistic logics have also adopted
explicit syntax for independence relations even when graphs are not employed
[2, 9, 10].

While Logical Credal Networks have points in common with existing formalisms,
they do have novel features that deserve attention. For one thing, they resort
to directed graphs that may contain directed cycles. Also they are endowed
with a sensible Markov condition that is distinct from previous ones. Little
is known about the consequences of these features, and how they interact with
the syntactic conventions that turn logical formulas into edges in graphs. In
particular, it seems that no study has focused on the consequences of Markov
conditions on factorization results; that is, how such conditions affect the
factors that constitute probability distributions.

In this paper we present a first investigation towards a deeper understanding
of Logical Credal Networks, looking at their specification, their Markov
conditions, their factorization properties. We introduce the notion of
“structure” for a LCN. We then show that the local Markov condition proposed
by Qian et al. [16] collapses to the usual local Markov condition applied to
chain graphs when the structure has no directed cycles. We analyze the
behavior of the former Markov condition in the presence of directed cycles, in
particular examining factorization properties and discussing the semantics of
the resulting language. To conclude, we propose a novel semantics for LCNs and
examine factorization results for their associated probability distributions.

##  2 Graphs and Markov Conditions

In this section we present the necessary concepts related to graphs and graph-
theoretical probabilistic models (Bayesian networks, Markov networks, and
chain graphs). Definitions and notation vary across the huge literature on
these topics; we rely here on three sources. We use definitions by Qian et al.
[16] and by Spirtes [18] in their work on LCNs and on directed graphs
respectively; we also use standard results from the textbook by Cowell et al.
[5].

A graph is a triple $(\mathcal{V},\mathcal{E}_{D},\mathcal{E}_{U})$, where
$\mathcal{V}$ is a set of nodes, and both $\mathcal{E}_{D}$ and
$\mathcal{E}_{U}$ are sets of edges. A node is always labeled with the name of
a random variable; in fact, we do not distinguish between a node and the
corresponding random variable. The elements of $\mathcal{E}_{D}$ are directed
edges. A directed edge is an ordered pair of distinct nodes, and is denoted by
$A\rightarrow B$. The elements of $\mathcal{E}_{U}$ are undirected edges. An
undirected edge is a pair of distinct nodes, and is denoted by $A\sim B$; note
that nodes are not ordered in an undirected edge, so there is no difference
between $A\sim B$ and $B\sim A$. Note that $\mathcal{E}_{D}$ and
$\mathcal{E}_{U}$ are sets, so there are no multiple copies of elements in
them (for instance, there are no multiple undirected edges between two nodes).
Note also that there is no loop from a node to itself.

If there is a directed edge from $A$ to $B$, the edge is said to be from $A$
to $B$, and then $A$ is a parent of $B$ and $B$ is a child of $A$. The parents
of $A$ are denoted by $\mbox{pa}(A)$. If there are directed edges
$A\rightarrow B$ and $B\rightarrow A$ between $A$ and $B$, we say there is bi-
directed edge between $A$ and $B$ and write $A\rightleftarrows B$. If $A\sim
B$, then both nodes are said to be neighbors. The neighbors of $A$ are denoted
by $\mbox{ne}(A)$. The boundary of a node $A$, denoted by $\mbox{bd}(A)$, is
the set $\mbox{pa}(A)\cup\mbox{ne}(A)$. The boundary of a set $\mathcal{B}$ of
nodes is
$\mbox{bd}(\mathcal{B})=\cup_{A\in\mathcal{B}}\mbox{bd}(A)\backslash\mathcal{B}$.
If we have a set $\mathcal{B}$ of nodes such that, for all $A\in\mathcal{B}$,
the boundary of $A$ contained in $\mathcal{B}$, then $\mathcal{B}$ is an
ancestral set.

A path from $A$ to $B$ is a sequence of edges, the first one between $A$ and
some node $C_{1}$, then from $C_{1}$ to $C_{2}$ and so on, until an edge from
$C_{k}$ to $B$, where all nodes other than $A$ and $B$ are distinct, and such
that for each pair $(D_{1},D_{2})$ of consecutive nodes in the path we have
either $D_{1}\rightarrow D_{2}$ or $D_{1}\sim D_{2}$ but never
$D_{2}\rightarrow D_{1}$. If $A$ and $B$ are identical, the path is a cycle.
If there is at least one directed edge in a path, the path is a directed path;
if that path is a cycle, then it is a directed cycle. If a path is not
directed, then it is undirected (hence all edges in the path are undirected
ones). A directed/undirected graph is a graph that only contains
directed/undirected edges. A graph without directed cycles is a chain graph.
Figure 1 depicts a number of graphs.

$A$$B$$C$$D$(a)

$A$$B$$C$$D$(b)

$A$$B$$C$$D$(c)

$A$$B$$C$$D$(d)

$A$$B$$C$$D$(e)

Figure 1: Graphs (directed/directed/undirected/directed/ chain). We have
$\mbox{pa}(B)=\\{A\\}$ in Figures 1.a and 1.e, $\mbox{pa}(B)=\\{A,D\\}$ in
Figures 1.b and 1.d, and $\mbox{pa}(B)=\emptyset$ in Figure 1.c.

$A$$B$$C$$D$(a)

$A$$B$$C$$D$(b)

$A$$B$$C$$D$(c)

$A$$B$$C$$D$(d)

$A$$B$$C$$D$(e)

Figure 2: The moral graphs of the graphs in Figure 1.

If there is a directed path from $A$ to $B$, then $A$ is an ancestor of $B$
and $B$ is a descendant of $A$. For instance, in Figure 1.a, $A$ is the
ancestor of $B$ and $D$ is the descendant of $B$; in Figure 1.c, there are no
ancestors nor descendants of $B$; in Figure 1.e, $A$ is the ancestor of $B$,
and there are no descendants of $B$. As a digression, note that Cowell et al.
[5] define “ancestor” and “descendant” somewhat differently, by asking that
there is a path from $A$ to $B$ but not from $B$ to $A$; this definition is
equivalent to the previous one for graphs without directed cycles, but it is
different otherwise (for instance, in Figure 1.b the node $B$ has descendants
$\\{A,C,D\\}$ in the previous definition but no descendants in the sense of
Cowell et al. [5]). We stick to our former definition, a popular one [13] that
seems appropriate in the presence of directed cycles [18].

We will need the following concepts:

  * •

Suppose we take graph $\mathcal{G}$ and remove its directed edges to obtain an
auxiliary undirected graph $\mathcal{G}^{\prime}$. A set of nodes
$\mathcal{B}$ is a chain multi-component of $\mathcal{G}$ iff every pair of
nodes in $\mathcal{B}$ is connected by a path in $\mathcal{G}^{\prime}$. And
$\mathcal{B}$ is a chain component iff it is either a chain multi-component or
a single node that does not belong to any chain multi-component.

  * •

Suppose we take graph $\mathcal{G}$ and add undirected edges between all pairs
of nodes that have a children in a common chain component of $\mathcal{G}$ and
that are not already joined in $\mathcal{G}$. Suppose we then take the
resulting graph and transform every directed edge into an undirected edge (if
$A\leftrightarrows B$, then both transformed undirected edges collapse into
$A\sim B$). The final result is the moral graph of $\mathcal{G}$, denoted by
$\mathcal{G}^{m}$.

  * •

Suppose we take a graph $\mathcal{G}$ and a triple
$(\mathcal{N}_{1},\mathcal{N}_{2},\mathcal{N}_{3})$ of disjoint subsets of
nodes, and we build the moral graph of the smallest ancestral set containing
the nodes in $\mathcal{N}_{1}\cup\mathcal{N}_{2}\cup\mathcal{N}_{3}$. The
resulting graph is denoted by
$\mathcal{G}^{ma}(\mathcal{N}_{1},\mathcal{N}_{2},\mathcal{N}_{3})$.

Figure 2 depicts the moral graphs that correspond respectively to the five
graphs in Figure 1.

There are several formalisms that employ graphs to represent stochastic
independence (and dependence) relations among the random variables associated
with nodes. In this paper we focus only on discrete random variables, so the
concept of stochastic independence is quite simple: random variables $X$ and
$Y$ are (conditionally) independent given random variables $Z$ iff
$\mathbb{P}\\!\left(X=x,Y=y|Z=z\right)=\mathbb{P}\\!\left(X=x|Z=z\right)\mathbb{P}\\!\left(Y=y|Z=z\right)$
for every possible $x$ and $y$ and every $z$ such that
$\mathbb{P}\\!\left(Z=z\right)>0$. In case $Z$ is absent, we have independence
of $X$ and $Y$ iff
$\mathbb{P}\\!\left(X=x,Y=y\right)=\mathbb{P}\\!\left(X=x\right)\mathbb{P}\\!\left(Y=y\right)$
for every possible $x$ and $y$.

A Markov condition explains how to extract independent relations from a graph;
there are many such conditions in the literature [5].

Consider first an undirected graph $\mathcal{G}$ with set of nodes
$\mathcal{N}$. The local Markov condition states that a node $A$ is
independent of all nodes in $\mathcal{N}$ other than $A$ itself and $A$’s
neighbors, $\mbox{ne}(A)$, given $\mbox{ne}(A)$. The global Markov condition
states that, given any triple
$(\mathcal{N}_{1},\mathcal{N}_{2},\mathcal{N}_{3})$ of disjoint subsets of
$\mathcal{N}$, such that $\mathcal{N}_{2}$ separates $\mathcal{N}_{1}$ and
$\mathcal{N}_{3}$, then nodes $\mathcal{N}_{1}$ and $\mathcal{N}_{3}$ are
independent given nodes $\mathcal{N}_{2}$.111In an undirected graph, a set of
nodes separates two other sets iff, by deleting the separating nodes, we have
no connecting path between a node in one set and a node in the other set. If a
probability distribution over all random variables in $\mathcal{G}$ is
everywhere larger than zero, then both conditions are equivalent and they are
equivalent to a factorization property: for each configuration of variables
$X=x$, where $X$ denotes the random variables in $\mathcal{G}$, we have
$\mathbb{P}\\!\left(X=x\right)=\prod_{c\in\mathcal{C}}\phi_{c}(x_{c})$, where
$\mathcal{C}$ is the set of cliques of $\mathcal{G}$, each $\phi_{c}$ is a
function over the random variables in clique $c$, and $x_{c}$ is the
projection of $x$ over the random variables in clique $c$.222A clique is a
maximal set of nodes such that each pair of nodes in the set is joined.

Now consider an acyclic directed graph $\mathcal{G}$ with set of nodes
$\mathcal{N}$. The local Markov condition states that a node $A$ is
independent, given $A$’s parents $\mbox{pa}(A)$, of all its non-descendants
non-parents except $A$ itself. The factorization produced by the local Markov
condition is

$\mathbb{P}\\!\left(X=x\right)=\prod_{N\in\mathcal{N}}\mathbb{P}\\!\left(N=x_{N}|\mbox{pa}(N)=x_{\mbox{pa}(N)}\right),$
(1)

where $x_{N}$ is the value of $N$ in $x$ and $x_{\mbox{pa}(N)}$ is the
projection of $x$ over the parents of $N$.

Finally, consider a chain graph $\mathcal{G}$ with set of nodes $\mathcal{N}$.
The local Markov condition for chain graphs is:

######  Definition 2.1 (LMC(C)).

A node $A$ is independent, given its parents, of all nodes that are not $A$
itself nor descendants nor boundary nodes of $A$.

The global Markov condition for chain graphs is significantly more
complicated:

######  Definition 2.2 (GMC(C)).

Given any triple $(\mathcal{N}_{1},\mathcal{N}_{2},\mathcal{N}_{3})$ of
disjoint subsets of $\mathcal{N}$, if $\mathcal{N}_{2}$ separates
$\mathcal{N}_{1}$ and $\mathcal{N}_{2}$ in the graph
$\mathcal{G}^{ma}(\mathcal{N}_{1},\mathcal{N}_{2},\mathcal{N}_{3})$, then
nodes $\mathcal{N}_{1}$ and $\mathcal{N}_{3}$ are independent given nodes
$\mathcal{N}_{2}$.

Again, if a probability distribution over all random variables in
$\mathcal{G}$ is everywhere larger than zero, then both Markov conditions are
equivalent and they are equivalent to a factorization property as follows.
Take the chain components $T_{1},\dots,T_{n}$ ordered so that nodes in $T_{i}$
can only be at the end of directed edges starting from chain compoents before
$T_{i}$; this is always possible in a chain graph. Then the factorization has
the form
$\mathbb{P}\\!\left(X=x\right)=\prod_{i=1}^{n}\mathbb{P}\\!\left(\mathcal{N}_{i}=x_{\mathcal{N}_{i}}\mid\mbox{bd}(\mathcal{N}_{i})=x_{\mbox{\scriptsize
bd}(\mathcal{N}_{i})}\right)$ where $\mathcal{N}_{i}$ is the set of nodes in
the $i$th chain component; $x_{\mathcal{N}_{i}}$ and $x_{\mbox{\scriptsize
bd}(\mathcal{N}_{i})}$ are respectively the projection of $x$ over
$\mathcal{N}_{i}$ and $\mbox{bd}(\mathcal{N}_{i})$. Moreover, each factor in
the product itself factorizes accordingly to an undirected graph that depends
on the corresponding chain component [5]. More precisely, for each chain
component $T_{i}$, build an undirected graph consisting of the nodes in
$\mathcal{N}_{i}$ and $\mbox{bd}(\mathcal{N}_{i})$ with all edges between
these nodes in $\mathcal{G}$ turned into undirected edges in this new graph,
and with new undirected edges connecting each pair of nodes in
$\mbox{bd}(\mathcal{N}_{i})$ that were not joined already; then each
$\mathbb{P}\\!\left(\mathcal{N}_{i}\mid\mbox{bd}(\mathcal{N}_{i})\right)$
equals the ratio
$\phi_{i}(\mathcal{N}_{i},\mbox{bd}(\mathcal{N}_{i}))/\phi_{i}(\mbox{bd}(\mathcal{N}_{i})))$
for positive function $\phi_{i}$, where
$\phi_{i}(\mbox{bd}(\mathcal{N}_{i})))=\sum\phi_{i}(\mathcal{N}_{i},\mbox{bd}(\mathcal{N}_{i}))$
with the sum extending over all configurations of $\mathcal{N}_{i}$.

##  3 Logical Credal Networks

A Logical Credal Network (LCN) consists of a set of propositions $\mathcal{N}$
and two sets of constraints $\mathcal{T}_{U}$ and $\mathcal{T}_{D}$. The set
$\mathcal{N}$ is finite with propositions $A_{1},\dots,A_{n}$. Each
proposition $A_{i}$ is associated with a random variable $X_{i}$ that is an
indicator variable: if $A_{i}$ holds in an interpretation of the propositions
then $X_{i}=1$; otherwise, $X_{i}=0$. From now on we simply use the same
symbol for a proposition and its corresponding indicator random variable. Each
constraint in $\mathcal{T}_{U}$ and in $\mathcal{T}_{D}$ is of the form

$\alpha\leq\mathbb{P}\\!\left(\phi|\varphi\right)\leq\beta,$

where each $\phi$ and each $\varphi$ is a formula. In this paper, formulas are
propositional (with propositions in $\mathcal{N}$ and connectives such as
negation, disjunction, conjunction). The definition of LCNs by Qian et al.
[16] allows for relational structures and first-order formulas; however, their
semantics is obtained by grounding on finite domains, so we can focus on a
propositional language for our purposes here.

Note that $\varphi$ can be a tautology $\top$, in which case we can just write
the “unconditional” probability $\mathbb{P}\\!\left(\phi\right)$. One can
obviously use simple variants of constraints, such as
$\mathbb{P}\\!\left(\phi|\varphi\right)=\beta$ or
$\mathbb{P}\\!\left(\phi|\varphi\right)\geq\alpha$ or
$\mathbb{P}\\!\left(\phi\right)\leq\alpha$, whenever needed.

The semantics of a LCN is given by a translation from the LCN to a directed
graph where each proposition/random variable is a node (we often refer to them
as proposition-nodes). Each constraint is then processed as follows. First, a
node labeled with formula $\phi$ is added and, in case $\varphi$ is not
$\top$, another node labeled with $\varphi$ is added (we often refer to them
as formula-nodes), with a directed edge from $\varphi$ to $\phi$. Then an edge
is added from each proposition in $\varphi$ to node $\varphi$ in case the
latter is in the graph, and an edge is added from node $\phi$ to each
proposition in $\phi$.333We note that the original presentation of LCNs is a
bit different from what we just described, as there are no edges added for a
constraint in $\mathcal{T}_{D}$ for which $\varphi$ is $\top$. But this does
not make any difference in the results and simplifies a bit the discussion.
Finally, in case the constraint is in $\mathcal{T}_{U}$, an edge is added from
each proposition in $\phi$ to node $\phi$. We do not distinguish between two
logically equivalent formulas (the original proposal by Qian et al. [16]
focused only on syntactic operations).

The graph just described is referred to as the dependency graph of the LCN.
Note that, when a formula is just a single proposition, we do not need to
present it explicitly in the dependency graph; we can just connect edges from
and to the corresponding proposition-node. As shown in the next example, in
our drawings formulas appear inside dashed rectangles.

######  Example 3.1.

Consider the following LCN, based on the Smokers and Friends example by Qian
et al. [16]. We have propositions $C_{i}$, $F_{i}$, $S_{i}$ for
$i\in\\{1,2,3\\}$. All constraints belong to $\mathcal{T}_{U}$ (that is,
$\mathcal{T}_{D}$ is empty), with $i,j\in\\{1,2,3\\}$:

$\begin{array}[]{ll}0.5\leq\mathbb{P}\\!\left(F_{i}|F_{j}\wedge
F_{k}\right)\leq 1,&i\neq j,i\neq k,j\neq k;\\\
0\leq\mathbb{P}\\!\left(S_{i}\vee S_{j}|F_{i}\right)\leq 0.2,&i\neq j;\\\
0.03\leq\mathbb{P}\\!\left(C_{i}|S_{i}\right)\leq 0.04;&\\\
0\leq\mathbb{P}\\!\left(C_{i}|\neg S_{i}\right)\leq 0.01.\end{array}$

The structure of the LCN is depicted in Figure 3. Note that there are several
directed cycles in this dependency graph.

$F_{2}\wedge F_{3}$$F_{1}\wedge F_{3}$$F_{1}\wedge
F_{2}$$F_{1}$$F_{2}$$F_{3}$$S_{1}\vee S_{2}$$S_{2}\vee S_{3}$$S_{1}\vee
S_{3}$$S_{1}$$S_{2}$$S_{3}$$\neg S_{1}$$\neg S_{2}$$\neg
S_{3}$$C_{1}$$C_{1}$$C_{1}$ Figure 3: The dependency graph of the LCN in
Example 3.1.

Qian et al. [16] then define:

######  Definition 3.2.

The lcn-parents of a proposition $A$, denoted by $\mbox{\rm lcn-pa}(A)$, are
the propositions such that there exists a directed path in the dependency
graph from each of them to $A$ in which all intermediate nodes are formulas.

######  Definition 3.3.

The lcn-descendants of a proposition $A$, denoted by $\mbox{\rm lcn-de}(A)$,
are the propositions such that there exists a directed path in the dependency
graph from $A$ to each of them in which no intermediate node is a parent of
$A$.

The connections between these concepts and the definitions of parent and
descendant in Section 2 will be clear in the next section.

In any case, using these definitions Qian et al. [16] proposed a Markov
condition:

######  Definition 3.4 (LMC(LCN)).

A node $A$ is independent, given its lcn-parents, of all nodes that are not
$A$ itself nor lcn-descendants of $A$ nor lcn-parents of $A$.

The Markov condition in Definition 3.4 is:

$X\;\rotatebox[origin={c}]{90.0}{$\models$}\;\mathcal{N}\backslash\\{\\{A\\}\cup\mbox{lcn-
de}(A)\cup\mbox{lcn-pa}(A)\\}\mid\mbox{lcn-pa}(A),$ (2)

where we use  $\models$ here, and in the remainder of the paper, to mean “is
independent of”.

We will often use the superscript $c$ to mean complement, hence
$\mathcal{A}^{c}\doteq\mathcal{N}\backslash\mathcal{A}$.

Qian et al. [16] have derived inference algorithms (that is, they consider the
computation of conditional probabilities) that exploit such independence
relations, and they examine applications that demonstrate the practical value
of LCNs.

It seems that a bit more discussion about the meaning of this Markov
condition, as well as its properties and consequences, would be welcome. To do
so, we find it useful to introduce a novel concept, namely, the structure of a
LCN.

$F_{2}\wedge F_{3}$$F_{1}\wedge F_{3}$$F_{1}\wedge
F_{2}$$F_{1}$$F_{2}$$F_{3}$$S_{1}\vee S_{2}$$S_{2}\vee S_{3}$$S_{1}\vee
S_{3}$$S_{1}$$S_{2}$$S_{3}$$\neg S_{1}$$\neg S_{2}$$\neg
S_{3}$$C_{1}$$C_{1}$$C_{1}$(a)

$F_{1}$$F_{2}$$F_{3}$$S_{1}$$S_{2}$$S_{3}$$C_{1}$$C_{1}$$C_{1}$(b)$F_{1,2,3}$$S_{1,2,3}$$C_{1}$$C_{2}$$C_{3}$(c)$F_{1,2}$$F_{2,3}$$S_{1,2,3}$$C_{1}$$C_{2}$$C_{3}$(d)

Figure 4: (a) The dependency graph for the LCN in Example 3.1, together with
the edges in the structure of the LCN. Edges in the structure are solid (the
ones added in the process are in blue); edges in and out of formula-nodes are
dotted. (b) The structure of the LCN, by removing the formula-nodes and
associated edges. (c) A directed acyclic graph with the chain components of
the chain graph that represents the structure. (d) A variant discussed in
Example 5.3.

##  4 The Structure of a LCN

The dependency graph of a LCN is rather similar in spirit to the factor graph
of a Bayesian network [13], where both random variables and conditional
probabilities are explicitly represented. This is a convenient device when it
comes to message-passing inference algorithms, but perhaps it contains too
much information when one wishes to examine independence relations.

We introduce another graph to be extracted from the dependency graph of a
given LCN, that we call the structure of the LCN, as follows:

  1. 1.

For each formula-node $\phi$ that appears as a conditioned formula in a
constraint in $\mathcal{T}_{U}$, place an undirected edge between any two
propositions that appear in $\phi$.

  2. 2.

For each pair of formula-nodes $\varphi$ and $\phi$ that appear in a
constraint, add a directed edge from each proposition in $\varphi$ to each
proposition in $\phi$.

  3. 3.

If, for some pair of proposition-nodes $A$ and $B$, there is now a pair of
edges $A\leftrightarrows B$, then replace both edges by an undirected edge.

  4. 4.

Finally, remove multiple edges and remove the formula-nodes and all edges in
and out of them.

######  Example 4.1.

Figures 4.a and 4.b depict the structure of the LCN in Example 3.1.

We have:

######  Lemma 4.2.

The set of lcn-parents of a proposition $A$ in a LCN is identical to the
boundary of $A$ with respect to the structure of the LCN.

######  Proof 4.3.

Consider a LCN with a dependency graph $\mathcal{D}$. If $B$ is a lcn-parent
of $A$ with respect to $\mathcal{D}$, then $B\rightarrow A$ or
$B\rightarrow\phi\rightarrow A$ or
$B\rightarrow\varphi\rightarrow\phi\rightarrow A$ or
$B\leftrightarrows\phi\rightarrow A$ or $B\rightarrow\phi\leftrightarrows A$
or $B\leftrightarrows\phi\leftrightarrows A$ for formula $\varphi$ and $\phi$;
hence $B$ appears either as a parent of $A$ or a neighbor in the structure of
the LCN. Conversely, if $B$ is a parent or a neighbor of $A$ in the structure
of the LCN, then one of the sequences of edges already mentioned must be in
$\mathcal{D}$, so $B$ is a lcn-parent of $A$ in $\mathcal{D}$.

The natural candidate for the concept of “descendant” in a structure, so as to
mirror the concept of lcn-descendant, is as follows:

######  Definition 4.4.

If there is a directed path from $A$ to $B$ such that no intermediate node is
a boundary node of $A$, then $B$ is a strict descendant of $A$.

Using the previous definitions, we can state a local Markov condition that
works for any graph but that, when applied to the structure of a LCN, has the
same effect as the original Markov condition LMC(LCN) (Definition 3.4) applied
to the LCN:

######  Definition 4.5 (LMC(C-STR)).

A node $A$ is independent, given its boundary, of all nodes that are not $A$
itself nor strict descendants of $A$ nor boundary nodes of $A$.

In symbols,

$X\;\rotatebox[origin={c}]{90.0}{$\models$}\;\mathcal{N}\backslash\\{\\{A\\}\cup\mbox{sde}(A)\cup\mbox{bd}(A)\\}\mid\mbox{bd}(A),$
(3)

where $\mbox{sde}(A)$ denotes the set of strict descendants of $A$.

We then have:

######  Theorem 4.6.

Given a LCN, the Markov condition LMC(LCN) in Definition 3.4 is identical,
with respect to the independence relations it imposes, to the local Markov
condition LMC(C-STR) in Definition 4.5 applied to the structure of the LCN.

######  Proof 4.7.

To prove that Expressions (2) and (3) are equivalent, we use the fact that
$\mbox{lcn-pa}(A)$ and $\mbox{bd}(A)$ are identical by Lemma 4.2 and we prove
(next) that $\mathcal{N}\backslash\\{\\{A\\}\cup\mbox{lcn-de}(A)\cup\mbox{lcn-
pa}(A)\\}$ is equal to
$\mathcal{N}\backslash\\{\\{A\\}\cup\mbox{sde}(A)\cup\mbox{bd}(A)\\}$.

Suppose then that $B\in\mathcal{N}\backslash\\{\\{A\\}\cup\mbox{lcn-
de}(A)\cup\mbox{lcn-pa}(A)\\}$ and assume, to obtain a contradiction, that
$B\in(\mathcal{N}\backslash\\{\\{A\\}\cup\mbox{sde}(A)\cup\mbox{bd}(A)\\})^{c}$.
So, our assumption is that $B\in\\{A\\}\cup\mbox{sde}(A)\cup\mbox{bd}(A)$, and
the latter union can be written as
$\\{A\\}\cup\mbox{bd}(A)\cup((\mbox{bd}(A))^{c}\cap\mbox{sde}(A))$, a union of
disjoint sets. So it may be either that
$\bullet$ We have $B=A$, a contradiction.
$\bullet$ We have $B\in\mbox{bd}(A)$. Then $B$ is either a parent or a
neighbor, and in both cases there must be an edge from $B$ to $A$ in the
dependency graph and then $B\in\mbox{lcn-pa}(A)$, a contradiction.
$\bullet$ We have $B\in(\mbox{bd}(A))^{c}\cap\mbox{sde}(A)$. Then there must
be a directed path from $A$ to $B$ (with intermediate nodes that are not
boundary nodes) in the structure, and so there must be a corresponding
directed path from $A$ to $B$ (with intermediate nodes that are not parents)
in the dependency graph; so $B\in\mbox{lcn-de}(A)$, a contradiction.
So, we always get a contradiction; hence if
$B\in\mathcal{N}\backslash\\{\\{A\\}\cup\mbox{lcn-de}(A)\cup\mbox{lcn-
pa}(A)\\}$ then
$B\in\mathcal{N}\backslash\\{\\{A\\}\cup\mbox{sde}(A)\cup\mbox{bd}(A)\\}$.

Suppose now that we have a node $B$, distinct from $A$, such that
$B\in\mathcal{N}\backslash\\{\\{A\\}\cup\mbox{sde}(A)\cup\mbox{bd}(A)\\}$ and
assume, to obtain a contradiction, that
$B\in(\mathcal{N}\backslash\\{\\{A\\}\cup\mbox{lcn-de}(A)\cup\mbox{lcn-
pa}(A)\\})^{c}$. The reasoning that follows is parallel to the one in the last
paragraph, but this case has a few additional twists to take care of. So, our
assumption is that $B\in\\{A\\}\cup\mbox{lcn-de}(A)\cup\mbox{lcn-pa}(A)$, and
the latter union can be written as $\\{A\\}\cup\mbox{lcn-
pa}(A)\cup((\mbox{lcn-pa}(A))^{c}\cap\mbox{lcn-de}(A))$, again a union of
disjoint sets. So it may be either that
$\bullet$ We have $B=A$, a contradiction.
$\bullet$ We have $B\in\mbox{lcn-pa}(A)$. Then there is a directed edge from
$B$ to $A$, or a bi-directed edge between them, and $B\in\mbox{bd}(A)$, a
contradiction.
$\bullet$ We have $B\in(\mbox{lcn-pa}(A))^{c}\cap\mbox{lcn-de}(A)$. Then there
must be a path from $A$ to $B$ in the dependency graph (with intermediate
nodes that are not parents), and by construction of the structure there must
be a path from $A$ to $B$ in the structure (with intermediate nodes that are
not boundary nodes). The latter path cannot be an undirected path; otherwise,
it would have passed through a parent of $A$ in the dependency graph,
contradicting the assumption that $B$ is a lcn-descendant. As there is a
directed path that cannot go through a parent in the structure,
$B\in\mbox{sde}(A)$, a contradiction.
So, we always get a contradiction; hence if
$B\in\mathcal{N}\backslash\\{\\{A\\}\cup\mbox{sde}(A)\cup\mbox{bd}(A)\\}$ then
$B\in\mathcal{N}\backslash\\{\\{A\\}\cup\mbox{lcn-de}(A)\cup\mbox{lcn-
pa}(A)\\}$. Thus the latter two sets are identical and the proof is finished.

##  5 Chain Graphs and Factorization

If the structure of a LCN is a directed acyclic graph, the LMC(LCN) is
actually the usual local Markov condition for directed acyclic graphs as
applied to Bayesian or credal networks [6, 14]. If instead all constraints in
a LCN belong to $\mathcal{T}_{U}$, all of them only referring to
“unconditional” probabilities (that is, $\varphi=\top$ in every constraint),
then the structure of the LCN is an undirected graph endowed with the usual
local Markov condition for undirected graphs.

These previous points can be generalized in a satisfying way whenever the
structure contains no directed cycle:

######  Theorem 5.1.

If the structure of a LCN is a chain graph, and probabilities are positive,
then the Markov condition LMC(LCN) in Definition 3.4 is identical, with
respect to the independence relations it imposes, to the LMC(C) applied to the
structure.

Before we prove this theorem, it should be noted that sets of descendants and
strict descendants are not identical. This is easy to see in graphs with
directed cycles: in Figure 1.b, node $B$ has descendants $\\{A,C,D\\}$ and
strict descendants $\\{A,D\\}$. But even in chain graphs we may have
differences: for instance, suppose that in Figure 1.e we add a single directed
edge from $D$ to a new node $E$; then $E$ is the only descendant of $B$, but
$B$ has no strict descendants.

In fact, the descendants of a node $A$ can be divided into two sets. First, a
node $B$ is in the first set if and only if there is at least one directed
path from $A$ to $B$ that starts with a directed edge. All of those nodes are
strict descendants of $A$ when the structure is a chain graph. Second, a node
$C$ is in the second set if and only if all directed paths from $A$ to $C$
start with an undirected edge. Then all directed paths from $A$ to $C$ first
reach a node that is in the boundary of $A$ and consequently $C$ is not a
strict descendant of $A$. When the structure is a chain graph, the first set
is thus exactly $\mbox{sde}(A)$, and we migh refer to the second set as
$\mbox{wde}(A)$, the set of “weak” descendants of $A$. By construction we have
$\mbox{sde}(A)\cap\mbox{wde}(A)=\emptyset$. Moreover, we conclude (see Figure
5) that

$(\mbox{sde}(A))^{c}=(\mbox{de}(A))^{c}\;\cup\;\mbox{wde}(A),$

from which we have that
$\mathcal{N}\backslash(\\{A\\}\cup\mbox{sde}(A)\cup\mbox{bd}(A))=\\{A\\}^{c}\cap((\mbox{de}(A))^{c}\;\cup\;\mbox{wde}(A))\cap(\mbox{bd}(A))^{c}$.
Note that
$\left(\\{A\\}^{c}\cap\mbox{wde}(A)\cap(\mbox{bd}(A))^{c}\right)=\mbox{wde}(A)$
by construction, hence
$\mathcal{N}\backslash(\\{A\\}\cup\mbox{sde}(A)\cup\mbox{bd}(A))$ is the union
of two disjoint sets:

$\left(\\{A\\}^{c}\cap(\mbox{de}(A))^{c}\cap(\mbox{bd}(A))^{c}\right)\;\;\cup\;\;\mbox{wde}(A).$
(4)

$A$$\mbox{bd}(A)$$\mbox{sde}(A)$$\mbox{wde}(A)$ Figure 5: Nodes of a LCN whose
structure is a chain graph. The dotted area contains the nodes that are not
descendants. In a chain graph, the strict descendants cannot be in the
boundary.

######  Proof 5.2.

Suppose we have the LMC(C-STR); so, for any node $A$, we have Expression (3).
Using Expression (4), we have
$A\rotatebox[origin={c}]{90.0}{$\models$}((\\{A\\}^{c}\cap(\mbox{de}(A))^{c}\cap(\mbox{bd}(A))^{c})\cup\mbox{wde}(A))|\mbox{bd}(A)$;
using the Decomposition property of probabilities,444The Decomposition
property states that $X\rotatebox[origin={c}]{90.0}{$\models$}Y\cup W|Z$
implies $X\rotatebox[origin={c}]{90.0}{$\models$}Y|Z$ for sets of random
variables $W,X,Y,Z$ [13]. we obtain
$A\rotatebox[origin={c}]{90.0}{$\models$}\\{A\\}^{c}\cap(\mbox{de}(A))^{c}\cap(\mbox{bd}(A))^{c}|\mbox{bd}(A)$.
Thus the LMC(C) holds.

Suppose the LMC(C) holds; given then positivity condition, the GMC(C) holds
[5]. Take a node $A$ and suppose there is a node
$B\in\mathcal{N}\backslash(\\{A\\}\cup\mbox{sde}(A)\cup\mbox{bd}(A))$. We now
prove that $B$ is separated from $A$ by $\mbox{bd}(A)$ in

$\displaystyle\mathcal{G}^{*}_{A}\\!\\!\\!\\!$ $\displaystyle\doteq$
$\displaystyle\\!\\!\\!\\!\mathcal{G}^{ma}(\\{A\\}\\!\cup\\!(\\{A\\}^{c}\\!\cap\\!(\mbox{sde}(A))^{c}\\!\cap\\!(\mbox{bd}(A))^{c})\\!\cup\\!\mbox{bd}(A))$
$\displaystyle=$ $\displaystyle\mathcal{G}^{ma}((\mbox{sde}(A))^{c}),$

and consequently the GMC(C) leads to
$A\rotatebox[origin={c}]{90.0}{$\models$}(\\{A\\}^{c}\cap(\mbox{sde}(A))^{c}\cap(\mbox{bd}(A))^{c})|\mbox{bd}(A)$
as desired. Note that, by construction, nodes in $\mbox{sde}(A)$ cannot be in
the ancestral set of any node in $\mbox{wde}(A)$, so $\mbox{sde}(A)$ is not in
$\mathcal{G}^{*}_{A}$ and consequently $\mathcal{G}^{*}_{A}$ is the moral
graph of the graph consisting of nodes in $(\mbox{sde}(A))^{c}$ and edges
among them in the structure. Now reason as follows. Paths that go from $A$ to
a parent or neighbor are obviously blocked by $\mbox{bd}(A)$. The only
possible “connecting” paths from $A$ to $B$ in $\mathcal{G}^{*}_{A}$ would
have to start with an undirected edge from $A$ to say $C$, an edge added to
$\mathcal{G}^{*}_{A}$ because $A$ and $C$ have directed edges to a common
chain component. Now suppose $A$ points to node $D$ in this latter chain
component. Then $D$ is not in the boundary of $A$ (no directed cycles) and the
only possible way for $D$ to be in $\mathcal{G}^{*}_{A}$ is if there is a
directed path from $D$ to a node $E$ in $\mbox{wde}(A)$, but the resulting
directed path from $A$ to $E$ would create a contradiction (as $E$ would then
not be in $\mbox{wde}(A)$). Such “connecting” paths from $A$ to $B$ are thus
impossible in $\mathcal{G}^{*}_{A}$. Hence we must have separation of $A$ and
$B$ by $\mbox{bd}(A)$ in $\mathcal{G}^{*}_{A}$.

The significance of the previous theorem is that, assuming that all
probabilities are positive, the local Markov condition for a chain graph is
equivalent both to the global Markov condition and to the factorization
property of chain graphs. This allows us to break down the probability
distribution over all random variables in a LCN in hopefully much smaller
pieces that require less specification effort.

######  Example 5.3.

Figure 4.b depicts a structure that is in fact a chain graph. We can group
variables to obtain chain components $F_{1,2,3}$ and $S_{1,2,3}$ and draw a
directed acyclic graph with the chain components, as in Figure 4.c. The joint
probability distribution factorizes as Expression (1):

$\displaystyle\mathbb{P}\\!\left(F_{1,2,3}=f,S_{1,2,3}=s,C_{1}\\!=\\!c_{1},C_{2}\\!=\\!c_{2},C_{3}\\!=\\!c_{3}\right)$
$\displaystyle=$
$\displaystyle\mathbb{P}\\!\left(F_{1,2,3}=f\right)\mathbb{P}\\!\left(S_{1,2,3}=s|F_{1,2,3}=f\right)$
$\displaystyle\mathbb{P}\\!\left(C_{1}=c_{1}|S_{1,2,3}=s\right)\mathbb{P}\\!\left(C_{2}=c_{2}|S_{1,2,3}=s\right)$
$\displaystyle\mathbb{P}\\!\left(C_{3}=c_{3}|S_{1,2,3}=s\right),$

where $f$ is a configuration of the random variables in $F_{1,2,3}$, while $s$
is a configuration of the random variables in $S_{1,2,3}$. Because there are
no independence relations “inside” the chain components, this factorization is
guaranteed even if some probability values are equal to zero [5].

Suppose that the three constraints
$0.5\leq\mathbb{P}\\!\left(F_{i}|F_{j}\wedge F_{k}\right)\leq 1$ were replaced
so that we had a similar structure but instead of a single chain component
with $F_{1}$, $F_{2}$, $F_{3}$, suppose we had two chain components, one with
$F_{1}$ and $F_{2}$, the other with $F_{2}$ and $F_{3}$. The chain components
might be organized as in Figure 4.d. If all probabilities are positive, that
chain graph leads to a factorization of the joint probability distribution
similar to the previous one, but now
$\mathbb{P}\\!\left(F_{1,2,3}=f_{1}f_{2}f_{3}\right)=\mathbb{F}_{1}(F_{1,2}=f_{1}f_{2})\mathbb{F}_{2}(F_{2,3}=f_{2}f_{3})$,
where $\mathbb{F}_{1}$ and $\mathbb{F}_{2}$ are positive functions, and the
values of $F_{1}$, $F_{2}$ and $F_{3}$ are indicated by $f_{1}$, $f_{2}$,
$f_{3}$ respectively.

In the previous paragraph the assumption that probabilities are positive is
important: when some probabilities are zero, there is no guarantee that a
factorization actually exists [15]. This is unfortunate as a factorization
leads to valuable computational simplifications. One strategy then is to
guarantee that all configurations do have positive probability, possibly by
adding language directives that bound probabilities from below. A language
command might consist of explict bounds, say $0.001$, or even a direct
guarantee of positivity without an explicit bounding value. This solution may
be inconvenient if we do have some hard constraints in the domain. For
instance, we may impose that $A\vee B$ (in which case $\mathbb{P}\\!\left(\neg
A\wedge\neg B\right)=0$). However, is is still possible to obtain a
factorization if hard constraints are imposed. Say we have a formula, for
instance $A\vee B$, that must be satisfied. We treat it as a constraint
$1\leq\mathbb{P}\\!\left(A\vee B\right)\leq 1$ in $\mathcal{T}_{U}$, thus
guaranteeing that there is a clique containing its propositions/random
variables. Then we remove the impossible configurations of these random
variables (in our running example, we remove $A=B=0$), thus reducing the
number of possible configurations for the corresponding clique. A
factorization is obtained again in the reduced space of configurations,
provided the remaining configurations do have positive probabilities. Finally,
an entirely different strategy may be pursued: adopt a stronger Markov
condition that guarantees factorization (and hence global independence
relations) in all circumstances. Moussouris [15] has identified one such
condition, where a system is strongly Markovian in case a Markov condition
holds for the system and suitable sub-systems. That (very!) strong condition
forces zero probabilities to be, in a sense, localized, so that probabilities
satisfy a nice factorization property; alas, the condition cannot be
guaranteed for all graphs, and its consequences have not been explored in
depth so far.

##  6 Directed Cycles

As noted already, existence of a factorization is a very desirable property
for any probabilistic formalism: not only it simplifies calculations, but it
also emphasizes modularity in modeling and ease of understanding. In the
previous section we have shown that LCNs whose structure is a chain graph do
have, under a positivity assumption, a well-known factorization property. We
now examine how that result might be extended when structures have directed
cycles.

The LMC(LCN) is, of course, a local condition that can be applied even in the
presence of directed cycles. However, local Markov conditions may not be very
satisfactory in the presence of directed cycles, as a simple yet key example
suggests:

######  Example 6.1.

Take a LCN whose dependency graph is a long cycle $A_{1}\rightarrow
A_{2}\rightarrow\dots A_{k}\rightarrow A_{1}$, for some large $k$. No $A_{i}$
has any non-descendant non-parent. And no $A_{i}$ has any non-strict-
descendant non-parent either. The local Markov conditions we have contemplated
do not impose any independence relation.

Local conditions seem too weak when there are long cycles. On the other hand,
a global condition may work fine in those settings. For instance, apply the
GMC(C) to the graph in Example 6.1; the condition does impose non-trivial
independence relations such as
$A_{1}\rotatebox[origin={c}]{90.0}{$\models$}A_{3},\dots,A_{k-1}|A_{2},A_{k}$
and
$A_{2}\rotatebox[origin={c}]{90.0}{$\models$}A_{4},\dots,A_{k}|A_{1},A_{3}$
(and more generally, for any $A_{i}$ with $2<i<k-2$, we have
$A_{i}\rotatebox[origin={c}]{90.0}{$\models$}A_{1},\dots,A_{i-2},A_{i+2},A_{k}|A_{i-1},A_{i+1}$).

At this point it is mandatory to examine results by Spirtes [18], as he has
studied local and global conditions for directed graphs, obtaining
factorization results even in the presence of directed cycles. The local
Markov condition adopted by Spirtes [18] is just the one adopted for directed
graphs in Section 2:

######  Definition 6.2 (LMC(D)).

A node $A$ is independent, given its parents, of all nodes that are not $A$
itself nor descendants nor parents of $A$.

The global Markov condition adopted by Spirtes [18] is just the GMC(C)
(Definition 2.2). Spirtes shows that the LMC(D) is not equivalent to the
GMC(C) for directed graphs with directed cycles. This observation can be
adapted to our setting as follows:

######  Example 6.3.

Suppose we have a LCN whose dependency graph is depicted in Figure 1.d. For
instance, we might have $0.1\leq\mathbb{P}\\!\left(X|Y\right)\leq 0.2$
whenever $Y\rightarrow X$ is an edge in that figure. Assume all configurations
have positive probability.

The LMC(D) applied to this dependency graph yields only
$A\rotatebox[origin={c}]{90.0}{$\models$}C$,
$B\rotatebox[origin={c}]{90.0}{$\models$}C|A,D$ and
$A\rotatebox[origin={c}]{90.0}{$\models$}D|B,C$.

However, if we apply the GMC(C) directly to the dependency graph, we do not
get the same independence relations: then we only obtain
$A\rotatebox[origin={c}]{90.0}{$\models$}C$ and
$A\rotatebox[origin={c}]{90.0}{$\models$}C|B,D$, perhaps a surprising result
(in this case, the graph $\mathcal{G}^{ma}(A,B,C,D)$ is depicted in Figure
2.d).

Spirtes [18, Lemma 3] has shown that, for a directed graph that may have
directed cycles, a positive probability distribution over the random variables
is a product of factors, one per random variable, iff the distribution
satisfies the GMC(C) for the graph. Note that the GMC(C) is equivalent, for
graphs without directed cycles, under a positivity assumption, to the LMC(C).

However, there is a difficulty in applying Spirtes’ result to our setting.

######  Example 6.4.

Consider Example 6.3. The structure of the LCN is the chain graph in Figure
1.e, and we know that the LMC(LCN) is equivalent to the LMC(C) and GMC(C) for
chain graphs. In fact, the LMC(LCN), the LMC(C), the LMC(C-STR), and the
GMC(C) also yield only $A\rotatebox[origin={c}]{90.0}{$\models$}C$,
$B\rotatebox[origin={c}]{90.0}{$\models$}C|A,D$ and
$A\rotatebox[origin={c}]{90.0}{$\models$}D|B,C$ when applied to the structure.
Clearly this is not the same set of independence relations imposed by the
GMC(C) applied to the dependency graph (as listed in Example 6.3). There is a
difference between undirected and bi-directed edges when it comes to the
GMC(C).

The message of this example is that we cannot impose the GMC(C) on (a suitable
version of) directed dependency graphs and hope to keep the LMC(LCN) by Qian
et al. [16]. If we want the factorization induced by the GMC(C) on (a version
of) dependency graphs, we must somehow modify the original semantics for LCNs
by Qian et al. [16].

It is worth summarizing the discussion so far. First, it is well-known that
the LMC(C) and the GMC(C) are equivalent, under a positivity assumption, for
chain graphs (both conditions may differ in the presence of directed cycles).
Second, we know that the LMC(LCN) for dependency graphs is equivalent to the
LMC(C-STR) with respect to the corresponding structures. And if the structure
is a chain graph, then the LMC(C-STR) and the LMC(C) are equivalent when
applied to the structure. But for general dependency graphs any local
condition seems quite weak. We might move to general dependency graphs by
adapting the GMC(C) to them, so as to look for a factorization result;
however, we saw that the result is not equivalent to what we obtained by
applying the GMC(C) to structures.

In the next section we examine alternative semantics that are based on
applying the GMC(C) to structures (possibly with directed cycles). Before we
jump into that, it is worth noticing that there are many other relevant
results in the literature besides the ones by Spirtes. For instance,
dependency networks [11] allow for directed cycles and do have a modular
specification scheme; they have only an approximate factorization, but that
may be enough in applications. Another proposal has been advanced by Schmidt
and Murphy [17], where directed cycles are allowed and the adopted Markov
condition looks only at the Markov blanket of nodes; it does not seem that a
factorization has been proven for that proposal, but it is attractive in its
simplicity. There are also many kinds of graphs that have been contemplated to
handle causal loops and dynamic feedback systems [3, 12, 4]. This is indeed a
huge literature, filled with independence conditions and factorization
properties, to which we cannot do justice in the available space. It is
necessary to examine whether we can bring elements of those previous efforts
into LCNs. We leave a more detailed study for the future.

##  7 New Semantics for LCNs

In this section we explore new semantics for LCNs by applying the GMC(C) to
structures. This is motivated by the weakness of local conditions as discussed
in the previous section, and also on the fact that a condition based on
moralized graphs is the most obvious route to factorization properties (as the
Hammersley-Clifford theorem can then be invoked under a positivity assumption
[15]).

Here is a (new) semantics: a LCN represents the set of probability
distributions over its nodes such that all constraints in the LCN are
satisfied, and each distribution satisfies the GMC(C) with respect to the
structure. Note that the GMC(C) is equivalent to the LMC(LCN) when a structure
is a chain graph, but these conditions may differ in the presence of directed
cycles.

The path to a factorization result is then as follows. Take the mixed-
structure and, for each node $A$, build a set $\mathcal{C}_{A}$ with all nodes
that belong to directed cycles starting at $A$. If there a directed cycle in a
set $\mathcal{C}_{B}$ such that $B$ is in $\mathcal{C}_{A}$, then merge
$\mathcal{C}_{A}$ and $\mathcal{C}_{B}$ into a set $\mathcal{C}_{A,B}$; repeat
this until there are no more sets to merge (this must stop, in the worst case
with a single set containing all nodes). For each set, replace all nodes in
the set by a single “super”-node, directing all edges in and out of nodes in
the set to this super-node. The resulting graph has no directed cycles, so the
GMC(C) applied to it results in the usual factorization over chain components
of the resulting graph. Now each super-node is in fact a set of nodes that can
be subject to further factorization, even though it is an open question
whether a decomposition can be obtained with factors that are directly related
to graph properties.

To continue, we suggest that, instead of using structures as mere secondary
objects that help us clarify the meaning of dependency graphs, structures
should be the primary tools in dealing with LCNs. That is, we should translate
every LCN to its structure (without going through the dependency graph) and
then apply appropriate Markov conditions there. Given a LCN, we can build its
structure by taking every proposition as a node and then:

  1. 1.

For each constraint
$\alpha\leq\mathbb{P}\\!\left(\phi|\varphi\right)\leq\beta$ in
$\mathcal{T}_{U}$, add an undirected arrow between each pair of proposition-
nodes in $\phi$.

  2. 2.

For each constraint
$\alpha\leq\mathbb{P}\\!\left(\phi|\varphi\right)\leq\beta$ add a directed
edge from each proposition-node in $\varphi$ to each proposition-node in
$\phi$ (if $\varphi$ is $\top$, there is no such edge to add).

  3. 3.

Remove multiple identical edges.

  4. 4.

For each pair of nodes $A$ and $B$, if there is a bi-directed edge
$A\leftrightarrows B$ between them, replace the two edges by a single
undirected edge $A\sim B$.

For instance, the procedure above goes directly from the LCN in Example 3.1 to
the structure in Figure 4.b.

When we think of structures this way, we might wish to differentiate the
symmetric connections that appear when a pair of propositions appear in a
formula $\phi$ from the mutual influences that one proposition is conditioned
on the other and vice-versa.

An alternative semantics would be as follows. Take a LCN and build a mixed-
structure by going through the first two steps above. That is, create a node
per proposition that appears in the LCN; then take each constraint in
$\mathcal{T}_{U}$ and add undirected edges between any two propositions in
$\phi$, and finally take each constraint and add a directed edge from each
proposition that appears in $\varphi$ to each proposition that appears in the
corresponding $\phi$. Figure 6 depicts the mixed-structure for Example 3.1.

Now adopt: a LCN represents the set of probability distributions over its
nodes such that all constraints in the LCN are satisfied, and each
distribution satisfies the GMC(C) with respect to the mixed-structure.

$F_{1}$$F_{2}$$F_{3}$$S_{1}$$S_{2}$$S_{3}$$C_{1}$$C_{1}$$C_{1}$ Figure 6: The
mixed-structure for the LCN in Example 3.1.

$A$$B$$C$$E$$D$(a)

$A$$B$$C$$E$$D$(b)

Figure 7: Structures and mixed-structures in Example 7.1.

The next example emphasizes the differences between semantics.

######  Example 7.1.

Suppose we have a LCN with constraints $\mathbb{P}\\!\left(B|A\right)=0.2$,
$\mathbb{P}\\!\left(D|E\right)=0.3$, $\mathbb{P}\\!\left(B\vee C\right)=0.4$,
$\mathbb{P}\\!\left(C\vee D\right)=0.5$. Both the structure and the mixed-
structure of this LCN is depicted in Figure 7.a. Consider another LCN with
constraints $\mathbb{P}\\!\left(B|A\wedge C\right)=0.2$,
$\mathbb{P}\\!\left(C|B\wedge D\right)=0.3$, and $\mathbb{P}\\!\left(D|C\wedge
E\right)=0.4$. This second LCN has the same structure as the first one, but
the mixed-structure is depicted in Figure 7.b. The GMC(C) produces quite
different sets of independence relations when applied to these distinct mixed-
structures; for instance, $A,B\rotatebox[origin={c}]{90.0}{$\models$}D|C,E$ in
the first LCN, but not necessarily in the second;
$A,B\rotatebox[origin={c}]{90.0}{$\models$}E|C,D$ in the second LCN, but not
necessarily in the first. This seems appropriate as the LCNs convey quite
distinct scenarios, one related to the symmetry of logical constraints, the
other related to the links induced by directed influences.

We hope to pursue a comparison between the theoretical and pragmatic aspects
of these semantics in future work.

##  8 Conclusion

In this paper we visited many Markov conditions that can be applied, if
properly adapted, to Logical Credal Networks [16]. We reviewed existing
concepts and introduced the notion of structure of a LCN, showing that the
original local condition LMC(LCN) can be viewed as a local condition on
structures. We then showed that the LMC(LCN) is equivalent to a usual local
condition when the structure is a chain graph, and this leads to a
factorization result. Moreover, we introduced a new semantics based on
structures and a global Markov condition — a semantics that agrees with the
original one when the structure is a chain graph but that offers a possible
path to factorization properties.

There are many issues left for future work. LCNs stress the connection between
the syntactic form of constraints and the semantic consequences of
independence assumptions, a theme that surfaces in many probabilistic logics.
We must investigate more carefully the alternatives when extracting
independence relations from constraints, in particular to differentiate ways
in which bi-directed edges are created.

We must also examine positivity assumptions. What is the best way to guarantee
a factorization? Should we require the user to explicitly express positivity
assumptions? Should we allow for logical constraints that assign probability
zero to some configurations; if so, which kinds of configurations, and how to
make those constraints compatible with factorization properties?

It is also important to study a large number of Markov conditions that can be
found in the literature, both the ones connected with chain graphs and the
ones connected with causal and feedback models, that we did not deal with in
this paper. We must verify which conditions lead to factorization results, and
which conditions are best suited to capture the content of logical formulas,
causal influences, feedback loops.

In a more applied perspective, we must investigate whether the ideas behind
LCNs can be used with practical specification languages such as Probabilistic
Answer Set Programming, and we must test how various semantics for LCNs fare
in realistic settings.

## Acknowledgements

This work was carried out at the Center for Artificial Intelligence (C4AI -
USP/IBM/FAPESP), with support by the São Paulo Research Foundation (FAPESP
grant 2019/07665-4) and by the IBM Corporation. The author was partially
supported by CNPq grant 312180/2018-7. We acknowledge support by CAPES -
Finance Code 001.

## References

  * Andersen and Hooker [1996] Kim A. Andersen and John N. Hooker.  A linear programming framework for logics of uncertainty.  _Decision Support Systems_ , 16:39–53, 1996.
  * Bacchus [1990] Fahiem Bacchus.  _Representing and Reasoning with Probabilistic Knowledge: A Logical Approach_.  MIT Press, Cambridge, 1990.
  * Baier et al. [2022] Christel Baier, Clemens Dubslaff, Holger Hermanns, and Nikolai Kafer.  On the foundations of cycles in bayesian networks.  In J. F. Raskin, K. Chatterjee, L. Doyen, and R. Majumdar, editors, _Principles of Systems Design_ , volume 13660 of _Lecture Notes in Computer Science_. Springer, 2022.
  * Bongers et al. [2021] Stephan Bongers, Patrick Forré, Jonas Peters, and Joris M. Mooij.  Foundations of structural causal models with cycles and latent variables.  _Annals of Statistics_ , 49(5):2885–2915, 2021\.
  * Cowell et al. [1999] Robert G. Cowell, A. Philip Dawid, Steffen L. Lauritzen, and David J. Spiegelhalter.  _Probabilistic Networks and Expert Systems_.  Springer-Verlag, New York, 1999.
  * Cozman [2000] Fabio G. Cozman.  Credal networks.  _Artificial Intelligence_ , 120:199–233, 2000.
  * Cozman and Polastro [2009] Fabio Gagliardi Cozman and Rodrigo Bellizia Polastro.  Complexity analysis and variational inference for interpretation-based probabilistic description logics.  In _Proceedings of the Twenty-Fifth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-09)_ , pages 117–125, Corvallis, Oregon, 2009. AUAI Press.
  * da Rocha and Cozman [2005] José Carlos Ferreira da Rocha and Fabio Gagliardi Cozman.  Inference in credal networks: branch-and-bound methods and the A/R+ algorithm.  _International Journal of Approximate Reasoning_ , 39(2-3):279–296, 2005.
  * Doder and Ognjanovic [2017] D. Doder and Z. Ognjanovic.  Probabilistic logics with independence and confirmation.  _Studia Logica_ , 105:943–969, 2017.
  * Halpern [2003] Joseph Y. Halpern.  _Reasoning about Uncertainty_.  MIT Press, Cambridge, Massachusetts, 2003.
  * Heckerman et al. [2000] David Heckerman, David Maxwell Chickering, Christopher Meek, Robert Rounthwaite, and Carl Kadie.  Dependency networks for inference, collaborative filtering, and data visualization.  _Journal of Machine Learning Research_ , 1:49–75, 2000\.
  * Hyttinen et al. [2012] A. Hyttinen, F. Eberhardt, and P. Hoyer.  Learning linear cyclic causal models with latent variables.  _Journal of Machine Learning Research_ , 13:3387–3439, 2012.
  * Koller and Friedman [2009] Daphne Koller and Nir Friedman.  _Probabilistic Graphical Models: Principles and Techniques_.  MIT Press, 2009.
  * Mauá and Cozman [2020] Denis Deratani Mauá and Fabio Gagliardi Cozman.  Thirty years of credal networks: Specification, algorithms and complexity.  _International Journal of Approximate Reasoning_ , 126:133–157, 2020.
  * Moussouris [1974] John Moussouris.  Gibbs and Markov random systems with constraints.  _Journal of Statistical Physics_ , 10(1):11–33, January 1974.  ISSN 0022-4715 (Print) 1572-9613 (Online).
  * Qian et al. [2022] Haifeng Qian, Radu Marinescu, Alexander Gray, Debarun Bhattacharjya, Francisco Barahona, Tian Gao, Ryan Riegel, and Pravinda Sahu.  Logical credal networks.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2022.
  * Schmidt and Murphy [2009] Mark Schmidt and Kevin Murphy.  Modeling discrete interventional data using directed cyclic graphical models.  In _Conference on Uncertainty in Artificial Intelligence_ , 2009.
  * Spirtes [1995] Peter Spirtes.  Directed cyclic graphical representations of feedback models.  In _Conference on Uncertainty in Artficial Intelligence_ , pages 491–498, 1995.