The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Aclass C of recursive functions is called robustly learnable in the sense I (where I is any success criterion of learning) if not only C itself but even all transformed classes T(C) where T is any general recursive operator, are learnable in the sense I. It was already shown before, see [14,19], that for I = Ex (learning in the limit) robust learning is rich in that there are classes being both not...
A new identification type close to the identification of minimal Gödel numbers is considered. The type is defined by allowing as input both the graph of the target function and an arbitrary upper bound of the minimal index of the target function in a Gödel numbering of all partial recursive functions. However, the result of the inference has to be bounded by a fixed function from the given bound....
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”...
Learning by erasing means the process of eliminating potential hypotheses from further consideration thereby converging to the least hypothesis never eliminated and this one must be a solution to the actual learning problem. The present paper deals with learnability by erasing of indexed families of languages from both positive data as well as positive and negative data. This refers to the...
The usual information in inductive inference for the purposes of learning an unknown recursive function f is the set of all input /output examples (n,f(n)), n ∈ ℕ. In contrast to this approach we show that it is considerably more powerful to work with finite sets of “good” examples even when these good examples are required to be effectively computable. The influence of the underlying numberings,...
We present two phenomena which were discovered in pure recursion-theoretic inductive inference, namely inconsistent learning (learning strategies producing apparently “senseless” hypotheses can solve problems unsolvable by “reasonable” learning strategies) and learning from good examples (“much less” information can lead to much more learning power). Recently, it has been shown that these phenomena...
Synthesis of programs of recursive functions from input/output examples is investigated where the synthesis is effective in the sense that one is able to algorithmically determine when the correct program of the function under consideration has been found. Necessary and sufficient conditions are derived that the synthesis can be done if the admissible number of input/output examples is bounded.
We study learning of indexable families of recursive languages from good examples. We show that this approach is considerably more powerful than learning from all examples and point out reasons for this additional power. We present several characterizations of types of learning from good examples. We derive similarities as well as differences to learning of recursive functions from good examples.
In designing learning algorithms it seems quite reasonable to construct them in a way such that all data the algorithm already has obtained are correctly and completely reflected in the description the algorithm outputs on these data. However, this approach may totally fail, i.e., it may lead to the unsolvability of the learning problem, or it may exclude any efficient solution of it. In particular,...
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”...
This paper was inspired by [FBW 94]. An arbitrary upper bound on the size of some program for the target function suffices for the learning of some program for this function. In [FBW 94] it was discovered that if “learning” is understood as “identification in the limit,” then in some programming languages it is possible to learn a program of size not exceeding the bound, while in some other programming...
Our goal is to arrive at a deeper understanding of the classification problem. We study a particular collection of classification problems, the classification of recursive predicates and languages. In particular, we compare the classification of predicates and languages with the classification of arbitrary recursive functions and with learning. Moreover, we refine our investigations by introducing...
In designing learning algorithms it seems quite reasonable to construct them in such a way that all data the algorithm already has obtained are correctly and completely reflected in the hypothesis the algorithm outputs on these data. However, this approach may totally fail. It may lead to the unsolvability of the learning problem, or it may exclude any efficient solution of it. Therefore we...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.