Application of Learning Theory to Language Learning
Date Issued
2008
Date
2008
Author(s)
Cheng, Kai-Ming
Abstract
In 1984, Valiant proposed a theory for learning called PAC (Probably Approximately Correct) learning theory, which involved the building of a model for learning algorithms that given positive and negative inputs (called examples), must construct a hypothesis that should come within a reasonable range (say, ) of the actual concept to be learned with high probability (say, ). Most of the previous research, however, has focused on providing polynomial time learning algorithms for the various types of problems while passing on the subject of the number of examples needed to "learn" the problem. In this thesis, we will establish a lower bound for the number of examples needed, which improves the previously known bound by a factor of . We also look at other related issues in the context of learning, such as whether it is plausible to learn from positive examples only and the open problem of establishing an exact bound for the number of examples needed.
Subjects
(PAC)Learning Theory
Machine Learning
Vapnik-Chervonenkis Dimension
Shattering
Chernoff Bound
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R93922121-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):4d78f0e1cc9c24dec6b432f6147b25b5