My field of research is algorithmic learning theory, which lies at the intersection of computability theory and computer science. I am pursuing my Ph.D. under the supervision of Steffen Lempp
. I spent the Spring 2012 term at the University of California - Berkeley working with Leo Harrington
. In my field, research examines effective models of learning and what information can be absorbed assuming various criteria for successful learning.
An excellent resource for information on learning theory is the webpage of Frank Stephan
at the National University of Singapore. If you are interested in learning theory, feel free to write to me. I am always interested in hearing questions and ideas.
Anomalous Vacillatory Learning
(Accepted for publication in the Journal of Symbolic Logic)
In 1986, Osherson, Stob and Weinstein asked whether two variants of anomalous vacillatory learning, TxtFex** and TxtFext**, could be distinguished. These learning criteria place bounds neither on the number of hypotheses between which the learner is allowed to vacillate nor on the number of errors permitted, merely that both are finite. The criteria differ in that the more restrictive one, TxtFext**-learning, requires that all hypotheses output infinitely often must describe the same finite variant of the correct set, while TxtFex** permits the learner to vacillate between finitely many different finite variants of the correct set. In this paper we show that TxtFex** ≠ TxtFext**, thereby answering the question posed by Osherson, et al. We prove this in a strong way by exhibiting a family in TxtFex*2\TxtFext**.
Learning Theory in the Arithmetic Hierarchy
(Submitted for publication)
We consider the arithmetic complexity of index sets of uniformly computably enumerable families learnable under different learning criteria. We determine the exact complexity for the standard notions of finite learning, learning in the limit, behaviourally correct learning and anomalous learning in the limit. In proving the Σ05-completeness result for behaviourally correct learning we prove a result of independent interest; if a u.c.e. family is not learnable, for any computable learner there is a Δ02 enumeration witnessing failure.