Semantic Loss Functions for Neuro-Symbolic Structured Prediction

Kareem Ahmed, Stefano Teso, Paolo Morettin, Luca Di Liello, Pierfrancesco Ardino, Jacopo Gobbi, Yitao Liang, Eric Wang, Kai-Wei Chang, Andrea Passerini, Guy Van den Broeck

Abstract

Structured output prediction problems are ubiquitous in machine learning. The prominent approach leverages neural networks as powerful feature extractors, otherwise assuming the independence of the outputs. These outputs, however, jointly encode an object, e.g. a path in a graph, and are therefore related through the structure underlying the output space. We discuss the semantic loss, which injects knowledge about such structure, defined symbolically, into training by minimizing the network's violation of such dependencies, steering the network towards predicting distributions satisfying the underlying structure. At the same time, it is agnostic to the arrangement of the symbols, and depends only on the semantics expressed thereby, while also enabling efficient end-to-end training and inference. We also discuss key improvements and applications of the semantic loss. One limitation of the semantic loss is that it does not exploit the association of every data point with certain features certifying its membership in a target class. We should therefore prefer minimum-entropy distributions over valid structures, which we obtain by additionally minimizing the neuro-symbolic entropy. We empirically demonstrate the benefits of this more refined formulation. Moreover, the semantic loss is designed to be modular and can be combined with both discriminative and generative neural models. This is illustrated by integrating it into generative adversarial networks, yielding constrained adversarial networks, a novel class of deep generative models able to efficiently synthesize complex objects obeying the structure of the underlying domain.

Introduction

Standard neural networks often treat their outputs as independent variables, a simplification that fails in structured prediction tasks where outputs are deeply interrelated. For example, in predicting a path through a graph, a network might output a sequence with gaps because it lacks the inherent knowledge that a path must be continuous. Traditionally, enforcing these rules required complex post-processing or specialized, domain-specific architectures. The challenge lies in making hard logical rules "visible" to gradient-based optimization. This paper presents a framework for integrating symbolic Boolean constraints into neural network training via a differentiable "semantic loss" function, allowing models to respect domain rules while maintaining the flexibility of deep learning.

Methods

The authors propose two primary mechanisms for neuro-symbolic integration:

  1. Semantic Loss (SL): This function measures the degree to which a network's output distribution violates a given logical constraint $\alpha$. It is defined as the negative log-probability that the network's output satisfies the constraint. Crucially, the loss is syntax-agnostic; it depends solely on the meaning of the constraint, not its symbolic representation.
  2. Neuro-Symbolic Entropy Regularization: While standard entropy regularization encourages model confidence, it can lead to high confidence in invalid outputs. The authors introduce a refined version that minimizes entropy conditioned on the constraint being satisfied. This pushes the model to be confident only within the subspace of valid structures.
Effect of semantic loss and neuro-symbolic entropy on the output distribution $p(y|x)$ relative to valid constraint models $m(\alpha)$.

To make the computation of these values tractable—a task that is generally #P-hard—the authors employ Knowledge Compilation. Logical formulas are transformed into "smooth, deterministic, and decomposable" logical circuits. This allows the semantic loss and its gradients to be computed in time linear to the size of the circuit, facilitating end-to-end training.

A logical circuit used for knowledge compilation to efficiently compute semantic loss.

Furthermore, the framework is extended to generative models through Constrained Adversarial Networks (CANs). By integrating semantic loss into the GAN objective, generative models are guided to produce complex objects, such as game levels or molecules, that strictly obey the underlying domain structure.

Experimental Results

The approach was evaluated across diverse domains, demonstrating significant improvements over standard neural baselines:

  • Semi-Supervised Learning: On the ACE05 entity-relation extraction dataset with only 75 labels, adding Neuro-Symbolic (NeSy) Entropy improved the F1-score from 33.02 to 41.28.
  • Warcraft Pathfinding: In predicting minimum-cost paths on 12x12 terrain maps, "Coherent" accuracy (the percentage of optimal-cost predictions) increased from 44.8% in a standard ResNet-18 to 55.0% with NeSy Entropy.
  • Generative Tasks: In Super Mario Bros. level generation, CANs nearly doubled the validity of generated pipes (from 47.6% to 83.2%) compared to standard GANs, without sacrificing diversity. Similarly, in molecular graph generation, semantic loss improved chemical property scores while maintaining high uniqueness.

Conclusion

The semantic loss framework provides a robust method for marrying symbolic logic with deep learning. By treating constraints as differentiable loss components and leveraging knowledge compilation for efficiency, the authors enable neural networks to learn complex structural dependencies. While the current approach requires expert-defined constraints and can face challenges with circuit complexity for global rules, it represents a significant step toward more reliable and "common-sense" AI systems. Future work may explore the automatic discovery of these symbolic rules directly from data.

Summary updated

Abstract

Structured output prediction problems are ubiquitous in machine learning. The prominent approach leverages neural networks as powerful feature extractors, otherwise assuming the independence of the outputs. These outputs, however, jointly encode an object, e.g. a path in a graph, and are therefore related through the structure underlying the output space. We discuss the semantic loss, which injects knowledge about such structure, defined symbolically, into training by minimizing the network's violation of such dependencies, steering the network towards predicting distributions satisfying the underlying structure. At the same time, it is agnostic to the arrangement of the symbols, and depends only on the semantics expressed thereby, while also enabling efficient end-to-end training and inference. We also discuss key improvements and applications of the semantic loss. One limitations of the semantic loss is that it does not exploit the association of every data point with certain features certifying its membership in a target class. We should therefore prefer minimum-entropy distributions over valid structures, which we obtain by additionally minimizing the neuro-symbolic entropy. We empirically demonstrate the benefits of this more refined formulation. Moreover, the semantic loss is designed to be modular and can be combined with both discriminative and generative neural models. This is illustrated by integrating it into generative adversarial networks, yielding constrained adversarial networks, a novel class of deep generative models able to efficiently synthesize complex objects obeying the structure of the underlying domain.
BibTeX
@inproceedings{ahmed2023semantic,
  author = {Kareem Ahmed and Stefano Teso and Paolo Morettin and Luca Di Liello and Pierfrancesco Ardino and Jacopo Gobbi and Yitao Liang and Eric Wang and Kai-Wei Chang and Andrea Passerini and Guy Van den Broeck},
  title = {{Semantic Loss Functions for Neuro-Symbolic Structured Prediction}},
  booktitle = {Compendium of Neurosymbolic Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=yogMy-QFWP},
}
Figure