Learning by the Process of Elimination

The process of elimination is a fundamental component of many learning processes. In order to understand the nature of elimination, herein we study an extreme model of learning from examples where learning is considered to be the elimination of all, save one, hypothesis from a given search space. Our study revolves around types of search spaces. We show that having multiple, semantically equivalent hypotheses in the search space will sometimes help the learning process and at other times hinder it. Furthermore, we find properties of search spaces that determine whether or not these multiple versions will help or hurt the learning process. The model of learning by elimination is compared to standard models of learning from examples. In some cases, the models coincide, and in others they differ. We especially show that our model is universal in that any learning problem solvable in a standard model can also be solved by elimination learning in a wide class of natural search..