Author name cluster

Samuel E. Moelius

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

TCS Journal 2013 Journal Article

Learning without coding

Sanjay Jain
Samuel E. Moelius
Sandra Zilles

Iterative learning is a model of language learning from positive data, due to Wiehagen. When compared to a learner in Gold’s original model of language learning from positive data, an iterative learner can be thought of as memory-limited. However, an iterative learner can memorize some input elements by coding them into the syntax of its hypotheses. A main concern of this paper is: to what extent are such coding tricks necessary? One means of preventing some such coding tricks is to require that the hypothesis space used be free of redundancy, i. e. , that it be 1–1. In this context, we make the following contributions. By extending a result of Lange and Zeugmann, we show that many interesting and non-trivial classes of languages can be iteratively identified using a Friedberg numbering as the hypothesis space. (Recall that a Friedberg numbering is a 1–1 effective numbering of all computably enumerable sets.) An example of such a class is the class of pattern languages over an arbitrary alphabet. On the other hand, we show that there exists an iteratively identifiable class of languages that cannot be iteratively identified using any 1–1 effective numbering as the hypothesis space. We also consider an iterative-like learning model in which the computational component of the learner is modeled as an enumeration operator, as opposed to a partial computable function. In this new model, there are no hypotheses, and, thus, no syntax in which the learner can encode what elements it has or has not yet seen. We show that there exists a class of languages that can be identified under this new model, but that cannot be iteratively identified. On the other hand, we show that there exists a class of languages that cannot be identified under this new model, but that can be iteratively identified using a Friedberg numbering as the hypothesis space.

Details DOI

I&C Journal 2011 Journal Article

Optimal language learning from positive data

John Case
Samuel E. Moelius

Goldʼs original paper on inductive inference introduced a notion of an optimal learner. Intuitively, a learner identifies a class of objects optimally iff there is no other learner that: requires as little of each presentation of each object in the class in order to identify that object, and, for some presentation of some object in the class, requires less of that presentation in order to identify that object. Beick considered this notion in the context of function learning, and gave an intuitive characterization of an optimal function learner. Jantke and Beick subsequently characterized the classes of functions that are algorithmically, optimally identifiable. Herein, Goldʼs notion is considered in the context of language learning. It is shown that a characterization of optimal language learners analogous to Beickʼs does not hold. It is also shown that the classes of languages that are algorithmically, optimally identifiable cannot be characterized in a manner analogous to that of Jantke and Beick. Other interesting results concerning optimal language learning include the following. It is shown that strong non-U-shapedness, a property involved in Beickʼs characterization of optimal function learners, does not restrict algorithmic language learning power. It is also shown that, for an arbitrary optimal learner F of a class of languages L, F optimally identifies a subclass K of L iff F is class-preserving with respect to K.

Details DOI

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.

Details DOI

TCS Journal 2009 Journal Article

Parallelism increases iterative learning power

John Case
Samuel E. Moelius

Iterative learning ( It -learning) is a Gold-style learning model in which each of a learner’s output conjectures may depend only upon the learner’s current conjecture and the current input element. Two extensions of the It -learning model are considered, each of which involves parallelism. The first is to run, in parallel, distinct instantiations of a single learner on each input element. The second is to run, in parallel, n individual learners incorporating the first extension, and to allow the n learners to communicate their results. In most contexts, parallelism is only a means of improving efficiency. However, as shown herein, learners incorporating the first extension are more powerful than It -learners, and, collective learners resulting from the second extension increase in learning power as n increases. Attention is paid to how one would actually implement a learner incorporating each extension. Parallelism is the underlying mechanism employed.

Details DOI

MFCS Conference 2007 Conference Paper

Properties Complementary to Program Self-reference

John Case
Samuel E. Moelius

Abstract In computability theory, program self-reference is formalized by the not-necessarily-constructive form of Kleene’s Recursion Theorem ( krt ). In a programming system in which krt holds, for any preassigned, algorithmic task, there exists a program that, in a sense, creates a copy of itself, and then performs that task on the self-copy. Herein, properties complementary to krt are considered. Of particular interest are those properties involving the implementation of control structures. One main result is that no property involving the implementation of denotational control structures is complementary to krt. This is in contrast to a result of Royer, which showed that implementation of if-then-else — a denotational control structure — is complementary to the constructive form of Kleene’s Recursion Theorem. Examples of non -denotational control structures whose implementation is complementary to krt are then given. Some such control structures so nearly resemble denotational control structures that they might be called quasi-denotational.

Details