Aarhus University Seal / Aarhus Universitets segl

Learnability

Research output: Working paper/Preprint Working paperResearch

  • Department of Computer Science
Les Valiant has recently conceived a remarkable mathematical model of learnability. The originality appears through several facets of the model. Objects belonging to a specific concept are given a measure of naturalness in the form of a probability distribution. The learning of a concept takes place by means of a protocol that among other tools allows the use of a source of natural examples. A concept is learnable if a recognition algorithm can be synthesized within a polynomial number of steps. The recognition algorithm is allowed to be incorrect for an adjustable fraction of inputs measured with respect to naturalness.

Technically the model is based on the propositional logic over a finite number of Boolean variables. However, the underlying ideas are quite universal and can be realised by means of an almost arbitrary formal language, which we will demonstrate in this note. A single concept may include infinitely many objects within a formal language frame. Fortunately we can learn such concepts from finite sets of examples only. We shall prove a specific class of concepts to be learnable within the nontrivial formal language of predicate logic.
Original languageEnglish
PublisherDepartment of Computer Science, Aarhus University
Number of pages21
Publication statusPublished - 1985

Bibliographical note

Part of Ph.D. thesis

See relations at Aarhus University Citationformats

ID: 36650822