Article FINite learning capabilities and their limits Share on Authors: Robert Daley Department of Computer Science, University of Pittsburgh, Pittsburgh, PA Department of Computer Science, University of Pittsburgh, Pittsburgh, PAView Profile , Bala Kalyanasundaram Department of Computer Science, University of Pittsburgh, Pittsburgh, PA Department of Computer Science, University of Pittsburgh, Pittsburgh, PAView Profile Authors Info & Claims COLT '97: Proceedings of the tenth annual conference on Computational learning theoryJuly 1997 Pages 81–89https://doi.org/10.1145/267460.267483Online:01 July 1997Publication History 2citation134DownloadsMetricsTotal Citations2Total Downloads134Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We show that for every probabilistic FIN-type learner with success ratio greater than 2449, there is another pluralistic (or team) FIN-type learner with success ratio 24 that simulates the former. We will also show that this simulation result is tight. We obtain as a consequence of this work a characterization of FIN-type team learning with success ratio between 2449 and 12. We also obtain several additional points (viz., 2041, 1837, 1735) in the capability sequence for FIN-type learning, which taken together suggest that the complete sequence of capabilities will turn out to be a very complex matter.

We consider the capabilities of probabilistic and team learners who (a) are allowed to conjecture only one hypothesis when given a function to learn; and (b) must always produce a program (i.e. hypotheses) that halts on every input. Learners satisfying only (a) are termed FIN-type learners, and learners satisfying both (a) and (b) are termed PFIN-type learners. We show that the structure of the learning capability of probabilistic and team learning with success ratio above 1/2 in PFIN-type learning is analogous to the structure observed in FIN-type learning. On the contrary, the structure of probabilistic and team learning with success ratio below 1/2 is more sparse for PFIN-type learning than for FIN-type learning. For n ≥ 2, we show that the probabilistic hierarchy below 1/2 for PFIN-type learning is denned by the sequence 4n/(9n − 2), which has an accumulation point at 4/9. We also show that the redundancy type at the accumulation point 4/9 is different from the one observed at 1/2. More interestingly, for the first time, we show the occurrence of redundancy even at points that are not accumulation points.

We consider the power of randomization in finite learning when a bounded number of mind changes are allowed.We show that in the ~m+2_3 range ( ~~+a _2, 1] the capability type of probabilistic as well as pluralistic FIN-type (also PFIN-type) learners is defined by the sequence 2"'+7-3 n+l {w n ~O}, where m ~O is the allowed number of mind changes for the learners.This generalizes most of the results known in the literature on finite learning.For any fixed number of mind changes, we show that deterministic strategies can simulate probabilistic strategies where the success ratio is close to but not equal to 1. F'inaHy, our results demonstrate the power of redundancy when a bounded number of mind changes are allowed.In contrast, it is known that the power of redundancy disappears when an apriori unbounded (but finite) number of mind changes are allowed.

The type of learning which we consider is finite learning( F]N-t ype) where a learner is permitted to conjecture only one program for the function which it is trying to learn.In this paper we investigate the relative learning capabilities of probabilistic and pluralistic learners when they are allowed to conjecture programs which have errors in them.Pluralistic learners are teams of learners which cooperate in trying to learn a function.We determine the exact point at which probabilistic learners are more powerful than deterministic (i.e., a team of size one) learners.

We show that for every probabilistic FIN-type learner with success ratio greater than 24/49, there is another probabilistic FIN-type learner with success ratio 1/2 that simulates the former. We will also show that this simulation result is tight. We obtain as a consequence of this work a characterization of FIN-type team learning with success ratio between 24/49 and 1/2. We conjecture that the learning capabilities of probabilistic FIN-type learners for probabilities beginning at probability 1/2 are delimited by the sequence 8n/17n-2 for n > 2, which has an accumulation point at 8/17.

In this paper we show how some of the finite injury priority arguments can be simplified by making explicit use of the primitive notions of axiomatic computational complexity theory. Phrases such as “perform n steps in the enumeration of Wi” certainly bear witness to the fact that many of these complexity notions have been used implicitly from the early days of recursive function theory. However, other complexity notions such as that of an “honest” function are not so apparent, neither explicitly nor implicitly. Accordingly, one of the main factors in our simplification of these diagonalization arguments is the replacement of the characteristic function χA of a set A by the function νA, which is the next-element function of the set A. Another important factor is the use of busy beaver sets (see [3]) to provide the basis for the required diagonalizations thereby permitting rather simple and explicit descriptions of the sets constructed. Although the differences between the priority method and our method of construction are subtle, they are nonetheless real and noteworthy. In preparation for the results which follow we devote the remainder of this section to the requisite definitions and notions as well as some preliminary lemmas. A more comprehensive discussion of many of the notions in this section can be found in [3]. Since we will be dealing extensively with relative computations most of our notions here have been correspondingly relativized.

We are concerned in this paper with infinite binary sequences which are noncomplex in the sense that their minimal-program complexity (i.e., the lengths of shortest programs for computing their finite initial segments), as a function of the lengths of their initial segments, grows arbitrarily (in an effective sense) slowly. Indeed, the existence of such sequences which are also nonrecursive raises some interesting questions concerning the notion of computability itself. Our first task is to give a characterization of these sequences which does not directly involve the notions of complexity theory. Although these characterizations do involve the primitives of recursive function theory, they do not involve the types of properties which one usually encounters there. While a closer connection is still hoped for, the lack of one is not entirely unexpected. For example, except for the trivial case of degree 0, there is no general correlation between program complexity and degrees of unsolvability. The reason, roughly, is this: even though the inequality deg (f) ≤ deg (g) expresses the relative information between f and g (in the sense that if one knows g then one can compute f), it is a qualitative sort of information. The minimal-program complexity is used as a measure of algorithmic information content and as such is quantitative. The second task of this paper is to present an example of one of these sequences which to its credit possesses a fairly long list of interesting properties, not the least attractive of which is that, though nonrecursive, it is very simple to describe. In fact this sequence has occurred previously in the literature. It is the characteristic sequence of the set of busy beaver numbers first studied by T. Rado [13]. Of particular interest to the discussion in the last section of this paper concerning the notion of computability is the fact that all the initial segments of this sequence are computable by arbitrarily short programs each of which is defined on all inputs and runs very quickly.

This paper is concerned with establishing the existence of a recursive sequence x which exhibits a "continuous" trade-off between the length of programs (information) which compute the finite initial segments of x and the computation resources (e.g.computation time) required by these programs for such computation.