Within the frameworks of learning in the limit of indexed classes of recursive languages from positive data and automatic learning in the limit of indexed classes of regular languages (with automatically computable sets of indices), we study the problem of minimizing the maximum number of mind changes F_M(n) by a learner M on all languages with indices not exceeding n. For inductive inference of recursive languages, we establish two conditions under which F_M(n) can be made smaller than any recursive unbounded non-decreasing function. We also establish how F_M(n) is affected if at least one of these two conditions does not hold. In the case of automatic learning, some partial results addressing speeding up the function F_M(n) are obtained.

The intrinsic complexity of learning compares the difficulty of learning classes of objects by using some reducibility notion.For several types of learning recursive functions (learning in the limit, learning with a bounded number of mind changes, learning with anomalies), both generic complete classes are exhibited and necessary and sufficient conditions for completeness are derived.Informally, a class is complete iff both its topological structure is highly complex while its algorithmic structure is surprisingly easy.Counter-intuitively, some self-describing classes turn out to be complete.

The functions of finite support have played a ubiquitous role in the study of inductive inference since its inception. In addition to providing a clear and simple example of a learnable class, the functions of finite support are employed in many proofs that distinguish various types and features of learning. Recent results show that this ostensibly simple class requires as much space to learn as any other learnable set and, furthermore, is as intrinsically difficult as any other learnable set. Since the class of functions of finite support sit at the top of two very different complexity hierarchies, this class is a candidate for being a canonical learning problem. We argue for this point in the paper and discuss the ramifications.

There have been several papers over the last ten years that consider the number of queries needed to compute a function as a measure of its complexity. The following function has been studied extensively in that light: FaA(x1,…,xa) = A(x1)…A(xa). We are interested in the complexity (in terms of the number of queries) of approximating FaA. Let b ⩽ a and let f be any function such that FaA(x1,…,xa) and f(x1,…,xa) agree on at least b bits. For a general set A we have matching upper and lower bounds on f that depend on coding theory. These are applied to get exact bounds for the case where A is semirecursive, A is superterse, and (assuming P ≠ NP) A = SAT. We obtain exact bounds when A is the halting problem using different methods.

Most work in the field of inductive inference regards the learning machine to be a passive recipient of data. In a prior paper the passive approach was compared to an active form of learning where the machine is allowed to ask questions. In this paper we continue the study of machines that ask questions by comparing such machines to teams of passive machines. This yields, via work of Pitt and Smith, a comparison of active learning with probabilistic learning. Also considered are query inference machines that learn an approximation of what is desired. The approximation differs from the desired result in finitely many anomalous places.

People tend not to have perfect memories when it comes to learning, or to anything else for that matter.Most formal studies of learning, however, assume a perfect memory.Some approaches have restricted the number of items that could be retained.We introduce a This work was facilitated by an international

A class U of recursive functions is said to be finitely (a, b) learnable if and only if for any b tuple of pairwise distinct functions from U at least a of the b functions have been learned correctly from examples of their behavior after some finite amount of time. It is shown that this approach, called learning in parallel, is more powerful than nonparallel learning. Furthermore, it is shown that imposing the restriction (called parallel super learning) on parallel learning that the learning algorithm also identiy on which of the input functions it is successful is still more powerful than nonparallel learning, A necessary and sufficient condition is derived for (a, b) superlearning and (c, d) superlearning being the same power. Our new notion of parallel learning is compared with other, previously defined notions of learning in parallel. Finally, we synthesize our notion of learning in parallel with the concept of team learning and obtain some interesting trade-offs and comparisons.

constant, finite amount of memory, there are and T such that

A class U of recursive functions is said to be finitely (a,b) learnable if and only if for any b tuple of pairwise distinct functions from U at least a of the b functions have been learned correctly from examples of their behaviour after some finite amount of time. It is shown that this approach, called learning in parallel, is more powerful than non parallel learning. Furthermore, it is shown that imposing the restriction (called parallel super learning) on parallel learning that the learning algorithm also identify which of the input functions it is successful on is still more powerful than non parallel learning. A necessary and sufficient condition is derived for (a,b) superlearning and (c,d) superlearning being the same power. Our new notion of parallel learning is compared with other, previously defined notions of learning in parallel. Finally, we synthesis our notion of learning in parallel with the concept of team learning and obtain some interesting trade offs and comparisons. (orig.)

Most theories of learning consider inferring a function f from either (1) observations about f or, (2) questions about f. We consider a scenario whereby the learner observes fand asks queries to some set A. EX[A] is the set of concept classes EX-learnable by an inductive inference machine with oracle A. A and F are EX-equivalent if EX[A] = EX[B]. The equivalence classes induced are the degrees of inferability. We prove several results about these degrees: (1) There are an uncountable number of degrees. (2) For A r.e., REC e BC[A] iff O'' ≤T A´, and there is evidence this holds for all sets A. (3) For A, B r.e., A ≡T B iff EX[A] = EX[B]. (4) There exists A, B low2 r.e., A|RB, EX[A] = EX[B]. (hence (3) is optimal).