On Aggregating Teams of Learning Machines

Abstract

The present paper studies the problem of when a team of learning machines can be aggregated into a single learning machine without any loss in learning power. The main results concern aggregation ratios for vacillatory identification of languages from texts. For a positive integer n , a machine is said to TxtFex _n-identify a language L just in case the machine converges to upto n grammars for L on any text for L . For such identification criteria, the aggregation ratio is derived for the n =2 case. It is shown that the collection of languages that can be TxtFex_2 identified by teams with success ratio greater than 5/6 are the same as those collections of languages that can be TxtFex _2-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 TxtFex_2-identified by a team employing 6 machines, at least 5 of which are required to be successful, but cannnot be TxtFex_2-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.