{"content":[{"text":"Feasible Iteration of Feasible Learning Functionals","bbox":{"left":0.541151,"top":0.179184,"width":0.47300700000000007,"height":0.016560999999999992}},{"text":"35","bbox":{"left":1.071843,"top":0.179184,"width":0.021304999999999907,"height":0.016560999999999992}},{"text":"1","bbox":{"left":0.289151,"top":0.214304,"width":0.015625,"height":0.021682000000000007}},{"text":"Introduction and Motivation","bbox":{"left":0.336049,"top":0.214304,"width":0.39319599999999993,"height":0.021682000000000007}},{"text":"One-shot (algorithmic) learners, on input data about a function, output at most \n a single (hopefully correct) conjectured program [JORS99]. Feasible (determin- \n istic) one-shot function learning can be modeled by the polytime multi-tape \n Oracle Turing machines (OTMs) as used in [IKR01] (see also [KC96, Meh76]). \n We call the corresponding functionals basic feasible functionals. \n In the context of learning in the limit, i.e., learning with a succession of one- \n shots, where only the ﬁnal shots are hoped to be correct, we are interested, then, \n in how one might deﬁne feasible for limiting-computable functionals. We next \n discuss the concepts we require for such a deﬁnition. \n Intuitively ordinals [Sie65] are representations of well-orderings. 0 represents \n the empty ordering, 1 represents the ordering of 0 by itself, 2 the ordering 0 < 1, \n 3 the ordering 0 < 1 < 2, . . . . The ordinal ω represents the standard ordering \n of all of N. ω + 1 represents the ordering of N consisting of the positive integers \n in standard order followed by 0. The successor ordinals are those of the form \n α + 1 which have a single element laid out after a copy of another ordinal α. \n ω + ω can be thought of as two copies of ω laid end to end — much bigger \n than ω. ω · 3 represents three copies of ω laid end to end. By contrast, 3 · ω \n represents ω copies of 3 — which is just ω. We see, for ordinals, +, · are not \n commutative. ω · ω is ω copies of ω laid out end to end. We can iterate this \n and deﬁne exponentiation for ordinals. Limit ordinals are those, like ω, ω + ω, \n ω · ω, and ωω, which are not 0 and are not successor ordinals. All of them are \n inﬁnite. Importantly, the constructive ordinals are just those that have a program \n (called a notation) in some system which speciﬁes how to build them (lay them \n out end to end, so to speak). Everyone knows how to use the natural numbers \n for counting, including for counting down. Freivalds and Smith [FS93], as well \n as [ACJS04], employed in learning theory notations for constructive ordinals as \n devices for algorithmic counting down. Herein we need to count down iterations \n of applications of feasible learning functionals. For example, for us, as we will see \n more formally in Section 4 below, algorithmic counting down iterations from any \n notation u for ω + 1 is roughly equivalent to counting down one iteration and, \n then, deciding dynamically how many further but ﬁnite number of iterations \n will be allowed. Herein, though, we want the counting down process itself to \n be feasible. Hence, in Section 3, we introduce feasibly related feasible systems of \n ordinal notations, where, basically, the deﬁnition of a system of ordinal notations \n (as in [Rog67]) is restricted to those systems where all necessary operations and \n decision processes are feasibly computable. In Section 3, by Theorem 8, for each \n constructive ordinal α, we have such a system containing a notation for α and \n all its predecessors. \n In Section 4, we present our proposed deﬁnition (Deﬁnition 11) for feasible it- \n eration of feasible learning functionals. Then we present our general main results \n providing for strict learning hierarchies at all and only notations for (inﬁnite) limit \n ordinals. First, Theorem 14 provides the learning hierarchy collapse between fea- \n sible notations for α and for α + 1. Importantly, Theorem 17, provides a strict \n learning hierarchy between feasible notations for successive feasible limit ordinals.","bbox":{"left":0.289149,"top":0.251903,"width":0.8049070000000002,"height":0.7973140000000001}}],"images_bbox":[],"images_bbox_not_text_overlap":[]}