學習理論在語言學習上的應用

Application of Learning Theory to Language Learning

鄭開明(Kai-Ming Cheng)

指導教授 ： 呂育道

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.01547

摘要

1984年時，Valiant提出了PAC學習的理論。這個理論中提到一種建造學習的模型的方法。在一個學習演算法同時得到正面和負面的例子之後，必須要建構出一個和它所想要學會的實際的概念不會相差太多的假設。之前的研究主要都是對於各式各樣的問題提出多項式時間之內的學習演算法，而沒有特別去探索到底需要多少個例子才能夠把一個問題「學會」。在這份論文裡，我們會發展出一個學習演算法所需要的例子的數目的下限，而這樣的下限比起之前的演算法所提出的又進步了 。我們也一併探討其他和學習相關的問題，像是是否能夠只透過正面的例子就能夠學習，還有對於學習演算法是否存在精確的所需的例子的數目的這個待解的問題。

關鍵字

PAC學習理論 ； 機器學習 ； Vapnik-Chervonenkis維度 ； Shattering(震碎) ； Chernoff限制式

並列摘要

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.

並列關鍵字

(PAC)Learning Theory ； Machine Learning ； Vapnik-Chervonenkis Dimension ； Shattering ； Chernoff Bound

參考文獻

[1] Baum, E., D. Haussler. “What Size Net Gives Valid Generalization?” Neural Computation, 1, 1990, pp. 151–160.

[2] Blumer, A., A. Ehrenfeucht, D. Haussler, M. Warmuth. “Learnability and the Vapnik-Chervonenkis Dimension.” Journal of the ACM, 36, 1989, pp. 929–965.

[4] Haussler, D. “Quantifying Inductive Bias: AI Learning Algorithms and Valiant’s Model.” Artificial Intelligence, 36, 1988, pp. 177–221.

[8] Pitt, L., L.G. Valiant. “Computational Limitations on Learning from Examples.” Journal of the ACM, 35, 1988, pp. 965–984.

[9] Rivest, R. “Learning Decision Lists.” Machine Learning, 2, 1987, pp. 229–246.