Advances in probabilistic sentential decision diagram learning and inference

Abstract

Probabilistic Sentential Decision Diagrams (PSDDs) are an elegant framework for learning from and reasoning about data. They provide tractable representations of discrete probability distributions over structured spaces defined by massive logical constraints, can be compiled from graphical models such as Bayesian networks, and can be learned from both complete and incomplete datasets. The effectiveness of PSDDs has been demonstrated in numerous real-world applications, including learning user preferences, anomaly detection, and route distribution modelling.

In this seminar, we present three novel contributions to PSDD learning and inference.

• First, rather than traversing the entire PSDD during parameter learning for each dataset example, we exploit determinism to focus only on the relevant portion of the model.
• Second, we show how to prune deterministic computation in inference, thereby avoiding the need to propagate probabilities through every node in the network for each query.
• Third, we introduce a technique that parallelizes a single circuit evaluation, rather than parallelizing individual multiplications or layer-wise inference.

For both learning and inference, experimental results on benchmark PSDDs from diverse application domains demonstrate state-of-the-art performance.

Bio

Cory J. Butz is a Professor of Computer Science at the University of Regina, Canada. His research in artificial intelligence has led to invitations to visit Google, the Massachusetts Institute of Technology, and the University of Cambridge. From 2012 to 2022, he served as Associate Dean (Research and Graduate Studies) in the Faculty of Science. He has also held a faculty position at the University of Ottawa and served as President of the Canadian Artificial Intelligence Association.