TY - JOUR

T1 - Open problems in "systems that learn"

AU - Fulk, Mark

AU - Jain, Sanjay

AU - Osherson, Daniel N.

N1 - Funding Information:
A typical learning scenario involving a subject learning a concept could be described thus: Subject receives successive finite pieces of data about the concept being learned over time. Based upon these data, the subject, each time, either holds or changes its previous explanation for the concept. The subject converges to a particular explanation, if, after some time, it always holds that explanation. The subject is said to learn the concept, just in case it converges to a correct explanation for the concept. Computational learning theory provides a framework for studying * Supported by NSF Grant CCR 832-0136. Supported in part by ONR Grants N00014-87-K-0401 and N00014-89-J-1725.

PY - 1994/12

Y1 - 1994/12

N2 - In this paper we solve some of the open problems in D. Osherson, M. Stob, and S. Weinstein ("Systems That Learn," MIT Press, Cambridge, MA, 1986). We also give partial solutions to some other open problems in the book. In particular we show that the collection of classes of languages that can be identified on "noisy" text (i.e., a text which may contain some elements which are not in the language being learned) strictly contains the collection of classes of languages that can be identified on "imperfect" text (i.e., a text which may contain some extra elements and may leave out some elements from the language being learned). We also show that memory limited identification is strictly more restrictive that memory bounded identification. Besides solving the above two open problems from op. cit., we also give partial solutions to other open problems in ibid.

AB - In this paper we solve some of the open problems in D. Osherson, M. Stob, and S. Weinstein ("Systems That Learn," MIT Press, Cambridge, MA, 1986). We also give partial solutions to some other open problems in the book. In particular we show that the collection of classes of languages that can be identified on "noisy" text (i.e., a text which may contain some elements which are not in the language being learned) strictly contains the collection of classes of languages that can be identified on "imperfect" text (i.e., a text which may contain some extra elements and may leave out some elements from the language being learned). We also show that memory limited identification is strictly more restrictive that memory bounded identification. Besides solving the above two open problems from op. cit., we also give partial solutions to other open problems in ibid.

UR - http://www.scopus.com/inward/record.url?scp=0028699849&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028699849&partnerID=8YFLogxK

U2 - 10.1016/S0022-0000(05)80072-8

DO - 10.1016/S0022-0000(05)80072-8

M3 - Article

AN - SCOPUS:0028699849

SN - 0022-0000

VL - 49

SP - 589

EP - 604

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 3

ER -