The Gradient of Algebraic Model Counting
This work addresses the challenge of integrating logical, probabilistic, and neural representations for researchers in AI, though it appears incremental as it builds on existing algebraic model counting methods.
The paper tackles the problem of unifying learning algorithms in statistical-relational and neurosymbolic AI by applying the semiring perspective of algebraic model counting to learning, showing that this generalization leads to memory-efficient backpropagation and empirical speed-ups compared to existing approaches.
Algebraic model counting unifies many inference tasks on logic formulas by exploiting semirings. Rather than focusing on inference, we consider learning, especially in statistical-relational and neurosymbolic AI, which combine logical, probabilistic and neural representations. Concretely, we show that the very same semiring perspective of algebraic model counting also applies to learning. This allows us to unify various learning algorithms by generalizing gradients and backpropagation to different semirings. Furthermore, we show how cancellation and ordering properties of a semiring can be exploited for more memory-efficient backpropagation. This allows us to obtain some interesting variations of state-of-the-art gradient-based optimisation methods for probabilistic logical models. We also discuss why algebraic model counting on tractable circuits does not lead to more efficient second-order optimization. Empirically, our algebraic backpropagation exhibits considerable speed-ups as compared to existing approaches.