Information Technology Reference
In-Depth Information
4 Direct Execution for Exploratory Games
In contrast to the other sections of this paper, the present section goes into
some more detail of, so to speak, foreign content. In practice it is known that
it is dicult to discuss details of didactics without some understanding of the
learning contents and goals. For the particular idea of learning certain algorithms
and variations of them in a playful manner, having some clue of the underlying
algorithmic ideas is inevitable for pondering didactic concepts.
4.1 The Problem Domain of Pattern Inference
Dana Angluin [2] introduced her seminal pattern concept concisely, formalized
an unprecedentedly clear concept of learning patterns, and developed learning
algorithms including deeper insights into the algorithmic complexity of learning
patterns. Because patterns in many application domains such as research into
media impact, in general, and into the impact of game playing, in particular,
are more expressive and of higher complexity than Dana Angluin's concepts, her
results may serve, so to speak, as lower estimates of the problems one is facing
in those application domains. Saying it laxly, what is complex in Dana Angluin's
setting is at least of the same complexity in those applications, and what does
not work in Dana Angluin's setting will never work in those applications.
Assume any finite, not empty alphabet
M
and any set of variables
X
,where
it is practically relevant that both are disjoint, i.e.
M
∩
X
=
∅
. For readability,
. For any set
A
,
A
+
denotes the set of all finite,
but not empty strings f symbols from
A
.
P
=(
M
we choose
X
=
{
x
1
,x
2
,x
3
,...
}
X
)
+
is the set of patterns
∪
P
allows for generating string of
M
+
by substituting for each variable in
p
some string from
M
+
. Seen in its right
perspective, every pattern
p
is a grammar of some formal language named
L
(
p
).
For investigations into learning patterns from examples, some notions and
notations are usefull.
If
s
and
t
are two strings or patterns, the notation
s t
indicates the
s
is
an initial segment of
t
, not necessarily a proper one. The notation
s
under consideration. Every pattern
p
∈
⊆
t
means
s
∈
M
∗
:
ss
=
t
.
that
s
occursasasubstringof
t
. More formally,
s
t
means
∃
M
∗
:
s
ss
=
t
.
For two given patterns
p
and
q
, it is helpful to be able to describe their
comparable expressiveness.
p
s
,s
∈
Similarly,
s
⊆
t
means
∃
q
means that
q
is similarly expressive or more
expressive than
p
which means in formal terms
L
(
p
)
⊆
L
(
q
). Accordingly,
p
≺
q
means
L
(
p
)
L
(
q
).
The latter terminology is useful, for instance, to specify what it means that
some pattern
p
isabestfittosomesampleset
S
⊂
M
+
formalized as follows:
⊆
S
L
(
p
). Dana Angluin [2] calls a pattern which fits
some sample best being
descriptive of the sample
. Note that patterns may be
seen as generalizations of sets of strings. Thus, for every sample
S
⊆
L
(
p
)
∧¬∃
q
:
S
⊆
L
(
q
)
⊂
M
+
,any
⊆
pattern
p
with
S
L
(
p
) is a generalization. If
p
is descriptive of
S
, it turns out
to be some
least general generalization
.
⊆
