Please use this identifier to cite or link to this item:
|Title:||Learning how to separate|
|Authors:||Jain, S. |
|Source:||Jain, S., Stephan, F. (2004). Learning how to separate. Theoretical Computer Science 313 (2) : 209-228. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2003.11.006|
|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 data-sequences; conservative learners which abandon only definitely wrong hypotheses; set-driven learners whose hypotheses are independent of the order and the number of repetitions of the data-items 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 set-driven. 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 partial-recursive functions separating the sets in a set-driven way. (2) There is a class for which one can find, in the limit, recursive functions separating the sets in a confident and set-driven way, but one cannot find even partial-recursive functions separating the sets in a conservative way. © 2003 Elsevier B.V. All rights reserved.|
|Source Title:||Theoretical Computer Science|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Mar 7, 2018
checked on Mar 11, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.