ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Sun, 26 Jan 2020 08:52:01 GMT2020-01-26T08:52:01Z501551- Counting extensional differences in BC-learninghttps://scholarbank.nus.edu.sg/handle/10635/39426Title: Counting extensional differences in BC-learning
Authors: Jain, S.; Stephan, F.; Terwijn, S.A.
Abstract: Let BC be the model of behaviourally correct function learning as introduced by Bārzdins [Theory of Algorithms and Programs, vol. 1, Latvian State University, 1974, p. 82-88] and Case and Smith [Theoret. Comput. Sci. 25 (1983) 193-220]. We introduce a mind change hierarchy for BC, counting the number of extensional differences in the hypotheses of a learner. We compare the resulting models BC n to models from the literature and discuss confidence, team learning, and finitely defective hypotheses. Among other things, we prove that there is a trade-off between the number of semantic mind changes and the number of anomalies in the hypotheses. We also discuss consequences for language learning. In particular we show that, in contrast to the case of function learning, the family of classes that are confidently BC-learnable from text is not closed under finite unions. © 2003 Elsevier Inc. All rights reserved.
Thu, 01 Jan 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394262004-01-01T00:00:00Z
- Language learning from texts: Degrees of intrinsic complexity and their characterizationshttps://scholarbank.nus.edu.sg/handle/10635/39085Title: Language learning from texts: Degrees of intrinsic complexity and their characterizations
Authors: Jain, S.; Kinber, E.; Wiehagen, R.
Abstract: This paper deals with two problems: (1) what makes languages learnable in the limit by natural strategies of varying hardness, and (2) what makes classes of languages the hardest ones to lear. To quantify hardness of learning, we use intrinsic complexity based on reductions between learning problems. Two types of reductions are considered: weak reductions mapping texts (representations of languages) to texts and strong reductions mapping languages to languages. For both types of reductions, characterizations of complete (hardest) classes in terms of their algorithmic and topological potentials have been obtained. To characterize the strong complete degree, we discovered a new and natural complete class capable of "coding" any learning problem using density of the set of rational numbers. We have also discovered and characterized rich hierarchies of degrees of complexity based on "core" natural learning problems. The classes in these hierarchies contain "multidimensional" languages, where the information learned from one dimension aids in learning other dimensions. In one formalization of this idea, the grammars learned from the dimensions 1, 2,...,k specify the "subspace" for the dimension k + 1, while the learning strategy for every dimension is predefined. In our other formalization, a "pattern" learned from the dimension k specifies the learning strategy for the dimension k + 1. A number of open problems are discussed.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/390852001-01-01T00:00:00Z
- Input-dependence in function-learninghttps://scholarbank.nus.edu.sg/handle/10635/43093Title: Input-dependence in function-learning
Authors: Jain, S.; Martin, E.; Stephan, F.
Abstract: In the standard model of inductive inference, a learner gets as input the graph of a function, and has to discover (in the limit) a program for the function. In this paper, we consider besides the graph also other modes of input such as the complement of the graph, the undergraph and the overgraph of the function. The relationships between these models are studied and a complete picture is obtained. Furthermore, these notions are also explored for learning with oracles, learning in teams and learning in the presence of additional information. © Springer Science+Business Media, LLC 2009.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/430932009-01-01T00:00:00Z
- Control structures in hypothesis spaces: The influence on learninghttps://scholarbank.nus.edu.sg/handle/10635/38986Title: Control structures in hypothesis spaces: The influence on learning
Authors: Case, J.; Jain, S.; Suraj, M.
Abstract: In any learnability setting, hypotheses are conjectured from some hypothesis space. Studied herein are the influence on learnability of the presence or absence of certain control structures in the hypothesis space. First presented are control structure characterizations of some rather specific but illustrative learnability results. The presence of these control structures is thereby shown essential to maintain full learning power. Then presented are the main theorems. Each of these non-trivially characterizes the invariance of a learning class over hypothesis space V and the presence of a particular projection control structure, called proj, in V as: V has suitable instances of all denotational control structures. In a sense, then, proj epitomizes the control structures whose presence need not help and whose absence need not hinder learning power. © 2002 Elsevier Science B.V. All rights reserved.
Tue, 01 Jan 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/389862002-01-01T00:00:00Z
- Mitotic classes in inductive inferencehttps://scholarbank.nus.edu.sg/handle/10635/43066Title: Mitotic classes in inductive inference
Authors: Jain, S.; Stephan, F.
Abstract: For the natural notion of splitting classes into two disjoint subclasses via a recursive classifier working on texts, the question of how these splittings can look in the case of learnable classes is addressed. Here the strength of the classes is compared using the strong and weak reducibility from intrinsic complexity. It is shown that, for explanatorily learnable classes, the complete classes are also mitotic with respect to weak and strong reducibility, respectively. But there is a weakly complete class that cannot be split into two classes which are of the same complexity with respect to strong reducibility. It is shown that, for complete classes for behaviorally correct learning, one-half of each splitting is complete for this learning notion as well. Furthermore, it is shown that explanatorily learnable and recursively enumerable classes always have a splitting into two incomparable classes; this gives an inductive inference counterpart of the Sacks splitting theorem from recursion theory. © 2008 Society for Industrial and Applied Mathematics.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/430662008-01-01T00:00:00Z
- The complexity of verbal languages over groupshttps://scholarbank.nus.edu.sg/handle/10635/41115Title: The complexity of verbal languages over groups
Authors: Jain, S.; Miasnikov, A.; Stephan, F.
Abstract: This paper investigates the complexity of verbal languages and pattern languages of Thurston automatic groups in terms of the Chomsky hierarchy. Here the language generated by a pattern is taken as the set of representatives of all strings obtained when chosing values for the various variables. For noncommutative free groups, it is shown that the complexity of the verbal and pattern languages (in terms of level on the Chomsky hierarchy) does not depend on the Thurston automatic representation and that verbal languages cannot be context-free (unless they are either the empty word or the full group). They can however be indexed languages. Furthermore, it is shown that in the general case, it might depend on the exactly chosen Thurston automatic representation which level a verbal language takes in the Chomsky hierarchy. There are examples of groups where, in an appropriate representation, all pattern languages are regular or context-free, respectively. © 2012 IEEE.
Sun, 01 Jan 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/411152012-01-01T00:00:00Z
- Some natural conditions on incremental learninghttps://scholarbank.nus.edu.sg/handle/10635/39260Title: Some natural conditions on incremental learning
Authors: Jain, S.; Lange, S.; Zilles, S.
Abstract: The present study aims at insights into the nature of incremental learning in the context of Gold's model of identification in the limit. With a focus on natural requirements such as consistency and conservativeness, incremental learning is analysed both for learning from positive examples and for learning from positive and negative examples. The results obtained illustrate in which way different consistency and conservativeness demands can affect the capabilities of incremental learners. These results may serve as a first step towards characterising the structure of typical classes learnable incrementally and thus towards elaborating uniform incremental learning methods. © 2007 Elsevier Inc. All rights reserved.
Mon, 01 Jan 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/392602007-01-01T00:00:00Z
- On some open problems in monotonic and conservative learninghttps://scholarbank.nus.edu.sg/handle/10635/39418Title: On some open problems in monotonic and conservative learning
Authors: Jain, S.
Abstract: In this paper we solve some open problems in monotonic and conservative learning. © 2009 Elsevier B.V. All rights reserved.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394182009-01-01T00:00:00Z
- On learning to coordinate: Random bits help, insightful normal forms, and competency isomorphismshttps://scholarbank.nus.edu.sg/handle/10635/41122Title: On learning to coordinate: Random bits help, insightful normal forms, and competency isomorphisms
Authors: Case, J.; Jain, S.; Montagna, F.; Simi, G.; Sorbi, A.
Abstract: A mere bounded number of random bits judiciously employed by a probabilistically correct algorithmic coordinator is shown to increase the power of learning to coordinate compared to deterministic algorithmic coordinators. Furthermore, these probabilistic algorithmic coordinators are provably not characterized in power by teams of deterministic ones. An insightful, enumeration technique based, normal form characterization of the classes that are learnable by total computable coordinators is given. These normal forms are for insight only since it is shown that the complexity of the normal form of a total computable coordinator can be infeasible compared to the original coordinator. Montagna and Osherson showed that the competence class of a total coordinator cannot be strictly improved by another total coordinator. It is shown in the present paper that the competencies of any two total coordinators are the same modulo isomorphism. Furthermore, a completely effective, index set version of this competency isomorphism result is given, where all the coordinators are total computable. We also investigate the competence classes of total coordinators from the points of view of topology and descriptive set theory. © 2004 Elsevier Inc. All rights reserved.
Sat, 01 Jan 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/411222005-01-01T00:00:00Z
- On a generalized notion of mistake boundshttps://scholarbank.nus.edu.sg/handle/10635/39138Title: On a generalized notion of mistake bounds
Authors: Jain, S.; Sharma, A.
Abstract: This paper proposes the use of constructive ordinals as mistake bounds in the on-line learning model. This approach elegantly generalizes the applicability of the on-line mistake bound model to learnabilily analysis of very expressive concept classes like pattern languages, unions of pattern languages, elementary formal systems, and minimal models of logic programs. The main result in the paper shows that the topological property of effective finite bounded thickness is a sufficient condition for on-line learnability with a certain ordinal mistake bound. An interesting characterization of the on-line learning model is shown in terms of the identification in the limit framework. It is established that the classes of languages learnable in the on-line model with a mistake bound of α are exactly the same as the classes of languages learnable in the limit from both positive and negative data by a Popperian, consistent learner with a mind change bound of α. This result nicely builds a bridge between the two models. © 2001 Academic Press.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/391382001-01-01T00:00:00Z
- Learning without codinghttps://scholarbank.nus.edu.sg/handle/10635/41125Title: Learning without coding
Authors: Jain, S.; Moelius III, S.E.; Zilles, S.
Abstract: Iterative learning is a model of language learning from positive data, due to Wiehagen. When compared to a learner in Gold's original model of language learning from positive data, an iterative learner can be thought of as memory-limited. However, an iterative learner can memorize some input elements by coding them into the syntax of its hypotheses. A main concern of this paper is: to what extent are such coding tricks necessary? One means of preventing some such coding tricks is to require that the hypothesis space used be free of redundancy, i.e., that it be 1-1. In this context, we make the following contributions. By extending a result of Lange and Zeugmann, we show that many interesting and non-trivial classes of languages can be iteratively identified using a Friedberg numbering as the hypothesis space. (Recall that a Friedberg numbering is a 1-1 effective numbering of all computably enumerable sets.) An example of such a class is the class of pattern languages over an arbitrary alphabet. On the other hand, we show that there exists an iteratively identifiable class of languages that cannot be iteratively identified using any 1-1 effective numbering as the hypothesis space. We also consider an iterative-like learning model in which the computational component of the learner is modeled as an enumeration operator, as opposed to a partial computable function. In this new model, there are no hypotheses, and, thus, no syntax in which the learner can encode what elements it has or has not yet seen. We show that there exists a class of languages that can be identified under this new model, but that cannot be iteratively identified. On the other hand, we show that there exists a class of languages that cannot be identified under this new model, but that can be iteratively identified using a Friedberg numbering as the hypothesis space. © 2012 Elsevier B.V. All rights reserved.
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/411252013-01-01T00:00:00Z
- LEARNING correction grammarshttps://scholarbank.nus.edu.sg/handle/10635/39417Title: LEARNING correction grammars
Authors: Carlucci, L.; Case, J.; Jain, S.
Abstract: We investigate a new paradigm in the context of learning in the limit, namely, learning correction grammars for classes of computably enumerable (c.e.) languages. Knowing a language may feature a representation of it in terms of two grammars. The second grammar is used to make corrections to the first grammar. Such a pair of grammars can be seen as a single description of (or grammar for) the language. We call such grammars correction grammars. Correction grammars capture the observable fact that people do correct their linguistic utterances during their usual linguistic activities. We show that learning correction grammars for classes of c.e. languages in the TxtEx-model (i.e., converging to a single correct correction grammar in the limit) is sometimes more powerful than learning ordinary grammars even in the 7"j:flc-model (where the learner is allowed to converge to infinitely many syntactically distinct but correct conjectures in the limit). For each n 0, there is a similar learning advantage, again in learning correction grammars for classes of c.e. languages, but where we compare learning correction grammars that make n + 1 corrections to those that make n corrections.The concept of a correction grammar can be extended into the constructive transfinite, using the idea of counting-down from notations for transfinite constructive ordinals. This transfinite extension can also be conceptualized as being about learning Ershov-descriptions for c.e. languages. For u a notation in Kleene's general system (O, o) of ordinal notations for constructive ordinals, we introduce the concept of an M-correction grammar, where u is used to bound the number of corrections that the grammar is allowed to make. We prove a general hierarchy result: if u and v are notations for constructive ordinals such that « o v, then there are classes of c.e. languages that can be TxtEx-eamed by conjecturing v-correction grammars but not by conjecturing H-correction grammars.Surprisingly, we show that-bove "o-many" corrections-t is not possible to strengthen the hierarchy: TxtEx-leaming u-correction grammars of classes of c.e. languages, where « is a notation in 0 for any ordinal, can be simulated by T ZJc-learning m-correction grammars, where w is any notation for the smallest infinite ordinal a. ©Association.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394172009-01-01T00:00:00Z
- Synthesizing noise-tolerant language learnershttps://scholarbank.nus.edu.sg/handle/10635/41010Title: Synthesizing noise-tolerant language learners
Authors: Case, J.; Jain, S.; Sharma, A.
Abstract: An index for an r.e. class of languages (by definition) generates a sequence of grammars defining the class. An index for an indexed family of languages (by definition) generates a sequence of decision procedures defining the family. F. Stephan's model of noisy data is employed, in which, roughly, correct data crops up infinitely often, and incorrect data only finitely often. Studied, then, is the synthesis from indices for r.e. classes and for indexed families of languages of various kinds of noise-tolerant language-learners for the corresponding classes or families indexed. Many positive results, as well as some negative results, are presented regarding the existence of such synthesizers. The proofs of most of the positive results yield, as pleasant corollaries, strict subset-principle or tell-tale style characterizations for the noise-tolerant learnability of the corresponding classes or families indexed. © 2001 Elsevier Science B.V. All rights reserved.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/410102001-01-01T00:00:00Z
- Learning how to separatehttps://scholarbank.nus.edu.sg/handle/10635/41121Title: Learning how to separate
Authors: Jain, S.; Stephan, F.
Abstract: The main question addressed in the present work is how to find effectively a recursive function separating two sets drawn arbitrarily from a given collection of disjoint sets. In particular, it is investigated when one can find better learners which satisfy additional constraints. Such learners are the following: confident learners which converge on all data-sequences; conservative learners which abandon only definitely wrong hypotheses; set-driven learners whose hypotheses are independent of the order and the number of repetitions of the data-items supplied; learners where either the last or even all hypotheses are programs of total recursive functions. The present work gives a complete picture of the relations between these notions: the only implications are that whenever one has a learner which only outputs programs of total recursive functions as hypotheses, then one can also find learners which are conservative and set-driven. The following two major results need a nontrivial proof: (1) There is a class for which one can find, in the limit, recursive functions separating the sets in a confident and conservative way, but one cannot find even partial-recursive functions separating the sets in a set-driven way. (2) There is a class for which one can find, in the limit, recursive functions separating the sets in a confident and set-driven way, but one cannot find even partial-recursive functions separating the sets in a conservative way. © 2003 Elsevier B.V. All rights reserved.
Thu, 01 Jan 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/411212004-01-01T00:00:00Z
- On the intrinsic complexity of learning recursive functionshttps://scholarbank.nus.edu.sg/handle/10635/39188Title: On the intrinsic complexity of learning recursive functions
Authors: Jain, S.; Kinber, E.; Papazian, C.; Smith, C.; Wiehagen, R.
Abstract: The intrinsic complexity of learning compares the difficulty of learning classes of objects by using some reducibility notion. For several types of learning recursive functions, both natural complete classes are exhibited and necessary and sufficient conditions for completeness are derived. Informally, a class is complete if both its topological structure is highly complex while its algorithmic structure is easy. Some self-describing classes turn out to be complete. Furthermore, the structure of the intrinsic complexity is shown to be much richer than the structure of the mind change complexity, though in general, intrinsic complexity and mind change complexity can behave "orthogonally".
Wed, 01 Jan 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/391882003-01-01T00:00:00Z
- Learning and extending sublanguageshttps://scholarbank.nus.edu.sg/handle/10635/39434Title: Learning and extending sublanguages
Authors: Jain, S.; Kinber, E.
Abstract: A number of natural models for learning in the limit are introduced to deal with the situation when a learner is required to provide a grammar covering the input even if only a part of the target language is available. Examples of language families are exhibited that are learnable in one model and not learnable in another one. Some characterizations for learnability of algorithmically enumerable families of languages for the models in question are obtained. Since learnability of any part of the target language does not imply monotonicity of the learning process, we consider our models also under the additional monotonicity constraint. © 2008 Elsevier Ltd. All rights reserved.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394342008-01-01T00:00:00Z
- Prescribed learning of r.e. classeshttps://scholarbank.nus.edu.sg/handle/10635/43056Title: Prescribed learning of r.e. classes
Authors: Jain, S.; Stephan, F.; Ye, N.
Abstract: This work extends studies of Angluin, Lange and Zeugmann on the dependence of learning on the hypothesis space chosen for the language class in the case of learning uniformly recursive language classes. The concepts of class-comprising (where the learner can choose a uniformly recursively enumerable superclass as the hypothesis space) and class-preserving (where the learner has to choose a uniformly recursively enumerable hypothesis space of the same class) are formulated in their study. In subsequent investigations, uniformly recursively enumerable hypothesis spaces have been considered. In the present work, we extend the above works by considering the question of whether learners can be effectively synthesized from a given hypothesis space in the context of learning uniformly recursively enumerable language classes. In our study, we introduce the concepts of prescribed learning (where there must be a learner for every uniformly recursively enumerable hypothesis space of the same class) and uniform learning (like prescribed, but the learner has to be synthesized effectively from an index of the hypothesis space). It is shown that while for explanatory learning, these four types of learnability coincide, some or all are different for other learning criteria. For example, for conservative learning, all four types are different. Several results are obtained for vacillatory and behaviourally correct learning; three of the four types can be separated, however the relation between prescribed and uniform learning remains open. It is also shown that every (not necessarily uniformly recursively enumerable) behaviourally correct learnable class has a prudent learner, that is, a learner using a hypothesis space such that the learner learns every set in the hypothesis space. Moreover the prudent learner can be effectively built from any learner for the class. © 2009 Elsevier B.V. All rights reserved.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/430562009-01-01T00:00:00Z
- Hypothesis spaces for learninghttps://scholarbank.nus.edu.sg/handle/10635/41059Title: Hypothesis spaces for learning
Authors: Jain, S.
Abstract: In this paper we survey some results in inductive inference showing how learnability of a class of languages may depend on hypothesis space chosen. We also discuss results which consider how learnability is effected if one requires learning with respect to every suitable hypothesis space. Additionally, optimal hypothesis spaces, using which every learnable class is learnable, is considered. © Springer-Verlag Berlin Heidelberg 2009.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/410592009-01-01T00:00:00Z
- Synthesizing learners tolerating computable noisy datahttps://scholarbank.nus.edu.sg/handle/10635/39279Title: Synthesizing learners tolerating computable noisy data
Authors: Case, J.; Jain, S.
Abstract: An index for an r.e. class of languages (by definition) generates a sequence of grammars defining the class. An index for an indexed family of recursive languages (by definition) generates a sequence of decision procedures defining the family. F. Stephan's model of noisy data is employed, in which, roughly, correct data crops up infinitely often and incorrect data only finitely often. In a computable universe, all data sequences, even noisy ones, are computable. New to the present paper is the restriction that noisy data sequences be, nonetheless, computable. This restriction is interesting since we may live in a computable universe. Studied, then, is the synthesis from indices for r.e. classes and for indexed families of recursite languages of various kinds of noise-tolerant language-learners for the corresponding classes or families indexed, where the noisy input data sequences are restricted to being computable. Many positive results, as well as some negative results, are presented regarding the existence of such synthesizers. The main positive result is: grammars for each indexed family can be learned behaviorally correctly from computable, noisy, positive data. The proof of another positive synthesis result yields, as a pleasant corollary, a strict subset-principle or telltale style characterization, for the computable noise-tolerant behaviorally correct learnability of grammars from positive and negative data, of the corresponding families indexed.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/392792001-01-01T00:00:00Z
- Mind change complexity of learning logic programshttps://scholarbank.nus.edu.sg/handle/10635/39937Title: Mind change complexity of learning logic programs
Authors: Jain, S.; Sharma, A.
Abstract: The present paper motivates the study of mind change complexity for learning minimal models of length-bounded logic programs. It establishes ordinal mind change complexity bounds for learnability of these classes both from positive facts and from positive and negative facts. Building on Angluin's notion of finite thickness and Wright's work on finite elasticity, Shinohara defined the property of bounded finite thickness to give a sufficient condition for learnability of indexed families of computable languages from positive data. This paper shows that an effective version of Shinohara's notion of bounded finite thickness gives sufficient conditions for learnability with ordinal mind change bound, both in the context of learnability from positive data and for learnability from complete (both positive and negative) data. Let ω be a notation for the first limit ordinal. Then, it is shown that if a language defining framework yields a uniformly decidable family of languages and has effective bounded finite thickness, then for each natural number m > 0, the class of languages defined by formal systems of length ≤ m: • is identifiable in the limit from positive data with a mind change bound of ω m; • is identifiable in the limit from both positive and negative data with an ordinal mind change bound of ω × m. The above sufficient conditions are employed to give an ordinal mind change bound for learnability of minimal models of various classes of length-bounded Prolog programs, including Shapiro's linear programs, Arimura and Shinohara's depth-bounded linearly covering programs, and Krishna Rao's depth-bounded linearly moded programs. It is also noted that the bound for learning from positive data is tight for the example classes considered. © 2002 Elsevier Science B.V. All rights reserved.
Tue, 01 Jan 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/399372002-01-01T00:00:00Z
- Classes with easily learnable subclasseshttps://scholarbank.nus.edu.sg/handle/10635/39425Title: Classes with easily learnable subclasses
Authors: Jain, S.; Menzel, W.; Stephan, F.
Abstract: In this paper we study the question of whether identifiable classes have subclasses which are identifiable under a more restrictive criterion. The chosen framework is inductive inference, in particular the criterion of explanatory learning (Ex) of recursive functions as introduced by Gold [Inform. Comput. 10 (1967) 447]. Among the more restrictive criteria is finite learning where the learner outputs, on every function to be learned, exactly one hypothesis (which has to be correct). The topic of the present paper are the natural variants (a) and (b) below of the classical question whether a given learning criterion like finite learning is more restrictive than Ex-learning, (a) Does every infinite Ex-identifiable class have an infinite finitely identifiable subclass? (b) If an infinite Ex-identifiable class S has an infinite finitely identifiable subclass, does it necessarily follow that some appropriate learner Ex-identifies S as well as finitely identifies an infinite subclass of S? These questions are also treated in the context of ordinal mind change bounds. © 2004 Elsevier Inc. All rights reserved.
Thu, 01 Jan 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394252004-01-01T00:00:00Z
- Learning all subfunctions of a functionhttps://scholarbank.nus.edu.sg/handle/10635/39116Title: Learning all subfunctions of a function
Authors: Jain, S.; Kinber, E.; Wiehagen, R.
Abstract: Sublearning, a model for learning of subconcepts of a concept, is presented. Sublearning a class of total recursive functions informally means to learn all functions from that class together with all of their subfunctions. While in language learning it is known to be impossible to learn any infinite language together with all of its sublanguages, the situation changes for sublearning of functions. Several types of sublearning are defined and compared to each other as well as to other learning types. For example, in some cases, sublearning coincides with robust learning. Furthermore, whereas in usual function learning there are classes that cannot be learned consistently, all sublearnable classes of some natural types can be learned consistently. Moreover, the power of sublearning is characterized in several terms, thereby establishing a close connection to measurable classes and variants of this notion. As a consequence, there are rich classes which do not need any self-referential coding for sublearning them. © 2004 Elsevier Inc. All rights reserved.
Thu, 01 Jan 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/391162004-01-01T00:00:00Z
- Identifying clusters from positive datahttps://scholarbank.nus.edu.sg/handle/10635/43097Title: Identifying clusters from positive data
Authors: Case, J.; Jain, S.; Martin, E.; Sharma, A.; Stephan, F.
Abstract: The present work studies clustering from an abstract point of view and investigates its properties in the framework of inductive inference. Any class S considered is given by a hypothesis space, i.e., numbering, A 0, A 1,... of nonempty recursively enumerable (r.e.) subsets of ℕ or ℚ k. A clustering task is a finite and nonempty set of r.e. indices of pairwise disjoint such sets. The class S is said to be clusterable if there is an algorithm which, for every clustering task I, converges in the limit on any text for ∪ i∈I A i to a finite set J of indices of pairwise disjoint clusters such that ∪ j∈J A j = ∪ i∈I A i. A class is called semiclusterable if there is such an algorithm which finds a J with the last condition relaxed to ∪ j∈J A j ⊇ ∪ i∈I A i. The relationship between natural topological properties and clusterability is investigated. Topological properties can provide sufficient or necessary conditions for clusterability, but they cannot characterize it. On the one hand, many interesting conditions make use of both the topological structure of the class and a well-chosen numbering. On the other hand, the clusterability of a class does not depend on which numbering of the class is used as a hypothesis space for the clusterer. These ideas are demonstrated in the context of naturally geometrically defined classes. Besides the text for the clustering task, clustering of many of these classes requires the following additional information: the class of convex hulls of finitely many points in a rational vector space can be clustered with the number of clusters as additional information. Interestingly, the class of polygons (together with their interiors) is clusterable if the number of clusters and the overall number of vertices of these clusters is given to the clusterer as additional information. Intriguingly, this additional information is not sufficient for classes including figures with holes. While some classes are unclusterable due to their topological structure, others are only computationally intractable. An oracle might permit clustering all computationally intractable clustering tasks but fail on some classes which are topologically difficult. It is shown that an oracle E permits clustering all computationally difficult classes iff E ≥ T K Λ E′ ≥ T K″. Furthermore, no 1-generic oracle below K and no 2-generic oracle permits clustering any class which is not clusterable without an oracle. © 2006 Society for Industrial and Applied Mathematics.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/430972006-01-01T00:00:00Z
- Robust learning - Rich and poorhttps://scholarbank.nus.edu.sg/handle/10635/39121Title: Robust learning - Rich and poor
Authors: Case, J.; Jain, S.; Stephan, F.; Wiehagen, R.
Abstract: A class script C sign of recursive functions is called robustly learnable in the sense I (where I is any success criterion of learning) if not only script C sign itself but even all transformed classes Θscript C sign), where Θ is any general recursive operator, are learnable in the sense I. It was already shown before, see Fulk (in: 31st Annual IEEE Symposium on Foundation of Computer Science, IEEE Computer Soc. Press, Silver Spring, MD 1990, pp. 405-410), Jain et al. (J. Comput. System Sci. 62 (2001) 178), that for I=Ex (learning in the limit) robust learning is rich in that there are classes being both not contained in any recursively enumerable class of recursive functions and, nevertheless, robustly learnable. For several criteria I, the present paper makes much more precise where we can hope for robustly learnable classes and where we cannot. This is achieved in two ways. First, for I=Ex, it is shown that only consistently learnable classes can be uniformly robustly learnable. Second, some other learning types I are classified as to whether or not they contain rich robustly learnable classes. Moreover, the first results on separating robust learning from uniformly robust learning are derived. © 2003 Elsevier Inc. All rights reserved.
Thu, 01 Jan 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/391212004-01-01T00:00:00Z
- Variations on U-shaped learninghttps://scholarbank.nus.edu.sg/handle/10635/43099Title: Variations on U-shaped learning
Authors: Carlucci, L.; Jain, S.; Kinber, E.; Stephan, F.
Abstract: The paper deals with the following problem: is returning to wrong conjectures necessary to achieve full power of algorithmic learning? Returning to wrong conjectures complements the paradigm of U-shaped learning when a learner returns to old correct conjectures. We explore our problem for classical models of learning in the limit from positive data: explanatory learning (when a learner stabilizes in the limit on a correct grammar) and behaviourally correct learning (when a learner stabilizes in the limit on a sequence of correct grammars representing the target concept). In both cases we show that returning to wrong conjectures is necessary to achieve full learning power. In contrast, one can modify learners (without losing learning power) such that they never show inverted U-shaped learning behaviour, that is, never return to old wrong conjecture with a correct conjecture in-between. Furthermore, one can also modify a learner (without losing learning power) such that it does not return to old "overinclusive" conjectures containing non-elements of the target language. We also consider our problem in the context of vacillatory learning (when a learner stabilizes on a finite number of correct grammars) and show that each of the following four constraints is restrictive (that is, reduces learning power): the learner does not return to old wrong conjectures; the learner is not inverted U-shaped; the learner does not return to old overinclusive conjectures; the learner does not return to old overgeneralizing conjectures. We also show that learners that are consistent with the input seen so far can be made decisive: on any text, they do not return to any old conjectures-wrong or right. © 2006 Elsevier Inc. All rights reserved.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/430992006-01-01T00:00:00Z
- A general comparison of language learning from examples and from querieshttps://scholarbank.nus.edu.sg/handle/10635/39315Title: A general comparison of language learning from examples and from queries
Authors: Jain, S.; Lange, S.; Zilles, S.
Abstract: In language learning, strong relationships between Gold-style models and query models have recently been observed: in some quite general setting Gold-style learners can be replaced by query learners and vice versa, without loss of learning capabilities. These 'equalities' hold in the context of learning indexable classes of recursive languages. Former studies on Gold-style learning of such indexable classes have shown that, in many settings, the enumerability of the target class and the recursiveness of its languages are crucial for learnability. Moreover, studying query learning, non-indexable classes have been mainly neglected up to now. So it is conceivable that the recently observed relations between Gold-style and query learning are not due to common structures in the learning processes in both models, but rather to the enumerability of the target classes or the recursiveness of their languages. In this paper, the analysis is lifted onto the context of learning arbitrary classes of recursively enumerable languages. Still, strong relationships between the approaches of Gold-style and query learning are proven, but there are significant changes to the former results. Though in many cases learners of one type can still be replaced by learners of the other type, in general this does not remain valid vice versa. All results hold even for learning classes of recursive languages, which indicates that the recursiveness of the languages is not crucial for the former 'equality' results. Thus we analyze how constraints on the algorithmic structure of the target class affect the relations between two approaches to language learning. © 2007 Elsevier Ltd. All rights reserved.
Mon, 01 Jan 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/393152007-01-01T00:00:00Z
- Machine Induction without Revolutionary Changes in Hypothesis Sizehttps://scholarbank.nus.edu.sg/handle/10635/99332Title: Machine Induction without Revolutionary Changes in Hypothesis Size
Authors: Case, J.; Jain, S.; Sharma, A.
Abstract: This paper provides a beginning study of the effects on inductive inference of paradigm shifts whose absence is approximately modeled by various formal approaches to forbidding large changes in the size of programs conjectured. One approach, called severely parsimonious, requires all the programs conjectured on the way to success to be nearly (i.e., within a recursive function of) minimal size. It is shown that this very conservative constraint allows learning infinite classes of functions, but not infinite r.e. classes of functions. Another approach, called non-revolutionary, requires all conjectures to be nearly the same size as one another. This quite conservative constraint is, nonetheless, shown to permit learning some infinite r.e. classes of functions. Allowing up to one extra bounded size mind change towards a final program learned certainly does not appear revolutionary. However, somewhat surprisingly for scientific (inductive) inference, it is shown that there are classes learnable with the non-revolutionary constraint (respectively, with severe parsimony), up to (i + 1) mind changes, and no anomalies, which classes cannot be learned with no size constraint, an unbounded, finite number of anomalies in the final program, but with no more than i mind changes. Hence, in some cases, the possibility of one extra mind change is considerably more liberating than removal of very conservative size shift constraints. The proofs of these results are also combinatorially interesting. © 1996 Academic Press, Inc.
Thu, 01 Aug 1996 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/993321996-08-01T00:00:00Z
- Prudence in vacillatory language identificationhttps://scholarbank.nus.edu.sg/handle/10635/99391Title: Prudence in vacillatory language identification
Authors: Jain, S.; Sharma, A.
Abstract: This paper settles a question about "prudent" "vacillatory" identification of languages. Consider a scenario in which an algorithmic device M is presented with all and only the elements of a language L, and M conjectures a sequence, possibly infinite, of grammars. Three different criteria for success of M on L have been extensively investigated in formal language learning theory. If M converges to a single correct grammar for L, then the criterion of success is Gold's seminal notion of TxtEx-identification. If M converges to a finite number of correct grammars for L, then the criterion of success is called TxtFex-identification. Further, if M, after a finite number of incorrect guesses, outputs only correct grammars for L (possibly infinitely many distinct grammars), then the criterion of success is known as TxtBc-identification. A learning machine is said to be prudent according to a particular criterion of success just in case the only grammars it ever conjectures are for languages that it can learn according to that criterion. This notion was introduced by Osherson, Stob, and Weinstein with a view to investigating certain proposals for characterizing natural languages in linguistic theory. Fulk showed that prudence does not restrict TxtEx-identification, and later Kurtz and Royer showed that prudence does not restrict TxtBc-identification. This paper shows that prudence does not restrict TxtFex-identification. © 1995 Springer-Verlag New York Inc.
Mon, 01 May 1995 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/993911995-05-01T00:00:00Z
- Rice and Rice-Shapiro theorems for transfinite correction grammarshttps://scholarbank.nus.edu.sg/handle/10635/39428Title: Rice and Rice-Shapiro theorems for transfinite correction grammars
Authors: Case, J.; Jain, S.
Abstract: Hay and, then, Johnson extended the classic Rice and Rice-Shapiro Theorems for computably enumerable sets, to analogs for all the higher levels in the finite Ershov Hierarchy. The present paper extends their work (with some motivations presented) to analogs in the transfinite Ershov Hierarchy. Some of the transfinite cases are done for all transfinite notations in Kleene's important system of notations. Other cases are done for all transfinite notations in a very natural, proper subsystem of, where has at least one notation for each constructive ordinal. In these latter cases it is open as to what happens for the entire set of transfinite notations in. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394282011-01-01T00:00:00Z
- Finite Identification of Functions by Teams with Success Ratio 1 2 and Abovehttps://scholarbank.nus.edu.sg/handle/10635/99293Title: Finite Identification of Functions by Teams with Success Ratio 1 2 and Above
Authors: Jain, S.; Sharma, A.; Velauthapillai, M.
Abstract: Consider a scenario in which an algorithmic machine, M, is being fed the graph of a computable function f{hook}. M is said to finitely identify f{hook} just in case, after inspecting a finite portion of the graph of f{hook}, it emits its first conjecture, which is a program for f{hook}, and it never abandons this conjecture thereafter. A team of machines is a multiset of such machines. A team is said to be successful just in case each member of some nonempty subset, of predetermined size, 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 the finite identification of computable functions by teams of learning machines. The results presented complete the picture for teams with success ratio 1 2 and greater. It is shown that at success ratio 1 2, introducing redundancy in the team can result in increased learning power. In particular, it is established that larger collections of functions can be learned by employing teams of 4 machines and requiring at least 2 to be successful than by employing teams of 2 machines and requiring at least 1 to be successful. Surprisingly, it is also shown that introducing further redundancy at success ratio 1 2 does not yield any extra learning power. In particular, it is shown that the collections of functions that can be finitely identified by a team of 2m machines requiring at least m to be successful is the same as: • the collections of functions that can be finitely identified by a team of 4 machines requiring at least 2 to be successful, if is even, and • the collections of functions that can be identified by a team of 2 machines requiring at least 1 to be successful, if is odd. These latter results require development of sophisticated simulation techniques. © 1995 Academic Press. All rights reserved.
Fri, 01 Sep 1995 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/992931995-09-01T00:00:00Z
- Urban rural differences in diet, physical activity and obesity in India: Are we witnessing the great Indian equalisation? Results from a cross-sectional STEPS surveyhttps://scholarbank.nus.edu.sg/handle/10635/144329Title: Urban rural differences in diet, physical activity and obesity in India: Are we witnessing the great Indian equalisation? Results from a cross-sectional STEPS survey
Authors: Tripathy J.P.; Thakur J.S.; Jeet G.; Chawla S.; Jain S.; Prasad R.
Fri, 01 Jan 2016 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1443292016-01-01T00:00:00Z
- Hypothesis spaces for learninghttps://scholarbank.nus.edu.sg/handle/10635/39424Title: Hypothesis spaces for learning
Authors: Jain, S.
Abstract: In this paper we survey some results in inductive inference showing how learnability of a class of languages may depend on the hypothesis space chosen. Additionally, optimal hypothesis spaces, usable for every learnable class, are considered. We also discuss results which consider how learnability is effected if one requires learning using every suitable hypothesis space. © 2010 Elsevier Inc. All rights reserved.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394242011-01-01T00:00:00Z
- Learning languages from positive data and negative counterexampleshttps://scholarbank.nus.edu.sg/handle/10635/39435Title: Learning languages from positive data and negative counterexamples
Authors: Jain, S.; Kinber, E.
Abstract: In this paper we introduce a paradigm for learning in the limit of potentially infinite languages from all positive data and negative counterexamples provided in response to the conjectures made by the learner. Several variants of this paradigm are considered that reflect different conditions/constraints on the type and size of negative counterexamples and on the time for obtaining them. In particular, we consider the models where (1) a learner gets the least negative counterexample; (2) the size of a negative counterexample must be bounded by the size of the positive data seen so far; (3) a counterexample can be delayed. Learning power, limitations of these models, relationships between them, as well as their relationships with classical paradigms for learning languages in the limit (without negative counterexamples) are explored. Several surprising results are obtained. In particular, for Gold's model of learning requiring a learner to syntactically stabilize on correct conjectures, learners getting negative counterexamples immediately turn out to be as powerful as the ones that do not get them for indefinitely (but finitely) long time (or are only told that their latest conjecture is not a subset of the target language, without any specific negative counterexample). Another result shows that for behaviorally correct learning (where semantic convergence is required from a learner) with negative counterexamples, a learner making just one error in almost all its conjectures has the "ultimate power": it can learn the class of all recursively enumerable languages. Yet another result demonstrates that sometimes positive data and negative counterexamples provided by a teacher are not enough to compensate for full positive and negative data. © 2007 Elsevier Inc. All rights reserved.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394352008-01-01T00:00:00Z
- The regulatory network of E. coli metabolism as a Boolean dynamical system exhibits both homeostasis and flexibility of responsehttps://scholarbank.nus.edu.sg/handle/10635/144302Title: The regulatory network of E. coli metabolism as a Boolean dynamical system exhibits both homeostasis and flexibility of response
Authors: Samal A.; Jain S.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1443022008-01-01T00:00:00Z
- Iterative learning from texts and counterexamples using additional informationhttps://scholarbank.nus.edu.sg/handle/10635/39093Title: Iterative learning from texts and counterexamples using additional information
Authors: Jain, S.; Kinber, E.
Abstract: A variant of iterative learning in the limit (cf. Lange and Zeugmann 1996) is studied when a learner gets negative examples refuting conjectures containing data in excess of the target language and uses additional information of the following four types: (a) memorizing up to n input elements seen so far; (b) up to n feedback memberships queries (testing if an item is a member of the input seen so far); (c) the number of input elements seen so far; (d) the maximal element of the input seen so far. We explore how additional information available to such learners (defined and studied in Jain and Kinber 2007) may help. In particular, we show that adding the maximal element or the number of elements seen so far helps such learners to infer any indexed class of languages class-preservingly (using a descriptive numbering defining the class)-as it is proved in Jain and Kinber (2007), this is not possible without using additional information. We also study how, in the given context, different types of additional information fare against each other, and establish hierarchies of learners memorizing n+1 versus n input elements seen and n+1 versus n feedback membership queries. © 2011 The Author(s).
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/390932011-01-01T00:00:00Z
- On the learnability of recursively enumerable languages from good exampleshttps://scholarbank.nus.edu.sg/handle/10635/41043Title: On the learnability of recursively enumerable languages from good examples
Authors: Jain, S.; Lange, S.; Nessel, J.
Abstract: The present paper investigates identification of indexed families L of recursively enumerable languages from good examples. We distinguish class-preserving learning from good examples (the good examples have to be generated with respect to a hypothesis space having the same range as L) and class-comprising learning from good examples (the good examples have to be selected with respect to a hypothesis space comprising the range of L). A learner is required to learn a target language on every finite superset of the good examples for it. If the learner's first and only conjecture is correct then the underlying learning model is referred to as finite identification from good examples and if the learner makes a finite number of incorrect conjectures before always outputting a correct one, the model is referred to as limit identification from good examples. In the context of class-preserving learning, it is shown that the learning power of finite and limit identification from good text examples coincide. When class comprising learning from good text examples is concerned, limit identification is strictly more powerful than finite learning. Furthermore, if learning from good informant examples is considered, limit identification is superior to finite identification in the class preserving as well as in the class-comprising case. Finally, we relate the models of learning from good examples to one another as well as to the standard learning models in the context of Gold-style language learning. © 2001 Elsevier Science B.V. All rights reserved.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/410432001-01-01T00:00:00Z
- Results on memory-limited U-shaped learninghttps://scholarbank.nus.edu.sg/handle/10635/43041Title: Results on memory-limited U-shaped learning
Authors: Carlucci, L.; Case, J.; Jain, S.; Stephan, F.
Abstract: U-shaped learning is a learning behaviour in which the learner first learns a given target behaviour, then unlearns it and finally relearns it. Such a behaviour, observed by psychologists, for example, in the learning of past-tenses of English verbs, has been widely discussed among psychologists and cognitive scientists as a fundamental example of the non-monotonicity of learning. Previous theory literature has studied whether or not U-shaped learning, in the context of Gold's formal model of learning languages from positive data, is necessary for learning some tasks. It is clear that human learning involves memory limitations. In the present paper we consider, then, the question of the necessity of U-shaped learning for some learning models featuring memory limitations. Our results show that the question of the necessity of U-shaped learning in this memory-limited setting depends on delicate tradeoffs between the learner's ability to remember its own previous conjecture, to store some values in its long term memory, to make queries about whether or not items occur in previously seen data and on the learner's choice of hypotheses space. © 2007 Elsevier Inc. All rights reserved.
Mon, 01 Jan 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/430412007-01-01T00:00:00Z
- Branch and bound on the network modelhttps://scholarbank.nus.edu.sg/handle/10635/39422Title: Branch and bound on the network model
Authors: Jain, S.
Abstract: Karp and Zhang developed a general randomized parallel algorithm for solving branch and bound problems. They showed that with high probability their algorithm attained optimal speedup within a constant factor (for p≤n/(logn) c, where p is the number of processors, n is the "size" of the problem, and c is a constant). Ranade later simplified the analysis and obtained a better processor bound. Karp and Zhang's algorithm works on models of computation where communication cost is constant. The present paper considers the Branch and Bound problem on networks where the communication cost is high. Suppose sending a message in a p processor network takes G = O(logp) time and node expansion (defined below) takes unit time (other operations being free). Then a simple randomized algorithm is presented which is, asymptotically, nearly optimal for p = O(2 logc n), where c is any constant <1/3 and n is the number of nodes in the input tree with cost no greater than the cost of the optimal leaf in the tree. © 2001 Elsevier Science B.V. All rights reserved.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394222001-01-01T00:00:00Z
- Costs of general purpose learninghttps://scholarbank.nus.edu.sg/handle/10635/39391Title: Costs of general purpose learning
Authors: Case, J.; Chen, K.-J.; Jain, S.
Abstract: Leo Harrington constructed a machine which can learn any computable function f according to Bc*-identification. His machine outputs a corresponding infinite sequence of programs and for some, the programs each compute a variant of f which differs from f at only finitely many argument places. A general purpose learning machine M was constructed such that on computable function input all but finitely many of the programs output by M are for total functions.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/393912001-01-01T00:00:00Z
- Learning multiple languages in groupshttps://scholarbank.nus.edu.sg/handle/10635/39086Title: Learning multiple languages in groups
Authors: Jain, S.; Kinber, E.
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.
Mon, 01 Jan 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/390862007-01-01T00:00:00Z
- Graphs realised by r.e. equivalence relationshttps://scholarbank.nus.edu.sg/handle/10635/113921Title: Graphs realised by r.e. equivalence relations
Authors: Gavruskin, A.; Jain, S.; Khoussainov, B.; Stephan, F.
Abstract: We investigate dependence of recursively enumerable graphs on the equality relation given by a specific r.e. equivalence relation on ω. In particular we compare r.e. equivalence relations in terms of graphs they permit to represent. This defines partially ordered sets that depend on classes of graphs under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal and maximal elements. We also fully describe the isomorphism types of some of these partial orders. © 2014 Elsevier B.V.
Wed, 01 Jan 2014 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1139212014-01-01T00:00:00Z
- Automatic learning of subclasses of pattern languageshttps://scholarbank.nus.edu.sg/handle/10635/43096Title: Automatic learning of subclasses of pattern languages
Authors: Case, J.; Jain, S.; Le, T.D.; Ong, Y.S.; Semukhin, P.; Stephan, F.
Abstract: Automatic classes are classes of languages for which a finite automaton can decide the membership problem for the languages in the class, in a uniform way, given an index for the language. For alphabet size of at least 4, every automatic class of erasing pattern languages is contained, for some constant n, in the class of all languages generated by patterns which contain (1) every variable only once and (2) at most n symbols after the first occurrence of a variable. It is shown that such a class is automatically learnable using a learner with the length of the long-term memory being bounded by the length of the first example seen. The study is extended to show the learnability of related classes such as the class of unions of two pattern languages of the above type. © 2012 Elsevier Inc.
Sun, 01 Jan 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/430962012-01-01T00:00:00Z
- Uncountable automatic classes and learninghttps://scholarbank.nus.edu.sg/handle/10635/43055Title: Uncountable automatic classes and learning
Authors: Jain, S.; Luo, Q.; Semukhin, P.; Stephan, F.
Abstract: In this paper we consider uncountable classes recognizable by ω-automata and investigate suitable learning paradigms for them. In particular, the counterparts of explanatory, vacillatory and behaviourally correct learning are introduced for this setting. Here the learner reads in parallel the data of a text for a language L from the class plus an ω-index α and outputs a sequence of ω-automata such that all but finitely many of these ω-automata accept the index α if and only if α is an index for L. It is shown that any class is behaviourally correct learnable if and only if it satisfies Angluin's tell-tale condition. For explanatory learning, such a result needs that a suitable indexing of the class is chosen. On the one hand, every class satisfying Angluin's tell-tale condition is vacillatorily learnable in every indexing; on the other hand, there is a fixed class such that the level of the class in the hierarchy of vacillatory learning depends on the indexing of the class chosen. We also consider a notion of blind learning. On the one hand, a class is blind explanatorily (vacillatorily) learnable if and only if it satisfies Angluin's tell-tale condition and is countable; on the other hand, for behaviourally correct learning, there is no difference between the blind and non-blind version. This work establishes a bridge between the theory of ω-automata and inductive inference (learning theory). © 2010 Elsevier B.V. All rights reserved.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/430552011-01-01T00:00:00Z
- Mind change speed-up for learning languages from positive datahttps://scholarbank.nus.edu.sg/handle/10635/78226Title: Mind change speed-up for learning languages from positive data
Authors: Jain, S.; Kinber, E.
Abstract: Within the frameworks of learning in the limit of indexed classes of recursive languages from positive data and automatic learning in the limit of indexed classes of regular languages (with automatically computable sets of indices), we study the problem of minimizing the maximum number of mind changes FM(n) by a learner M on all languages with indices not exceeding n. For inductive inference of recursive languages, we establish two conditions under which FM(n) can be made smaller than any recursive unbounded non-decreasing function. We also establish how FM(n) is affected if at least one of these two conditions does not hold. In the case of automatic learning, some partial results addressing speeding up the function F M(n) are obtained. © S. Jain and E. Kinber.
Sun, 01 Jan 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/782262012-01-01T00:00:00Z
- Learning languages from positive data and a limited number of short counterexampleshttps://scholarbank.nus.edu.sg/handle/10635/39436Title: Learning languages from positive data and a limited number of short counterexamples
Authors: Jain, S.; Kinber, E.
Abstract: We consider two variants of a model for learning languages in the limit from positive data and a limited number of short negative counterexamples (counterexamples are considered to be short if they are smaller than the largest element of input seen so far). Negative counterexamples to a conjecture are examples which belong to the conjectured language but do not belong to the input language. Within this framework, we explore how/when learners using n short (arbitrary) negative counterexamples can be simulated (or simulate) using least short counterexamples or just 'no' answers from a teacher. We also study how a limited number of short counterexamples fairs against unconstrained counterexamples, and also compare their capabilities with the data that can be obtained from subset, superset, and equivalence queries (possibly with counterexamples). A surprising result is that just one short counterexample can sometimes be more useful than any bounded number of counterexamples of arbitrary sizes. Most of the results exhibit salient examples of languages learnable or not learnable within corresponding variants of our models. © 2007 Elsevier Ltd. All rights reserved.
Mon, 01 Jan 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394362007-01-01T00:00:00Z
- On a question of nearly minimal identification of functionshttps://scholarbank.nus.edu.sg/handle/10635/39419Title: On a question of nearly minimal identification of functions
Authors: Jain, S.
Abstract: Suppose A and B are classes of recursive functions. A is said to be an m-cover (*-cover) for B, iff for each g∈B, there exists an f∈A such that f differs from g on at most m inputs (finitely many inputs). C, a class of recursive functions, is a-immune iff C is infinite and every recursively enumerable subclass of C has a finite a-cover. C is a-isolated iff C is finite or a-immune. Chen (1981) conjectured that every class of recursive functions that is MEx* m-identifiable is *-isolated. We refute this conjecture.
Fri, 01 Jan 1999 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394191999-01-01T00:00:00Z
- Iterative learning from positive data and negative counterexampleshttps://scholarbank.nus.edu.sg/handle/10635/39429Title: Iterative learning from positive data and negative counterexamples
Authors: Jain, S.; Kinber, E.
Abstract: A model for learning in the limit is defined where a (so-called iterative) learner gets all positive examples from the target language, tests every new conjecture with a teacher (oracle) if it is a subset of the target language (and if it is not, then it receives a negative counterexample), and uses only limited long-term memory (incorporated in conjectures). Three variants of this model are compared: when alearner receives least negative counterexamples, the ones whose sizeis boundedbythe maximum size of input seen so far, and arbitrary ones. A surprising result is that sometimes absence of bounded counterexamples can help an iterative learner whereas arbitrary counterexamples are useless. We also compare our learnability model with other relevant models of learnability in the limit, study how our model works for indexed classes of recursive languages, and show that learners in our model can work in non-U-shaped way-never abandoning the first right conjecture. © 2007 Elsevier Inc. All rights reserved.
Mon, 01 Jan 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394292007-01-01T00:00:00Z
- Learning languages from positive data and a finite number of querieshttps://scholarbank.nus.edu.sg/handle/10635/39430Title: Learning languages from positive data and a finite number of queries
Authors: Jain, S.; Kinber, E.
Abstract: A computational model for learning languages in the limit from full positive data and a bounded number of queries to the teacher (oracle) is introduced and explored. Equivalence, superset, and subset queries are considered (for the latter one we consider also a variant when the learner tests every conjecture, but the number of negative answers is uniformly bounded). If the answer is negative, the teacher may provide a counterexample. We consider several types of counterexamples: arbitrary, least counterexamples, the ones whose size is bounded by the size of positive data seen so far, and no counterexamples. A number of hierarchies based on the number of queries (answers) and types of answers/counterexamples is established. Capabilities of learning with different types of queries are compared. In most cases, one or two queries of one type can sometimes do more than any bounded number of queries of another type. Still, surprisingly, a finite number of subset queries is sufficient to simulate the same number of equivalence queries when behaviourally correct learners do not receive counterexamples and may have unbounded number of errors in almost all conjectures. © 2005 Elsevier Inc. All rights reserved.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394302006-01-01T00:00:00Z
- Learnability of automatic classeshttps://scholarbank.nus.edu.sg/handle/10635/43288Title: Learnability of automatic classes
Authors: Jain, S.; Luo, Q.; Stephan, F.
Abstract: The present work initiates the study of the learnability of automatic indexable classes which are classes of regular languages of a certain form. Angluin's tell-tale condition characterises when these classes are explanatorily learnable. Therefore, the more interesting question is when learnability holds for learners with complexity bounds, formulated in the automata-theoretic setting. The learners in question work iteratively, in some cases with an additional long-term memory, where the update function of the learner mapping old hypothesis, old memory and current datum to new hypothesis and new memory is automatic. Furthermore, the dependence of the learnability on the indexing is also investigated. This work brings together the fields of inductive inference and automatic structures. © 2012 2012 Elsevier Inc. All rights reserved.
Sun, 01 Jan 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/432882012-01-01T00:00:00Z
- Incremental learning with temporary memoryhttps://scholarbank.nus.edu.sg/handle/10635/39157Title: Incremental learning with temporary memory
Authors: Jain, S.; Lange, S.; Moelius III, S.E.; Zilles, S.
Abstract: In the inductive inference framework of learning in the limit, a variation of the bounded example memory (Bem) language learning model is considered. Intuitively, the new model constrains the learner's memory not only in how much data may be stored, but also in how long those data may be stored without being refreshed. More specifically, the model requires that, if the learner commits an example x to memory, and x is not presented to the learner again thereafter, then eventually the learner forgetsx, i.e., eventually x no longer appears in the learner's memory. This model is called temporary example memory (Tem) learning. Many interesting results concerning the Tem-learning model are presented. For example, there exists a class of languages that can be identified by memorizing k + 1 examples in the Tem sense, but that cannot be identified by memorizing k examples in the Bem sense. On the other hand, there exists a class of languages that can be identified by memorizing just one example in the Bem sense, but that cannot be identified by memorizing any number of examples in the Tem sense. Results are also presented concerning the special case of learning classes of infinite languages. © 2010 Elsevier B.V. All rights reserved.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/391572010-01-01T00:00:00Z