On the Kolmogorov Complexity of Binary Classifiers

2022/01/28 by Samuel S. Epstein, Epstein, Samuel
Computer Science · Mathematics · #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2201.12374

openalex publication_date 2022/01/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We provide tight upper and lower bounds on the expected minimum Kolmogorov complexity of binary classifiers that are consistent with labeled samples. The expected size is not more than complexity of the target concept plus the conditional entropy of the labels given the sample.

Related

• Adjusted Kolmogorov Complexity of Binary Words with Empirical Entropy Normalization
• Statistical Learning of Arbitrary Computable Classifiers
• Analytical Bounds between Entropy and Error Probability in Binary Classifications
• Binary Classification with Karmic, Threshold-Quasi-Concave Metrics
• Kolmogorov complexity and generalized length functions