Source-linked AI summary
Semantic Strengthening of Neuro-Symbolic Learning
Kareem Ahmed, Kai-Wei Chang, Guy Van den Broeck
TL;DR
Neuro-symbolic learning seeks to make neural predictions respect domain rules, but exact probabilistic inference can be computationally infeasible, and common alternatives have limitations. This paper approximates constraint probabilities through conditional factorization and iteratively restores selected dependencies. It reports improvements over baselines on three tasks with a small computation increase.
Problem
Neural networks may disregard joint label structure, while exact probabilistic inference over domain constraints is generally #P-hard and common alternatives are limited.
Source: §1 · p. 1Method
The method initially assumes constraints are independent given learned features, then iteratively restores dependencies selected using conditional mutual information.
Source: §1 · pp. 1–2Results
The approach improves on baselines for Warcraft minimum-cost paths, minimum-cost perfect matching, and Sudoku, with a minuscule increase in computation time.
Source: §1 · p. 2Takeaways & Limitations
The reported results show semantic strengthening sidestepping intractability across three structured prediction tasks while retaining sound semantics.
Source: §1 · pp. 1–2Fuzzy approximations sacrifice sound probabilistic semantics, while Monte Carlo can be infeasible when valid outputs occupy a sliver of an exponentially large output space.
Source: §1 · p. 1
Abstract
from arXiv · showhide
Numerous neuro-symbolic approaches have recently been proposed typically with the goal of adding symbolic knowledge to the output layer of a neural network. Ideally, such losses maximize the probability that the neural network's predictions satisfy the underlying domain. Unfortunately, this type of probabilistic inference is often computationally infeasible. Neuro-symbolic approaches therefore commonly resort to fuzzy approximations of this probabilistic objective, sacrificing sound probabilistic semantics, or to sampling which is very seldom feasible. We approach the problem by first assuming the constraint decomposes conditioned on the features learned by the network. We iteratively strengthen our approximation, restoring the dependence between the constraints most responsible for degrading the quality of the approximation. This corresponds to computing the mutual information between pairs of constraints conditioned on the network's learned features, and may be construed as a measure of how well aligned the gradients of two distributions are. We show how to compute this efficiently for tractable circuits. We test our approach on three tasks: predicting a minimum-cost path in Warcraft, predicting a minimum-cost perfect matching, and solving Sudoku puzzles, observing that it improves upon the baselines while sidestepping intractability.
1 Introduction
The introduction presents semantic strengthening as a way to scale probabilistic neuro-symbolic learning while retaining sound logic semantics. It reports improvements over baselines on three structured prediction tasks with a small computation increase.
1 Introduction
- Without symbolic domain rules, neural networks can achieve label-level accuracy while disregarding joint structure among labels, such as paths, matchings, or Sudoku solutions.Source: §1 · p. 1
- Exact probability inference for domain constraints is generally #P-hard, while fuzzy replacements lose sound probabilistic semantics and Monte Carlo can be infeasible in exponentially large output spaces.Source: §1 · p. 1
- The method initially factorizes constraint probabilities conditioned on learned features, then uses conditional mutual information to identify dependencies to restore through iterative semantic strengthening.The paper describes tractable computation of conditional mutual information for circuits with certain structural properties.Source: §1 · pp. 1–2
- The approach improves on baselines for Warcraft minimum-cost paths, minimum-cost perfect matching, and Sudoku, with a minuscule increase in computation time.The experiments are described as sidestepping the intractability of the problem.Source: §1 · p. 2
2 Problem Statement and Motivation
The section frames structured prediction as assigning probability to outputs that satisfy logical constraints, but exact inference can be intractable and common approximations can distort semantics or produce conflicting gradients.
2 Problem Statement and Motivation
- A Boolean world is an assignment to variables, and a model is a world that satisfies a logical sentence.Source: §2 · p. 2
A Probability Distribution over Possible Structures
- Semantic loss computes the probability mass assigned to satisfying models by weighted model counting, and its negative logarithm is semantic loss.Source: A Probability Distribution over… · p. 2
- Computing a constraint’s probability is generally #P-hard because it may require summing over exponentially many satisfying models.The passage cites 6.67 × 10^21 valid 9 × 9 Sudokus as an example.Source: A Probability Distribution over… · p. 2
- Fuzzy t-norm relaxations can change which assignments satisfy a formula, make equivalent statements yield different truth values, and lose sound probabilistic semantics.Source: A Probability Distribution over… · pp. 2–3
- Assuming constraint events are independent given learned features factorizes their joint probability; this is exact for constraints over disjoint variable sets and otherwise approximates their dependencies.Source: A Probability Distribution over… · p. 3
- Independently modeling strongly coupled constraints can produce opposing gradients, as the Sudoku row and column constraints favor different values for one cell.Source: A Probability Distribution over… · p. 3
- Sampling may yield almost no learning signal when valid structures are rare or violations are very unlikely, while REINFORCE has high variance and makes learning difficult.Source: A Probability Distribution over… · p. 3
3 Semantic Strengthening
The method begins with a tractable conditional-independence approximation, then selectively restores dependencies between constraints using their conditional mutual information. Compatible tractable circuits support the probability computations required for this strengthening.
3 Semantic Strengthening
- Assuming CNF clauses are independent given learned features makes constraint probability a product of tractable clause probabilities, and is exact for clauses over disjoint variables.The approximation assumes the network has encoded shared dependencies in its features and that the true function is deterministic; its semantic loss is zero exactly when all clauses are satisfied.Source: §3 · p. 4
3.1 Deriving the Criterion
- Pairwise mutual information measures dependence between constraints; conditioned on network features, it identifies independence assumptions whose relaxation most improves the approximation.The unconditioned criterion is the KL divergence between the joint distribution and the product of the constraints’ marginals, measured in bits.Source: §3.1 · p. 4
- The criterion can remain hard to compute: individually tractable constraints may have an intractable conjunction because finding intersecting satisfying assignments is difficult.Probability computation is #P-hard in general, and conjunction introduces an additional source of hardness.Source: §3.1 · p. 4
3.2 The Semantic Strengthening Algorithm
- Every η epochs, the algorithm ranks overlapping-variable constraint pairs by conditional mutual information, merges the top κ pairs, and repeats until computational budget τ is exhausted.Strongly connected components are conjoined so that dependencies linked through shared constraints are merged together.Source: §3.2 · p. 5
3.3 Tractably Computing the Criterion
- Compatible circuits make pairwise mutual information tractable without variational approximations or neural estimation; their conjunction must preserve the structural properties needed for tractable probabilities.Compatibility requires smooth, decomposable circuits whose same-scope AND nodes can be aligned; shared hierarchical scope partitioning is sufficient.Source: §3.3 · pp. 5–6
4 Related Work
Related work combines neural learning with symbolic reasoning through fuzzy relaxations, logic-programming frameworks, and predictive constraint layers. These approaches differ in how they represent constraints and preserve probabilistic semantics.
Related approaches
- Fuzzy logic methods turn logical formulas into differentiable arithmetic objectives, while semantic loss replaces fuzzy reasoning with exact probabilistic queries over compiled structures.Liu et al. (2023) use semantic loss to learn a network and extract generalized logic rules with minimal priors.Source: §4 · pp. 6–7
- Logic-programming approaches range from DeepProbLog’s neural predicates to top-k proof-path scaling, iterative hypothesis revision, and neural programs guided by procedural knowledge.The cited examples include Manhaeve et al. (2018, 2021), Dai et al. (2018), and Bošnjak et al. (2017).Source: §4 · p. 7
- Predictive constraint layers include SPLs, MultiplexNet, and HMCCN; their scope varies, with MultiplexNet restricted to disjunctive normal form and HMCCN to a constraint family.SPLs retain sound probabilistic semantics but may struggle with harder constraints; SIMPLE targets the k-subset distribution.Source: §4 · p. 7
5 Experimental Evaluation
The evaluation tests Warcraft minimum-cost paths, MNIST perfect matchings, and Sudoku, reporting improvements from semantic strengthening over the neural and product t-norm baselines. The reported measures assess whether predictions are optimal, valid, or—on Sudoku—correct solutions.
Evaluation Scope
- The tasks have state spaces too large to enumerate, including 6.6 × 10^21 valid 9 × 9 Sudoku grids.The paper also notes that valid matchings and grid paths grow doubly exponentially with grid size.Source: §5 · p. 7
Evaluation Metrics
- The experiments assess exact structure prediction and constraint consistency, rather than relying only on individual-label accuracy; for Sudoku, these measures coincide because a valid puzzle has a unique solution.“Exact” asks whether the predicted structure matches the ground truth, while “Consistent” asks whether it satisfies the constraint.Source: §5 · p. 7
Warcraft Shortest Path
- 61.20% Exact accuracy for optimal Warcraft paths and 72.70% Consistent accuracy for valid paths, versus 44.80% and 50.40%, and 56.90% and 63.20%, respectively, for the baseline and product t-norm.The comparison reports semantic strengthening against both baselines.Source: Table 1 · p. 8, §5 · p. 8
MNIST Perfect Matching
- 15.50% accuracy for optimal MNIST perfect matchings and 18.40% for valid matchings, versus 9.30% and 12.70%, and 10.00% and 12.90%, respectively, for the baseline and product t-norm.The “Exact” and “Consistent” metrics denote optimal and valid matching accuracy, respectively.Source: Table 2 · p. 8, §5 · p. 8
Sudoku
- 28.00% accuracy for correct Sudoku solutions, versus 16.80% for the baseline and 22.10% for product t-norm.The reported comparison is for semantic strengthening against both baselines.Source: §5 · pp. 7, 9, Table 3 · p. 8
6 Conclusion
Semantic strengthening approximates constraint satisfaction by initially assuming clause independence, then uses conditional mutual information to relax harmful independence assumptions. It improves accuracy and consistency over baselines on three tasks while retaining probabilistic semantics.
Conclusion
- Semantic strengthening is a tractable neuro-symbolic approach that remains faithful to the neural network’s probabilistic semantics for a constraint.It begins with clause independence, then uses conditional mutual information to identify and relax unjustified assumptions that most harm approximation quality.Source: §6 · p. 9