Learning by Erasing

Authors: Steffen Lange, Rolf Wiehagen and Thomas Zeugmann

Source: Algorithmic Learning Theory, 7th International Workshop, ALT '96, Sydney, Australia, October 1996, Proceedings, (S. Arikawa and A.K. Sharma, Eds.), Lecture Notes in Artificial Intelligence 1160, pp. 228 - 241, Springer-Verlag 1996.

Abstract. Learning by erasing means the process of eliminating potential hypotheses from further consideration thereby converging to the least hypothesis never eliminated and this one must be a solution to the actual learning problem.

The present paper deals with learnability by erasing of indexed families of languages from both positive data as well as positive and negative data. This refers to the following scenario. A family of target languages and a hypothesis space for it are specified. The learner is fed eventually all positive examples (all labeled examples) of an unknown target language L chosen from . The target language L is learned by erasing if the learner erases some set of possible hypotheses and the least hypothesis never erased correctly describes L.

The capabilities of learning by erasing are investigated in dependence on the requirement of what sets of hypotheses have to be or may be erased, and in dependence of the choice of the hypothesis space.

Class preserving learning by erasing ( has to be learned w.r.t. some suitably chosen enumeration of all and only the languages from ), class comprising learning by erasing ( has to be learned w.r.t. some hypothesis space containing at least all the languages from ), and absolute learning by erasing ( has to be learned w.r.t. all class preserving hypothesis spaces for ) are distinguished.

For all these models of learning by erasing necessary and sufficient conditions for learnability are presented. A complete picture of all separations and coincidences of the learning by erasing models is derived. Learning by erasing is compared with standard models of language learning such as learning in the limit, finite learning and conservative learning. The exact location of these types within the hierarchy of the learning by erasing models is established.