-
A simple example showing the need of coherently combining logic and
probability is considered in [
7
]. Assume we are given a report of the results of 100
students in four subjects, namely logic (L), knowledge representation (K),
probability (P ) and AI (A). From those data, depicted in Table 1, we thus want to
learn a probabilistic model such as a Bayesian network (BN) [
8
]. The white nodes
in Figure 1 show a BN model that assumes conditional independence between K
and P given A and L. To learn BN parameters we use a Laplace prior of strength
one. This assigns probability Pr(X = x) = [n(X = x) + jXj 1]=[n( ) + 1] to the
state x of variable X, where jXj is the cardinality of X and n is a counting
function for the data set (e.g., Pr(L = 0) = 70:5=101). Out of sixteen possible
combinations, Table 1 reports no observations for eight cases (grey rows). Yet, seven
of these eight cases (dark grey) are not observed because of logical constraints:
L _ P (it is compulsory for a student to either take logic or probability), A ! P
(probability is prerequisite for AI), and K ! A _ L (knowledge representation
is a prerequisite to either AI or logic). The light grey row corresponds instead
to a possible con guration for which we just do not have observations. Yet, the
BN cannot distinguish between those two cases and non-zero probabilities can
be therefore assigned to impossible events (e.g., Pr(A = 1; P = 0) ' 0:005). The
logical constraints can then be embedded in the BN by adding auxiliary nodes
(grey nodes in Figure 1). Each constraint induces a Boolean variable which is a
child of all the variables involved in the logical constraint and whose conditional
probability table has zero/one values modelling the fact that the variable is true
if and only if the logical constraint is satis ed. The model is therefore queried
given the fact that the auxiliary variables implementing the constraints are in
their true state. Such a BN approach to the learning of probability mass
functions that are subject to domain constraints might increase the treewidth of the
original graphical model, thus potentially a ecting the speed of the inferences
(exact inference is exponential in this parameter).
Probabilistic sentential decision diagrams (PSDDs for short) [
7
] o er an
elegant alternative approach to the learning of probabilistic models from data
subject to logical constraints. A PSDD is a circuit representation of a joint
probability mass function assigning zero probability to the impossible states of
the logical constraints. More speci cally, it is a parametrised directed acyclic
graph. Each non-root node is either a logical AND gate with two inputs, or a
logical OR gate with an arbitrary number of inputs and whose incoming wires
are annotated with the probabilities of a conditional mass function (that can
be learned from the data). These types of nodes alternate. Each root node is
a univariate mass function, assigning probability one to X, when X is always
true, to :X when X is always false, or assigning to X (written as ( : X))
when X is true with probability (conditional to a certain context encoded by
the circuit). E.g., the circuit in Figure 2 with sharp numbers instead of intervals
associated to the wires de nes a PSDD consistent with the logical constraints in
the example.
Inference in PSDDs, intended here as the computation of the probability of
marginal or conditional queries for single variables, takes time linear in the size
of the graph. Dedicated algorithms have been developed to identify the smallest
circuit modeling a given formula [
2
]. This makes inferences based on a PSDD
typically faster than those based on a BN with auxiliary nodes implementing the
same constraints [
7
]. Yet, PSDDs embed context-speci c independence relations
and the problem of trading o the search for a small circuit with the learning of
proper dependence relations from the data is still relatively unexplored [
9
], while
many techniques have been proposed for the structural learning of BNs [
8
].
From sharp to interval probabilities. Both BN and PSDD parameters are
probabilities to be learned from the data set. These are sharp numerical
values corresponding to the mean of a posterior distribution or the maximum of a
likelihood. Yet, standard inference algorithms adopt only the sharp estimators,
while propagating the whole distribution might increase the inferential
complexity (e.g., [
6
]). This might be an issue especially if few data are available [
13
] or if
some data are missing according to an asystematic incompleteness process [
4
]. In
these cases, coping with sets instead of single probability mass functions might
o er a more cautious, and hence reliable, approach to probabilistic modelling.1
In particular the imprecise Dirichlet model (IDM) [
13
] replaces the above
considered estimate for P (X = x) with the interval [n(x); n(x) + jXj 1]=(n( ) + 1).
Thus, for instance, P (L = 0) 2 [70; 71]=101. IDM has been often applied to
BN quanti cation from data (e.g., [
1
]). The approach transforms the BN into a
credal network [
3
], and the local conditional probability mass functions,
associated to each variable and each con guration of the parent variables are replaced
by sets of probability mass functions consistent with such interval constraints.
The same can be done with PSDDs by replacing each probability mass function
annotating the incoming wires of a OR gate or a root node with a IDM-based
set of probability mass function.2 This might be valuable as the local parameters
of a PSDD are conditional probabilities based on a context. Indeed, the higher
is the number of variables in the context, the less data might be available to
learn the probabilities, and therefore IDM appears as more reliable from a
modelling perspective. As an example, Figure 2 depicts a PSDD with interval-valued
weights obtained in this way. We call such a model credal PSDD (CPSDD).
Exactly as a PSDD de nes a joint probability mass function which assigns non-zero
probability only to the joint states satisfying the logical constraints, a CPSDD
de nes a (credal) set of joint probability mass function assigning non-zero
proba1 Other extensions of the classical probability theory have been proposed. Among
others, we mention the evidence theory [
11
], the possibility theory [
5
], and fuzzy
sets theory [
15
]. The set-valued approach we consider here is based instead on the
imprecise probability theory [
12
] and can be regarded as a generalization of all the
previous ones [
14
], with a direct sensitivity analysis interpretation. To the best of
our knowledge, none of the other formalisms has been applied to PSDDs so far.
2 If the application of the IDM involves zero counts because of the logical constraints,
the IDM interval associated to the impossible event is replaced by a sharp zero.
bility to the non-impossible con gurations. The model semantics is as expected,
each element of this set of joint mass functions corresponds to a PSDD whose
(sharp) parameters have values consistent with the intervals in the CPSDD.
Inferences in CPSDDs are thence intended as the computation of the lower and
upper bounds of a query with respect to such a joint set of probability mass
functions. Notably, it seems possible to apply the same strategy proposed by
[
10
] for sum-product networks (SPNs) with set-valued speci cations of the
parameters to PSDDs. Yet, compared to SPNs, PSDDs allows to cope with logical
constraints. For joint or marginal queries, the inference corresponds to a
simple bottom-up propagation which can be easily achieved by interval arithmetic.
E.g., the query Pr(A = 0; P = 0) corresponds to a product of IDM intervals
and has value [ 3514301 ; 11091 ]. For conditional queries the situation might be more
involved. This is because local (linear) optimisation should be solved during the
intermediate steps of the propagation. By a derivation analogous to that in [
10
],
it is possible to argue that for CPSDDs with singly connected diagrams, i.e.,
such that each node has exactly one child, inference can be computed in time
linear with respect to the size of the circuit.
:L
L
:P
:L
:P
P
:L
L
:P
1
^
K
_
[ 11001 ; 11011 ]
^
_
^
[ 13001 ; 13011 ]
[ 16001 ; 16011 ]
_
0 [ 1381 ; 1391 ]
[ 1321 ; 1331 ] 1
_
0
^
?
^
1
^
A :
[ 5641 ; 5651 ]
_
P
0
^
?
1
^
A
_
P
0
^
?
0
^
?
_
L
1
^
K :
[ 2341 ; 2351 ]