We consider tractable representations of probability distributions and the polytime operations they support. In particular, we consider a recently proposed arithmetic circuit representation, the Probabilistic Sentential Decision Diagram (PSDD). We show that PSDDs support a polytime multiplication operator, while they do not support a polytime operator for summing-out variables. A polytime multiplication operator makes PSDDs suitable for a broader class of applications compared to classes of arithmetic circuits that do not support multiplication. As one example, we show that PSDD multiplication leads to a very simple but effective compilation algorithm for probabilistic graphical models: represent each model factor as a PSDD, and then multiply them.

Neural Information Processing Systems http://nips.cc/

Neural Information Processing Systems http://nips.cc/

In this work, we aim to leverage prior symbolic knowledge to improve the performance ofdeepmodels.

In contrast, we show that the computation of one PI-explanation for an NBC can be achieved in log-linear time, and that the same result also applies to the more general class of linear classifiers. Furthermore, we show that the enumeration ofPI-explanations can beobtained with polynomial delay. Experimental results demonstrate the performance gains ofthe newalgorithms when compared with earlierwork.

In this paper we use explainability queries to formally compare the interpretability of machinelearningmodels.

In particular, we introduce the notion of a hierarchical route distribution and show how they can be leveraged to construct tractable PSDDs over route distributions, allowing them to scale to larger maps.

These properties are used implicitly in exact inference, but are difficult to harness for approximate inference.

These properties are used implicitly in exact inference, but are difficult to harness for approximate inference.

We study the task of smoothing a circuit, i.e., ensuring that all children of a