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  and, in more polished form,
Outline of the AlgorithmReceiving 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 LearningTo 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).
You may also test a modified version of this algorithm with faster convergence in case of highly symmetric sample strings.
Back to my Homepage
Implemented by Semen Gehman and Rüdiger Reischuk, and Thomas Zeugmann
Last change: November 1, 2004