Please use this identifier to cite or link to this item:
https://doi.org/10.1016/j.tcs.2003.11.006
Title: | Learning how to separate | Authors: | Jain, S. Stephan, F. |
Issue Date: | 2004 | Citation: | 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 | URI: | http://scholarbank.nus.edu.sg/handle/10635/41121 | ISSN: | 03043975 | DOI: | 10.1016/j.tcs.2003.11.006 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.