This article reviews a number of different areas in the foundations of formal learning theory. After outlining the general framework for formal models of learning, the Bayesian approach to learning is summarized. This leads to a discussion of Solomonoff's Universal Prior Distribution for Bayesian learning. Gold's model of identification in the limit is also outlined. We next discuss a number of aspects of learning theory raised in contributed papers, related to both computational and representational complexity. The article concludes with a (...) description of how semi-supervised learning can be applied to the study of cognitive learning models. Throughout this overview, the specific points raised by our contributing authors are connected to the models and methods under review. (shrink)

A method is described for inducing a type-logical grammar from a sample of bare sentence trees which are annotated by lambda terms, called term-labelled trees . Any type logic from a permitted class of multimodal logics may be specified for use with the procedure, which induces the lexicon of the grammar including the grammatical categories. A first stage of semantic bootstrapping is performed, which induces a general form lexicon from the sample of term-labelled trees using Fulop’s (J Log Lang Inf (...) 14(1):49–86, 2005) procedure. Next we present a two-stage procedure for performing distributional learning by unifying the lexical types that are initially discovered. The first structural unification algorithm in essence unifies the initial family of sets of types so that the resulting grammar will generate all term-labelled trees that follow the usage patterns evident from the learning sample. Further altering the lexical categories to generate a recursively extended language can be accomplished by a second unification. The combined unification algorithm is shown to yield a new type-logical lexicon that extends the learning sample to a possibly infinite (and possibly context-sensitive) language in a principled fashion. Finally, the complete learning strategy is analyzed from the perspective of algorithmic learning theory; the range of the procedure is shown to be a class of term-labelled tree languages which is finitely learnable from good examples (Lange et al in Algorithmic learning theory, Vol 872 of lecture notes in artificial intelligence, Springer, Berlin, pp 423–437), and so is identifiable in the limit as a corollary. (shrink)

A two-stage procedure is described which induces type-logical grammar lexicons from sentences annotated with skeletal terms of the simply typed lambda calculus. First, a generalized formulae-as-types correspondence is exploited to obtain all the type-logical proofs of the sample sentences from their lambda terms. The resulting lexicons are then optimally unified. The first stage constitutes the semantic bootstrapping (Pinker, Language Learnability and Language Development, Harvard University Press, 1984), while the unification procedure of Buszkowski and Penn represents a first attempt at structure-dependent (...) distributional learning of the syntactic and semantic categories. This effort extends earlier induction procedures (Buszkowski and Penn, 1990, Studia Logica 49, 431–454; Kanazawa, 1998, CSLI Publications and the European Association for Logic, Language and Information) for classical categorial grammar to at first the non-associative Lambek calculus, and then to a large class of type logics enriched by modal operators and structural rules. (shrink)

A two-stage procedure is described which induces type-logical grammar lexicons from sentences annotated with skeletal terms of the simply typed lambda calculus. First, a generalized formulae-as-types correspondence is exploited to obtain all the type-logical proofs of the sample sentences from their lambda terms. The resulting lexicons are then optimally unified. The first stage constitutes the semantic bootstrapping (Pinker, Language Learnability and Language Development, Harvard University Press, 1984), while the unification procedure of Buszkowski and Penn represents a first attempt at structure-dependent (...) distributional learning of the syntactic and semantic categories. This effort extends earlier induction procedures (Buszkowski and Penn, 1990, Studia Logica 49, 431–454; Kanazawa, 1998, CSLI Publications and the European Association for Logic, Language and Information) for classical categorial grammar to at first the non-associative Lambek calculus, and then to a large class of type logics enriched by modal operators and structural rules. (shrink)