Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Computional Learning of Languages

Computional Learning of Languages

File(s)
91-1234.ps (1006.07 KB)
91-1234.pdf (5.11 MB)
Permanent Link(s)
https://hdl.handle.net/1813/7074
Collections
Computer Science Technical Reports
Author
Kapur, Shyam
Abstract

This thesis focuses on the Gold model of inductive inference from positive data. There are several aspects in which the model appears unsatisfactory for language learning: the class of families of learnable languages is highly restricted; even if a family is learnable, there exists no uniform method to obtain a learner for it, and the learner itself is complex. In this thesis, some such criticisms are being addressed. It is shown that no automatic synthesis of a learner from the description of a learnable family is possible. Nevertheless, in some special cases, this synthesis can be achieved and a general result is developed. In order to make the learner simpler, it is stipulated that the learner can change its guess only when the guess is inconsistent with the input evidence. Such a conservative learner never overgeneralizes. Exactly learnable families are characterized for prudent learners with the following types of constraints: (0) conservative, (1) conservative and consistent, (2) conservative and responsive, and (3) conservative, consistent and responsive. It is also shown that, when exactness is not required, prudence, consistency and responsiveness, even together, do not restrict the power of conservative learners. Conservative learners are simple in only one respect; even though it is easy to determine when to make a new guess, it is still hard to know what this guess should be. Finally, a learner that exploits pattern evident in the input is developed. Absence of a particular string over a suitable interval of the input can be viewed as a kind of "indirect negative evidence". Now, the learning criterion needs to be weakened to allow limited failure. 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. Given the family, the learner is uniformly constructible. Further, the behavior of the learner is simpler in many aspects. It is expected that a variety of other natural constraints can be imposed on this learner without additional cost.

Date Issued
1991-09
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1234
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance