Dissertation/Thesis Abstract

Abstraction and complexity in computational learning in the limit
by Kotzing, Timo, Ph.D., University of Delaware, 2009, 155; 3373055
Abstract (Summary)

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.

Indexing (document details)
Advisor: Case, John
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
Subjects: Computer science
Keywords: Complexity, Computational learning, Conservativeness, Consistency, Learning in the limit, Prudence
Publication Number: 3373055
ISBN: 978-1-109-38695-0
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy