Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.tcs.2007.07.025
Title: Learning multiple languages in groups
Authors: Jain, S. 
Kinber, E.
Keywords: Classification
Computational learning theory
Learning in the limit
Learning multiple languages
Issue Date: 2007
Citation: Jain, S., Kinber, E. (2007). Learning multiple languages in groups. Theoretical Computer Science 387 (1) : 67-76. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2007.07.025
Abstract: We consider a variant of Gold's learning paradigm where a learner receives as input n different languages (in the form of one text where all input languages are interleaved). Our goal is to explore the situation when a more "coarse" classification of input languages is possible, whereas more refined classification is not. More specifically, we answer the following question: under which conditions, a learner, being fed n different languages, can produce m grammars covering all input languages, but cannot produce k grammars covering input languages for any k > m. We also consider a variant of this task, where each of the output grammars may not cover more than r input languages. Our main results indicate that the major factor affecting classification capabilities is the difference n - m between the number n of input languages and the number m of output grammars. We also explore the relationship between classification capabilities for smaller and larger groups of input languages. For the variant of our model with the upper bound on the number of languages allowed to be represented by one output grammar, for classes consisting of disjoint languages, we found complete picture of relationship between classification capabilities for different parameters n (the number of input languages), m (number of output grammars), and r (bound on the number of languages represented by each output grammar). This picture includes a combinatorial characterization of classification capabilities for the parameters n, m, r of certain types. © 2007 Elsevier Ltd. All rights reserved.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/39086
ISSN: 03043975
DOI: 10.1016/j.tcs.2007.07.025
Appears in Collections:Staff Publications

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

Page view(s)

53
checked on Jul 13, 2018

Google ScholarTM

Check

Altmetric


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