Variable Elimination as Rewriting in a Linear Lambda Calculus

Abstract

Abstract Variable Elimination ( $$\textsf{VE}$$ VE ) is a classical exact inference algorithm for probabilistic graphical models such as Bayesian Networks, computing the marginal distribution of a subset of the random variables in the model. Our goal is to understand Variable Elimination as an algorithm acting on programs in an idealized probabilistic functional language—a linear simply-typed $$\lambda $$ λ -calculus suffices for our purpose. Precisely, we express $$\textsf{VE}$$ VE as a term rewriting process, which transforms a global definition of a variable into a local definition, by swapping and nesting let-in expressions. We exploit in an essential way linear types.