On aggregating teams of learning machines

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.