Steffen Lange

JMLR Journal 2011 Journal Article

Models of Cooperative Teaching and Learning

• Sandra Zilles
• Steffen Lange
• Robert Holte
• Martin Zinkevich

While most supervised machine learning models assume that training examples are sampled at random or adversarially, this article is concerned with models of learning from a cooperative teacher that selects "helpful" training examples. The number of training examples a learner needs for identifying a concept in a given class C of possible target concepts (sample complexity of C ) is lower in models assuming such teachers, that is, "helpful" examples can speed up the learning process. The problem of how a teacher and a learner can cooperate in order to reduce the sample complexity, yet without using "coding tricks", has been widely addressed. Nevertheless, the resulting teaching and learning protocols do not seem to make the teacher select intuitively "helpful" examples. The two models introduced in this paper are built on what we call subset teaching sets and recursive teaching sets. They extend previous models of teaching by letting both the teacher and the learner exploit knowing that the partner is cooperative. For this purpose, we introduce a new notion of "coding trick"/"collusion". We show how both resulting sample complexity measures (the subset teaching dimension and the recursive teaching dimension ) can be arbitrarily lower than the classic teaching dimension and known variants thereof, without using coding tricks. For instance, monomials can be taught with only two examples independent of the number of variables. The subset teaching dimension turns out to be nonmonotonic with respect to subclasses of concept classes. We discuss why this nonmonotonicity might be inherent in many interesting cooperative teaching and learning scenarios. [abs] [ pdf ][ bib ] &copy JMLR 2011. ( edit, beta )

TCS Journal 2010 Journal Article

Incremental learning with temporary memory

• Sanjay Jain
• Steffen Lange
• Samuel E. Moelius
• Sandra Zilles

In the inductive inference framework of learning in the limit, a variation of the bounded example memory ( Bem ) language learning model is considered. Intuitively, the new model constrains the learner’s memory not only in how much data may be stored, but also in how long those data may be stored without being refreshed. More specifically, the model requires that, if the learner commits an example x to memory, and x is not presented to the learner again thereafter, then eventually the learner forgets x, i. e. , eventually x no longer appears in the learner’s memory. This model is called temporary example memory ( Tem ) learning. Many interesting results concerning the Tem -learning model are presented. For example, there exists a class of languages that can be identified by memorizing k + 1 examples in the Tem sense, but that cannot be identified by memorizing k examples in the Bem sense. On the other hand, there exists a class of languages that can be identified by memorizing just one example in the Bem sense, but that cannot be identified by memorizing any number of examples in the Tem sense. Results are also presented concerning the special case of learning classes of infinite languages.

TCS Journal 2008 Journal Article

Learning indexed families of recursive languages from positive data: A survey

• Steffen Lange
• Thomas Zeugmann
• Sandra Zilles

In the past 40 years, research on inductive inference has developed along different lines, e. g. , in the formalizations used, and in the classes of target concepts considered. One common root of many of these formalizations is Gold’s model of identification in the limit. This model has been studied for learning recursive functions, recursively enumerable languages, and recursive languages, reflecting different aspects of machine learning, artificial intelligence, complexity theory, and recursion theory. One line of research focuses on indexed families of recursive languages — classes of recursive languages described in a representation scheme for which the question of membership for any string in any of the given languages is effectively decidable with a uniform procedure. Such language classes are of interest because of their naturalness. The survey at hand picks out important studies on learning indexed families (including basic as well as recent research), summarizes and illustrates the corresponding results, and points out links to related fields such as grammatical inference, machine learning, and artificial intelligence in general.

TCS Journal 2007 Journal Article

A general comparison of language learning from examples and from queries

• Sanjay Jain
• Steffen Lange
• Sandra Zilles

In language learning, strong relationships between Gold-style models and query models have recently been observed: in some quite general setting Gold-style learners can be replaced by query learners and vice versa, without loss of learning capabilities. These ‘equalities’ hold in the context of learning indexable classes of recursive languages. Former studies on Gold-style learning of such indexable classes have shown that, in many settings, the enumerability of the target class and the recursiveness of its languages are crucial for learnability. Moreover, studying query learning, non-indexable classes have been mainly neglected up to now. So it is conceivable that the recently observed relations between Gold-style and query learning are not due to common structures in the learning processes in both models, but rather to the enumerability of the target classes or the recursiveness of their languages. In this paper, the analysis is lifted onto the context of learning arbitrary classes of recursively enumerable languages. Still, strong relationships between the approaches of Gold-style and query learning are proven, but there are significant changes to the former results. Though in many cases learners of one type can still be replaced by learners of the other type, in general this does not remain valid vice versa. All results hold even for learning classes of recursive languages, which indicates that the recursiveness of the languages is not crucial for the former ‘equality’ results. Thus we analyze how constraints on the algorithmic structure of the target class affect the relations between two approaches to language learning.

I&C Journal 2007 Journal Article

Some natural conditions on incremental learning

• Sanjay Jain
• Steffen Lange
• Sandra Zilles

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.

TCS Journal 2005 Journal Article

Inductive inference of approximations for recursive concepts

• Steffen Lange
• Gunter Grieser
• Thomas Zeugmann

This paper provides a systematic study of inductive inference of indexable concept classes in learning scenarios where the learner is successful if its final hypothesis describes a finite variant of the target concept, i. e. , learning with anomalies. Learning from positive data only and from both positive and negative data is distinguished. The following learning models are studied: learning in the limit, finite identification, set-driven learning, conservative inference, and behaviorally correct learning. The attention is focused on the case that the number of allowed anomalies is finite but not a priori bounded. However, results for the special case of learning with an a priori bounded number of anomalies are presented, too. Characterizations of the learning models with anomalies in terms of finite tell-tale sets are provided. The observed varieties in the degree of recursiveness of the relevant tell-tale sets are already sufficient to quantify the differences in the corresponding learning models with anomalies. Finally, a complete picture concerning the relations of all models of learning with and without anomalies mentioned above is derived.

TCS Journal 2005 Journal Article

Learning erasing pattern languages with queries

• Jochen Nessel
• Steffen Lange

A pattern is a finite string of constant and variable symbols. The non-erasing language generated by a pattern is the set of all strings of constant symbols that can be obtained by substituting non-empty strings for variables. In order to build the erasing language generated by a pattern, it is also admissible to substitute the empty string. The present paper deals with the problem of learning erasing pattern languages within Angluin's model of learning with queries. Moreover, the learnability of erasing pattern languages with queries is studied when additional information is available. The results obtained are compared with previously known results in case non-erasing pattern languages have to be learned. First, when regular pattern languages have to be learned, it is shown that the learnability results for the non-erasing case remain valid, if the proper superclass of all erasing regular pattern languages is the object of learning. Second, in the general case, serious differences have been observed. For instance, it turns out that arbitrary erasing pattern languages cannot be learned in settings in which, in the non-erasing case, even polynomially many queries will suffice.

I&C Journal 2005 Journal Article

Relations between Gold-style learning and query learning

• Steffen Lange
• Sandra Zilles

Different formal learning models address different aspects of human learning. Below we compare Gold-style learning—modelling learning as a limiting process in which the learner may change its mind arbitrarily often before converging to a correct hypothesis—to learning via queries—modelling learning as a one-shot process in which the learner is required to identify the target concept with just one hypothesis. In the Gold-style model considered below, the information presented to the learner consists of positive examples for the target concept, whereas in query learning, the learner may pose a certain kind of queries about the target concept, which will be answered correctly by an oracle (called teacher). Although these two approaches seem rather unrelated at first glance, we provide characterisations of different models of Gold-style learning (learning in the limit, conservative inference, and behaviourally correct learning) in terms of query learning. Thus we describe the circumstances which are necessary to replace limit learners by equally powerful one-shot learners. Our results are valid in the general context of learning indexable classes of recursive languages. This analysis leads to an important observation, namely that there is a natural query learning type hierarchically in-between Gold-style learning in the limit and behaviourally correct learning. Astonishingly, this query learning type can then again be characterised in terms of Gold-style inference.

TCS Journal 2003 Journal Article

Advanced elementary formal systems

• Steffen Lange
• Gunter Grieser
• Klaus P. Jantke

An elementary formal system (EFS) is a logic program such as a Prolog program, for instance, that directly manipulates strings. Arikawa and his co-workers proposed elementary formal systems as a unifying framework for formal language learning. In the present paper, we introduce advanced elementary formal systems (AEFSs), i. e. , elementary formal systems which allow for the use of a certain kind of negation, which is nonmonotonic, in essence, and which is conceptually close to negation as failure. We study the expressiveness of this approach by comparing certain AEFS definable language classes to the levels in the Chomsky hierarchy and to the language classes that are definable by EFSs that meet the same syntactical constraints. Moreover, we investigate the learnability of the corresponding AEFS definable language classes in two major learning paradigms, namely in Gold's model of learning in the limit and Valiant's model of probably approximately correct learning. In particular, we show which learnability results achieved for EFSs extend to AEFSs and which do not.

TCS Journal 2003 Journal Article

Decision lists over regular patterns

• Steffen Lange
• Jochen Nessel

The paper introduces the notion of decision lists over regular patterns. This formalism provides a strict extension of regular erasing pattern languages and of containment decision lists. Formal properties of the resulting language class, a subclass of the regular languages, are investigated. In particular, we show that decision lists over regular patterns have exactly the same expressive power as decision trees over regular patterns. Moreover, we study the learnability of the resulting language class within different formal settings including Gold's model of learning in the limit as well as Valiant's model of approximately correct learning.

TCS Journal 2003 Journal Article

Variants of iterative learning

• Steffen Lange
• Gunter Grieser

We investigate the principal learning capabilities of iterative learners in some more details. Thereby, we confine ourselves to study the learnability of indexable concept classes. The general scenario of iterative learning is as follows. An iterative learner successively takes as input one element of a text (an informant) for a target concept as well as its previously made hypothesis and outputs a new hypothesis about the target concept. The sequence of hypotheses has to converge to a hypothesis correctly describing the target concept. We study two variants of this basic scenario and compare the learning capabilities of all resulting models of iterative learning to one another as well to the standard learning models finite inference, conservative identification, and learning in the limit. First, we consider the case that an iterative learner has to learn from fat texts (fat informants), only. In this setting, it is guaranteed that relevant information is, in principle, accessible at any time in the learning process. Second, we study a variant of iterative learning, where an iterative learner is supposed to learn no matter which initial hypothesis is actually chosen. This variant is suited to describe scenarios that are typical for case-based reasoning.

TCS Journal 2002 Journal Article

On the power of incremental learning

• Steffen Lange
• Gunter Grieser

This paper provides a systematic study of incremental learning from noise-free and from noisy data. As usual, we distinguish between learning from positive data and learning from positive and negative data, synonymously called learning from text and learning from informant. Our study relies on the notion of noisy data introduced by Stephan. The basic scenario, named iterative learning, is as follows. In every learning stage, an algorithmic learner takes as input one element of an information sequence for some target concept and its previously made hypothesis and outputs a new hypothesis. The sequence of hypotheses has to converge to a hypothesis describing the target concept correctly. We study the following refinements of this basic scenario. Bounded example-memory inference generalizes iterative inference by allowing an iterative learner to additionally store an a priori bounded number of carefully chosen data elements, while feedback learning generalizes it by allowing the iterative learner to additionally ask whether or not a particular data element did already appear in the input data seen so far. For the case of learning from noise-free data, we show that, when both positive and negative data are available, restrictions on the accessibility of the input data do not limit the learning capabilities if and only if the relevant iterative learners are allowed to query the history of the learning process or to store at least one carefully selected data element. This insight nicely contrasts the fact that, in case only positive data are available, restrictions on the accessibility of the input data seriously affect the learning capabilities of all versions of incremental learners. For the case of learning from noisy data, we present characterizations of all kinds of incremental learning in terms being independent from learning theory. The relevant conditions are purely structural ones. Surprisingly, when learning from noisy text and noisy informant is concerned, even iterative learners are exactly as powerful as unconstrained learning devices.

TCS Journal 2001 Journal Article

On the learnability of recursively enumerable languages from good examples

• Sanjay Jain
• Steffen Lange
• Jochen Nessel

The present paper investigates identification of indexed families L of recursively enumerable languages from good examples. We distinguish class-preserving learning from good examples (the good examples have to be generated with respect to a hypothesis space having the same range as L ) and class-comprising learning from good examples (the good examples have to be selected with respect to a hypothesis space comprising the range of L ). A learner is required to learn a target language on every finite superset of the good examples for it. If the learner's first and only conjecture is correct then the underlying learning model is referred to as finite identification from good examples and if the learner makes a finite number of incorrect conjectures before always outputting a correct one, the model is referred to as limit identification from good examples. In the context of class-preserving learning, it is shown that the learning power of finite and limit identification from good text examples coincide. When class comprising learning from good text examples is concerned, limit identification is strictly more powerful than finite learning. Furthermore, if learning from good informant examples is considered, limit identification is superior to finite identification in the class preserving as well as in the class-comprising case. Finally, we relate the models of learning from good examples to one another as well as to the standard learning models in the context of Gold-style language learning.

TCS Journal 2000 Journal Article

Learning languages and functions by erasing

• Sanjay Jain
• Efim Kinber
• Steffen Lange
• Rolf Wiehagen
• Thomas Zeugmann

Learning by erasing means the process of eliminating potential hypotheses from further consideration thereby converging to the least hypothesis never eliminated. This hypothesis must be a solution to the actual learning problem. The capabilities of learning by erasing are investigated in relation to two factors: the choice of the overall hypothesis space itself and what sets of hypotheses must or may be erased. These learning capabilities are studied for two fundamental kinds of objects to be learned, namely languages and functions. For learning languages by erasing, the case of learning indexed families is investigated. A complete picture of all separations and coincidences of the considered models is derived. Learning by erasing is compared with standard models of language learning such as learning in the limit, finite learning and conservative learning. The exact location of these types within the hierarchy of the models of learning by erasing is established. Necessary and sufficient conditions for language learning by erasing are presented. For learning functions by erasing, mainly the case of learning minimal programs is studied. Various relationships and differences between the considered types of function learning by erasing and also to standard function learning are exhibited. In particular, these types are explored in Kolmogorov numberings that can be viewed as natural Gödel numberings of the partial recursive functions. Necessary and sufficient conditions for function learning by erasing are derived.

I&C Journal 1999 Journal Article

Incremental Concept Learning for Bounded Data Mining

• John Case
• Sanjay Jain
• Steffen Lange
• Thomas Zeugmann

Important refinements of concept learning in the limit from positive data considerably restricting the accessibility of input data are studied. Let c be any concept; every infinite sequence of elements exhausting c is called positive presentation of c. In all learning models considered the learning machine computes a sequence of hypotheses about the target concept from a positive presentation of it. With iterative learning, the learning machine, in making a conjecture, has access to its previous conjecture and the latest data items coming in. In k-bounded example-memory inference (k is a priori fixed) the learner is allowed to access, in making a conjecture, its previous hypothesis, its memory of up to k data items it has already seen, and the next element coming in. In the case of k-feedback identification, the learning machine, in making a conjecture, has access to its previous conjecture, the latest data item coming in, and, on the basis of this information, it can compute k items and query the database of previous data to find out, for each of the k items, whether or not it is in the database (k is again a priori fixed). In all cases, the sequence of conjectures has to converge to a hypothesis correctly describing the target concept. Our results are manyfold. An infinite hierarchy of more and more powerful feedback learners in dependence on the number k of queries allowed to be asked is established. However, the hierarchy collapses to 1-feedback inference if only indexed families of infinite concepts are considered, and moreover, its learning power is then equal to learning in the limit. But it remains infinite for concept classes of only infinite r. e. concepts. Both k-feedback inference and k-bounded example-memory identification are more powerful than iterative learning but incomparable to one another. Furthermore, there are cases where redundancy in the hypothesis space is shown to be a resource increasing the learning power of iterative learners. Finally, the union of at most k pattern languages is shown to be iteratively inferable.

ECAI Conference 1996 Conference Paper

Case-Based Representability of Classes of Boolean Functions

• Christoph Globig
• Steffen Lange

TCS Journal 1996 Journal Article

Monotonic and dual monotonic language learning

• Steffen Lange
• Thomas Zeugmann
• Shyam Kapur

Monotonic and dual monotonic language learning from positive as well as from positive and negative examples is investigated. Three different notions of monotonicity are considered. Each of them reflects an alternative formalization of the requirement that the learner has to produce better and better generalizations when fed more and more data on the concept to be learned. Strong-monotonicity absolutely requires that only better and better generalizations be produced. Monotonic learning reflects the demand that for any two guesses the one output later has to be, with respect to the target language, at least as good as the earlier one. Weak-monotonicity is the analogue in learning theory of cumulativity. The corresponding three versions of dual monotonicity describe the requirement that the inference device only produces specializations that fit the target language better and better. Dual strong-monotonic learning generates a chain of shrinking specializations converging to the target language. Dual monotonicity describes the same goal with respect to the target language and dual weak-monotonic learning is the analogue of the dual of cumulativity. The power of each of these types of monotonic and dual monotonic inference from positive as well as from positive and negative data in the context of algorithmic language learning theory is completely investigated, thereby obtaining strong hierarchies.

TCS Journal 1995 Journal Article

Case-based representation and learning of pattern languages

• Klaus P. Jantke
• Steffen Lange

Pattern languages seem to suit case-based reasoning particularly well. Therefore, the problem of inductively learning pattern languages is paraphrased in a case-based manner. A careful investigation requires a formal semantics for case bases together with similarity measures in terms of formal languages. Two basic semantics are introduced and investigated. It turns out that representability problems are major obstacles for case-based learnability. Restricting the attention to the so-called proper patterns avoids these representability problems. A couple of learnability results for proper pattern languages are derived both for case-based learning from only positive data and for case-based learning from positive and negative data. Under the so-called competing semantics, we show that the learnability result for positive and negative data can be lifted to the general case of arbitrary patterns. Learning under the standard semantics from positive data is closely related to monotonic language learning.