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
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
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.

SCOPUSTM   
Citations

1
checked on Dec 6, 2017

Page view(s)

37
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.