Frank Stephan

I&C Journal 2023 Journal Article

Learnability and positive equivalence relations

• David Belanger
• Ziyuan Gao
• Sanjay Jain
• Wei Li
• Frank Stephan

Prior work of Gavryushkin, Khoussainov, Jain and Stephan investigated what algebraic structures can be realised in worlds given by a positive (= recursively enumerable) equivalence relation which partitions the natural numbers into infinitely many equivalence classes. The present work investigates the infinite one-one numbered recursively enumerable (r. e.) families realised by such relations and asks how the choice of the equivalence relation impacts the learnability properties of these classes when studying learnability in the limit from positive examples, also known as learning from text. For all choices of such positive equivalence relations, for each of the following entries, there are one-one numbered r. e. families which satisfy it: (a) they are behaviourally correctly learnable but not vacillatorily learnable; (b) they are explanatorily learnable but not confidently learnable; (c) they are not behaviourally correctly learnable. Furthermore, there is a positive equivalence relation which enforces that (d) every vacillatorily learnable one-one numbered family of languages closed under this equivalence relation is already explanatorily learnable and cannot be confidently learnable. In addition, if there is for a positive equivalence relation a confidently learnable class, then there is also a class which is confidently but not finitely learnable.

TCS Journal 2023 Journal Article

String compression in FA–presentable structures

• Dmitry Berdinsky
• Sanjay Jain
• Bakhadyr Khoussainov
• Frank Stephan

We construct a FA–presentation ψ: L → N of the structure ( N; S ) for which a numerical characteristic r ( n ) defined as the maximum number ψ ( w ) for all strings w ∈ L of length less than or equal to n grows faster than any tower of exponents of a fixed height. This result leads us to a more general notion of a compressibility rate defined for FA–presentations of any FA–presentable structure. We show the existence of FA–presentations for the configuration space of a Turing machine and Cayley graphs of some groups for which it grows faster than any tower of exponents of a fixed height. For FA–presentations of the Presburger arithmetic ( N; + ) we show that it is bounded from above by a linear function.

TCS Journal 2022 Journal Article

A computation model with automatic functions and relations as primitive operations

• Ziyuan Gao
• Sanjay Jain
• Zeyong Li
• Ammar Fathin Sabili
• Frank Stephan

Prior work of Hartmanis and Simon [36] and Floyd and Knuth [30] investigated what happens if a device uses primitive steps more natural than single updates of a Turing tape. One finding was that in the numerical setting, addition, subtraction and bit-wise Boolean operations of numbers preserve polynomial time while incorporating concatenation or multiplication allows to solve all PSPACE problems in polynomially many steps. Therefore we propose to use updates and comparisons with automatic functions as primitive operations and use constantly many registers; the resulting model covers all primitive operations of Hartmanis and Simon as well as Floyd and Knuth, but the model remains in polynomial time. The present work investigates in particular the deterministic complexity of various natural problems and also gives an overview on the nondeterministic complexity of this model.

I&C Journal 2022 Journal Article

Learners based on transducers

• Sanjay Jain
• Shao Ning Kuek
• Eric Martin
• Frank Stephan

The learners considered here process data in cycles and maintain as a long term memory a string which provides all internal data the learner can use in the next cycle. Updating of these strings is usually done by either recursive or automatic learners. The present work looks at transduced learners, which sit in-between. The results include that transduced learners can learn all learnable automatic families with memory exponential in the size of the longest input seen so far. Furthermore, there is a hierarchy based on the memory-allowance: if n is the size of the largest datum seen so far, then for all k ≥ 1, memory n k + 1 allows one to learn more automatic families than memory n k. Further results shed light on when it can be imposed that transduced learners be consistent, conservative or iterative. The main result of this kind is that all learnable automatic families have a consistent and conservative transduced learner.

TCS Journal 2022 Journal Article

Randomness and initial segment complexity for measures

• André Nies
• Frank Stephan

We study algorithmic randomness properties for probability measures on Cantor space. We say that a measure μ on the space of infinite bit sequences is Martin-Löf absolutely continuous if the non-Martin-Löf random bit sequences form a null set with respect to μ. We think of this as a weak randomness notion for measures. We begin with examples, and provide a robustness property related to Solovay tests. The initial segment complexity of a measure μ at a length n is defined as the μ-average over the descriptive complexity of strings of length n, in the sense of either C or K. We relate this weak randomness notion for a measure to the growth of its initial segment complexity. We show that a maximal growth implies the weak randomness property, but also that both implications of the Levin-Schnorr theorem fail. We discuss C-triviality and K-triviality for measures and relate these two notions with each other. Here, triviality means that the initial segment complexity grows as slowly as possible. We show that every measure that is Martin-Löf random in the sense of Hoyrup and Rojas is Martin-Löf absolutely continuous; the converse fails because only the latter property is compatible with having atoms. In a final section we consider weak randomness relative to a general ergodic computable measure. We seek appropriate effective versions of the Shannon-McMillan-Breiman theorem and the Brudno theorem where the bit sequences are replaced by measures. We conclude with several open questions.

TCS Journal 2021 Journal Article

Bi-immunity over different size alphabets

• Cristian S. Calude
• Karen Frilya Celine
• Ziyuan Gao
• Sanjay Jain
• Ludwig Staiger
• Frank Stephan

In this paper we study various notions of bi-immunity over alphabets with b ≥ 2 elements and recursive transformations between sequences on different alphabets which preserve them. Furthermore, we extend the study from sequences bounded by a constant to sequences over the alphabet of all natural numbers, which may or may not be bounded by a recursive function, and relate them to the Turing degrees in which they can occur.

TCS Journal 2021 Journal Article

Improved algorithms for the general exact satisfiability problem

• Gordon Hoi
• Frank Stephan

The Exact Satisfiability problem asks if we can find a satisfying assignment to each clause such that exactly one literal in each clause is assigned 1, while the rest are all assigned 0. We can generalise this problem further by defining that a C j clause is solved iff exactly j of the literals in the clause are 1 and all others are 0. We now introduce the family of Generalised Exact Satisfiability problems called GiXSAT as the problem to check whether a given instance consisting of C j clauses with j ∈ { 0, 1, …, i } for each clause has a satisfying assignment. In this paper, we present faster exact polynomial space algorithms, using a nonstandard measure, to solve GiXSAT, for i ∈ { 2, 3, 4 }, in O ( 1. 3674 n ) time, O ( 1. 5687 n ) time and O ( 1. 6545 n ) time, respectively, using polynomial space, where n is the number of variables. This improves the current state of the art for polynomial space algorithms from O ( 1. 4203 n ) time for G2XSAT by Zhou, Jiang and Yin and from O ( 1. 6202 n ) time for G3XSAT by Dahllöf and from O ( 1. 6844 n ) time for G4XSAT which was by Dahllöf as well. In addition, we present faster exact algorithms solving G2XSAT, G3XSAT and G4XSAT in O ( 1. 3188 n ) time, O ( 1. 3407 n ) time and O ( 1. 3536 n ) time respectively at the expense of using exponential space.

I&C Journal 2021 Journal Article

On the amount of nonconstructivity in learning formal languages from text

• Sanjay Jain
• Frank Stephan
• Thomas Zeugmann

Nonconstructive computations by various types of machines and automata have been considered by, for example, Karp and Lipton as well as Freivalds. They allow to regard more complicated algorithms from the viewpoint of much more primitive computational devices. The amount of nonconstructivity is a quantitative characterization of the distance between types of computational devices with respect to solving a specific problem. This paper studies the amount of nonconstructivity needed to learn classes of formal languages. Different learning types are compared with respect to the amount of nonconstructivity needed to learn indexable classes and recursively enumerable classes, respectively, of formal languages from positive data. Matching upper and lower bounds for the amount of nonconstructivity needed are shown.

TCS Journal 2020 Journal Article

Searching for shortest and least programs

• Cristian S. Calude
• Sanjay Jain
• Wolfgang Merkle
• Frank Stephan

The Kolmogorov complexity of a string x is defined as the length of a shortest program p of x for some appropriate universal machine U, that is, U ( p ) = x and p is a shortest string with this property. Neither the plain nor the prefix-free version of Kolmogorov complexity are recursive but for both versions it is well-known that there are recursive exact Solovay functions, that is, recursive upper bounds for Kolmogorov complexity that are infinitely often tight. Let a coding function for a machine M be a function f such that f ( x ) is always a program of x for M. From the existence of exact Solovay functions it follows easily that for every universal machine there is a recursive coding function that maps infinitely many strings to a shortest program. Extending a recent line of research, in what follows it is investigated in which situations there is a coding function for some universal machine that maps infinitely many strings to the length-lexicographically least program. The main results which hold in the plain as well as in the prefix-free setting are the following. For every universal machine there is a recursive coding function that maps infinitely many strings to their least programs. There is a partial recursive coding function (defined in the natural way) for some universal machine that for every set maps infinitely many prefixes of the set to their least programs. Exactly for every set that is Bennett shallow (not deep), there is a recursive coding function for some universal machine that maps all prefixes of the set to their least programs. Differences between the plain and the prefix-free frameworks are obtained by considering effective sequences I 1, I 2, … of mutually disjoint finite sets and asking for a recursive coding function for some universal machine that maps at least one string in each set I n to its least code. Such coding functions do not exist in the prefix-free setting but exist in the plain setting in case the sets I n are not too small.

TCS Journal 2018 Journal Article

Effectivity questions for Kleene's recursion theorem

• John Case
• Sanjay Jain
• Frank Stephan

The present paper investigates the quality of numberings measured in three different ways: (a) the complexity of finding witnesses of Kleene's Recursion Theorem in the numbering; (b) for which learning notions from inductive inference the numbering is an optimal hypothesis space; (c) the complexity needed to translate the indices of other numberings to those of the given one. In all three cases, one assumes that the corresponding witnesses or correct hypotheses are found in the limit and one measures the complexity with respect to the best criterion of convergence which can be achieved. The convergence criteria considered are those of finite, explanatory, vacillatory and behaviourally correct convergence. The main finding is that the complexity of finding witnesses for Kleene's Recursion Theorem and the optimality for learning are independent of each other. Furthermore, if the numbering is optimal for explanatory learning and also allows to solve Kleene's Recursion Theorem with respect to explanatory convergence, then it also allows to translate indices of other numberings with respect to explanatory convergence.

I&C Journal 2018 Journal Article

Equivalences between learning of data and probability distributions, and their applications

• George Barmpalias
• Nan Fang
• Frank Stephan

Algorithmic learning theory traditionally studies the learnability of effective infinite binary sequences (reals), while recent work by Vitányi and Chater has adapted this framework to the study of learnability of effective probability distributions from random data. We prove that for certain families of probability measures that are parametrized by reals, learnability of a subclass of probability measures is equivalent to learnability of the class of the corresponding real parameters. This equivalence allows to transfer results from classical algorithmic theory to learning theory of probability measures. We present a number of such applications, providing many new results regarding EX and BC learnability of classes of measures, thus drawing parallels between the two learning theories.

TCS Journal 2018 Journal Article

Learning pattern languages over groups

• Rupert Hölzl
• Sanjay Jain
• Frank Stephan

This article studies the learnability of classes of pattern languages over automatic groups. It is shown that the class of bounded unions of pattern languages over finitely generated Abelian automatic groups is explanatorily learnable. For patterns in which variables occur at most n times, it is shown that the classes of languages generated by such patterns as well as their bounded unions are, for finitely generated automatic groups, explanatorily learnable by an automatic learner. In contrast, automatic learners cannot learn the unions of up to two arbitrary pattern languages over the integers. Furthermore, there is an algorithm which, given an automaton describing a group G, generates a learning algorithm M G such that either M G explanatorily learns all pattern languages over G or there is no learner for this set of languages at all, not even a non-recursive one. For some automatic groups, non-learnability results of natural classes of pattern languages are provided.

Highlights Conference 2017 Conference Abstract

An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space

• John Fearnley
• Sanjay Jain
• Sven Schewe
• Frank Stephan
• Dominik Wojtczak

Abstract available in PDF.

I&C Journal 2017 Journal Article

Automatic learning from positive data and negative counterexamples

• Sanjay Jain
• Efim Kinber
• Frank Stephan

We introduce and study a model for learning in the limit by finite automata from positive data and negative counterexamples. The focus is on learning classes of languages with the membership problem computable by finite automata (so-called automatic classes). We show that, within the framework of our model, finite automata (automatic learners) can learn all automatic classes when memory of a learner is restricted by the size of the longest datum seen so far. We also study capabilities of automatic learners in our model with other restrictions on the memory and how the choice of negative counterexamples (arbitrary, or least, or the ones which are bounded by the largest positive datum seen so far) can impact automatic learnability.

I&C Journal 2016 Journal Article

Enlarging learnable classes

• Sanjay Jain
• Timo Kötzing
• Frank Stephan

We study which classes of recursive functions satisfy that their union with any other explanatorily learnable class of recursive functions is again explanatorily learnable. We provide sufficient criteria for classes of recursive functions to satisfy this property and also investigate its effective variants. Furthermore, we study the question which learners can be effectively extended to learn a larger class of functions. We solve an open problem by showing that there is no effective procedure which does this task on all learners which do not learn a dense class of recursive functions. However, we show that there are two effective extension procedures such that each learner is extended by one of them.

I&C Journal 2016 Journal Article

Finite state incompressible infinite sequences

• Cristian S. Calude
• Ludwig Staiger
• Frank Stephan

In this paper we define and study finite state complexity of finite strings and infinite sequences as well as connections between these complexity notions to randomness and normality. We show that the finite state complexity does not only depend on the codes for finite transducers, but also on how the codes are mapped to transducers. As a consequence we relate the finite state complexity to the plain (Kolmogorov) complexity, to the process complexity and to prefix-free complexity. Working with prefix-free sets of codes we characterise Martin-Löf random sequences in terms of finite state complexity: the weak power of finite transducers is compensated by the high complexity of enumeration of finite transducers. We also prove that every finite state incompressible sequence is normal, but the converse implication is not true. These results also show that our definition of finite state incompressibility is stronger than all other known forms of finite automata based incompressibility, in particular the notion related to finite automaton based betting systems introduced by Schnorr and Stimm. The paper concludes with a discussion of open questions.

TCS Journal 2016 Journal Article

Guest Editors' foreword

• Sanjay Jain
• Rémi Munos
• Frank Stephan
• Thomas Zeugmann

TCS Journal 2016 Journal Article

On block pumpable languages

• Christopher Hanrui Chak
• Rūsiņš Freivalds
• Frank Stephan
• Henrietta Tan Wan Yik

Ehrenfeucht, Parikh and Rozenberg gave an interesting characterisation of the regular languages called the block pumping property. When requiring this property only with respect to members of the language but not with respect to nonmembers, one gets the notion of block pumpable languages. It is shown that these block pumpable are a more general concept than regular languages and that they are an interesting notion of their own: they are closed under intersection, union and homomorphism by transducers; they admit multiple pumping; they have either polynomial or exponential growth.

I&C Journal 2016 Journal Article

On the role of update constraints and text-types in iterative learning

• Sanjay Jain
• Timo Kötzing
• Junqi Ma
• Frank Stephan

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.

TCS Journal 2016 Journal Article

Partial learning of recursively enumerable languages

• Ziyuan Gao
• Frank Stephan
• Sandra Zilles

This paper studies several typical learning criteria in the model of partial learning of r. e. sets in the recursion-theoretic framework of inductive inference. Its main contribution is a complete picture of how the criteria of confidence, consistency and conservativeness in partial learning of r. e. sets separate, also in relation to basic criteria of learning in the limit. Thus this paper constitutes a substantial extension to prior work on partial learning. Further highlights of this work are very insightful characterisations of some of the inference criteria studied, leading to interesting consequences about the structural properties of the collection of classes learnable under these criteria. In particular a class is consistently partially learnable iff it is a subclass of a uniformly recursive family.

TCS Journal 2016 Journal Article

Reducibilities among equivalence relations induced by recursively enumerable structures

• Alex Gavryushkin
• Bakhadyr Khoussainov
• Frank Stephan

In this paper we investigate the dependence of recursively enumerable structures on the equality relation which is fixed to a specific r. e. equivalence relation. We compare r. e. equivalence relations on the natural numbers with respect to the amount of structures they permit to represent from a given class of structures such as algebras, permutations and linear orders. In particular, we show that for various types of structures represented, there are minimal and maximal elements.

TCS Journal 2016 Journal Article

Tree-automatic scattered linear orders

• Sanjay Jain
• Bakhadyr Khoussainov
• Philipp Schlicht
• Frank Stephan

Tree-automatic linear orders on regular tree languages are studied. It is shown that there is no tree-automatic scattered linear order, and therefore no tree-automatic well-order, on the set of all finite labeled trees, and that a regular tree language admits a tree-automatic scattered linear order if and only if for some n, no binary tree of height n can be embedded into the union of the domains of its trees. Hence the problem whether a given regular tree language can be ordered by a scattered linear order or a well-order is decidable. Moreover, sharp bounds for tree-automatic well-orders on some regular tree languages are computed by connecting tree automata with automata on ordinals. The proofs use elementary techniques of automata theory.

TCS Journal 2014 Journal Article

Confident and consistent partial learning of recursive functions

• Ziyuan Gao
• Frank Stephan

Partial learning is a criterion where the learner infinitely often outputs one correct conjecture while every other hypothesis is issued only finitely often. This paper addresses two variants of partial learning in the setting of inductive inference of functions: first, confident partial learning requires that the learner also on those functions which it does not learn, singles out exactly one hypothesis which is output infinitely often; second, essentially class-consistent partial learning is partial learning with the additional constraint that on the functions to be learnt, almost all hypotheses issued are consistent with all the data seen so far. The results of the present work are that confident partial learning is more general than explanatory learning, incomparable with behaviourally correct learning and closed under union; essentially class-consistent partial learning is more general than behaviourally correct learning and incomparable with confident partial learning. Furthermore, it is investigated which oracles permit to learn all recursive functions under these criteria: for confident partial learning, some non-high oracles are omniscient; for essentially class-consistent partial learning, all PA-complete and all oracles of hyperimmune Turing degree are omniscient.

I&C Journal 2014 Journal Article

Initial segment complexities of randomness notions

• Rupert Hölzl
• Thorsten Kräling
• Frank Stephan
• Guohua Wu

Schnorr famously proved that Martin-Löf-randomness of a sequence A can be characterised via the complexity of Aʼs initial segments. Nies, Stephan and Terwijn as well as independently Miller showed that a set is 2-random (that is, Martin-Löf random relative to the halting problem K) iff there is no function f such that for all m and all n > f ( m ) it holds that C ( A ( 0 ) A ( 1 ) … A ( n ) ) ⩽ n − m; before the proof of this equivalence the notion defined via the latter condition was known as Kolmogorov random. In the present work it is shown that characterisations of this style can also be given for other randomness criteria like strong randomness (also known as weak 2-randomness), Kurtz randomness relative to K, Martin-Löf randomness of PA-incomplete sets, and strong Kurtz randomness; here one does not just quantify over all functions f but over functions f of a specific form. For example, A is Martin-Löf random and PA-incomplete iff there is no A-recursive function f such that for all m and all n > f ( m ) it holds that C ( A ( 0 ) A ( 1 ) … A ( n ) ) ⩽ n − m. The characterisation for strong randomness relates to functions which are the concatenation of an A-recursive function executed after a K-recursive function; this solves an open problem of Nies. In addition to this, characterisations of a similar style are also given for Demuth randomness, weak Demuth randomness and Schnorr randomness relative to K. Although the unrelativised versions of Kurtz randomness and Schnorr randomness do not admit such a characterisation in terms of plain Kolmogorov complexity, Bienvenu and Merkle gave one in terms of Kolmogorov complexity defined by computable machines.

I&C Journal 2014 Journal Article

Things that can be made into themselves

• Frank Stephan
• Jason Teutsch

One says that a property P of sets of natural numbers can be made into itself iff there is a numbering α 0, α 1, … of all left-r. e. sets such that the index set { e: α e satisfies P } has the property P as well. For example, the property of being Martin-Löf random can be made into itself. Herein we characterize those singleton properties which can be made into themselves. A second direction of the present work is the investigation of the structure of left-r. e. sets under inclusion modulo a finite set. In contrast to the corresponding structure for r. e. sets, which has only maximal but no minimal members, both minimal and maximal left-r. e. sets exist. Moreover, our construction of minimal and maximal left-r. e. sets greatly differs from Friedberg's classical construction of maximal r. e. sets. Finally, we investigate whether the properties of minimal and maximal left-r. e. sets can be made into themselves.

TCS Journal 2013 Journal Article

Guest Editors’ foreword

• Marcus Hutter
• Frank Stephan
• Vladimir Vovk
• Thomas Zeugmann

TCS Journal 2013 Journal Article

Learning and classifying

• Sanjay Jain
• Eric Martin
• Frank Stephan

We define and study a learning paradigm that sits between identification in the limit and classification. More precisely, we expect a learner to determine in the limit which members of a finite set D of possible data belong to a target language L, where D is arbitrary. So as D becomes larger and larger, the task becomes closer and closer to identifying L. But as D is always finite and L can be infinite, it can still be expected that Ex- and BC-learning are often more difficult than performing this classification task. The paper supports this intuition and makes it precise, taking into account desirable constraints on how the learner behaves, such as bounding the number of mind changes and being conservative. Special attention is given to various forms of consistency. In particular, we might not only require consistency between the members of D to classify, the current data σ and a language L, but also consistency between larger sets of possible data to classify (supersets of D ) and the same σ and L: whereas in the classical paradigms of inductive inference or classification, only the available data can grow, here both the available data and the set of possible data to classify can grow. We provide a fairly comprehensive set of results, many of which are optimal, that demonstrate the fruitfulness of the approach and the richness of the paradigm.

I&C Journal 2012 Journal Article

Automatic learning of subclasses of pattern languages

• John Case
• Sanjay Jain
• Trong Dao Le
• Yuh Shin Ong
• Pavel Semukhin
• Frank Stephan

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.

TCS Journal 2011 Journal Article

Uncountable automatic classes and learning

• Sanjay Jain
• Qinglong Luo
• Pavel Semukhin
• Frank Stephan

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).

TCS Journal 2011 Journal Article

Universal recursively enumerable sets of strings

• Cristian S. Calude
• André Nies
• Ludwig Staiger
• Frank Stephan

The main topics of the present work are universal machines for plain and prefix-free description complexity and their domains. It is characterised when an r. e. set W is the domain of a universal plain machine in terms of the description complexity of the spectrum function s W mapping each non-negative integer n to the number of all strings of length n in W; furthermore, a characterisation of the same style is given for supersets of domains of universal plain machines. Similarly the prefix-free sets which are domains or supersets of domains of universal prefix-free machines are characterised. Furthermore, it is shown that the halting probability Ω V of an r. e. prefix-free set V containing the domain of a universal prefix-free machine is Martin-Löf random, while V may not be the domain of any universal prefix-free machine itself. Based on these investigations, the question whether every domain of a universal plain machine is the superset of the domain of some universal prefix-free machine is discussed. A negative answer to this question had been presented at CiE 2010 by Mikhail Andreev, Ilya Razenshteyn and Alexander Shen, while this paper was under review.

TCS Journal 2010 Journal Article

Iterative learning of simple external contextual languages

• Leonor Becerra-Bonache
• John Case
• Sanjay Jain
• Frank Stephan

It is investigated for which choice of a parameter q, denoting the number of contexts, the class of simple external contextual languages is iteratively learnable. On the one hand, the class admits, for all values of q, polynomial time learnability provided an adequate choice of the hypothesis space is given. On the other hand, additional constraints like consistency and conservativeness or the use of a one–one hypothesis space changes the picture — iterative learning limits the long term memory of the learner to the current hypothesis and these constraints further hinder storage of information via padding of this hypothesis. It is shown that if q > 3, then simple external contextual languages are not iteratively learnable using a class preserving one–one hypothesis space, while for q = 1 it is iteratively learnable, even in polynomial time. It is also investigated for which choice of the parameters the simple external contextual languages can be learnt by a consistent and conservative iterative learner.

TCS Journal 2009 Journal Article

Prescribed learning of r.e. classes

• Sanjay Jain
• Frank Stephan
• Nan Ye

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.

TCS Journal 2008 Journal Article

Absolute versus probabilistic classification in a logical setting

• Sanjay Jain
• Eric Martin
• Frank Stephan

Suppose we are given a set W of logical structures, or possible worlds, a set of logical formulas called possible data and a logical formula φ. We then consider the classification problem of determining in the limit and almost always correctly whether a possible world M satisfies φ, 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 φ for the members of the complement of W ′ in W. We compare these notions with absolute classification of W with respect to a formula that is almost always equivalent to φ in W, hence we 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.

I&C Journal 2008 Journal Article

Learning in Friedberg numberings

• Sanjay Jain
• Frank Stephan

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.

TCS Journal 2008 Journal Article

Preface

• Philip M. Long
• Frank Stephan

I&C Journal 2008 Journal Article

When unlearning helps

• Ganesh Baliga
• John Case
• Wolfgang Merkle
• Frank Stephan
• Rolf Wiehagen

Overregularization seen in child language learning, for example, verb tense constructs, involves abandoning correct behaviours for incorrect ones and later reverting to correct behaviours. Quite a number of other child development phenomena also follow this U-shaped form of learning, unlearning and relearning. A decisive learner does not do this and, more generally, never abandons an hypothesis H for an inequivalent one where it later conjectures an hypothesis equivalent to H, where equivalence means semantical or behavioural equivalence. The first main result of the present paper entails that decisiveness is a real restriction on Gold’s model of explanatory (or in the limit) learning of grammars for languages from positive data. This result also solves an open problem posed in 1986 by Osherson, Stob and Weinstein. Second-time decisive learners semantically conjecture each of their hypotheses for any language at most twice. By contrast, such learners are shown not to restrict Gold’s model of learning. Non U-shaped learning liberalizes the requirement of decisiveness from being a restriction on all hypotheses output to the same restriction but only on correct hypotheses. The situation regarding learning power for non U-shaped learning is a little more complex than that for decisiveness. This is explained shortly below. Gold’s original model for learning grammars from positive data, called EX-learning, requires, for success, syntactic convergence to a correct grammar. A slight variant, called BC-learning, requires only semantic convergence to a sequence of correct grammars that need not be syntactically identical to one another. The second main result says that non U-shaped learning does not restrict EX-learning. However, from an argument of Fulk, Jain and Osherson, non U-shaped learning does restrict BC-learning. In the final section is discussed the possible meaning, for cognitive science, of these results and, in this regard, indicated are some avenues worthy of future investigation.

TCS Journal 2007 Journal Article

Invertible classes

• Sanjay Jain
• Jochen Nessel
• Frank Stephan

This paper considers when one can invert general recursive operators which map a class of functions F to F. In this regard, we study four different notions of inversion. We additionally consider enumeration of operators which cover all general recursive operators which map F to F in the sense that, for every general recursive operator Ψ mapping F to F, there is a general recursive operator in the enumerated sequence which behaves the same way as Ψ on F. Three different possible types of enumeration are studied.

TCS Journal 2007 Journal Article

On the data consumption benefits of accepting increased uncertainty

• Eric Martin
• Arun Sharma
• Frank Stephan

In the context of learning paradigms of identification in the limit, we address the question: why is uncertainty sometimes desirable? We use mind change bounds on the output hypotheses as a measure of uncertainty and interpret ‘desirable’ as reduction in data memorization, also defined in terms of mind change bounds. The resulting model is closely related to iterative learning with bounded mind change complexity, but the dual use of mind change bounds — for hypotheses and for data — is a key distinctive feature of our approach. We show that situations exist where the more mind changes the learner is willing to accept, the less the amount of data it needs to remember in order to converge to the correct hypothesis. We also investigate relationships between our model and learning from good examples, set-driven, monotonic and strong-monotonic learners, as well as class-comprising versus class-preserving learnability.

I&C Journal 2007 Journal Article

Results on memory-limited U-shaped learning

• Lorenzo Carlucci
• John Case
• Sanjay Jain
• Frank Stephan

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.

TCS Journal 2006 Journal Article

Learning a subclass of regular patterns in polynomial time

• John Case
• Sanjay Jain
• Rüdiger Reischuk
• Frank Stephan
• Thomas Zeugmann

An algorithm for learning a subclass of erasing regular pattern languages is presented. On extended regular pattern languages generated by patterns π of the form x 0 α 1 x 1 … α m x m, where x 0, …, x m are variables and α 1, .. ., α m strings of terminals of length c each, it runs with arbitrarily high probability of success using a number of examples polynomial in m (and exponential in c). It is assumed that m is unknown, but c is known and that samples are randomly drawn according to some distribution, for which we only require that it has certain natural and plausible properties. Aiming to improve this algorithm further we also explore computer simulations of a heuristic.

TCS Journal 2006 Journal Article

On ordinal VC-dimension and some notions of complexity

• Eric Martin
• Arun Sharma
• Frank Stephan

We generalize the classical notion of Vapnik–Chernovenkis (VC) dimension to ordinal VC-dimension, in the context of logical learning paradigms. Logical learning paradigms encompass the numerical learning paradigms commonly studied in Inductive Inference. A logical learning paradigm is defined as a set W of structures over some vocabulary, and a set D of first-order formulas that represent data. The sets of models of ϕ in W, where ϕ varies over D, generate a natural topology W over W. We show that if D is closed under boolean operators, then the notion of ordinal VC-dimension offers a perfect characterization for the problem of predicting the truth of the members of D in a member of W, with an ordinal bound on the number of mistakes. This shows that the notion of VC-dimension has a natural interpretation in Inductive Inference, when cast into a logical setting. We also study the relationships between predictive complexity, selective complexity—a variation on predictive complexity—and mind change complexity. The assumptions that D is closed under boolean operators and that W is compact often play a crucial role to establish connections between these concepts. We then consider a computable setting with effective versions of the complexity measures, and show that the equivalence between ordinal VC-dimension and predictive complexity fails. More precisely, we prove that the effective ordinal VC-dimension of a paradigm can be defined when all other effective notions of complexity are undefined. On a better note, when W is compact, all effective notions of complexity are defined, though they are not related as in the noncomputable version of the framework.

TCS Journal 2006 Journal Article

Unifying logic, topology and learning in Parametric logic

• Éric Martin
• Arun Sharma
• Frank Stephan

Many connections have been established between learning and logic, or learning and topology, or logic and topology. Still, the connections are not at the heart of these fields. Each of them is fairly independent of the others when attention is restricted to basic notions and main results. We show that connections can actually be made at a fundamental level, and result in a logic with parameters that needs topological notions for its early developments, and notions from learning theory for interpretation and applicability. One of the key properties of first-order logic is that the classical notion of logical consequence is compact. We generalize the notion of logical consequence, and we generalize compactness to β -weak compactness where β is an ordinal. The effect is to stratify the set of generalized logical consequences of a theory into levels, and levels into layers. Deduction corresponds to the lower layer of the first level above the underlying theory, learning with less than β mind changes to layer β of the first level, and learning in the limit to the first layer of the second level. Refinements of Borel-like hierarchies provide the topological tools needed to develop the framework.

I&C Journal 2006 Journal Article

Variations on U-shaped learning

• Lorenzo Carlucci
• Sanjay Jain
• Efim Kinber
• Frank Stephan

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.

I&C Journal 2004 Journal Article

Classes with easily learnable subclasses

• Sanjay Jain
• Wolfram Menzel
• Frank Stephan

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.

I&C Journal 2004 Journal Article

Counting extensional differences in BC-learning

• Sanjay Jain
• Frank Stephan
• Sebastiaan A. Terwijn

Let BC be the model of behaviourally correct function learning as introduced by B a ̄ 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.

I&C Journal 2004 Journal Article

Generalized notions of mind change complexity

• Arun Sharma
• Frank Stephan
• Yuri Ventsov

Gold introduced the notion of learning in the limit where a class S is learnable iff there is a recursive machine M which reads the course of values of a function f and converges to a program for f whenever f is in S. An important measure for the speed of convergence in this model is the quantity of mind changes before the onset of convergence. The oldest model is to consider a constant bound on the number of mind changes M makes on any input function; such a bound is referred here as type 1. Later this was generalized to a bound of type 2 where a counter ranges over constructive ordinals and is counted down at every mind change. Although ordinal bounds permit the inference of richer concept classes than constant bounds, they still are a severe restriction. Therefore the present work introduces two more general approaches to bounding mind changes. These are based on counting by going down in a linearly ordered set (type 3) and on counting by going down in a partially ordered set (type 4). In both cases the set must not contain infinite descending recursive sequences. These four types of mind changes yield a hierarchy and there are identifiable classes that cannot be learned with the most general mind change bound of type 4. It is shown that existence of type 2 bound is equivalent to the existence of a learning algorithm which converges on every (also nonrecursive) input function and the existence of type 4 is shown to be equivalent to the existence of a learning algorithm which converges on every recursive function. A partial characterization of type 3 yields a result of independent interest in recursion theory. The interplay between mind change complexity and choice of hypothesis space is investigated. It is established that for certain concept classes, a more expressive hypothesis space can sometimes reduce mind change complexity of learning these classes. The notion of mind change bound for behaviourally correct learning is indirectly addressed by employing the above four types to restrict the number of predictive errors of commission in finite error next value learning (NV′′)—a model equivalent to behaviourally correct learning. Again, natural characterizations for type 2 and type 4 bounds are derived. Their naturalness is further illustrated by characterizing them in terms of branches of uniformly recursive families of binary trees.

TCS Journal 2004 Journal Article

Learning how to separate

• Sanjay Jain
• Frank Stephan

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.

I&C Journal 2004 Journal Article

On the classification of recursive languages

• John Case
• Efim Kinber
• Arun Sharma
• Frank Stephan

A one-sided classifier for a given class of languages converges to 1 on every language from the class and outputs 0 infinitely often on languages outside the class. A two-sided classifier, on the other hand, converges to 1 on languages from the class and converges to 0 on languages outside the class. The present paper investigates one-sided and two-sided classification for classes of recursive languages. Theorems are presented that help assess the classifiability of natural classes. The relationships of classification to inductive learning theory and to structural complexity theory in terms of Turing degrees are studied. Furthermore, the special case of classification from only positive data is also investigated.

I&C Journal 2003 Journal Article

Learning by switching type of information

• Sanjay Jain
• Frank Stephan

The present work is dedicated to the study of modes of data-presentation in the range between text and informant within the framework of inductive inference. In this study, the learner alternatingly requests sequences of positive and negative data. We define various formalizations of valid data presentations in such a scenario. We resolve the relationships between these different formalizations, and show that one of these is equivalent to learning from informant. We also show a hierarchy formed (for each of the formalizations studied) by considering the number of switches between requests for positive and negative data.

TCS Journal 2003 Journal Article

Learning power and language expressiveness

• Eric Martin
• Arun Sharma
• Frank Stephan

The topic of the present work is to study the relationship between the power of the learning algorithms on the one hand, and the expressive power of the logical language which is used to represent the problems to be learned on the other hand. The central question is whether enriching the language results in more learning power. In order to make the question relevant and nontrivial, it is required that both texts (sequences of data) and hypotheses (guesses) be translatable from the “rich” language into the “poor” one. The issue is considered for several logical languages suitable to describe structures whose domain is the set of natural numbers. It is shown that enriching the language does not give any advantage for those languages which define a monadic second-order language being decidable in the following sense: there is a fixed interpretation in the structure of natural numbers such that the set of sentences of this extended language true in that structure is decidable. But enriching the original language even by only one constant gives an advantage if this language contains a binary function symbol (which will be interpreted as addition). Furthermore, it is shown that behaviourally correct learning has exactly the same power as learning in the limit for those languages which define a monadic second-order language with the property given above, but has more power in case of languages containing a binary function symbol. Adding the natural requirement that the set of all structures to be learned is recursively enumerable, it is shown that it pays off to enrich the language of arithmetics for both finite learning and learning in the limit, but it does not pay off to enrich the language for behaviourally correct learning.

TCS Journal 2003 Journal Article

Refuting learning revisited

• Wolfgang Merkle
• Frank Stephan

We consider, within the framework of inductive inference, the concept of refuting learning as introduced by Mukouchi and Arikawa, where the learner is not only required to learn all concepts in a given class but also has to explicitly refute concepts outside the class. In the first part of the paper, we consider learning from text and introduce a concept of limit-refuting learning that is intermediate between refuting learning and reliable learning. We give characterizations for these concepts and show some results about their relative strength and their relation to confident learning. In the second part of the paper we consider learning from texts that for some k contain all positive Π k -formulae that are valid in the standard structure determined by the set to be learned. In this model, the following results are shown. For the language with successor, any countable axiomatizable class can be limit-refuting learned from Π 1-texts. For the language with successor and order, any countable axiomatizable class can be reliably learned from Π 1-texts and can be limit-refuting learned from Π 2-texts, whereas the axiomatizable class of all finite sets cannot be limit-refuting learned from Π 1-texts. For the full language of arithmetic, which contains in addition plus and times, for any even k there is an axiomatizable class that can be limit-refuting learned from Π k+1-texts but not from Π k -texts. A similar result with k+3 in place of k+1 holds with respect to the language of Presburger's arithmetic.

TCS Journal 2002 Journal Article

Avoiding coding tricks by hyperrobust learning

• Matthias Ott
• Frank Stephan

The present work introduces and justifies the notion of hyperrobust learning where one fixed learner has to learn all functions in a given class plus their images under primitive recursive operators. The following are shown: The notion of learnability does not change if the class of primitive recursive operators is replaced by a larger enumerable class of operators. A class is hyperrobustly Ex-learnable iff it is a subclass of a recursively enumerable family of total functions. So, the notion of hyperrobust learning overcomes a problem of the traditional definitions of robustness which either do not preserve learning by enumeration or still permit topological coding tricks for the learning criterion Ex. Hyperrobust BC-learning as well as the hyperrobust version of Ex-learning by teams are more powerful than hyperrobust Ex-learning. The notion of bounded totally reliable BC-learning is properly between hyperrobust Ex-learning and hyperrobust BC-learning. Furthermore, the bounded totally reliable BC-learnable classes are characterized in terms of infinite branches of certain enumerable families of bounded recursive trees. A class of infinite branches of another family of trees separates hyperrobust BC-learning from totally reliable BC-learning. Furthermore, the notion of hyperrobust learning aided by selected context turns out to be much more restrictive than its counterpart for robust learning.

TCS Journal 2002 Journal Article

Learning classes of approximations to non-recursive functions

• Frank Stephan
• Thomas Zeugmann

Blum and Blum (Inform. and Control 28 (1975) 125–155) showed that a class B of suitable recursive approximations to the halting problem K is reliably EX-learnable but left it open whether or not B is in NUM. By showing B to be not in NUM we resolve this old problem. Moreover, variants of this problem obtained by approximating any given recursively enumerable set A instead of the halting problem K are studied. All corresponding function classes U(A) are still EX-inferable but may fail to be reliably EX-learnable, for example if A is non-high and hypersimple. Blum and Blum (1975) considered only approximations to K defined by monotone complexity functions. We prove this condition to be necessary for making learnability independent of the underlying complexity measure. The class B ̃ of all recursive approximations to K generated by all total complexity functions is shown to be not even behaviorally correct learnable for a class of natural complexity measures. On the other hand, there are complexity measures such that B ̃ is EX-learnable. A similar result is obtained for all classes U ̃ (A). For natural complexity measures, B is shown to be not robustly learnable, but again there are complexity measures such that B and, more generally, every class U(A) is robustly EX-learnable. This result extends the criticism of Jain et al. (J. Comput. System Sci. 62(1) (2001) 178–212), since the classes defined by artificial complexity measures turn out to be robustly learnable while those defined by natural complexity measures are not robustly learnable.

I&C Journal 2002 Journal Article

Learning to Win Process-Control Games Watching Game-Masters

• John Case
• Matthias Ott
• Arun Sharma
• Frank Stephan

The present paper focuses on some interesting classes of process-control games, where winning essentially means successfully controlling the process. A master for one of these games is an agent who plays a winning strategy. In this paper we investigate situations in which even a complete model (given by a program) of a particular game does not provide enough information to synthesize—even incrementally—a winning strategy. However, if in addition to getting a program, a machine may also watch masters play winning strategies, then the machine is able to incrementally learn a winning strategy for the given game. Studied are successful learning from arbitrary masters and from pedagogically useful selected masters. It is shown that selected masters are strictly more helpful for learning than are arbitrary masters. Both for learning from arbitrary masters and for learning from selected masters, though, there are cases where one can learn programs for winning strategies from masters but not if one is required to learn a program for the master's strategy itself. Both for learning from arbitrary masters and for learning from selected masters, one can learn strictly more by watching m+1 masters than one can learn by watching only m. Last, a simulation result is presented where the presence of a selected master reduces the complexity from infinitely many semantic mind changes to finitely many syntactic ones.

TCS Journal 2001 Journal Article

Learning algebraic structures from text

• Frank Stephan
• Yuri Ventsov

The present work investigates the learnability of classes of substructures of some algebraic structures: submonoids and subgroups of given groups, ideals of given commutative rings, subfields of given vector spaces. The learner sees all positive data but no negative one and converges to a program enumerating or computing the set to be learned. Besides semantical (BC) and syntactical (Ex) convergence also the more restrictive ordinal bounds on the number of mind changes are considered. The following is shown: (a) Learnability depends much on the amount of semantic knowledge given at the synthesis of the learner where this knowledge is represented by programs for the algebraic operations, codes for prominent elements of the algebraic structure (like 0 and 1 fields) and certain parameters (like the dimension of finite-dimensional vector spaces). For several natural examples, good knowledge of the semantics may enable to keep ordinal mind change bounds while restricted knowledge may either allow only BC-convergence or even not permit learnability at all. (b) The class of all ideals of a recursive ring is BC-learnable iff the ring is Noetherian. Furthermore, one has either only a BC-learner outputting enumerable indices or one can already get an Ex-learner converging to decision procedures and respecting an ordinal bound on the number of mind changes. The ring is Artinian iff the ideals can be Ex-learned with a constant bound on the number of mind changes, this constant is the length of the ring. Ex-learnability depends not only on the ring but also on the representation of the ring. Polynomial rings over the field of rationals with n variables have exactly the ordinal mind change bound ωn in the standard representation. Similar results can be established for unars. Noetherian unars with one function can be learned with an ordinal mind change bound aω for some a.

TCS Journal 2001 Journal Article

Predictive learning models for concept drift

• John Case
• Sanjay Jain
• Susanne Kaufmann
• Arun Sharma
• Frank Stephan

Concept drift means that the concept about which data is obtained may shift from time to time, each time after some minimum permanence. Except for this minimum permanence, the concept shifts may not have to satisfy any further requirements and may occur infinitely often. Within this work is studied to what extent it is still possible to predict or learn values for a data sequence produced by drifting concepts. Various ways to measure the quality of such predictions, including martingale betting strategies and density and frequency of correctness, are introduced and compared with one another. For each of these measures of prediction quality, for some interesting concrete classes, (nearly) optimal bounds on permanence for attaining learnability are established. The concrete classes, from which the drifting concepts are selected, include regular languages accepted by finite automata of bounded size, polynomials of bounded degree, and sequences defined by recurrence relations of bounded size. Some important, restricted cases of drifts are also studied, for example, the case where the intervals of permanence are computable. In the case where the concepts shift only among finitely many possibilities from certain infinite, arguably practical classes, the learning algorithms can be considerably improved.

TCS Journal 2001 Journal Article

Robust learning with infinite additional information

• Susanne Kaufmann
• Frank Stephan

The present work investigates Gold-style algorithmic learning from input–output examples where the learner has access to oracles as additional information. This access is required to be robust in the sense that a single learning algorithm has to succeed with every oracle which meets a given specification. The first main result considers oracles of the same Turing degree: Robust learning with any oracle from a given degree does not achieve more than learning without any additional information. The further work considers learning from function oracles which describe the whole class of functions to be learned in one of the following five ways: as a list of all functions in this class, a predictor for this class, a one-sided classifier accepting just the functions in this class, an identifier for the class or a martingale succeeding on this class. It is shown that for learning in the limit (Ex), lists are the most powerful additional information, the powers of predictors and classifiers are incomparable and identifiers and martingales are of no help at all. Similar results are obtained for the criteria of predicting the next value, finite, Popperian and finite Popperian learning. Lists are omniscient for the criterion of predicting the next value and also identifiers are helpful at this criterion. So it turns out that algorithms to predict the next value can much better exploit robustly oracles than algorithms which give explanations (Ex-learning). For Ex-learning none of these five types of help is omniscient, that is, some classes cannot be Ex-learned with any of these types of additional information. The class REC of all recursive functions is Ex-learnable with the help of a list, a predictor or a classifier.

TCS Journal 2000 Journal Article

Structural measures for games and process control in the branch learning model

• Matthias Ott
• Frank Stephan

Process control problems can be modeled as closed recursive games. Learning strategies for such games is equivalent to the concept of learning infinite recursive branches for recursive trees. We use this branch learning model to measure the difficulty of learning and synthesizing process controllers. We also measure the difference between several process learning criteria, and their difference to controller synthesis. As measure we use the information content (i. e. , the Turing degree) of the oracle which a machine needs to get the desired power. The investigated learning criteria are finite, EX-, BC-, weak BC- and on-line learning. Finite, EX- and BC-style learning are well known from inductive inference, while weak BC- and on-line learning came up with the new notion of branch (i. e. , process) learning. For all considered criteria – including synthesis – we also solve the questions of their trivial degrees, their omniscient degrees and with some restrictions their inference degrees. While most of the results about finite, EX- and BC-style branch learning can be derived from inductive inference, new techniques had to be developed for on-line learning, weak BC-style learning and synthesis, and for the comparisons of all process learning criteria with the power of controller synthesis.

TCS Journal 2000 Journal Article

Vacillatory and BC learning on noisy data

• John Case
• Sanjay Jain
• Frank Stephan

The present work employs a model of noise introduced earlier by the third author. In this model noisy data nonetheless uniquely determines the true data: correct information occurs infinitely often while incorrect information occurs only finitely often. The present paper considers the effects of this form of noise on vacillatory and behaviorally correct learning of grammars – both from positive data alone and from informant (positive and negative data). For learning from informant, the noise, in effect, destroys negative data. Various noisy-data hierarchies are exhibited, which, in some cases, are known to collapse when there is no noise. Noisy behaviorally correct learning is shown to obey a very strong “subset principle”. It is shown, in many cases, how much power is needed to overcome the effects of noise. For example, the best we can do to simulate, in the presence of noise, the noise-free, no mind change cases takes infinitely many mind changes. One technical result is proved by a priority argument.

I&C Journal 1999 Journal Article

The Complexity of Universal Text-Learners

• Frank Stephan
• Sebastiaan A. Terwijn

The present work deals with language learning from text. It considers universal learners for classes of languages in models of additional information and analyzes their complexity in terms of Turing degrees. The following is shown: If the additional information is given by a set containing at least one index for each language from the class to be learned but no index for any language outside the class, then there is a universal learner having the same Turing degree as the inclusion problem for recursively enumerable sets. This result is optimal in the sense that any other successful learner has the same or higher Turing degree. If the additional information is given by the index set of the class of languages to be learned then there is a computable universal learner. Furthermore, if the additional information is presented as an upper bound on the size of some grammar that generates the language, then a high oracle is necessary and sufficient. Finally, it is shown that for the concepts of finite learning and learning from good examples, the index set of the class to be learned gives insufficient information due to the restrictive convergence constraints, these criteria need the jump of the index set instead of the index set itself. So, they have infinite access to the information of the index set in finite time.

TCS Journal 1998 Journal Article

On the relative sizes of learnable sets

• Lance Fortnow
• Rūsiņs̆ Freivalds
• William I. Gasarch
• Martin Kummer
• Stuart A. Kurtz
• Carl H. Smith
• Frank Stephan

Measure and category (or rather, their recursion-theoretical counterparts) have been used in theoretical computer science to make precise the intuitive notion “for most of the recursive sets”. We use the notions of effective measure and category to discuss the relative sizes of inferrible sets, and their complements. We find that inferable sets become large rather quickly in the standard hierarchies of learnability. On the other hand, the complements of the learnable sets are all large.

TCS Journal 1997 Journal Article

Noisy inference and oracles

• Frank Stephan

The present paper deals with several variants of inductive inference from noisy data. The notion of noise is based on the idea that the learner recieves a sequence of data elements such that each correct element appears infinitely often and each incorrect element appears at most finitely often. The main result is that the concept of learning in the limit from noisy informant has the same power as finite learning using a K-oracle from noise-free informant. The analog equality for text fails in general and holds only in one direction in the case of learning uniformly recursive families. Furthermore, learnability from noisy informant or text in presence of using oracles is investigated. It is shown that partial identification of all r. e. sets can also cope with noisy informant and text.