Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/99353
Title: On aggregating teams of learning machines
Authors: Jain, S. 
Sharma, A.
Issue Date: 9-Jan-1995
Source: Jain, S.,Sharma, A. (1995-01-09). On aggregating teams of learning machines. Theoretical Computer Science 137 (1) : 85-108. ScholarBank@NUS Repository.
Abstract: A team of learning machines is a multiset of learning machines. A team is said to be successful just in case each member of some nonempty subset of the team is successful. The ratio of the number of machines required to be successful to the size of the team is referred to as the success ratio of the team. The present paper investigates for which success ratios can a team be replaced by a single machine without any loss in learning power. The answer depends on the concepts being learned and the criteria of success employed. For a given criterion of success, the minimum cut-off ratio where a team can be replaced by a single machine is referred to as the aggregation ratio of the criterion. The main results in the present paper concern aggregation ratios for vacillatory identification of languages from texts. According to this criterion of success, a learning machine is successful just in case it eventually vacillates between a finite set of grammars instead of converging to a single grammar. For a positive integer n, a machine is said to TxtFexn-identify a language L just in case the machine converges to up to n grammars for L on any text for L. For such identification criteria, the aggregation ratio is derived for the case n = 2. It is shown that the collection of languages that can be TxtFex2-identified by teams with success ratio greater than 5 6 are the same as those collections of languages that can be TxtFex2-identified by a single machine. It is also established that 5 6 is indeed the cut-off point by showing that there are collections of languages that can be TxtFex2-identified by a team employing six machines, at least five of which are required to be successful, but cannot be TxtFex2-identified by any single machine. Additionally, aggregation ratios are also derived for finite identification of languages from positive data and for numerous criteria involving language learning from both positive and negative data. © 1995.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/99353
ISSN: 03043975
Appears in Collections:Staff Publications

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

Page view(s)

15
checked on Feb 15, 2018

Google ScholarTM

Check


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