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 -