Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/111276
Title: Probability is more powerful than team for language identification from positive data
Authors: Jain, Sanjay 
Sharma, Arun
Issue Date: 1993
Citation: Jain, Sanjay,Sharma, Arun (1993). Probability is more powerful than team for language identification from positive data : 192-198. ScholarBank@NUS Repository.
Abstract: A team of learning machines is essentially a multiset of learning machines. A team is said to successfully identify a concept just in case each member of some nonempty subset of the team identifies the concept. The ratio between the minimum number of team members required to be successful to the cardinality of the team is referred to as the success ratio of the team identification criteria. Team identification of programs for computable functions from their graphs has been investigated by Smith. Pitt showed that this notion is essentially equivalent to function identification by a single probabilistic machine. As a consequence of this equivalence, it was shown by Pitt and Smith that introducing redundancy in a team does not yield any extra function learning power. The present paper studies the more difficult subject of probabilistic and team identification of grammars for languages from positive data. Earlier results had established that for team success ratio 1/2, redundancy helps in certain cases. Results in the present paper complete the picture for team success ratio 1/2 and show that probabilistic identification with probability of success at least 1/2 is strictly more powerful than team identification with success ratio 1/2. With a view to cope with the complexity of diagonalization arguments, a general tool is presented that yields new diagonalization results from simple arithmetic manipulation of the parameters of known results. Employing this tool on results about success ratio 1/2, it is shown that for k>2, probabilistic identification with probability of success at least 1/k is strictly more powerful than team identification with success ratio 1/k. Additionally, several new general results are obtained using this tool. It is also observed that for identification of languages from both positive and negative data, probabilistic learning and team learning are equivalent.
URI: http://scholarbank.nus.edu.sg/handle/10635/111276
ISBN: 0897916115
Appears in Collections:Staff Publications

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

Page view(s)

54
checked on Oct 14, 2021

Google ScholarTM

Check

Altmetric


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