Information Technology Reference
In-Depth Information
5. While LE(
e
i
,+
x
) = no, for positive example set +
x
,or
6. LE(
e
i
,-
x
) = yes, for negative example set -
x
,
7.
i
←
i
+ 1;
8. Output
e
i
.
7.9.2
Model inference
A model inference problem is an abstraction from scientific problems. In this
abstraction we try to find some unknown model
M
which can explain some
results. Shapiro gave the following definition of the model inference problem.
Suppose that a first order language
and two subsets of it, an observational
language
Lo
, a hypothesis language
L
h
, are given. In addition, an oracle for some
unknown model
M
of
L
is given. The model inference problem is to find a finite
Lo
L
. In order to solve the model inference problem,
Shapiro has developed a model inference algorithm in terms of Gold's theory
(Shapiro, 1981).
-complete axiomatization of
M
L
sentence is divided into two subsets: observable language
Lo
and
hypothesis language
L
h
. Assuming that
□
∈
'
Where
□
is empty sentence. Then model inference problem can be defined as
follows: given one-order language
L
o
Ք
L
h
Ք
L
L
and two subsets: observable language
L
o
and
hypothesis language
L
h
. Further, given a handle mechanism oracle to unknown
model
M
of
L
, model inference problem is to find a definite
L
o
of
M
─
completed
axiomatization.
Algorithm to solve model inference problem is referred to as model inference
algorithm. Enumeration of model
M
is an infinite sequence
F
1
, F
2
, F
3
,
…
, where
F
i
is the fact about
M
, each sentence α of
L
o
is taken place at fact
F
i
= <α,V>,
i
>
0. Model reasoning algorithm reads a enumeration of observable language
L
o
once. A fact which generates definite set of sentences of hypothesis language
L
h
is referred to as speculation of algorithm. A kind of model inference algorithm is
as follows:
Algorithm 7.13
An enumeration model inference algorithm (Shapiro, 1981).
1. Let
h
be a total recursive function
false
to {
□
}, S
true
to {},
k
to 0
3. Repeat
4. read the next fact
2. Set
S
F
n
=<α,V>
5. add α to
S
v