Research map / Label-efficient and robust learning / Noisy labels
Learning MDL Logic Programs from Noisy Data
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.
Introduces MaxSynth, an ILP system that learns MDL (minimal description length) recursive logic programs from noisy examples by combining Popper-style learning-from-failures with noise-tolerant constraints and a MaxSAT-based combine step.
Problem
Inductive logic programming struggles to learn recursive, textually minimal programs from noisy data because existing learners require programs that exactly entail all positive and no negative examples.
Approach
Relax the consistency requirement: save inconsistent but partially complete programs as promising, combine them with a MaxSAT solver to minimise size plus false positives and negatives, and prune with noise-tolerant (optimally sound) specialisation and generalisation constraints.
Key results
- On iggp-rps with 30% noise, MaxSynth has over 90% accuracy while Popper and Aleph have less than 55%.
- MaxSynth significantly outperforms Popper (p<0.01) on 25/42 tasks and is outperformed on 4/42.
- Noisy constraints reduce learning time by up to 99% (e.g. iggp-md (10): 109s to 2s).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MDL-based learning that tolerates noisy examples instead of requiring perfect consistency | MaxSynth · IGGP, Zendo, program synthesis, Alzheimer, and WN18RR tasks | predictive accuracy | Mixed |
| Use MaxSynth instead of Popper | iggp-coins (20) · iggp-coins (20) | predictive accuracy: 100 $\pm$ 0 vs 50 $\pm$ 0 | Helped |
| Use MaxSynth instead of Popper | zendo1 (20) · zendo1 (20) | predictive accuracy: 99 $\pm$ 0 vs 74 $\pm$ 1 | Helped |
| Use MaxSynth instead of Aleph | alzheimer_toxic · alzheimer_toxic | predictive accuracy: 74 $\pm$ 1 vs 83 $\pm$ 1 | Hurt |
| Increase training-label noise | MaxSynth · IGGP-RPS and dropk | predictive accuracy | Hurt |
| Use noisy constraints rather than unconstrained learning (ablation) | MaxSynth · IGGP, Zendo, program synthesis, Alzheimer, and WN18RR tasks | learning time: 109 $\pm$ 2 -> 2 $\pm$ 0 | Helped |
| Use MaxSynth instead of Popper | zendo2 (0) · zendo2 (0) | learning time: 48 $\pm$ 1 vs 102 $\pm$ 2 | Helped |
| Use MaxSynth instead of Popper | iggp-buttons (0) · iggp-buttons (0) | learning time: 7 $\pm$ 0 vs 7 $\pm$ 0 | No clear effect |
| Use MaxSynth instead of Popper | dropk (0) · dropk (0) | learning time: 7 $\pm$ 1 vs 4 $\pm$ 1 | Hurt |
Surprising findings
- MDL hypotheses are not always the most accurate; MaxSynth reaches only 75% on iggp-md (0) while Popper finds an 11-literal hypothesis with 100% accuracy on test data.
- Aleph's default coverage cost ignores hypothesis size, causing overfitting.
Limitations
- MDL is not always the best criterion; the MDL hypothesis can have lower predictive accuracy than alternatives.
- Scales only to moderate noise (around 30%).
- Some program synthesis and wn18rr tasks hit timeouts, so only the best found hypothesis is returned.
Experimental setup
Datasets: IGGP (minimal decay, buttons, rock-paper-scissors, coins) Zendo program synthesis list transformation tasks Alzheimer drug design Wn18RR
Benchmarks: IGGP Zendo program synthesis Alzheimer Wn18RR
Metrics: predictive accuracy learning time
Baselines: Popper Aleph NoisyPopper
Builds on: Popper learning from failures Combo NoisyPopper
Closest papers by meaning
- Learning Logic Programs Though Divide, Constrain, and Conquer (AAAI 2022 · similarity 0.88)
- Learning Logic Programs by Discovering Where Not to Search (AAAI 2023 · similarity 0.86)
- Self-Supervised Inductive Logic Programming (AAAI 2026 · similarity 0.85)
- Differentiable Inductive Logic Programming for Structured Examples (AAAI 2021 · similarity 0.85)
- GENSYNTH: Synthesizing Datalog Programs without Language Bias (AAAI 2021 · similarity 0.85)
- Inductive Learning of Logical Theories with LLMs: A Expressivity-graded Analysis (AAAI 2025 · similarity 0.81)
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.