Average-Case Optimal 1-Variable Pattern Language Learning Algorithm I
This page presents an implementation
of a learning algorithm first described in
the technical report [1] and, in more polished form,
in [3].
Receiving a sequence of example strings from an unknown 1-variable pattern language the algorithm computes a sequence of hypotheses that explain the examples 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
where a,b,c,d,...
denote single letters (the constants) and
x the pattern variable.
Each example 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 examples 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 example strings.
Bibliography
Back to my Homepage
Implemented by Semen Gehman and Rüdiger Reischuk. Last change: November 1, 2004 |