Kolmogorov-Arnold Classifier Systems as Universal Approximators

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 O(mn) 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 O(mn) to O(mn2) 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.