Learning how to separate
Authors: Sanjay Jain and Frank Stephan
Source: Theoretical Computer Science Vol. 313, Issue 2, 17 February 2004, pp. 209228. Abstract. The main question addressed in the present work is how to find effectively a recursive function separating two sets drawn arbitrarily from a given collection of disjoint sets. In particular, it is investigated when one can find better learners which satisfy additional constraints. Such learners are the following: confident learners which converge on all datasequences; conservative learners which abandon only definitely wrong hypotheses; setdriven learners whose hypotheses are independent of the order and the number of repetitions of the dataitems supplied; learners where either the last or even all hypotheses are programs of total recursive functions. The present work gives a complete picture of the relations between these notions: the only implications are that whenever one has a learner which only outputs programs of total recursive functions as hypotheses, then one can also find learners which are conservative and setdriven. The following two major results need a nontrivial proof: (1) There is a class for which one can find, in the limit, recursive functions separating the sets in a confident and conservative way, but one cannot find even partialrecursive functions separating the sets in a setdriven way. (2) There is a class for which one can find, in the limit, recursive functions separating the sets in a confident and setdriven way, but one cannot find even partialrecursive functions separating the sets in a conservative way.

©Copyright 2004 Elsevier Science B.V.