An Advance on Variable Elimination with Applications to Tensor-Based
  Computation
  We present new results on the classical algorithm of variable elimination,
which underlies many algorithms including for probabilistic inference. The
results relate to exploiting functional dependencies, allowing one to perform
inference and learning efficiently on models that have very large treewidth.
The highlight of the advance is that it works with standard (dense) factors,
without the need for sparse factors or techniques based on knowledge
compilation that are commonly utilized. This is significant as it permits a
direct implementation of the improved variable elimination algorithm using
tensors and their operations, leading to extremely efficient implementations
especially when learning model parameters. Moreover, the proposed technique
does not require knowledge of the specific functional dependencies, only that
they exist, so can be used when learning these dependencies. We illustrate the
efficacy of our proposed algorithm by compiling Bayesian network queries into
tensor graphs and then learning their parameters from labeled data using a
standard tool for tensor computation.
