Robust Behaviorally Correct Learning

Abstract

Intuitively, a class of functions is robustly learnable if not only the class itself, but also all of the transformations of the class under natural transformations (such as via general recursive operators) are learnable. Fulk showed the existence of a nontrivial class which is robustly learnable under the criterion Ex. However, several of the hierarchies (such as the anomaly hierarchies for Ex and Bc) do not stand robustly. Fulk left open the question about whether Bc and Ex can be robustly separated. In this paper we resolve this question positively. © 1999 Academic Press.