Please use this identifier to cite or link to this item:
Title: Robust learning is rich
Authors: Jain, S. 
Smith, C.
Wiehagen, R.
Issue Date: 2001
Citation: Jain, S., Smith, C., Wiehagen, R. (2001). Robust learning is rich. Journal of Computer and System Sciences 62 (1) : 178-212. ScholarBank@NUS Repository.
Abstract: Intuitively, a class of objects is robustly learnable if not only this class itself is learnable but all of its computable transformations remain learnable as well. In that sense, being learnable robustly seems to be a desirable property in all fields of learning. We will study this phenomenon within the paradigm of inductive inference. Here a class of recursive functions is called robustly learnable under the criterion I iff all of its images under general recursive operators are learnable under the criterion I. M. Fulk (1990, in "31st Annual IEEE Symposium on Foundations of Computer Science," pp. 405-410, IEEE Comput. Soc. Press, Los Alamitos, CA) 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. Hence, up to now it was not clear if robust learning is really rich. The main intention of this paper is to give strong evidence that robust learning is rich. Our main result proved by a priority construction is that the mind change hierarchy for Ex stands robustly. Moreover, the hierarchies of team learning for both Ex and Bc stand robustly as well. In several contexts, we observe the surprising fact that a more complex topological structure of the classes to be learned leads to positive robustness results, whereas an easy topological structure yields negative results. We also show the counterintuitive fact that even some self-referential classes can be learned robustly. Some of our results point out the difficulty of robust learning when only a bounded number of mind changes is allowed. Further results concerning uniformly robust learning are derived. © 2001 Academic Press.
Source Title: Journal of Computer and System Sciences
ISSN: 00220000
DOI: 10.1006/jcss.2000.1700
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.