Symbolic machine learning

Symbolic machine learning is machine learning whose output is an explicit, human-readable symbolic structure, such as a rule set, a decision tree, a logic program, a stored case or a mathematical formula, rather than numeric weights. It generalises from examples, often with background knowledge, and every prediction can be traced to the learned rule that made it.

1. Learning concepts from examples

1.1 Concept learning

Concept learning is the oldest form of the problem: given positive and negative examples of a category, find a description that covers the positives and excludes the negatives. Patrick Winston’s 1970 MIT thesis, Learning Structural Descriptions from Examples, learned structural concepts such as an “arch” (two standing blocks supporting a third) from a sequence of drawings, including “near misses” that differ from the concept in one important way and therefore show which relation is essential [2]. The description it learned was a network of relations (supports, must-not-touch), readable as a definition.

The general framing is learning as search. Fix a hypothesis language $H$ (for example, conjunctions of attribute values). A hypothesis $h\in H$ is consistent with the training examples $E$ if it classifies every one of them correctly. Hypotheses are ordered from general to specific: $h_1{\ge }_g{h}_2$ when every instance covered by $h_2$ is covered by $h_1$. Learning means moving through this ordered space in response to examples [1]. Limits. The hypothesis language decides what can be learned at all; a learner restricted to conjunctions can never learn “red or round”. This “inductive bias” is unavoidable, and symbolic learners make it explicit.

1.2 Version spaces and candidate elimination

Tom Mitchell introduced version spaces at IJCAI-77 (“Version spaces: a candidate elimination approach to rule learning”) and developed them in “Generalization as search” (Artificial Intelligence, 1982) [3] [4]. The version space is the set of all hypotheses consistent with the examples so far. It can be huge, but because hypotheses are ordered by generality it is fully described by two boundaries: the most specific consistent hypotheses $S$ and the most general ones $G$.

The candidate elimination algorithm generalises $S$ just enough to cover each positive example and specialises $G$ just enough to exclude each negative one. A worked example with three attributes (size, colour, shape), where ? means “any value”:

At the third example, $G$ must stop covering a small blue circle. Of the minimal specialisations, ⟨large, ?, ?⟩ and ⟨?, ?, square⟩ are discarded because they are not more general than $S$ (they would exclude the red circles already seen), leaving ⟨?, red, ?⟩. The fourth example forces ⟨?, red, circle⟩, and the version space collapses to one hypothesis. Before that point, the learner knows exactly what it does not know: an instance on which every member of the version space agrees can be classified with certainty, and one on which they disagree can be flagged as undetermined. Limits. A single mislabelled example can make the version space empty, because no consistent hypothesis remains; the boundary sets can also grow exponentially. Version spaces are now mainly a teaching device and a clean theory of what a learner can know, not a production method.

2. Decision trees and rules

2.1 Decision trees: ID3, C4.5 and CART

A decision tree classifies an instance by a sequence of attribute tests from root to leaf. The learning method descends from Earl Hunt, Janet Marin and Philip Stone’s Concept Learning System (CLS), described in Experiments in Induction (1966) [5].

ID3. Ross Quinlan developed ID3 from 1979 and described it in “Induction of Decision Trees” in the first issue of the journal Machine Learning (1986) [6]. It grows the tree top-down: at each node, choose the attribute whose test most reduces uncertainty about the class, split the examples by its values, and recurse. Uncertainty is measured by entropy, and the reduction by information gain:

where $p_c$ is the fraction of examples in $S$ with class $c$ and $S_v$ are the examples with $A=v$. Quinlan’s own example has 14 Saturday mornings described by outlook, temperature, humidity and wind, 9 of class P and 5 of class N:

Sunny mornings split 2–3, overcast 4–0 and rain 3–2. The other attributes gain less (humidity 0.151, wind 0.048, temperature 0.029), so outlook becomes the root; every overcast morning is P, so that branch is already a leaf, and the procedure recurses on the other two. The final tree reads as three rules a person can check against the data.

C4.5 and CART. Quinlan’s C4.5 (book, 1993) extended ID3 to continuous attributes (by thresholds), missing values and pruning, and replaced raw gain with the gain ratio to avoid favouring attributes with many values [7]; its commercial successor is C5.0. Independently, Leo Breiman, Jerome Friedman, Richard Olshen and Charles Stone’s Classification and Regression Trees (1984) introduced CART, with binary splits and cost-complexity pruning [8].

Today. Single trees are used where a decision must be explained, and ensembles of trees (random forests, gradient-boosted trees) are among the strongest methods for tabular data, at the cost of readability: a forest of five hundred trees is no longer a symbolic explanation. Limits. Finding the smallest consistent tree is NP-complete, so greedy growth can miss simple concepts; trees are unstable (a small change in the data can change the root); and axis-parallel splits approximate diagonal boundaries poorly.

2.2 Rule induction: AQ, CN2 and RIPPER

Rule induction learns an unordered or ordered list of if–then rules directly, usually by sequential covering: learn one rule that covers many positive examples and few negatives, remove the positives it covers, and repeat until none remain.

AQ. Ryszard Michalski’s AQ family (from 1969) is the classic covering algorithm: pick an uncovered positive “seed”, generate the most general descriptions that cover it and no negative example (a “star”), keep the best, and continue [9]. At Stanford, Meta-DENDRAL learned rules of mass spectrometry from pairs of molecular structures and spectra, one of the first cases of a program inducing scientific rules for an expert system [10]; see expert systems.

CN2. Peter Clark and Tim Niblett’s CN2 (1989) combined AQ-style rule search with ID3-style statistical tests so that rules could tolerate noise, allowing a rule to cover a few negatives when that is statistically justified [11]. William Cohen’s RIPPER (1995) made rule learning competitive with C4.5 in accuracy while scaling to large noisy datasets [12].

A learned rule looks like IF outlook = overcast THEN P, or IF outlook = sunny AND humidity = high THEN N, and can be audited one line at a time. Today. Rule learners are used where regulations or clinicians require a decision to be stated as rules, and as a way to summarise what a more opaque model does. Limits. Greedy covering can produce long, overlapping rule lists, and accuracy on complex data usually trails ensembles.

2.3 Association rule learning

Association rule learning finds rules of the form $X\Rightarrow Y$ that hold often in a database of transactions (customers who buy bread and butter also buy milk), ranked by support (how often $X\cup Y$ occurs) and confidence (how often $Y$ occurs when $X$ does). Rakesh Agrawal, Tomasz Imieliński and Arun Swami introduced the problem in 1993 [13]. The output is symbolic and readable, but it is descriptive: an association is not a cause, and with many items the number of rules found can overwhelm the reader.

3. Learning with background knowledge

3.1 Explanation-based learning

Inductive learners need many examples because they know nothing about the domain. Explanation-based learning (EBL) turns this around: given a domain theory (rules that can explain examples), a single example is enough. The learner proves that the example is an instance of the target concept, then generalises the proof by keeping its structure and replacing the example’s constants with variables, so the result covers every case the same explanation would cover. Two papers in the first volume of Machine Learning (1986) defined the method: Tom Mitchell, Richard Keller and Smadar Kedar-Cabelli’s “Explanation-based generalization: a unifying view” and Gerald DeJong and Raymond Mooney’s “Explanation-based learning: an alternative view” [14] [15].

Example. Suppose the theory says an object can be safely stacked on another if it is lighter, and that weight is volume times density. Shown that a particular box can be stacked on a particular table, EBL proves it from the box’s volume and density and the table’s weight, then generalises the proof into a new operational rule: any object whose volume times density is below the weight of another can be stacked on it. Nothing new is true that the theory did not already imply; what is learned is a shortcut that makes the next proof one step instead of many. This is the same idea as chunking in the Soar cognitive architecture. Limits. EBL is only as good as its domain theory: an incomplete or wrong theory yields wrong rules, and adding many learned shortcuts can slow a system down (the utility problem).

3.2 Inductive logic programming (ILP)

Inductive logic programming learns logic programs (first-order Horn clauses, as in Prolog) from examples and background knowledge. Its roots are Gordon Plotkin’s work on least general generalisation (1970) [16] and Ehud Shapiro’s Model Inference System (1981), a Prolog program that inferred Horn-clause programs from positive and negative examples [17]. Stephen Muggleton named the field in 1990 and set out its programme in “Inductive Logic Programming” (New Generation Computing, 1991) [18].

A worked example on a family tree:

$H$ derives both positives (through bob and through cal) and neither negative, so $B\wedge H\models E^{+}$ and no $e\in E^{-}$ follows. The shorter $\mathrm{grandparent}(X,Z)\leftarrow \mathrm{parent}(X,Z)$ is rejected because it entails the negative example grandparent(ann, bob). The learned hypothesis is itself a program: it applies to families of any size, and anyone can read it.

FOIL, Golem and Progol. Quinlan’s FOIL (1990) grows clauses one literal at a time, choosing literals by an information-gain measure, top-down like ID3 [19]. Muggleton and Cao Feng’s Golem (1990) works bottom-up from relative least general generalisations.

Muggleton’s Progol (1995) introduced inverse entailment: it builds the most specific clause that, with the background knowledge, entails a chosen example, and searches the lattice of clauses that generalise it [20].

Aleph and after. Ashwin Srinivasan’s Aleph (2001), in the Progol tradition, became one of the most widely used ILP systems. Later systems include Metagol (2014), which learns by meta-interpretation and can invent new predicates, and Popper (Andrew Cropper and Rolf Morel, 2021), which learns from failures by turning each failed hypothesis into constraints that prune the search [23] [22]. Differentiable ILP (Richard Evans and Edward Grefenstette, 2018) recasts rule search as gradient descent, one of the bridges described on the neuro-symbolic AI page [24].

Today. ILP’s main successes have been in the sciences, where a readable relational hypothesis matters: by the mid-1990s it had been applied to drug design, mutagenicity prediction and protein structure [21]. Limits. The space of clauses grows very fast with clause length and the number of predicates, so systems depend on strong language restrictions (mode declarations) supplied by the user; handling noise and learning recursive programs remain active problems [22]. For the logic underneath, see logic programming and theorem proving.

4. Learning from cases and analogies

4.1 Case-based reasoning

Case-based reasoning (CBR) solves a new problem by retrieving a similar past case and adapting its solution, and learns by storing the result. It grew from Roger Schank’s model of dynamic memory at Yale (Dynamic Memory, 1982) [25]; Janet Kolodner’s CYRUS (1983), which organised memories of events for retrieval, was an early system, and her 1993 book Case-Based Reasoning became the standard text [26]. Agnar Aamodt and Enric Plaza (1994) described the process as a cycle of four steps, now called the 4 R’s [27]:

A help desk shows the idea: a new fault report is matched to the most similar resolved tickets (retrieve), their fix is adapted to this machine (reuse), checked (revise), and the confirmed ticket is added to the base (retain). Every answer comes with its precedent, which is why CBR suits domains that already reason from precedent, such as law, medicine and engineering design. Limits. Everything depends on the similarity measure and on adaptation knowledge, which are hard to engineer; and reasoning from a handful of precedents is anecdotal unless the case base is curated.

4.2 Analogy and structure-mapping

Analogy transfers knowledge from a familiar base domain to a new target by aligning their structure. Dedre Gentner’s structure-mapping theory (Cognitive Science, 1983) holds that analogies map relations between objects, not the objects’ surface attributes, and prefer systems of relations connected by higher-order relations such as causes (the systematicity principle) [28]. Her standard example is the analogy between the solar system and the atom: the sun attracts the planet and the sun is more massive than the planet together cause the planet revolves around the sun, and the same causal structure maps onto nucleus and electron, while attributes such as “the sun is hot and yellow” are not carried over.

Brian Falkenhainer, Kenneth Forbus and Gentner implemented the theory as the Structure-Mapping Engine (SME, 1989), which builds consistent one-to-one correspondences between two symbolic descriptions and proposes candidate inferences: facts true in the base whose counterparts are missing in the target [29]. Those inferences are hypotheses, not conclusions: an analogy suggests what to check. Limits. Structure-mapping needs both domains already described in comparable relational vocabulary, and finding the best mapping between large descriptions is computationally hard; deciding which of many possible bases to use is a retrieval problem of its own.

5. Searching for programs and formulas

5.1 Genetic programming

Genetic programming (GP) searches for a program by simulated evolution. It builds on John Holland’s genetic algorithms (Adaptation in Natural and Artificial Systems, 1975) [30]; Nichael Cramer evolved tree-structured programs at the first International Conference on Genetic Algorithms in 1985 [31], and John Koza’s 1992 book Genetic Programming: On the Programming of Computers by Means of Natural Selection established the field [32]. Programs are represented as expression trees (in Koza’s work, Lisp S-expressions). A population of random trees is scored on test cases; the fitter ones are more likely to be selected; crossover swaps randomly chosen subtrees between two parents, and mutation replaces a subtree with a random one:

parent 1:  (* (+ x 1) x)          parent 2:  (- x (* x x))
                 ^^^^^^^                           ^^^^^^^
child:     (* (* x x) x)          i.e. x^3, after swapping the marked subtrees

The output is a symbolic program that can be read and simplified, which is why GP is grouped with symbolic learning even though the search is stochastic. Since 2004 the Genetic and Evolutionary Computation Conference has given “Humies” awards for GP and evolutionary results judged competitive with human work. Limits. Evolved programs tend to bloat with redundant code, the search is expensive and hard to reproduce, and nothing guarantees the result generalises beyond the test cases it was scored on.

5.2 Symbolic regression

Symbolic regression searches the space of mathematical expressions for a formula that fits data, balancing accuracy against simplicity, instead of fitting parameters of a fixed model. Schematically, over a grammar $\mathcal{G}$ of expressions built from variables, constants and operators:

Given the orbital distance $a$ (in astronomical units) and period $T$ (in years) of Earth (1, 1), Mars (1.524, 1.881) and Jupiter (5.203, 11.86), the simplest formula that fits is $T=a^{3/2}$, Kepler’s third law: a readable law rather than a curve. Koza used GP for symbolic regression in 1992; Michael Schmidt and Hod Lipson (Science, 2009) recovered conservation laws and equations of motion from measurements of physical systems [33]; Silviu-Marian Udrescu and Max Tegmark’s AI Feynman (2020) combined neural-network fitting with symbolic simplification to recover 100 equations from the Feynman Lectures on Physics [34]; and Miles Cranmer’s open-source PySR (2023) is widely used in the sciences [35]. Limits. Symbolic regression is NP-hard in general [36]; with noisy data many different formulas fit equally well, and a formula that fits is not thereby a law: it still has to be tested like any other hypothesis. Note that symbolic regression fits data; it does not deduce, which is why the pillar page lists it under not to be confused with symbolic reasoning.

6. Symbolic vs statistical machine learning

7. Timeline

8. Where symbolic learning is used today, and its limits

• Tabular prediction. Decision trees and their ensembles are standard for structured data in finance, operations and medicine; single trees and rule lists are chosen when the model itself must be shown to a regulator or a clinician.
• Science. Symbolic regression proposes candidate laws from measurements; ILP learns relational hypotheses in chemistry and biology that domain experts can criticise in their own terms.
• Precedent-driven work. Case-based reasoning supports help desks, design reuse and decision support wherever people already reason from similar past cases.
• Program synthesis. Learning programs from examples, in the ILP and GP traditions, continues in example-based synthesis; see formal verification and program synthesis.

The limits are consistent across the family. Search cost: the space of rules, clauses or programs grows combinatorially, so every method needs an inductive bias chosen by a person. Noise: exact methods (version spaces, early ILP) break on mislabelled data, and the statistical fixes trade some readability for robustness. Perception: symbolic learners need symbols as input; they cannot learn directly from pixels or waveforms, which is where neural networks took over and where neuro-symbolic systems try to join the two. And readable is not the same as correct: a learned rule can be clear and wrong, which is exactly why it matters that it can be checked.

9. Symbolic learning and fail-safe models

A fail-safe model is an AI model built so that its failures end in a controlled, safe state: it abstains when evidence is missing, and its learning can narrow what it does but never widen what it is authorised to do. Symbolic learning is the part of machine learning where that second property can even be stated, because what is learned is a readable object that can be inspected before it takes effect. Three ideas on this page point the same way. A version space knows the difference between “all consistent hypotheses agree” and “they disagree”, and can abstain on the second. ILP’s consistency condition gives negative examples a veto: a hypothesis that entails a single known falsehood is rejected, however well it covers the positives. And explanation-based learning only compiles what its theory already implies, so it can speed a system up without letting it believe anything new.

None of this makes a learner safe by itself. A readable rule can be wrong, and a learned rule that is allowed to act before anyone checks it is no safer than a weight. The design choice that matters is where learned content goes: into a proposal that must be admitted, or straight into the system’s beliefs. A model may propose; only the floor admits a fact. Peel, a research prototype by Perslis Research, follows this rule: there is no neural network in the loop that decides, knowledge is typed, sourced cards, and learning is readable counts. To our knowledge it is the first fail-safe model; the exact claim and the closest earlier work are on What is a fail-safe model?

For every other family of techniques, see the guide to symbolic AI techniques; for how learning entered symbolic AI, the history of symbolic AI.

10. Questions

What is symbolic machine learning?

Symbolic machine learning is machine learning whose result is an explicit symbolic structure, such as a set of rules, a decision tree, a logic program, a library of cases or a mathematical formula, rather than numeric weights. The learned model can be read, checked and edited by a person.

Is a decision tree symbolic AI?

A single decision tree is a symbolic model: each path from root to leaf is a readable if-then rule. The algorithms that learn trees, such as ID3, C4.5 and CART, use statistics to choose splits, so they sit where symbolic AI and statistical learning meet. Large ensembles of trees lose most of that readability.

What is inductive logic programming?

Inductive logic programming learns logic programs from positive and negative examples plus background knowledge. The learned hypothesis, together with the background knowledge, must entail every positive example and no negative example. Stephen Muggleton named the field in 1990; well-known systems include FOIL, Progol, Aleph and Popper.

What is the difference between ID3 and C4.5?

ID3, described by Ross Quinlan in 1986, grows a decision tree over discrete attributes by choosing the split with the highest information gain. C4.5, published in 1993, extends it to continuous attributes and missing values, prunes the tree to reduce overfitting, and uses the gain ratio to avoid favouring attributes with many values.

What is explanation-based learning?

Explanation-based learning uses a domain theory to prove why a single training example belongs to a concept, then generalises that proof into a rule covering every case with the same explanation. It needs very few examples but can only be as correct as the domain theory it starts from.

What is case-based reasoning?

Case-based reasoning solves a new problem by retrieving similar past cases, reusing and adapting their solutions, revising the result after testing, and retaining the new case for the future. Aamodt and Plaza described this four-step cycle in 1994.

Is symbolic regression the same as symbolic reasoning?

No. Symbolic regression searches for a mathematical formula that fits data, often with genetic programming, and its output is readable. But it is fitted to observations rather than deduced from knowledge, so the formula is a hypothesis that still has to be tested.

Why is symbolic machine learning less common than deep learning?

Deep learning scales to raw images, audio and text and to very large datasets, where symbolic learners struggle because their search over rules grows combinatorially and they need symbols as input. Symbolic learning remains strong where data are structured, examples are few, background knowledge exists, or the model must be readable.

11. References

1. T. M. Mitchell. Machine Learning. McGraw-Hill, 1997.
2. P. H. Winston. Learning Structural Descriptions from Examples. PhD thesis, MIT, 1970.
3. T. M. Mitchell. Version Spaces: A Candidate Elimination Approach to Rule Learning. Proceedings of IJCAI-77, 1977.
4. T. M. Mitchell. Generalization as Search. Artificial Intelligence 18(2):203–226, 1982.
5. E. B. Hunt, J. Marin, P. J. Stone. Experiments in Induction. Academic Press, 1966.
6. J. R. Quinlan. Induction of Decision Trees. Machine Learning 1(1):81–106, 1986. doi:10.1007/BF00116251
7. J. R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.
8. L. Breiman, J. H. Friedman, R. A. Olshen, C. J. Stone. Classification and Regression Trees. Wadsworth, 1984.
9. R. S. Michalski. On the Quasi-Minimal Solution of the General Covering Problem. Proceedings of the Fifth International Symposium on Information Processing (FCIP-69), Bled, 1969.
10. B. G. Buchanan, E. A. Feigenbaum. DENDRAL and Meta-DENDRAL: Their Applications Dimension. Artificial Intelligence 11, 1978. doi:10.1016/0004-3702(78)90010-3
11. P. Clark, T. Niblett. The CN2 Induction Algorithm. Machine Learning 3(4):261–283, 1989. doi:10.1007/BF00116835
12. W. W. Cohen. Fast Effective Rule Induction. Machine Learning: Proceedings of the 12th International Conference (ICML), 115–123, 1995. doi:10.1016/B978-1-55860-377-6.50023-2
13. R. Agrawal, T. Imieliński, A. Swami. Mining Association Rules between Sets of Items in Large Databases. Proceedings of ACM SIGMOD, 1993. doi:10.1145/170035.170072
14. T. M. Mitchell, R. M. Keller, S. T. Kedar-Cabelli. Explanation-Based Generalization: A Unifying View. Machine Learning 1(1):47–80, 1986. doi:10.1007/BF00116250
15. G. DeJong, R. Mooney. Explanation-Based Learning: An Alternative View. Machine Learning 1(2):145–176, 1986. doi:10.1007/BF00114116
16. G. D. Plotkin. A Note on Inductive Generalization. In Machine Intelligence 5. Edinburgh University Press, 1970.
17. E. Y. Shapiro. Algorithmic Program Debugging. MIT Press, 1983. (Model Inference System first reported 1981.)
18. S. Muggleton. Inductive Logic Programming. New Generation Computing 8(4):295–318, 1991. doi:10.1007/BF03037089
19. J. R. Quinlan. Learning Logical Definitions from Relations. Machine Learning 5(3):239–266, 1990. doi:10.1007/BF00117105
20. S. Muggleton. Inverse Entailment and Progol. New Generation Computing 13:245–286, 1995. doi:10.1007/BF03037227
21. I. Bratko, S. Muggleton. Applications of Inductive Logic Programming. Communications of the ACM 38(11), 1995. doi:10.1145/219717.219771
22. A. Cropper, S. Dumančić. Inductive Logic Programming at 30: A New Introduction. Journal of Artificial Intelligence Research, 2022. doi:10.1613/jair.1.13507
23. A. Cropper, R. Morel. Learning Programs by Learning from Failures. Machine Learning, 2021. doi:10.1007/s10994-020-05934-z
24. R. Evans, E. Grefenstette. Learning Explanatory Rules from Noisy Data. Journal of Artificial Intelligence Research 61, 2018.
25. R. C. Schank. Dynamic Memory: A Theory of Reminding and Learning in Computers and People. Cambridge University Press, 1982.
26. J. Kolodner. Case-Based Reasoning. Morgan Kaufmann, 1993.
27. A. Aamodt, E. Plaza. Case-Based Reasoning: Foundational Issues, Methodological Variations, and System Approaches. AI Communications 7(1):39–59, 1994. doi:10.3233/AIC-1994-7104
28. D. Gentner. Structure-Mapping: A Theoretical Framework for Analogy. Cognitive Science 7(2):155–170, 1983. doi:10.1016/S0364-0213(83)80009-3
29. B. Falkenhainer, K. D. Forbus, D. Gentner. The Structure-Mapping Engine: Algorithm and Examples. Artificial Intelligence 41(1):1–63, 1989. doi:10.1016/0004-3702(89)90077-5
30. J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975.
31. N. L. Cramer. A Representation for the Adaptive Generation of Simple Sequential Programs. Proceedings of the First International Conference on Genetic Algorithms and their Applications, Carnegie-Mellon University, 1985.
32. J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992.
33. M. Schmidt, H. Lipson. Distilling Free-Form Natural Laws from Experimental Data. Science 324(5923):81–85, 2009. doi:10.1126/science.1165893
34. S.-M. Udrescu, M. Tegmark. AI Feynman: A Physics-Inspired Method for Symbolic Regression. Science Advances 6(16), 2020. doi:10.1126/sciadv.aay2631
35. M. Cranmer. Interpretable Machine Learning for Science with PySR and SymbolicRegression.jl. 2023. arXiv:2305.01582
36. M. Virgolin, S. P. Pissis. Symbolic Regression is NP-hard. Transactions on Machine Learning Research, 2022.