Learning Attribute-Efficiently with Corrupt Oracles

Authors: Rotem Bennet and Nader H. Bshouty

Source: Algorithmic Learning Theory, 16th International Conference, ALT 2005, Singapore, October 2005, Proceedings, (Sanjay Jain, Hans Ulrich Simon and Etsuji Tomita, Eds.), Lecture Notes in Artificial Intelligence 3734, pp. 183 - 197, Springer 2005.

Abstract. We study learning in a modified EXACT model, where the oracles are corrupt and only few of the presented attributes are relevant. Both modifications were already studied in the literature, and efficient solutions were found to most of their variants. Nonetheless, their reasonable combination is yet to be studied, and combining the existing solutions either fails or works with complexity that can be significantly improved. In this paper we prove equivalence of EXACT learning attribute-efficiently with and without corrupt oracles. For each of the possible scenarios we describe a generic scheme that enables learning in these cases using modifications of the standard learning algorithms. We also generalize and improve previous non attribute-efficient algorithms for learning with corrupt oracles.

©Copyright 2005, Springer