2017/10/30 by George Barmpalias, Barmpalias, George, Frank Stephan +1
Computer Science · Mathematics · #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1710.11303
openalex publication_date 2017/10/30 · openalex created_date 2022/08/31 · openalex updated_date 2026/07/28
We study the problem of identifying a probability distribution for some given\nrandomly sampled data in the limit, in the context of algorithmic learning\ntheory as proposed recently by Vinanyi and Chater. We show that there exists a\ncomputable partial learner for the computable probability measures, while by\nBienvenu, Monin and Shen it is known that there is no computable learner for\nthe computable probability measures. Our main result is the characterization of\nthe oracles that compute explanatory learners for the computable (continuous)\nprobability measures as the high oracles. This provides an analogue of a\nwell-known result of Adleman and Blum in the context of learning computable\nprobability distributions. We also discuss related learning notions such as\nbehaviorally correct learning and orther variations of explanatory learning, in\nthe context of learning probability distributions from data.\n