Skip to main content
Article
The Functions of Finite Support: A Canonical Learning Problem
Computer Science & Information Technology Faculty Publications
  • Rūsiņš Freivalds, University of Latvia
  • Efim Kinber, Sacred Heart University
  • Carl H. Smith, University of Maryland - College Park
Document Type
Article
Publication Date
10-1-1999
Disciplines
Abstract
The functions of finite support have played a ubiquitous role in the study of inductive inference since its inception. In addition to providing a clear and simple example of a learnable class, the functions of finite support are employed in many proofs that distinguish various types and features of learning. Recent results show that this ostensibly simple class requires as much space to learn as any other learnable set and, furthermore, is as intrinsically difficult as any other learnable set. Since the class of functions of finite support sit at the top of two very different complexity hierarchies, this class is a candidate for being a canonical learning problem. We argue for this point in the paper and discuss the ramifications.
Comments

Published: Freivalds, Rūsiņš, Efim B. Kinber, Carl H. Smith. "The Functions of Finite Support: A Canonical Learning Problem." Journal of Experimental & Theoretical Artificial Intelligence 11.4 (1999): 543-552.

DOI
10.1080/095281399146418
Citation Information
Freivalds, Rūsiņš, Efim B. Kinber, Carl H. Smith: "The Functions of Finite Support: A Canonical Learning Problem." Journal of Experimental & Theoretical Artificial Intelligence 11.4 (1999): 543-552.