Tractable learning for complex probability queries

Tractable learning aims to learn probabilistic models where inference is guaran-teed to be efficient. However, the particular class of queries that is tractable de-pends on the model and underlying representation. Usually this class is MPE or conditional probabilities Pr(x|y) for joint assignments x,y. We propose a tractable learner that guarantees efficient inference for a broader class of queries. It simultaneously learns a Markov network and its tractable circuit representation, in order to guarantee and measure tractability. Our approach differs from earlier work by using Sentential Decision Diagrams (SDD) as the tractable language in-stead of Arithmetic Circuits (AC). SDDs have desirable properties, which more general representations such as ACs lack, that enable basic primitives for Boolean circuit compilation. This allows us to support a broader class of complex proba-bility queries, including counting, threshold, and parity, in polytime. 1