DSpace Angular :: Browsing by Author "JAIN, Sanjay"

Browsing by Author "JAIN, Sanjay"

Now showing 1 - 20 of 22

Absolute versus probabilistic classification in a logical setting
(2006-03-22T01:23:33Z) JAIN, Sanjay; MARTIN, Eric; STEPHAN, Frank
Given a set W of logical structures, or possible worlds, a set of logical formulas called possible data and a logical formula phi, we consider the classification problem of determining in the limit and almost always correctly whether a possible world M in W satisfies phi, from a complete enumeration of the possible data that are true in M. One interpretation of almost always correctly is that the classification might be wrong on a set of possible worlds of measure 0, with respect to some natural probability distribution over the set of possible worlds. Another interpretation is that the classifier is only required to classify a set W' of possible worlds of measure 1, without having to produce any claim in the limit on the truth of phi in the members of W which are not in W'. We compare these notions with absolute classification of W with respect to a formula that is almost always equivalent to phi in W, hence investigate whether the set of possible worlds on which the classification is correct is definable. We mainly work with the probability distribution that corresponds to the standard measure on the Cantor space, but we also consider an alternative probability distribution proposed by Solomonoff and contrast it with the former. Finally, in the spirit of the kind of computations considered in Logic programming, we address the issue of computing almost correctly in the limit witnesses to leading existentially quantified variables in existential formulas.
Consistent and Conservative Iterative Learning
(2007-03-21T01:32:49Z) JAIN, Sanjay; LANGE, Steffen; ZILLES, Sandra
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.
Index Sets and Universal Numberings
(2009-03-17T01:51:08Z) JAIN, Sanjay; STEPHAN, Frank; TEUTSCH, Jason
This paper studies the Turing degrees of various properties defined for universal numberings, that is, for numberings which list all partial-recursive functions. In particular properties relating to the domain of the corresponding functions are investigated like the set DEQ of all pairs of indices of functions with the same domain, the set DMIN of all minimal indices of sets and DMIN* of all indices which are minimal with respect to equality of the domain modulo finitely many differences. A partial solution to a question of Schaefer is obtained by showing that for every universal numbering with the Kolmogorov property, the set DMIN* is Turing equivalent to the double jump of the halting problem. Furthermore, it is shown that the join of DEQ and the halting problem is Turing equivalent to the jump of the halting problem and that there are numberings for which DEQ itself has 1-generic Turing degree.
Invertible Classes
(2005-12-08T07:17:18Z) JAIN, Sanjay; NESSEL, Jochen; STEPHAN, Frank
In this paper we consider how and when general recursive operators can be inverted. This is motivated by the fact that in many situations in real life, one is interested in finding causes from the results. We also introduce the notion of coverability, which allows us to get a simpler representative enumeration of operators which satisfy some nice properties. We consider four notions of inversion --- strong inversion, inversion, weak inversion and bounded weak inversion --- and show that these separate. We also considered three notions of enumerations of operators to cover a class in the sense that the behaviour of every general recursive operator on the class is met. These three notions are strong covering, covering and weak covering --- where an acceptable numbering weakly covers all classes. We seaprate the induced notions of coverability. We also consider some special classes such as recursively enumerable classes and periodic classes. We show some interesting properties such as these classes are strongly invertible. We also show that some recursively enumerable classes, but not the class of periodic functions, are coverable.
Iterative Learning from Positive Data and Negative Counterexamples
(2006-03-13) JAIN, Sanjay; KINBER, Efim
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 a learner receives least negative counterexamples, the ones whose size is bounded by the maximum size of input seen so far, and arbitrary ones. 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.
Iterative Learning from Texts and Counterexamples Using Additional Information
(2009-04-27T01:24:54Z) JAIN, Sanjay; KINBER, Efim
A variant of iterative learning in the limit 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 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 was proved by Jain and Kinber, this is not possible without using additional information. We also study how, in the given context, different types of additional information fare agains each other, and establish hierarchies of learners memorizing n+1 versus n input elements seen and n+1 versus n feedback membership queries.
Learnability of Automatic Classes
(2009-01-29T02:57:33Z) JAIN, Sanjay; LUO, Qinglong; STEPHAN, Frank
The present work initiates the study of the learnability of automatic indexable classes which are classes of regular languages of a certain form. It is characterised which of these classes are explanatorily learnable. Furthermore, the notion of an automatic iterative learner is introduced and it is studied for automatic classes whether they are learnable by an automatic iterative learner, learnable by an automatic iterative learner with additional long-term memory or unlearnable by such a learner. The dependence of the learnability on the indexing is also investigated. This work brings together the fields of inductive inference and automatic structures.
Learning Correction Grammars
(2006-12-18T03:22:00Z) CARLUCCI, Lorenzo; CASE, John; JAIN, Sanjay
We investigate a new paradigm in the context of learning in the limit, namely, learning correction grammars for classes of r.e. languages. Knowing a language may feature a representation of the target language in terms of two sets of rules (two grammars). The second grammar is used to edit errors of (make corrections to) the first grammar. Such a pair of two grammars can be seen as a single description of (or grammar for) the language. We call such grammars correction grammars. Correction grammars can be thought of as capturing the observable fact that people do correct their linguistic utterances during their usual linguistic activities. Is the need for self-corrections implied by using correction grammars instead of normal grammars compensated by a learning advantage? We show that learning correction grammars for classes of r.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 in the TxtBc-model (where the learner is allowed to converge to infinitely many syntactically distinct but correct conjectures in the limit). For each n, there is a similar learning advantage, again in learning correction grammars for classes of r.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 by employing the idea of counting-down from notations for transfinite constructive ordinals. For u a notation in Kleene's system (O,<_o) of notations for constructive ordinals, we introduce the concept of an u-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 u <_o v, then there are classes of r.e. languages that can be TxtEx-learned by conjecturing v-correction grammars but not by conjecturing u-correction grammars. Surprisingly, we show that --- above omega-many corrections --- it is not possible to strengthen the hierarchy: TxtEx-learning u-correction grammars of classes of r.e. languages, where u is a notation in O for any ordinal, can be simulated by TxtBc-learning w-correction grammars, where w is any notation for the smallest infinite ordinal omega.
Learning in Friedberg Numberings
(2007-11-14) JAIN, Sanjay; STEPHAN, Frank
In this paper we consider learnability in some special numberings, such as Friedberg numberings, which contain all the recursively enumerable languages, but have simpler grammar equivalence problem compared to acceptable numberings. We show that every explanatorily learnable class can be learnt in some Friedberg numbering. However, such a result does not hold for behaviourally correct learning or finite learning. One can also show that some Friedberg numberings are so restrictive that all classes which can be explanatorily learnt in such Friedberg numberings have only finitely many infinite languages. We also study similar questions for several properties of learners such as consistency, conservativeness, prudence, iterativeness and non U-shaped learning. Besides Friedberg numberings, we also consider the above problems for programming systems with $K$-recursive grammar equivalence problem.
Memory-Limited U-Shaped Learning
(2005-12-02T09:37:07Z) CARLUCCI, Lorenzo; CASE, John; JAIN, Sanjay; STEPHAN, Frank
U-shaped learning is a learning behaviour in which the learner first learns something, 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, this 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 hypothesis space.
Mitotic Classes
(2007-08-21T03:16:07Z) JAIN, Sanjay; STEPHAN, Frank
For the natural notion of splitting classes into two disjoint subclasses via a recursive classifier working on texts, the question is addressed how these splittings can look in the case of learnable classes. 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 weak complete class which 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 behaviourally 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 Sacks Splitting Theorem from recursion theory.
Numberings Optimal for Learning
(2008-08-25) JAIN, Sanjay; STEPHAN, Frank
This paper extends previous studies on learnability in non-acceptable numberings by considering the question: for which criteria which numberings are optimal, that is, for which numberings it holds that one can learn every learnable class using the given numbering as hypothesis space. Furthermore an effective version of optimality is studied as well. It is shown that the effectively optimal numberings for finite learning are just the acceptable numberings. In contrast to this, there are non-acceptable numberings which are optimal for finite learning and effectively optimal for explanatory, vacillatory and behaviourally correct learning. The numberings effectively optimal for explanatory learning are the K-acceptable numberings. A similar characterization is obtained for the numberings which are effectively optimal for vacillatory learning. Furthermore, it is studied which numberings are optimal for one and not for another criterion: among the criteria of finite, explanatory, vacillatory and behaviourally correct learning all separations can be obtained; however every numbering which is optimal for explanatory learning is also optimal for consistent learning.
On Automatic Families
(2010-01-19) JAIN, Sanjay; ONG, Yuh Shin; PU, Shi; STEPHAN, Frank
This paper summarises previous work on automatic families. It then investigates a natural measure which exists inside every automatic family: the size of a regular language in this family is just the length of its index. This measure satisfies various properties similar to those of Kolmogorov complexity. Furthermore, there is a quite natural extension of it to all regular languages such that, for each automatic family, the new general measure differs from that of the least index only by up to a constant. However, this generalisation fails to have several properties similar to Kolmogorov complexity. Furthermore, a characterisation is given regarding when a class of languages is a subclass of an automatic family.
On Learning Languages from Positive Data and a Limited Number of Short Counterexamples
(2005-11-21T08:42:25Z) JAIN, Sanjay; KINBER, Efim
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 that 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 size. Most of results exhibit salient examples of languages learnable or not learnable within corresponding variants of our models.
On the Role of Update Constraints and Text-Types in Iterative Learning
(2014-07-10) JAIN, Sanjay; KÖTZING, Timo; MA, Junqi; STEPHAN, Frank
The present work investigates the relationship of iterative learning with other learning criteria such as decisiveness, caution, reliability, non-U-shapedness, monotonicity, strong monotonicity and conservativeness. Building on the result of Case and Moelius that iterative learners can be made non-U-shaped, we show that they also can be made cautious and decisive. Furthermore, we obtain various special results with respect to one-one texts, fat texts and one-one hypothesis spaces.
One-shot Learners Using Negative Counterexamples and Nearest Positive Examples
(2007-03-13T06:47:20Z) JAIN, Sanjay; KINBER, Efim
As some cognitive research suggests, in the process of learning languages, in addition to overt explicit negative evidence, a child often receives covert explicit evidence in form of corrected or rephrased sentences. In this paper, we suggest one approach to formalization of overt and covert evidence within the framework of one-shot learners via subset and membership queries to a teacher (oracle). We compare and explore general capabilities of our models, as well as complexity advantages of learnability models of one type over models of other types, where complexity is measured in terms of number of queries.
Prescribed Learning of Indexed Families
(2007-09-21T01:27:00Z) JAIN, Sanjay; STEPHAN, Frank; YE, Nan
This work extends studies of Angluin, Lange and Zeugmann on how learnability of a language class depends on the hypotheses space used by the learner. While previous studies mainly focused on the case where the learner chooses a particular hypotheses space, the goal of this work is to investigate the case where the learner has to cope with all possible hypotheses spaces. In that sense, the present work combines the approach of Angluin, Lange and Zeugmann with the question of how a learner can be synthesized. The investigation for the case of uniformly recursively enumerable classes has been presented by Jain, Stephan and Ye at the conference Algorithmic Learning Theory 2007. This paper investigates the case for indexed families and gives a special attention to the notions of conservative and non U-shaped learning.
Prescribed Learning of R.E. Classes
(2007-10-11) JAIN, Sanjay; STEPHAN, Frank; YE, Nan
This work extends studies of Angluin, Lange and Zeugmann on the dependence of learning on the hypotheses space chosen for the class. In subsequent investigations, uniformly recursively enumerable hypotheses spaces have been considered. In the present work, the following four types of learning are distinguished: class-comprising (where the learner can choose a uniformly recursively enumerable superclass as hypotheses space), class-preserving (where the learner has to choose a uniformly recursively enumerable hypotheses space of the same class), prescribed (where there must be a learner for every uniformly recursively enumerable hypotheses space of the same class) and uniform (like prescribed, but the learner has to be synthesized effectively from an index of the hypothesis space). 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 hypotheses space such that it learns every set in the hypotheses space. Moreover the prudent learner can be effectively built from any learner for the class.
Robust learning of automatic classes of languages
(2010-04-22T05:28:14Z) JAIN, Sanjay; MARTIN, Eric; STEPHAN, Frank
This paper adapts and investigates the paradigm of robust learning, originally defined in the framework of inductive inference of classes of recursive functions, to learning languages from positive data. Robustness is a very desirable property, as it captures a form of invariance of learnability under admissible transformations of the object of study.The classes of languages of interest are automatic, that is, recognisable by finite automata. A class of first-order definable operators - called translators - is introduced as natural transformations that preserve automaticity of a class of languages and the inclusion relationships between languages in the class. For many learning criteria, we provide a characterization of the classes of languages all of whose translations are learnable under that criterion. The learning criteria have been chosen from the literature on both explanatory learning and query learning, and include consistent and conservative learning, strong-monotonic learning, strong-monotonic consistent learning, finite learning, learning from subset queries, learning from superset queries and learning from membership queries.
Some Recent Results in U-Shaped Learning
(2005-11-25T01:41:20Z) JAIN, Sanjay; STEPHAN, Frank
U-shaped learning deals with a learner first having the correct hypothesis, then changing it to an incorrect hypothesis and then relearning the correct hypothesis. This phenomenon has been observed by psychologists in various studies of children development. In this survey talk, we will discuss some recent results regarding U-shaped learning and related crtieria.

Browsing by Author "JAIN, Sanjay"

Results Per Page

Sort Options