Probability is more powerful than team for language identification from positive data

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.