EDC: Equation Discovery for Classification

AI summary

Overview

Research area: Machine learning — specifically equation discovery (symbolic regression) applied to binary classification, sitting at the intersection of explainable AI and symbolic classification.

Technical level: Intermediate. No deep learning prerequisites are needed, but familiarity with classification metrics (AUC, log loss) and basic search concepts (grammars, beam search) helps.

Scope in one sentence: The paper proposes EDC, an equation-discovery framework that produces a single interpretable analytical equation defining a binary decision boundary, and evaluates it against symbolic and standard classifiers on artificial and UCI datasets.

What This Paper Is About

Equation discovery (often called symbolic regression) has been successful at producing concise, readable models for regression, but far less work applies it to classification, where the goal is a class label rather than a numeric value. This paper builds a binary classification framework in which the model is an analytical function f(x) whose sign determines the class: a sample is predicted true whenever f(x) >= 0. The aim is a classifier that is a single readable equation — competitive with state-of-the-art accuracy while remaining transparent to a domain expert.

Key Contributions

1. The EDC method. Equation Discovery for Classification is proposed as an interpretable binary classifier that models the decision boundary as an analytical function, with a configurable grammar of building blocks that can be tailored to a domain.
2. A redundancy-conscious grammar. The authors define a specific grammar built from additive summands (linear, quadratic/product, and exponential terms) designed to avoid syntactic variants that are semantically equivalent — for example, subtraction is excluded because a constant can simply be optimised to a negative value.
3. Demonstrated recovery of known boundaries and XOR-like behaviour. On artificial data, EDC reconstructs hard-coded decision boundaries and models challenging XOR-like dependencies, which the product-of-two-features summand captures as hyperbolic curves.
4. Benchmarking on UCI data. EDC is compared against other symbolic classifiers (AMAXSC, M4GP), other interpretable methods (decision tree, LDA), and state-of-the-art classifiers (MLP, RF, SVM) in terms of AUC, interpretability and model size. The core algorithm, experimental setup and datasets are released for reproduction.

Main Findings

• Recovers equations from its own search space. On artificial datasets whose target equation lies within EDC's search space and contains no noise, EDC reached a mean AUC of 0.999 (± 0.00), versus 1.000 (± 0.00) for the original decision boundary — errors on the order of 0.1% from the perfect score, attributed to suboptimal constant optimisation.

• Proposed boundaries shift under noise. When Gaussian noise (mean 0, standard deviation 2) was added to 2000 data points drawn uniformly from [-10,10] x [-10,10], EDC scored 0.951 (± 0.03) against 0.943 (± 0.03) for the original boundary. A paired t-test reported a significant difference in favour of EDC, t(99) = 5.4, p < .001. The authors argue that adding data noise can shift the implicit boundary in the data, so they deliberately avoid calling the original boundary "ground truth." A shown example had the target at 0.952 and EDC at 0.978.

• Approximates equations outside its grammar. When targets were sampled from a richer grammar that added c·X³ and c·X⁴ building blocks unavailable to EDC, EDC still scored 0.962 (± 0.03) against 0.956 (± 0.03) for the original boundary, again a significant difference (t(99) = 5.9, p < .001). A shown example had the target at 0.959 and EDC at 0.967.

• Competitive on Gaussian cluster data. Across 100 datasets built from a mixture of six randomly generated Gaussian clusters, EDC scored 0.965 (± 0.043), close to MLP at 0.972 (± 0.034), SVM at 0.970 (± 0.038) and RF at 0.967 (± 0.037), and clearly ahead of the other explainable methods: Tree 0.899 (± 0.079), M4GP 0.894 (± 0.082), LDA 0.811 (± 0.139) and AMAXSC 0.802 (± 0.181).

• Best of the equation-discovery classifiers on UCI data. Under 10-fold cross-validation, EDC achieved a higher AUC than AMAXSC and M4GP on every one of the nine UCI datasets, with an average score of 0.857 versus 0.810 for both AMAXSC and M4GP, and an average rank of 4.00 versus 6.44 and 6.78.

• Still behind the top general-purpose classifiers. Average UCI scores were MLP 0.901, RF 0.899, SVM 0.890 and LDA 0.863, against EDC's 0.857. Random Forest outperformed EDC on 6 of the 9 datasets, and LDA scored higher on 5 of the 9. On IONOSPHERE and SONAR the RF, MLP and SVM scores were substantially higher, which the authors attribute to relationships between features and class that are absent from EDC's building blocks.

• Rank differences are not statistically significant. In a critical distance plot with CD = 3.49, three overlapping groups emerged: {MLP, RF, SVM, LDA, EDC}, {LDA, EDC, AMAXSC, M4GP} and {AMAXSC, M4GP, Tree}. EDC outperformed AMAXSC, M4GP and the decision tree, and was not significantly outperformed by the leading classifiers.

• Models are readable. An example equation from the ADULT dataset is 0.75 − 1.27·own-child·education-num + 3.37·capitalgain + 8.01·exp(8.18·married-civ-spouse). Because own-child and married-civ-spouse are effectively binary, the first term acts like a conditional statement and the last contributes 8.01 when false and 8.01·exp(8.18) = 28,586 when true.

• Run time is a real cost. EDC's run time grows linearly with the number of examples and also depends on the number of features; the DIABETES dataset took roughly 167 minutes, compared with under 1 second for the comparison algorithms. The authors trace this to the large number of function evaluations in the search, especially the x_i · x_j building block, which introduces a quadratic number of building blocks, compounded by feature expansion from one-hot encoding.

Methodology in Plain English

The classifier's output is a single mathematical expression built from the dataset's features. The sign of that expression decides the class, so the expression functions as a landscape: anywhere the landscape is above zero, the prediction is true.

Defining the space of allowed equations. The set of candidate equations is described by a context-free grammar, so only syntactically legal expressions are ever considered. The authors' generic grammar has three ingredients: a start constant; summands joined by addition; and summand types covering a linear term, a product of two features (which also covers quadratic terms), and an exponential term. Each summand carries one or more constants that get tuned. Subtraction is deliberately omitted because a constant can be optimised negative, and an additive constant inside exp is superfluous since exp(a + x) equals exp(a)·exp(x). The grammar is explicitly a parameter of the method — a domain expert can extend or reshape it, and the non-terminal for features is expanded to match however many features a dataset has.

Searching. Because the space is far too large to enumerate, EDC uses beam search with a beam width of 10, starting from a constant and repeatedly adding one summand at a time. For example, c0 + c1·x1 + c2·exp(c3·x2) is found at search depth d = 2 after two refinements of the starting constant.

Fitting constants. Constants are optimised with stochastic gradient descent when the expression is differentiable with respect to them, and with a Hill Climber otherwise — which is the case for the exponential summand. The Hill Climber spends a portion f of its budget on random configurations, keeps the top k as starting points, and distributes the remaining n·(1−f) evaluations evenly among them, taking a step of size α up and down for each feature and keeping whichever step reduces the loss most.

Scoring. Candidate equations are evaluated with Log Loss after the output is passed through the logistic function. Found equations are ranked by probability score and AUC is the reported performance measure. No label is assigned directly; a threshold is chosen to maximise accuracy, on the assumption that misclassification costs are equal.

Preprocessing and data. Data are linearly scaled to [0,1] before the algorithm runs, so constants operate on a predictable range. Categorical features are one-hot encoded, and one-hot encoded features occurring at a frequency of 2% or less are grouped together.

Evaluation design. Four artificial scenarios increase in difficulty: equations inside the search space without noise; inside the search space with Gaussian noise added to points after labelling; targets drawn from a richer grammar with cubic and quartic terms not available to EDC; and a purely data-driven setting of 100 datasets built from a mixture of six Gaussian clusters, with two clusters labelled true and four false. The UCI evaluation uses 10-fold cross-validation and reports mean AUC against AMAXSC, M4GP, LDA, a decision tree, MLP, RF and an RBF-kernel SVM.

Why This Matters

Impact on research. The paper shows that equation discovery can be pushed into classification with a single-expression model, and that it beats existing symbolic classification methods across the tested UCI datasets. It also raises a methodological point that reaches beyond its own method: when noise is added to data, the implicit boundary embedded in the data can drift from the original equation, which complicates the common practice of treating a generating equation as ground truth. Its use of a configurable grammar ties it to prior work on grammar-defined search spaces in equation discovery.

Real-world applications.

• High-stakes decisions requiring transparency, where a practitioner must be able to read, check and if necessary correct the model — the paper's motivating scenario for interpretable models.
• Domain-specific modelling, where an expert can add functions to the grammar so the classifier expresses relationships in terms the domain already uses.
• Scientific discovery from data, extending the classical use of equation discovery (the paper cites Boyle's law as an example of the kind of relationship such methods can recover) into settings with categorical outcomes.
• Tabular binary classification such as the UCI datasets used here, including credit and demographic-style problems like CREDIT and ADULT, where the discovered equation can be inspected term by term.

Industry relevance. The method targets deployments where a readable single equation has value for audit, regulatory review or expert verification, and it can be adapted by editing the grammar rather than by retraining a different architecture. The trade-off is practical: the DIABETES dataset took roughly 167 minutes, against under 1 second for the comparison algorithms, so compute budget is a genuine constraint on adoption.

Future Directions

• Extending beyond binary classification. The paper states explicitly that it focuses on binary classification and that extensions to multi-class classification are possible but outside its scope.
• Loosening the feature-count limitation. The authors hypothesise that EDC struggles when a problem needs more than the maximum of six features their grammar imposes (illustrated by a form such as c0 + c1·x0x1 + c2·x2x3 + c3·x4x5), and note this limitation did not frequently occur in their results.
• Reducing run time. The authors suggest the current beam width of w = 10 could perhaps be reduced in favour of shorter run times, and point to the quadratic blow-up from the x_i · x_j building block combined with one-hot feature expansion as the cause of long runs.
• Reading the redundancy question. The discovered equations may not take the same structure as the original even when they score well, since different equations can produce roughly the same boundary — which is why the authors did not include a grammatical validation between equations.

Target Audience

Researchers and practitioners in explainable machine learning, symbolic regression and symbolic classification will find the direct comparison against AMAXSC and M4GP most useful. Data scientists working on tabular binary classification with a requirement for auditable, human-readable models are the natural applied audience, along with domain experts who would need to adapt the grammar for their own field. Readers looking for a fast, general-purpose classifier will find less here, since the paper reports run times far longer than the comparison algorithms and average UCI scores below MLP, RF and SVM.

Authors’ abstract

Equation Discovery techniques have shown considerable success in regression tasks, where they are used to discover concise and interpretable models (\textit{Symbolic Regression}). In this paper, we propose a new ED-based binary classification framework. Our proposed method EDC finds analytical functions of manageable size that specify the location and shape of the decision boundary. In extensive experiments on artificial and real-life data, we demonstrate how EDC is able to discover both the structure of the target equation as well as the value of its parameters, outperforming the current state-of-the-art ED-based classification methods in binary classification and achieving performance comparable to the state of the art in binary classification. We suggest a grammar of modest complexity that appears to work well on the tested datasets but argue that the exact grammar -- and thus the complexity of the models -- is configurable, and especially domain-specific expressions can be included in the pattern language, where that is required. The presented grammar consists of a series of summands (additive terms) that include linear, quadratic and exponential terms, as well as products of two features (producing hyperbolic curves ideal for capturing XOR-like dependencies). The experiments demonstrate that this grammar allows fairly flexible decision boundaries while not so rich to cause overfitting.