The Gradient of Algebraic Model Counting
作者: Jaron Maene, Luc De Raedt
发布时间: 2025-02-27
来源: arxiv
研究方向: 统计关系学习、神经符号人工智能、代数模型计数、梯度计算、优化算法
主要内容
本文研究了代数模型计数（Algebraic Model Counting，AMC）在统计关系学习和神经符号人工智能中的应用，将AMC的半群视角扩展到学习领域，提出了一种通用的梯度计算方法，并探讨了不同半群在优化算法中的应用。
主要贡献
1. 引入了∇AMC算法，用于在逻辑半群框架内计算代数梯度。
2. 提供了一种优化的∇AMC算法，通过利用动态规划和半群性质来提高效率。
3. 实现了∇AMC算法的Rust库Kompyle，并在实验中优于现有的神经符号学习算法。
4. 证明了二阶代数梯度无法在可处理电路中以线性时间计算。
研究方法
1. 代数模型计数（AMC）
2. 半群理论
3. 梯度计算
4. 反向传播
5. 动态规划
6. 优化算法
实验结果
实验结果表明，Kompyle在计算代数梯度方面比PyTorch和Jax等现有算法快几个数量级。
未来工作
未来工作将探索以下方向：1）研究更有效的二阶优化算法；2）将AMC应用于更广泛的领域；3）开发更高效的算法和工具。