Robust learning—rich and poor

摘要

A class 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 Θ(C), where Θ is any general recursive operator, are learnable in the sense I. It was already shown before, see Fulk (in: 31st Annual IEEE Symposium on Foundation of Computer Science, IEEE Computer Soc. Press, Silver Spring, MD 1990, pp. 405–410), Jain et al. (J. Comput. System Sci. 62 (2001) 178), that for I=Ex (learning in the limit) robust learning is rich in that there are classes being both not contained in any recursively enumerable class of recursive functions and, nevertheless, robustly learnable. For several criteria I, the present paper makes much more precise where we can hope for robustly learnable classes and where we cannot. This is achieved in two ways. First, for I=Ex, it is shown that only consistently learnable classes can be uniformly robustly learnable. Second, some other learning types I are classified as to whether or not they contain rich robustly learnable classes. Moreover, the first results on separating robust learning from uniformly robust learning are derived.