{'fraction_non_alphanumeric': 0.023963133640552997, 'fraction_numerical': 0.012903225806451613, 'mean_word_length': 5.067039106145251, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension

We extend Valiant's learnability model to learning classes of concepts defined by regions in Euclidean space E". Our methods lead to a unified treatment of some of Valiant's results, along with previous results of Pearl and Devroye and Wagner on distribution-free convergence of certain pattern recognition algorithms. We show that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned. Using this parameter, we analyze the complexity and closure properties of learnable classes. Authors A. Blumer and D. Haussler gratefully acknowledge the support of NSF grant IST-8317918, author A. Ehrenfeucht the support of NSF grant MCS-8305245, and author M. Warmuth the support of the Faculty Research Committee of the University of California at Santa Cruz. Part of this work was done while A. Blumer was visiting the University of California at Santa Cruz and M. Warmuth the Univer-