On Faster Marginalization with Squared Circuits via Orthonormalization
This work addresses a bottleneck for researchers using squared circuits in machine learning applications, offering an incremental improvement in computational efficiency.
The paper tackles the computational complexity of marginalizing variables in squared circuits, which are used as expressive distribution estimators, by introducing a parameterization that ensures normalized distributions and a more efficient marginalization algorithm.
Squared tensor networks (TNs) and their generalization as parameterized computational graphs -- squared circuits -- have been recently used as expressive distribution estimators in high dimensions. However, the squaring operation introduces additional complexity when marginalizing variables or computing the partition function, which hinders their usage in machine learning applications. Canonical forms of popular TNs are parameterized via unitary matrices as to simplify the computation of particular marginals, but cannot be mapped to general circuits since these might not correspond to a known TN. Inspired by TN canonical forms, we show how to parameterize squared circuits to ensure they encode already normalized distributions. We then use this parameterization to devise an algorithm to compute any marginal of squared circuits that is more efficient than a previously known one. We conclude by formally showing the proposed parameterization comes with no expressiveness loss for many circuit classes.