The present work introduces and justifies the notion of hyperrobust learning where one fixed learner has to learn all functions in a given class plus their images under primitive recursive operators. ...The following are shown: The notion of learnability does not change if the class of primitive recursive operators is replaced by a larger enumerable class of operators. A class is hyperrobustly Ex-learnable iff it is a subclass of a recursively enumerable family of total functions. So, the notion of hyperrobust learning overcomes a problem of the traditional definitions of robustness which either do not preserve learning by enumeration or still permit topological coding tricks for the learning criterion Ex. Hyperrobust BC-learning as well as the hyperrobust version of Ex-learning by teams are more powerful than hyperrobust Ex-learning. The notion of bounded totally reliable BC-learning is properly between hyperrobust Ex-learning and hyperrobust BC-learning. Furthermore, the bounded totally reliable BC-learnable classes are characterized in terms of infinite branches of certain enumerable families of bounded recursive trees. A class of infinite branches of another family of trees separates hyperrobust BC-learning from totally reliable BC-learning. Furthermore, the notion of hyperrobust learning aided by selected context turns out to be much more restrictive than its counterpart for robust learning.
On C-Degrees, H-Degrees and T-Degrees Merkle, W.; Stephan, F.
Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07),
2007-June
Conference Proceeding
Following a line of research that aims at relating the computation power and the initial segment complexity of a set, the work presented here investigates into the relations between Turing ...reducibility, defined in terms of computation power, and C-reducibility and H-reducibility, defined in terms of the complexity of initial segments. The global structures of all C-degrees and of all H-degrees are rich and allows to embed the lattice of the powerset of the natural numbers under inclusion. In particular, there are C-degrees, as well as H-degrees, that are different from the least degree and are the meet of two other degrees, whereas on the other hand there are pairs of sets that have a meet neither in the C-degrees nor in the H-degrees; these results answer questions in a survey by Nies and Miller. There are r.e. sets that form a minimal pair for C-reducibility and Sigma 2 0 sets that form a minimal pair for H-reducibility, which answers questions by Downey and Hirschfeldt. Furthermore, the following facts on the relation between C-degrees, H-degrees and Turing degrees hold. Every C-degree contains at most one Turing degree and this bound is sharp since there are C-degrees that do contain a Turing degree. For the comprising class of complex sets, neither the C-degree nor the H-degree of such a set can contain a Turing degree, in fact, the Turing degree of any complex set contains infinitely many C-degrees. Similarly the Turing degree of any set that computes the halting problem contains infinitely many H-degrees, while the H-degree of any 2-random set R is never contained in the Turing degree of R. By the latter, H-equivalence of Martin-Lof random sets does not imply their Turing equivalence. The structure of the Cdegrees contained in the Turing degree of a complex sets is rich and allows to embed any countable distributive lattice; a corresponding statement is true for the structure of H-degrees that are contained in the Turing degree of a set that computes the halting problem.
Post's Programme for the Ershov Hierarchy Afshari, Bahareh; Barmpalias, George; Cooper, S. Barry ...
Journal of logic and computation,
12/2007, Volume:
17, Issue:
6
Journal Article
Peer reviewed
Open access
This article extends Post's; programme to finite levels of the Ershov hierarchy of Δ2 sets. Our initial characterization, in the spirit of Post (1994, Bulletin of the American Mathematical Society, ...50, 284–316), of the degrees of the immune and hyperimmune n-enumerable sets leads to a number of results setting other immunity properties in the context of the Turing and wtt-degrees derived from the Ershov hierarchy. For instance, we show that any n-enumerable hyperhyperimmune set must be co-enumerable, for each n ≥ 2. The situation with regard to the wtt-degrees is particularly interesting, as demonstrated by a range of results concerning the wtt-predecessors of hypersimple sets. Finally, we give a number of results directed at characterizing basic classes of n-enumerable degrees in terms of natural information content. For example, a 2-enumerable degree contains a 2-enumerable dense immune set iff it contains a 2-enumerable r-cohesive set iff it bounds a high enumerable set. This result is extended to a characterization of n-enumerable degrees which bound high enumerable degrees. Furthermore, a characterization for n-enumerable degrees bounding only low2 enumerable degrees is given.
In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not א₀-categorical saturated structure with a unique computable isomorphism ...type? Our answer is affirmative and uses a construction based on Kolmogorov complexity. With a variation of this construction, we also provide an example of an א₁-categorical but not א₀-categorical saturated $\Sigma _{1}^{0}$-structure with a unique computable isomorphism type. In addition, using the construction we give an example of an א₁-categorical but not א₁-categorical theory whose only non-computable model is the prime one.
ObjectiveTo examine sex differences in prevalence, volume and distribution of vascular brain lesions on MRI among patients with atrial fibrillation (AF).MethodsIn this cross-sectional analysis, we ...included 1743 patients with AF (27% women) from the multicentre Swiss Atrial Fibrillation study (SWISS-AF) with available baseline brain MRI. We compared presence and total volume of large non-cortical or cortical infarcts (LNCCIs), small non-cortical infarcts, microbleeds (MB) and white matter hyperintensities (WMH, Fazekas score ≥2 for moderate or severe degree) between men and women with multivariable logistic regression. We generated voxel-based probability maps to assess the anatomical distribution of lesions.ResultsWe found no strong evidence for an association of female sex with the prevalence of all ischaemic infarcts (LNCCI and SNCI combined; adjusted OR 0.86, 95% CI 0.67 to 1.09, p=0.22), MB (adjusted OR 0.91, 95% CI 0.68 to 1.21, p=0.52) and moderate or severe WMH (adjusted OR 1.15, 95% CI 0.90 to 1.48, p=0.27). However, total WMH volume was 17% larger among women than men (multivariable adjusted multiplicative effect 1.17, 95% CI 1.01 to 1.35; p=0.04). Lesion probability maps showed a right hemispheric preponderance of ischaemic infarcts in both men and women, while WMH were distributed symmetrically.ConclusionWomen had higher white matter disease burden than men, while volume and prevalence of other lesions did not differ. Our findings highlight the importance of controlling risk factors for cerebral small vessel disease in patients with AF, especially among women.
Enlarging Learnable Classes Jain, Sanjay; Kötzing, Timo; Stephan, Frank
Algorithmic Learning Theory
7568
Book Chapter
Peer reviewed
An early result in inductive inference shows that the class of Ex-learnable sets is not closed under unions. In this paper we are interested in the following question: For what classes of functions ...is the union with an arbitrary Ex-learnable class again Ex-learnable, either effectively (in an index for a learner of an Ex-learnable class) or non-effectively? We show that the effective case and the non-effective case separate, and we give a sufficient criterion for the effective case. Furthermore, we extend our notions to considering unions with classes of single functions, as well as to other learning criteria, such as finite learning and behaviorally correct learning.
Furthermore, we consider the possibility of (effectively) extending learners to learn (infinitely) more functions. It is known that all Ex-learners learning a dense set of functions can be effectively extended to learn infinitely more. It was open whether the learners learning a non-dense set of functions can be similarly extended. We show that this is not possible, but we give an alternative split of all possible learners into two sets such that, for each of the sets, all learners from that set can be effectively extended. We analyze similar concepts also for other learning criteria.
Nonconstructive computations by various types of machines and automata have been considered by e.g., Karp and Lipton 18 and Freivalds 9, 10. They allow to regard more complicated algorithms from the ...viewpoint of more primitive computational devices. The amount of nonconstructivity is a quantitative characterization of the distance between types of computational devices with respect to solving a specific problem.
This paper studies the amount of nonconstructivity needed to learn classes of formal languages from positive data. Different learning types are compared with respect to the amount of nonconstructivity needed to learn indexable classes and recursively enumerable classes, respectively, of formal languages from positive data. Matching upper and lower bounds for the amount of nonconstructivity needed are shown.
PDF
