  Probabilistic dependency graphs (PDGs) are a flexible class of probabilistic
graphical models, subsuming Bayesian Networks and Factor Graphs. They can also
capture inconsistent beliefs, and provide a way of measuring the degree of this
inconsistency. We present the first tractable inference algorithm for PDGs with
discrete variables, making the asymptotic complexity of PDG inference similar
that of the graphical models they generalize. The key components are: (1) the
observation that, in many cases, the distribution a PDG specifies can be
formulated as a convex optimization problem (with exponential cone
constraints), (2) a construction that allows us to express these problems
compactly for PDGs of boundeed treewidth, (3) contributions to the theory of
PDGs that justify the construction, and (4) an appeal to interior point methods
that can solve such problems in polynomial time. We verify the correctness and
complexity of our approach, and provide an implementation of it. We then
evaluate our implementation, and demonstrate that it outperforms baseline
approaches. Our code is available at
http://github.com/orichardson/pdg-infer-uai.
