Technical Summary: NeSyCat Torch

Problem Statement

Neurosymbolic (NeSy) AI aims to combine the perceptual capabilities of neural networks with the structured reasoning of symbolic logic. However, the field suffers from fragmentation: classical, fuzzy, and probabilistic systems each define truth via distinct inductive rules, preventing the transfer of knowledge bases and learning objectives between them. While the Unified Language for Learning and Reasoning (ULLER) previously unified these semantics under a single categorical framework based on monads, it lacked an implementation for predicates and functions learned by neural networks. Furthermore, existing implementations often struggle with scalability and numerical stability when moving from discrete to continuous or large-batch settings.

Methodology

The paper introduces NeSyCat Torch, a differentiable tensor implementation of the NeSyCat categorical framework. The core methodology involves interpreting computational symbols via neural networks within a unified, monad-parametric architecture.

1. Categorical Framework and Monads

The framework extends the categorical semantics of Johnstone (2002) by organizing syntax and semantics into four layers: categorical, logical, domain, and grammatical. The unifying mechanism is the strong monad $M$, which parameterizes the effect (e.g., probability, tensor weights). The paper utilizes three specific monad layers (Table 1):

• Distribution Monad ($D$): Represents finitely supported probability distributions. It serves as the reference semantics and metric readout, where bind ($>>=$) performs marginalization (law of total probability).
• Tensor Monad ($T$) / Log-Tensor Monad ($T_{log}$): Implements the distribution monad in a differentiable manner using real numbers (logits) instead of probabilities. $T_{log}$ operates over the log-semiring $(\mathbb{R}, \text{logsumexp}, +)$ to ensure numerical stability and differentiability, avoiding the gradient degeneration associated with fuzzy operators in $[0,1]$.
• Batch Monad ($B$): A reader monad over a batch index set that enables parallel processing of mini-batches without introducing randomness.

2. Syntax and Semantics

The system supports three types of symbols:

• Tarski: Deterministic maps (standard FOL).
• Kleisli: Effectful maps into $M$.
• NeSy: Neural maps taking monadic carriers as input and producing monadic carriers as output.

Formulas are constructed using do-notation (syntactic sugar for monadic bind). A key innovation is the treatment of computational function symbols (e.g., $digit: \text{Image} \to M \text{Digit}$) and predicates. The semantics are defined inductively:

• Bind ($\leftarrow$): Performs marginalization in $D$ and log-space convolution in $T$.
• Quantifiers: Aggregate monadic truth values over finite domains.
• Lazy Evaluation: The framework employs lazy monads to defer the computation of marginalized probabilities until they are strictly necessary, pruning unneeded branches.

3. Training and Inference

Training minimizes the knowledge loss (mean negative log-truth of axioms) over a dataset.

• Batching: Instead of running the do-notation program $N$ times for $N$ samples, the system runs it once on a batch tensor. The batch monad $B$ is composed with the tensor monad $T$ ($B \circ T$).
• Data Handling: Observations are treated as "certain" values (one-hot encoded in log-space) that enter the formula via liftB.
• Implementation: The framework is implemented in Haskell (HaskTorch), Python (JAX), and Python (PyTorch). The JAX backend utilizes JIT compilation for log-space convolution and differentiation.

Key Contributions

1. Neural Implementation of NeSyCat: Provides the first neural implementation of the NeSyCat framework, bridging the gap between abstract categorical semantics and practical deep learning.
2. Unified Monad Parametricity: Demonstrates that a single codebase, written in monadic do-notation, can instantiate different semantics (probabilistic, fuzzy, classical) simply by changing the underlying monad.
3. Differentiable Log-Tensor Monad: Introduces a numerically stable, differentiable training backend using the log-semiring, avoiding the need for explicit softmax normalization during intermediate steps (deferring it to the boundary).
4. Scalability via Laziness: Achieves efficient training on batches and multi-digit problems by deferring marginalization calculations.

Experimental Results

The authors evaluated the framework on the MNIST addition task (distant supervision: only the sum of two handwritten digits is observed, not the digits themselves).

• Accuracy:
  • Single Digit ($N=1$): NeSyCat Torch achieved 94.6% (LTN-style) and 94.2% (DeepProbLog-style), outperforming LTN (93.5%) and DeepProbLog (92.2%).
  • Multi-Digit ($N=4$): NeSyCat Torch achieved 92.0% accuracy. In contrast, LTN and DeepProbLog timed out (T/O) on this task.
  • Comparison: The approach approaches the accuracy of DeepStochLog (92.7% for $N=4$), which is currently the most accurate baseline, while maintaining a uniform framework applicable to various first-order approaches.
• Efficiency:
  • Training steps on a single A100 GPU were significantly faster than LTN (0.52ms vs. 5.36ms per step for LTN-style on older hardware).
  • The system converges quickly; the full 15-seed sweep for single-digit addition took approximately 1.5 minutes.
• Generalization: The network learned to recognize digits with ~97% accuracy solely from the observed sums, without using digit labels.

Significance and Claims

The paper claims that NeSyCat Torch successfully scales the generality of the NeSyCat categorical framework to the neural implementation level. Its primary significance lies in:

• Unification: It offers a single, uniform framework that applies to many first-order NeSy approaches (classical, fuzzy, probabilistic) by simply instantiating the monad, rather than requiring separate definitions for each.
• Scalability: By utilizing lazy monads and tensor structures, it overcomes the computational bottlenecks (such as #P-hard weighted model counting in DeepProbLog) that limit other methods on larger problems (e.g., $N=4$ digits).
• Extensibility: The framework is parametric; while the current work focuses on finitely supported distributions, the authors note that instantiating it with the Giry monad could extend the approach to continuous probability (though a neural representation for this is left for future work).

The authors modestly note that while the current implementation handles finite domains and discrete distributions effectively, generalizing to infinite domains and efficient neural representations of continuous probability remains an open challenge for future research.