The functions of finite support: a canonical learning problem
| Autor: | Carl Smith, Efim Kinber, Rusins Freivalds |
|---|---|
| Rok vydání: | 1999 |
| Předmět: |
Computer Science::Machine Learning
Class (set theory) Theoretical computer science business.industry Computer science Inference Inductive reasoning Space (commercial competition) Mathematical proof Theoretical Computer Science Set (abstract data type) Artificial Intelligence Simple (abstract algebra) Point (geometry) Artificial intelligence business Software |
| Zdroj: | Journal of Experimental & Theoretical Artificial Intelligence. 11:543-552 |
| ISSN: | 1362-3079 0952-813X |
| DOI: | 10.1080/095281399146418 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|