In Computational Learning in the Limit, many criteria of successful learning have been proposed in the literature. For example, an algorithmic learner h tries to find a program for a computable function g (learnee) given successively more values of g, each time outputting a conjectured program for g; learning is considered successful, iff, from some point on, the learner always conjectures the same program p, and p is a program for g.
In the present thesis we will give a unifying framework, an abstraction of these criteria, and discuss its many merits. For example, a new learning paradigm, called Dynamic Modeling, is introduced. It actually arose out of the above abstraction.
Dynamic Modeling provides an idealization of, for example, a social interaction in which learner h seeks to discover program models of learnee g's behavior it sees in interacting with g, and h openly discloses to g its sequence of candidate program models to see what g says back. The learnee g, then, could try to learn back the behavior of learner h. We say that h cooperatively learns g iff h learns g and g learns h back. We say that h secretively learns g iff h learns g and g cannot learn h back. We show that there are non-trivial cases of both cooperative and secretive learning.
Furthermore, we will analyze efficient use of time in learning. Many notions of time restrictions suffer from unfair postponement tricks, i.e., the possibility to bypass runtime restrictions by postponing necessary computations. An important question to address is, then, how to avoid these postponement tricks and to achieve fair runtime restricted learning in the limit.
A learner is called postdictively complete iff all available data is correctly postdicted by each conjecture. The present thesis will show how postdictive completeness (and variants thereof) introduce some degree of fairness into runtime restricted learning in the limit.
Contrasting these latter results, we will point out many difficulties for introducing fairness into polynomial time restricted learning, for example by showing how several restrictions previously thought to forbid postponement tricks fail to do so.
Finally, some criteria in Dynamic Modeling are shown to naturally include some degree of fairness; however, some settings still allow for arbitrary postponement tricks.
|Commitee:||Chester, Daniel, Royer, James, Saunders, David|
|School:||University of Delaware|
|Department:||Department of Computer and Information Sciences|
|School Location:||United States -- Delaware|
|Source:||DAI-B 70/09, Dissertation Abstracts International|
|Keywords:||Complexity, Computational learning, Conservativeness, Consistency, Learning in the limit, Prudence|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
supplemental files is subject to the ProQuest Terms and Conditions of use.