Information Technology Reference
In-Depth Information
Unfortunately, both the problem of computing
descr
and the problem of decid-
ing consistency are NP-hard [2]. The crux is that the decision problem “
s
L
(
p
)
?” for any string
s
and any pattern
p
is even NP-complete. There is an ingenious
proof of NP-completeness by reduction of the SAT problem in [2].
∈
The Algorithm of Lange and Wiehagen.
Rolf Wiehagen when pondering
the question for
best examples
when learning from positive data has pointed out
that for learning patterns it is sucient to process only the shortest examples.
This insight lead to some algorithm published in [23] which will be subsequently
briefly called the Lange/Wiehagen algorithm.
The Lange/Wiehagen algorithm solves the problem of learning patterns in
polynomial time. This surprising result is possible by giving up consistency-
not every intermediate hypothesis is able to generate the data on which it has
been generated. Although some of the intermediate hypotheses output by the
Lange/Wiehagen algorithm appear useless and do not reflect much of the process
of learning so far, the process as a whole always converges to a correct solution.
A
is used to denote the Lange/Wiehagen algorithm. Its subsequent outputs
on some input sequence
s
1
,
s
2
, ... are named
p
1
,
p
2
,... asbefore.
p
1
=
s
1
⎧
⎨
p
n
if
|
p
n
|
<
|
s
n
+1
|
[L/W i]
p
n
+1
=
s
n
+1
if
|
p
n
|
>
|
s
n
+1
|
[L/W ii]
⎩
[L/W iii]
The procedure
lgg
computes some least general generalization of the current
hypothesis
p
n
and the presented new instance
s
n
+1
.
This computation is quite easy, because both inputs are of the same length.
For specifying
lgg
, it is helpful to assume two local variables, i.e. internal short
term memories. These are some counter
c
to hold the value of the currently used
largest variable index and some storage of temporary variable assignments
VA
.
The initial settings are
c
=0and
VA
=
lgg
(
p
n
,s
n
+1
)
if
|
p
n
|
=
|
s
n
+1
|
.
If
l
denotes the length of
p
n
and
s
n
+1
, one may write both strings symbol by
symbol as
p
n
=
p
n
(1)
...p
n
(
l
)and
s
n
+1
=
s
n
+1
(1)
...s
n
+1
(
l
), respectively.
There will be constructed some output string
q
symbol by symbol, accordingly.
∅
(1) for
i
=1to
i
=
l
do
(1.1) if
p
n
(
i
)=
s
n
+1
(
i
)
M
then
q
(
i
):=
p
n
(
i
);
if
i
=
l
then
goto
(2)
(1.2) if
p
n
(
i
)
∈
=
s
n
+1
(
i
)then
(1.2.1) if
VA
then
q
(
i
):=
x
j
(1.2.2) else
c
:=
c
+1;
q
(
i
):=
x
c
VA
:=
VA
∃
j
:[
p
n
(
i
)
,s
n
+1
(
i
)
,j
]
∈
∪{
[
p
n
(
i
)
,s
n
+1
(
i
)
,c
]
}
;
if
i
=
l
then
goto
(2)
(2) return
q
=
q
(1)
...q
(
l
)
In contrast to the NP-hardness of the computations in [DA i] and [DA ii], the
test [L/W i] and [L/W ii] are of linear complexity, and the computation of [L/W
iii] is of quadratic complexity. Consistence is lost in [L/W i] and [L/W ii].
