Information Technology Reference
In-Depth Information
To see this more explicitly, let us have a closer look at the example of figure 5
where the string of length l =6is abacac and the pattern constructed so far is
x 1 x 2 x 3 x 4 x 1 x 3 . The string differs in its 3rd and its 6th position, but the pattern
does not. Hence, abacac /
L ( x 1 x 2 x 3 x 4 x 1 x 3 ).
The variable x 3 appearing in two different positions has to be split into x 3 and
x 5 to match s . The resulting pattern is x 1 x 2 x 3 x 4 x 1 x 5 . To fit as close as possible,
this pattern is specialized to x 1 cx 3 bx 1 x 5 and finally normalized to x 1 cx 2 bx 1 x 3 .
Missing algorithmic details are described below.
To sum up, the Lange/Wiehagen algorithm with Jantke/Grieser refinement
shortly named
A returns on the input pattern p = ax 1 x 2 x 3 cx 4 bbax 1 x 2 x 3 x 4 b
and the input string acabac the new hypothesis x 1 cx 2 bx 1 x 3 .
The procedure performed after annotation of the input pattern is as follows.
Note that there are exactly l substrings, where l is the length of the input string s .
Consequently, every substring corresponds to a uniquely defined position in s .
1. Take the pattern p and replace every string annotated by some number i
simply by the one variable x i .
2. For every x i representing a substring of length 1, i.e. some letter z ,check
whether at all the corresponding position in s , the same letter z does occur.
If so, substitute x i by z .
3. For every x i , look at all occurrences and check whether or not all corre-
spondig letters in s are identical. If not, split the variable until all occurrences
of the same variable relate to identical letters in s .
4. Rename variables from left to right to get a canonical pattern.
Step 2 is specialization and step 3 is generalization. The order of both may be
changed, i.e. there is some inherent nondeterminism. This completes
A .
A in case [J/Gii] does the
following: (i) generalizing p by some pattern of the length of s , (ii) generalizing
to match string s as well, (iii) specializing to fit string s as close as possible, and
(iv) normalizing.
At this point of discussion, the reader knows a bit about patterns a la Angluin,
about the pattern learning problem, about its computational complexity, and
about the algorithms and algorithmic variants, respectively, named
Seen from a bird's eye view, the refined algorithm
A ,and
A
,
A .
There is no doubt about the relevance of formulas, flowcharts and other formal
descriptions for specifying algorithms in depth and detail. In particular, when
variants of algorithms are distinguished by subtle details, nothing competes for-
malisms. Nevertheless, the mastery of algorithms means more than knowing
about details. It covers some feeling for the algorithms' behavior, some experi-
ence, and some familiarity as well. To gain this requires much doing.
By means of the following subsection 4.3, we return to the issue of technology
enhanced learning. The exclusive purpose of the lengthy and rather detailed
investigation above into some particular learning domain is to firmly lay some
cornerstone for the discussion of learning with emphasis on direct execution and
on ideas for playful exploration.
 
Search WWH ::




Custom Search