Monotonic language learning

Lecture notes in computer sciencePublished 1 January 1993

Shyam Kapur

DOI10.1007/3-540-57369-0_35

Source URL

Citations23

SJR quartileQ2

SJR score0.35

SNIP0.55

TL;DR

The ideas from inductive reasoning are instantiated in alternative ways, and links are established between the various new constraints both among themselves as well as with other well-known constraints, such as conservativeness.

Abstract

Learnability of families of recursive languages from positive data is studied in the Gold paradigm of inductive inference, where the learner obeys certain constraints motivated by work in inductive reasoning. Previously, various notions of monotonicity have been defined in the context of language learning. These constraints require that the learner's guess monotonically 'improves' with regard to the target language. In this paper, the ideas from inductive reasoning are instantiated in alternative ways. Links are established between the various new constraints both among themselves as well as with other well-known constraints, such as conservativeness. Exactly learnable families are characterized for prudent learners which obey various combinations of these constraints. Applications of these characterizations are also shown.

Keywords

Computer Science

Information and ControlLanguage identification in the limit

3,569 Citations1967Eric Gold

It was found that theclass of context-sensitive languages is learnable from an informant, but that not even the class of regular languages is learningable from a text.

Information and ControlInductive inference of formal languages from positive data

750 Citations1980Dana Angluin

A theorem characterizing when an indexed family of nonempty recursive formal languages is inferrable from positive data is proved, and other useful conditions for inference frompositive data are obtained.

Telematics and InformaticsThe Acquisition of Syntactic Knowledge

666 Citations1986

The MIT Press eBooksThe Acquisition of Syntactic Knowledge

512 Citations1985Robert C. Berwick

An explicit computational model of language acquisition is presented which can actually learn rules of English syntax given a sequence of grammatical, but otherwise unprepared, sentences and demonstrates how constraints that may be reasonably assumed to aid sentence processing also aid language acquisition.

New Generation ComputingMonotonic and non-monotonic inductive inference

84 Citations1991Klaus P. Jantke

The main goal is to exhibit the relationship between research work on non-monotonic reasoning and recursion-theoretically based approaches to inductive learning.

Types of monotonic language learning and their characterization

81 Citations1992Steffen Lange, Thomas Zeugmann

It is proved that strong-monotonic inference can be performed with iteratively learning devices without limiting the inference capabilities, while monotonic and weak-monotsonic inference cannot.

Lecture notes in computer scienceA thesis in inductive inference

79 Citations2005Rolf Wiehagen

The following thesis was stated: Any class of recursive functions which is identifiable at all can always be identified by an enumeratively working strategy and the identification canAlways be realized with respect to a suitable nonstandard (i.e. non-Godel) numbering.

Lecture notes in computer scienceMonotonic versus non-monotonic language learning

64 Citations2006Steffen Lange, Thomas Zeugmann

Strong- monotonic, monotonie and weak-monotonic reasoning is studied in the context of algorithmic language learning theory from positive as well as from positive and negative data.

Lecture notes in computer scienceCharacterization of finite identification

51 Citations1992Yasuhito Mukouchi

Finite identification for a class of recursive languages, where the inference machine produces a unique guess just once when it is convinced the termination of the inference, and the results do not involve any risks.

Cornell University eBooksComputational learning of languages

35 Citations1992Shyam Kapur

It is shown that any family of languages can be learned with probability 1 from stochastic input, provided something is known about the probability distribution according to which the input is presented.