Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.tcs.2007.03.037
Title: On the data consumption benefits of accepting increased uncertainty
Authors: Martin, E.
Sharma, A.
Stephan, F. 
Keywords: Inductive inference
Iterative learning
Memory limitations
Mind change bounds
Issue Date: 6-Sep-2007
Source: Martin, E., Sharma, A., Stephan, F. (2007-09-06). On the data consumption benefits of accepting increased uncertainty. Theoretical Computer Science 382 (3) : 170-182. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2007.03.037
Abstract: In the context of learning paradigms of identification in the limit, we address the question: why is uncertainty sometimes desirable? We use mind change bounds on the output hypotheses as a measure of uncertainty and interpret 'desirable' as reduction in data memorization, also defined in terms of mind change bounds. The resulting model is closely related to iterative learning with bounded mind change complexity, but the dual use of mind change bounds - for hypotheses and for data - is a key distinctive feature of our approach. We show that situations exist where the more mind changes the learner is willing to accept, the less the amount of data it needs to remember in order to converge to the correct hypothesis. We also investigate relationships between our model and learning from good examples, set-driven, monotonic and strong-monotonic learners, as well as class-comprising versus class-preserving learnability. © 2007 Elsevier Ltd. All rights reserved.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/103784
ISSN: 03043975
DOI: 10.1016/j.tcs.2007.03.037
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

31
checked on Feb 25, 2018

Google ScholarTM

Check

Altmetric


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