UCSC-CRL-92-22: TOWARDS A MORE COMPREHENSIVE THEORY OF LEARNING IN COMPUTERS

06/01/1992 09:00 AM
Computer Science
We attempt to determine the theoretical boundaries of the ability of computers to learn. We consider several rigorous models of learning, aimed at addressing types of learning problems excluded from earlier models. In Part I, we consider learning dependencies between real-valued quantities in situations where the environment is assumed to be an adversary, operating within constraints that model the prior knowledge of the learner. While our assumptions as to the form of these dependencies is taken from previous work in statistics, this work is distinguished by the fact that the analysis is worst case. In Part II, we consider learning in situations in which the learner\'s enviroment is assumed to be at least partially random. We consider methods for extending the tools for learning {0,1}-valued functions to apply to the learning of many-valued and real-valued functions. We also study the learning of {0,1}- valued functions in situations in which the relationship to be learned is gradually changing as learning is taking place. Notes: Ph.D. thesis

UCSC-CRL-92-22