Tractable Inference in Credal Sentential Decision Diagrams
  Probabilistic sentential decision diagrams are logic circuits where the
inputs of disjunctive gates are annotated by probability values. They allow for
a compact representation of joint probability mass functions defined over sets
of Boolean variables, that are also consistent with the logical constraints
defined by the circuit. The probabilities in such a model are usually learned
from a set of observations. This leads to overconfident and prior-dependent
inferences when data are scarce, unreliable or conflicting. In this work, we
develop the credal sentential decision diagrams, a generalisation of their
probabilistic counterpart that allows for replacing the local probabilities
with (so-called credal) sets of mass functions. These models induce a joint
credal set over the set of Boolean variables, that sharply assigns probability
zero to states inconsistent with the logical constraints. Three inference
algorithms are derived for these models, these allow to compute: (i) the lower
and upper probabilities of an observation for an arbitrary number of variables;
(ii) the lower and upper conditional probabilities for the state of a single
variable given an observation; (iii) whether or not all the probabilistic
sentential decision diagrams compatible with the credal specification have the
same most probable explanation of a given set of variables given an observation
of the other variables. These inferences are tractable, as all the three
algorithms, based on bottom-up traversal with local linear programming tasks on
the disjunctive gates, can be solved in polynomial time with respect to the
circuit size. For a first empirical validation, we consider a simple
application based on noisy seven-segment display images. The credal models are
observed to properly distinguish between easy and hard-to-detect instances and
outperform other generative models not able to cope with logical constraints.
