Source-linked AI summary
A Semantic Loss Function for Deep Learning with Symbolic Knowledge
Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, Guy Van den Broeck
TL;DR
Deep learning needs a principled way to use symbolic constraints without losing differentiability or logical meaning. The paper derives semantic loss from first principles and integrates it with neural networks, obtaining near-state-of-the-art semi-supervised classification and improved structured prediction. The method is simple to add but remains sensitive to the underlying model’s performance.
Problem
The paper addresses how neural networks can learn predictions subject to symbolic constraints while preserving differentiable learning and precise logical meaning.
Method
The paper derives a differentiable semantic loss from axioms and computes it tractably through Boolean-circuit compilation for integration with standard neural-network losses.
Results
Semantic loss yields near-state-of-the-art semi-supervised classification and significantly improves prediction of structured objects such as rankings and paths.
Takeaways & Limitations
A simple additional loss term can provide useful learning signals from unlabeled data and logical structure for complex output spaces.
Takeaways & Limitations
The method’s benefits depend on the underlying predictive power of the supervised model, and a later CIFAR-10 system surpassed the paper’s performance by 5%.
Abstract
from arXiv · showhide
This paper develops a novel methodology for using symbolic knowledge in deep learning. From first principles, we derive a semantic loss function that bridges between neural output vectors and logical constraints. This loss function captures how close the neural network is to satisfying the constraints on its output. An experimental evaluation shows that it effectively guides the learner to achieve (near-)state-of-the-art results on semi-supervised multi-class classification. Moreover, it significantly increases the ability of the neural network to predict structured objects, such as rankings and paths. These discrete concepts are tremendously difficult to learn, and benefit from a tight integration of deep learning and symbolic reasoning methods.
1. Introduction
The paper integrates symbolic Boolean constraints with neural outputs through a differentiable semantic loss. Experiments show benefits for semi-supervised classification and structured prediction of rankings and paths.
- Motivation: Semantic loss bridges neural network outputs and Boolean constraints, including one-hot encodings and complex structured objects.The constraints considered include rankings, subgraphs, and paths.
- Approach: The method is designed to preserve logical meaning while remaining differentiable, unlike approaches that may lose precise constraint semantics.It is derived from first principles and is independent of constraint syntax.
- Semi-Supervised Classification: Semantic loss uses exactly-one constraints to extract a learning signal from unlabeled data in semi-supervised classification.The signal improves confidence in classifications of unlabeled examples.
- Semi-Supervised Classification: The method achieves near-state-of-the-art semi-supervised classification performance on MNIST, FASHION, and CIFAR-10.The reported result is described as (near-)state-of-the-art across these datasets.
- Structured Prediction: For structured prediction, logical constraints encode output structure so networks become much more likely to predict rankings and graph paths correctly.These tasks require learning both the output-space structure and the classification function within it.
2. Background and Notation
The paper represents neural outputs and symbolic structures using propositional-logic notation. It studies exactly-one, simple-path, and total-ordering constraints as increasingly structured output domains.
- Propositional Logic: Propositional logic represents Boolean variables, their assignments, literals, sentences, satisfaction, entailment, and logical equivalence.A state is a complete assignment to the variables, and satisfaction means the sentence evaluates to true in that state.
- Neural Outputs: A neural network output vector p contains probabilities in [0, 1], produced using softmax or sigmoid output units.Each value corresponds to the predicted probability of one output variable.
- Output Constraints: The exactly-one constraint requires one and only one indicator variable to be true, encoding a one-hot multi-class output.It combines pairwise at-most-one clauses with an at-least-one clause.
- Output Constraints: The simple-path constraint requires active edge indicators to form a valid simple path between a specified source and destination.The ordering constraint instead encodes a total ordering as a permutation matrix.
3. Semantic Loss
Semantic loss measures the probability that neural outputs generate assignments satisfying a logical constraint, yielding a differentiable loss with principled logical properties. Its axiomatic derivation establishes uniqueness and syntax independence.
- Definition: Semantic loss is defined for a propositional sentence α and neural probability vector p, measuring how closely p supports satisfying assignments.For one-hot constraints, it measures proximity to any valid one-hot assignment, regardless of which output is correct.
- Definition: The loss is proportional to the negative logarithm of the probability of sampling a state that satisfies the constraint.It therefore represents the self-information of obtaining a satisfying assignment.
- Derivation from First Principles: The semantic loss function is the unique function satisfying the stated axioms, up to a multiplicative constant.The axioms include differentiability and logical correspondence properties.
- Properties: Semantic loss is monotone under logical implication: strengthening a constraint cannot reduce the loss.A path constraint is stricter than a subtree constraint, so its loss cannot be lower.
- Properties: Logically equivalent constraints receive identical semantic loss for the same probability vector, making the loss independent of syntax.This follows from the monotonicity axiom and establishes semantic equivalence.
- Properties: Any satisfying deterministic assignment has zero semantic loss, while literal constraints correspond to cross-entropy losses.The identity and satisfaction properties connect logical constraints to supervised labels.
4. Semi-Supervised Classification
Semantic loss adds logical constraints to semi-supervised classification so unlabeled examples provide a signal encouraging confident, consistent predictions. Across MNIST, FASHION, and CIFAR-10, it delivers strong improvements with a simple additional loss term and little computational overhead.
- Motivation and Method: Semantic loss uses the exactly-one constraint to extract a learning signal from unlabeled examples by encouraging confident class assignments.It is added to an existing neural-network loss with weight w and directly supports one-hot classification outputs.
- Motivation and Method: For exactly-one classification, semantic loss is efficiently computable and causes no noticeable computational overhead in the experiments.Automated reasoning can reduce computation from O(n^2) to O(n) for this constraint.
- MNIST: 20% improvement over the purely supervised baseline was achieved by an MLP with semantic loss using 100 labeled MNIST examples.The improvement was around 25% compared with self-training, while ladder nets slightly outperformed semantic loss by 0.5% accuracy.
- FASHION: 17% improvement over the baseline was achieved on FASHION when only 100 labels were provided.The method compared favorably to ladder nets except in the fully supervised setting and nearly reached maximum accuracy with 500 labels.
- CIFAR-10: 4.66% net improvement over the baseline was obtained on CIFAR-10, compared with 2.93% for ladder nets.The paper compares net improvements because the supervised base models differed slightly, making direct comparison methodologically flawed.
- Discussion: Across the semi-supervised experiments, semantic loss surpassed ladder nets on FASHION and CIFAR-10 while remaining close on MNIST.Its simplicity comes from using only an additional loss term, but the method remains sensitive to the underlying model’s performance.
5. Learning with Complex Constraints
The paper develops tractable semantic-loss computation through compiled circuits, then evaluates whether constraints improve learning on difficult structured-output problems. Experiments cover shortest paths and preference rankings, emphasizing coherent validity over independent label accuracy.
- Tractable computation: Weighted model counting provides the basis for computing semantic loss, while compiled decomposable and deterministic circuits support value and gradient computation.For suitable circuit forms, both quantities can be computed in time linear in circuit size; compilation may be efficient for bounded-treewidth constraints but theoretically hard for some constraints.
- Evaluation scope: Semantic loss is evaluated on difficult constrained-output problems where simple MLPs cannot directly learn the output structure from data.The evaluation intentionally prioritizes demonstrating the effect of semantic loss rather than achieving state-of-the-art performance on a particular task.
- Grid shortest paths: The grid experiment predicts valid simple shortest paths in 4×4 graphs with randomly removed edges and source-destination constraints.Inputs encode sources, destinations, and removed edges; labels encode the shortest-path edges.
- Grid shortest paths: Semantic loss strongly improves coherent path accuracy and constraint satisfaction, while having little effect on incoherent binary-label accuracy.Coherent accuracy requires the entire configuration to be correct, whereas constraint accuracy measures predictions that satisfy the path constraint.
- Preference learning: The preference-learning experiment predicts complete orderings over four sushi types from orderings over six others, using a valid-total-order constraint.Without semantic loss, the network produces a valid ordering on only 1% of examples; semantic loss significantly improves valid, correct orderings while marginally affecting incoherent accuracy.
6. Related Work
Related work incorporates symbolic knowledge into machine learning through constrained prediction, probabilistic graphical models, embeddings, and differentiable arithmetic or logical objectives. The paper studies semantic loss in a discriminative deep-learning setting.
- Constraint-based prediction: Earlier structured-prediction approaches enforce constraints on linear models through integer linear programming, including supervised and semi-supervised applications in natural language processing.The related work situates symbolic constraints within a long-standing machine-learning research problem.
- Differentiable constraints: Deep-learning methods have addressed arithmetic and logical constraints by replacing logical operators with differentiable arithmetic objectives.These approaches seek to preserve differentiability while imposing output constraints.
- Structured labels and semi-supervision: Other techniques exploit label structure through hierarchy and exclusion graphs, while semantic loss relates to information-theoretic approaches to semi-supervised learning.The paper studies semantic loss in a discriminative setting.
7. Conclusions & Future Work
The paper presents semantic loss as a principled integration of propositional reasoning with deep learning and identifies approximation methods as future work when exact methods are insufficient.
- Semantic loss combines automated propositional reasoning with existing deep learning architectures.
- Semantic loss provides significant benefits for semi-supervised classification and deep structured prediction in highly complex output spaces.
- Effective approximations remain a future-work direction for settings where the described semantic-loss methods are insufficient.Suggested approaches include hierarchical abstractions, constraint relaxations, and projections on random variable subsets.
A. Axiomatization of Semantic Loss: Details
The axiomatization makes semantic loss logically meaningful by enforcing monotonicity, symmetry, locality, satisfaction, and consistency with probability-based loss behavior. These axioms characterize the function uniquely up to scale.
- Independence and locality: Loss decomposes additively for constraints on disjoint variables and is unaffected by probabilities of variables absent from the constraint.Setting the second constraint to true yields the locality proposition.
- Monotonicity: Semantic loss is monotone under implication: stricter constraints cannot have lower loss.If α implies β, then Ls(α, p) ≥ Ls(β, p); tightening a subtree requirement to a path illustrates the relationship.
- Semantic invariance: Logically equivalent sentences incur identical semantic loss, so the loss depends on logical meaning rather than syntax.
- Bounds and satisfaction: Semantic loss is nonnegative, and any vector satisfying a constraint incurs zero loss.The nonnegativity result follows from monotonicity and the zero loss of the true sentence; satisfaction follows with the identity axiom.
- Literal correspondence: For single literals, semantic loss is proportional to cross-entropy, with −log(p) for X and −log(1 −p) for ¬X.Symmetry arguments show that the multiplicative constant is shared across literals.
- Uniqueness: The semantic loss function satisfies all stated axioms and is the only function that does so up to a multiplicative constant.The uniqueness proof connects exponential additivity with the axioms of a finite discrete probability distribution.
B. Specification of the Convolutional Neural Network Model
The convolutional model differs slightly from the ladder-net architecture to reproduce the reported baseline performance.
- The model replaces the ladder-net ReLU choice and adds padded cropping preprocessing plus a final fully connected layer.These modifications are made so the baseline performance reported by Rasmus et al. (2015) can be reproduced.
C. Hyper-parameter Tuning Details
Hyper-parameter tuning focuses on the semantic-loss weight, with dataset-specific validation choices and a fixed choice reused across semi-supervised classification experiments.
- The semantic-loss weight is the only hyper-parameter reported to cause a noticeable performance difference in semi-supervised classification.A grid search over {0.001, 0.005, 0.01, 0.05, 0.1} found 0.005 best or nearly best empirically.
- The FASHION experiments reuse MNIST hyper-parameters, while ladder nets receive limited tuning for fairness.The shared image size and structure motivate transferring the MNIST settings.
- Validation selects a semantic-loss weight of 0.5 for grids and 0.25 for preference learning after initial tuning.The grids search included values through 1; preference learning was initially set to 0.1 before further tuning.
D. Specification of Complex Constraint Models
The complex-constraint experiments construct grid and preference-learning tasks alongside specified neural baselines, with semantic loss producing confident correct predictions on the illustrated FASHION examples.
- Grid constraints: Grid constraints combine source–destination constraints with indicators for selected source and destination pairs, then disjoin the resulting alternatives.
- FASHION illustration: In the illustrated FASHION examples, the final semi-supervised model with semantic loss predicts every image correctly and confidently.
- Grid data generation: The grid dataset is generated by removing one third of edges, excluding components with fewer than 5 nodes, and sampling node pairs.
- Predictive models: The grid baseline is a 5-layer MLP with 50 hidden sigmoid units per layer, trained with Adam, full batches, and validation-loss early stopping.
- Preference learning: The preference-learning task uses orderings over sushis 1,2,3,5,7,8 as features and orderings over 4,6,9,10 as labels.
- Predictive models: The preference-learning model is a 3-layer MLP with 25 hidden sigmoid units per layer, using Adam, full batches, and validation-loss early stopping.
E. Probabilistic Soft Logic Encodings
The paper presents alternative probabilistic soft logic encodings for exactly-one constraints and defines interpretation loss using norm functions from prior work.
- Exactly-one constraints: The paper gives two encodings for the exactly-one constraint over three variables, x1, x2, and x3.
- Exactly-one constraints: Both exactly-one encodings extend to an arbitrary number of variables.
- Interpretation loss: The experimental norm functions follow Kimmig et al. (2012), with loss defined for an interpretation I.