Equation Discovery for Classification: Finding Interpretable Symbolic Specifications of the Decision Boundary

Machine Learning, vol. 115

Abstract

Abstract Equation discovery has traditionally focused on regression, where the goal is to recover analytical expressions that model numerical targets. In this paper, we extend this paradigm to binary classification and introduce Equation Discovery for Classification (EDC), a framework that discovers concise symbolic expressions that explicitly define decision boundaries. EDC searches over a configurable grammar of analytical expressions using beam search and optimises equation parameters via dedicated numerical procedures, yielding a single interpretable equation whose sign determines class membership. We design a redundancy-aware grammar that balances expressivity and tractability, enabling the discovery of non-linear decision boundaries while maintaining interpretability. Through experiments on artificial datasets with known generating mechanisms, we show that EDC reliably reconstructs complex target boundaries, including XOR-like and interaction-driven structures, and adapts effectively under increasing levels of noise. Notably, in noisy settings EDC can outperform the original generating equation by approximating the implicit, noise-shifted decision boundary. On UCI benchmark datasets, EDC consistently outperforms existing symbolic classification approaches and other interpretable baselines, while achieving performance competitive with state-of-the-art black-box models. Although computationally more demanding than standard classifiers, we demonstrate that substantial speed-ups can be achieved with reduced search depth and simplified grammars at minimal loss of predictive performance. Overall, EDC provides a principled bridge between symbolic regression and classification, offering a transparent yet expressive alternative to black-box models for applications where interpretability of the decision boundary is essential.

Authors 2

1. Godfried Toussaint corresponding Aachen

   Leiden University

   Affiliation as printed

   Leiden University, Leiden, The Netherlands

2. Arno Knobbe Aachen

   Leiden University

   Affiliation as printed

   Leiden University, Leiden, The Netherlands