language: en

Team Learning of Formal Languages

Sanjay Jain
Dept. of Info. Systems & Computer Science National University of Singapore
Singapore 0511, Republic of Singapore
sanjay@iscs.nus.sg
Arun Sharma
School of Computer Science and Engineering The University of New South Wales
Sydney, NSW 2052, Australia
arun@cse.unsw.edu.au

Abstract A team of learning machines is a multiset of learning machines. A team is said to successfully learn a concept just in case each member of some nonempty subset, of predetermined size, of the team learns the concept. Team learning of computer programs for computable functions from their graphs has been studied extensively. However, team learning of languages turns out to be a more suitable theoretical model for studying computational limits on multi-agent machine learning. The main reason for this is that language learning can model both learning from positive data and learning from positive and negative data, whereas function learning models only learning from positive and negative data. Some theoretical results about learnability of formal languages by teams of algorithmic machines are surveyed. Some new results about restricted classes of languages are presented. These results are mainly about two issues: redundancy and aggregation. The issue of redundancy deals with the impact of increasing the size of a team and increasing the number of machines required to be successful. The issue of aggregation deals with conditions under which a team may be replaced by a single machine without any loss in learning ability. Scenarios which can be modeled by team learning are also presented.

1 INTRODUCTION