LANGUAGE LEARNING OF INDUCTIVE INFERENCE MACHINES WITH MEMORY LIMITATION

Abstract

Inductive inference is a machine learning model inspired by learning activities in real life, in which the learner keeps accepting inputs from the environment while giving conjectures about the learning target continuously without knowing whether the conjectures are correct. Such learning process is successful if the conjectures made by the learner converge to the correct learning target. This thesis investigates the properties of inductive inference with memory limitation in two topics. The first topic introduces priced learning, an inductive inference model implicitly constrains the memory usage by adding a cost on each memory update based on a given price function, while requiring a successful priced learner not take infinite cost during the whole learning process. The learning capacity of priced learning is proved between iterative learning and set-driven learning. The second topic reviews some variants of iterative learning model, showing that the decisiveness is unrestrictive under the iterative learning framework.