Research map / Learning theory and algorithms / Combinatorial and search optimization
A learnability analysis on neuro-symbolic learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical analysis showing a neuro-symbolic task is learnable iff its derived constraint satisfaction problem (DCSP) has a unique solution, with sample complexity and asymptotic error bounds, validated on MNIST-style addition and modular addition experiments.
Problem
When can concept-level risk be minimized via empirical risk minimization on the neuro-symbolic (NeSy) risk in hybrid learning-plus-reasoning systems (e.g., abductive learning, probabilistic NeSy), i.e., which NeSy tasks are learnable?
Approach
Formulate NeSy learning as a derived constraint satisfaction problem over concept clusters; a task is learnable iff the DCSP has a unique solution (disagreement d=0), yielding a sample complexity bound and an asymptotic error bound d/L; unlearnable tasks can become learnable via ensembles of tasks whose combined DCSP is unique.
Key results
- A task is learnable iff its DCSP has a unique solution; sample complexity is N > (1/kappa) log(|B|/epsilon).
- Asymptotic average concept error is bounded by d/L, where d is DCSP solution disagreement and L the concept space size.
- Experiments show addition and multiplication (learnable) reach aligned concept and reasoning accuracy, while mod-addition configs with ambiguous DCSPs show a lower accuracy bound 1 - d/L; ensembling mod 3 and mod 4 tasks reduces d from 10 to 0 and becomes learnable.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Combine the mod-2 and mod-3 addition tasks | MNIST modular addition ensemble · MNIST, k1=2 and k2=3 | DCSP solution disagreement: 10 -> 8 | Helped |
| Combine the mod-3 and mod-4 addition tasks | MNIST modular addition ensemble · MNIST, k1=3 and k2=4 | DCSP solution disagreement: 10 -> 0 | Helped |
| Increase DCSP solution disagreement | NeSy tasks · Addition and modular addition tasks | Asymptotic concept accuracy bound | Hurt |
| Use an ensemble whose combined DCSP still has multiple solutions | Unlearnable NeSy tasks · MNIST modular addition ensemble, k1=2 and k2=3 | Learnability: 10 -> 8 | No clear effect |
| Use an ensemble whose combined DCSP has a unique solution | Unlearnable NeSy tasks · MNIST modular addition ensemble, k1=3 and k2=4 | Learnability: 10 -> 0 | Helped |
Surprising findings
- Ensembling two individually unlearnable modular-addition tasks (mod 3 and mod 4) can yield a unique DCSP solution and thus become learnable.
- The number of DCSP solutions is not monotonically related to DCSP disagreement d.
Limitations
- Analysis restricted to hybrid systems (PNL and ABL) and a restricted hypothesis space with clustering property assumed (e.g., via pretraining).
- Assumes finite concept sequence set and non-vanishing sampling probability.
- Experiments limited to small digit-based tasks on MNIST-style datasets.
Experimental setup
Datasets: MNIST KMNIST CIFAR-10 SVHN
Benchmarks: addition multiplication modular addition XOR
Metrics: concept accuracy reasoning accuracy NeSy risk DCSP solution disagreement d/L
Baselines: ABL PNL surrogate risk (A3BL-style)
Builds on: abductive learning DeepProbLog PAC learning
Closest papers by meaning
- Deciphering Raw Data in Neuro-Symbolic Learning with Provable Guarantees (AAAI 2024 · similarity 0.91)
- Verification Learning: Make Unsupervised Neuro-Symbolic System Feasible (ICML 2025 · similarity 0.89)
- Position: The Road to Generalizable Neuro-Symbolic Learning Should be Paved with Foundation Models (NeurIPS 2026 · similarity 0.88)
- Right for the Right Reasons: Avoiding Reasoning Shortcuts via Prototypical Neurosymbolic AI (NeurIPS 2025 · similarity 0.87)
- Concise and Logically Consistent Conformal Sets for Neuro-Symbolic Concept-Based Models (NeurIPS 2026 · similarity 0.87)
- NeSyC: A Neuro-symbolic Continual Learner For Complex Embodied Tasks In Open Domains (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.