Concept Tree Learner (CTL): An Incremental and Interpretable Symbolic Framework for Binary String Rule Induction

Abstract

Symbolic and rule-based learning offers a transparent, sample-efficient alternative to the statistical paradigm that dominates contemporary machine learning. Whereas large language models and deep networks approximate target functions from massive corpora without exposing the rules they rely on, many practical problems instead call for compact, human-readable concept definitions learned from only a handful of examples. In this paper, we introduce the Concept Tree Learner (CTL), an incremental and interpretable symbolic framework that induces logical concepts over binary strings from minimal labeled data. CTL represents knowledge as a rooted tree of logical predicates; it extends this tree incrementally as each labeled example is processed and, after observing the data, distills the simplest rule set consistent with all examples through a set-cover filtering step, in accordance with Occam’s Razor. We give formal definitions for the tree structure, its construction and pruning operations, and the rule-selection objective, and we analyze the worst-case time and space complexity of the procedure. A prototype implementation, operating over a small set of atomic binary-string predicates whose numeric arguments scale dynamically with the input length, is evaluated across 29 concept-learning tasks of varying complexity. CTL recovers a consistent concept for every task—the intended one on 26 of the 29 datasets, and an equally consistent alternative on the three whose training set does not uniquely determine it—typically converging before all training examples are exhausted, and produces fully interpretable rule sets. On the same atomic vocabulary, it generalizes substantially better to unseen strings than both a classical entropy-based decision tree and the RIPPER (Repeated Incremental Pruning to Produce Error Reduction) rule learner (95.5% mean accuracy across all tasks—and 100% on the 26 tasks whose training set uniquely determines the target—versus 72.1% and 77.2% respectively), while using fewer and shorter rules. We position CTL within the literature on symbolic machine learning, inductive logic programming, and decision-tree induction, discuss the current limitations of the prototype—its restriction to noise-free binary input, its batch (sorted) training regime, and its fixed predicate vocabulary—and outline concrete directions for extending it toward a self-expanding, hierarchical concept-learning system.