טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentBentov Iddo
SubjectOn Exact Learning from Random Walk
DepartmentDepartment of Computer Science
Supervisor Professor Nader Bshouty
Full Thesis textFull thesis text - English Version


Abstract

The well known learning models in Computational Learning Theory are either adversarial, meaning that the examples are arbitrarily selected by the teacher, or i.i.d., meaning that the teacher generates the examples independently and identically according to a certain distribution. However, it is also quite natural to study learning models in which the teacher generates the examples according to a stochastic process.


A particularly simple and natural time-driven process is the random walk stochastic process. We consider exact learning models based on random walk, and thus having in effect a more restricted teacher compared to both the adversarial and the uniform exact learning models. We investigate the learnability of common concept classes via random walk, and give positive and negative separation results as to whether exact learning in the random walk models is easier than in less restricted models.