Search results for "recursive function"
showing 10 items of 26 documents
General inductive inference types based on linearly-ordered sets
1996
In this paper, we reconsider the definitions of procrastinating learning machines. In the original definition of Freivalds and Smith [FS93], constructive ordinals are used to bound mindchanges. We investigate the possibility of using arbitrary linearly ordered sets to bound mindchanges in a similar way. It turns out that using certain ordered sets it is possible to define inductive inference types more general than the previously known ones. We investigate properties of the new inductive inference types and compare them to other types.
Learning with confidence
1996
Herein we investigate learning in the limit where confidence in the current conjecture accrues with time. Confidence levels are given by rational numbers between 0 and 1. The traditional requirement that for learning in the limit is that a device must converge (in the limit) to a correct answer. We further demand that the associated confidence in the answer (monotonically) approach 1 in the limit. In addition to being a more realistic model of learning, our new notion turns out to be a more powerful as well. In addition, we give precise characterizations of the classes of functions that are learnable in our new model(s).
On the Intrinsic Complexity of Learning
1995
AbstractA new view of learning is presented. The basis of this view is a natural notion of reduction. We prove completeness and relative difficulty results. An infinite hierarchy of intrinsically more and more difficult to learn concepts is presented. Our results indicate that the complexity notion captured by our new notion of reduction differs dramatically from the traditional studies of the complexity of the algorithms performing learning tasks.
Error detecting in inductive inference
1995
Several well-known inductive inference strategies change the actual hypothesis only when they discover that it “provably misclassifies” an example seen so far. This notion is made mathematically precise and its general power is characterized. In spite of its strength it is shown that this approach is not of universal power. Consequently, then hypotheses are considered which “unprovably misclassify” examples and the properties of this approach are studied. Among others it turns out that this type is of the same power as monotonic identification. Then it is shown that universal power can be achieved only when an unbounded number of alternations of these dual types of hypotheses is allowed. Fi…
Dual types of hypotheses in inductive inference
2006
Several well-known inductive inference strategies change the actual hypothesis only when they discover that it “provably misclassifies” an example seen so far. This notion is made mathematically precise and its general power is characterized. In spite of its strength it is shown that this approach is not of “universal” power. Consequently, then hypotheses are considered which “unprovably misclassify” examples and the properties of this approach are studied. Among others it turns out that this type is of the same power as monotonic identification. Finally, it is shown that “universal” power can be achieved only when an unbounded number of alternations of these dual types of hypotheses is all…
Topological considerations in composing teams of learning machines
1995
Classes of total recursive functions may be identifiable by a team of strategies, but not by a single strategy, in accordance with a certain identification type (EX, FIN, etc.). Qualitative aspects in composing teams are considered. For each W ∉ EX all recursive strategies can be split into several families so that any team identifying W contains strategies from all the families. For W ∉ FIN the possibility of such splitting depends upon W. The relation between these phenomena and “voting” properties for types EX, FIN, etc. is revealed.
Vertical Representation of C∞-words
2015
International audience; We present a new framework for dealing with C∞-words, based on their left and right frontiers. Thisallows us to give a compact representation of them, and to describe the set of C∞-words throughan infinite directed acyclic graph G. This graph is defined by a map acting on the frontiers ofC∞-words. We show that this map can be defined recursively and with no explicit reference toC∞-words. We then show that some important conjectures on C∞-words follow from analogousstatements on the structure of the graph G.
Vertical representation of C∞-words
2015
We present a new framework for dealing with C ∞ -words, based on their left and right frontiers. This allows us to give a compact representation of them, and to describe the set of C ∞ -words through an infinite directed acyclic graph G. This graph is defined by a map acting on the frontiers of C ∞ -words. We show that this map can be defined recursively and with no explicit reference to C ∞ -words. We then show that some important conjectures on C ∞ -words follow from analogous statements on the structure of the graph G.
Co-learning of recursive languages from positive data
1996
The present paper deals with the co-learnability of enumerable families L of uniformly recursive languages from positive data. This refers to the following scenario. A family L of target languages as well as hypothesis space for it are specified. The co-learner is fed eventually all positive examples of an unknown target language L chosen from L. The target language L is successfully co-learned iff the co-learner can definitely delete all but one possible hypotheses, and the remaining one has to correctly describe L.
On the intrinsic complexity of learning
1995
A new view of learning is presented. The basis of this view is a natural notion of reduction. We prove completeness and relative difficulty results. An infinite hierarchy of intrinsically more and more difficult to learn concepts is presented. Our results indicate that the complexity notion captured by our new notion of reduction differs dramatically from the traditional studies of the complexity of the algorithms performing learning tasks.