Learnability

Abstract

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.