Average-Case Optimal 1-Variable Pattern Learner

Implementation for Interactive Learning

This page presents an implementation of an average case optimal learning algorithm for 1-variable pattern languages described in the technical report [1] and, in more polished form, in [3].
First, you may wish to see an animation of the algorithm (if you still use netscape 4.x, please click here).

Outline of the Algorithm

Receiving a sequence of example strings from an unknown 1-variable pattern language the algorithm computes a sequence of hypotheses that explain the samples seen. At any stage of the learning procedure the algorithm remembers the common prefix and suffix of all strings received so far plus a single appropriate example among them (that means it requires only constant space).

Starting the Interactive Learning

To test the algorithm choose a 1-variable pattern like abxbcaxxdad,
where a,b,c,d,... denote single letters (the constants) and x the pattern variable.
Then input a sequence of sample strings generated from this pattern,
for example replacing x by dag one gets the string abdagbcadagdagdad.

Each sample string can be entered in the marked box. After each string press the button Learn and the algorithm will answer with a new hypothesis. A correct hypothesis will be computed as soon as samples are provided that are generated from the pattern by substituting the pattern variable with a nonsymmetric string (that means x is not replaced by a string of the form y z y, where y,z are (nonempty) substrings - for precise definitions see the paper).

If You see this text, Your Browser doesn't support Java-Applets

You may also test a modified version of this algorithm with faster convergence in case of highly symmetric sample strings.

Bibliography

  1. Rüdiger Reischuk and Thomas Zeugmann
    Learning One-Variable Pattern Languages in Linear Average Time.
    Technical Report DOI-TR-140, Department of Informatics, Kyushu University, Fukuoka, Japan, September 1997.
    [Abstract] [Full Paper].
  2. R. Reischuk and T. Zeugmann, Learning One-Variable Pattern Languages in Linear Average Time, in ``Proc. 11th Annual Conference on Computational Learning Theory - COLT'98,'' July 24th - 26th, Madison, pp. 198 - 208, ACM Press 1998.
    [Abstract] [Full Paper].
  3. R. Reischuk and T. Zeugmann, An Average-Case Optimal One-Variable Pattern Language Learner, Journal of Computer and System Sciences Vol. 60, No. 2, 2000, 302-335. (Special Issue for COLT'98). [Abstract] [Full Paper].

Back Back to my Homepage

Implemented by Semen Gehman and Rüdiger Reischuk, and Thomas Zeugmann

Last change: November 1, 2004

Valid HTML 4.0!