1-Variable Pattern Learner
Original Version, Animation
This page presents an animation
of an average case optimal learning algorithm for 1-variable pattern languages
firstly described in the technical report [1]
and in more polished form in the article [3].
To use a modified algorithm with faster convergence, click
here.
We also have modified algorithms that can handle
empty substitutions, too. They are provided
here.
If you want to test the algorithm actively
by providing your own inputs, you may use this
applet (if you still use netscape 4.x, please
click
here).
Outline of the Algorithm
Receiving a sequence of sample 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 Animation
Before starting the algorithm one has to choose
the size of the alphabet
{a,b,c,...} of the pattern language, which has to be at least 2,
a 1-variable pattern p, for example
abxbcaxxdad,
where x denotes the pattern variable, and
a probability distribution
for substituting appearances of the pattern variable x
in p
by a string w
over the pattern alphabet.
To visualize the probability distribution this animation has to limit the maximal size
of the alphabet as specifed below.
Distributions
For the length uniform distribution the length of
w is allowed to vary between 1 and 24.
This value is probabilistically chosen according to weights.
To each possible length assign as weight a natural number between 0 and 10
(the default is 0, but at least one weight should be positive).
The weights define the frequency by which each specific length is chosen
(the fraction between an individual weight and the sum of all weights gives its
probability).
The maximal alphabet size is 10.
For each new sample string after having selected a length
the animation then will probabilistically select
a string of this length over the chosen alphabet with uniform probability.
In the Markov chain distribution the substitution string
w is generated by a random walk in the alphabet.
You may choose weights for the transitions between the letters of the alphabet.
(NOTE: the transition graph derived from the positive weights should have
the property that the random walk will eventually reach the final state with probability 1.
This animation will not check this property and thus will be trapped if you choose
unsuitable weights).
The maximal alphabet size is 4.
In case of a symmetric distribution
you may also choose weights for the
k-symmetries of a substitution
w
(that means w = yk z yk
for substrings y, z - for details see the paper).
k runs from 0 to 6.
(NOTE: If you give weight 0 to the case k=0 it will imply that only symmetric substitutions
occur. In this case any algorithm (including this one) may not be able to deduce the
correct hypothesis because it does not get enough information about the pattern language.)
y and z
will be chosen length uniform with a maximal length 6.
The maximal alphabet size is 5 in this case.
| 
Back to my
Homepage
