Kolmogorov-Arnold classifier reduces rules needed for function learning
Kolmogorov-Arnold Classifier Systems as Universal Approximators
Machine LearningNeural and Evolutionary Computing
Summary
Learning systems that use many rules to understand complex inputs struggle because the number of rules grows very fast as input size grows. The authors introduce a new way to organize these rules by breaking down complex problems into simpler one-dimensional parts, inspired by a famous math theorem. This new system can approximate any continuous function without needing as many rules, making it more efficient. Their approach was tested and found to give similar accuracy while using fewer parameters.
What this means in practice
- •For machine learning engineers: Build more scalable rule-based models for high-dimensional input spaces with fewer parameters while maintaining accuracy.
- •For control systems developers: Implement efficient function approximators for continuous system modeling that require fewer rules and simpler parameters.
Authors
Hiroki Shiraishi, Hisao Ishibuchi, Masaya Nakata
Abstract
As the input dimension $n$ grows, rule-based machine learning, such as Learning Classifier Systems (LCSs), faces a fundamental scalability bottleneck for function approximation: both rule count and parameter count grow exponentially with $n$. Traditional LCSs partition the $n$-dimensional input space directly, requiring $\mathcal{O}(m^n)$ rules for adequate coverage, where $m$ is the per-variable resolution. This article breaks from this paradigm by reorganizing rules dimension-wise, guided by the Kolmogorov-Arnold representation theorem: any continuous $n$-dimensional function can be expressed as a finite superposition of one-dimensional functions. The proposed Kolmogorov-Arnold Classifier System (KACS) decomposes the target function into one-dimensional subproblems and assigns a dedicated ruleset to each, reducing the worst-case rule count from $\mathcal{O}(m^n)$ to $\mathcal{O}(mn^2)$ and replacing $n$-dimensional local models with one-dimensional models requiring only two parameters per rule, independent of $n$. We also provide the first constructive proof that an LCS, namely KACS, is a universal approximator for continuous functions on compact domains. Evaluated against a direct $n$-dimensional input space partitioning approach under otherwise identical conditions, KACS achieves competitive accuracy in many settings while using only 2\% to 40\% of the parameters. Our implementation is available at https://github.com/YNU-NakataLab/KACS.