Reviews: Tractability in Structured Probability Spaces

This paper looks at the problem of representing simple routes on a graph as a probability distribution using Probabilistic Sentential Decision Diagrams (PSDDs). Representing a complex structure such as a graph is difficult, and the authors transform the problem by turning a graph into a Boolean circuit where it is straightforward to perform inference, and as an experiment, use their method on a route prediction method for San Francisco taxi cabs, where it beats two baselines. PSDDs refer to a framework that represents probability distributions over structured objects through Boolean circuits. Once the object is depicted as a Boolean circuit, it becomes straightforward to parameterize it. More formally, PSDD's are parameterized by including a distribution over each or-gate, and PSDD's can represent any distribution (and under some conditions, this distribution is unique).