Information Technology Reference
In-Depth Information
more large, forming an infinite sequence
. If there
exists a number m, they would make gm be the correct description of R,
g m =
g 1 , g 2 , speculated by
M
g m
1 =
g m
2 = ,
Then the limit of the example sequence
M
can identify
R
correctly. As unknown
rules are learned more and more,
M
can successfully modify the speculation
about
stops modifying its speculation after definite times, and the final
speculation is the correct description of
R
. If
M
R
, then
M
correctly identifies
R
at the
limit of the example sequence. Notice,
cannot confirm whether it can converge
into a correct assumption, because whether there exists a contradiction between
new data and current speculation is unknown.
Enumeration identification is the first approach to speculate the abstraction of
multinomial sequence, that is, it systematically searches possible rule space, until
finds speculation in accordance with all data so far. Suppose that concrete
domain of rule is prescribed, there is a enumeration, i.e.
M
d 1, d 2, d 3, , so that each
rule in enumeration has one or multiple description. Given an example set of a
rule, through the table, enumeration identification will find the first description
d
1 ,
that is, if it is compatible with given example, then speculation is
1 . This
approach cannot confirm whether it can achieve correct limit identification. If
example representation and compatible relation meet following two conditions,
enumeration approach assures limit identifying all rules of that domain:
d
(1) A correct assumption is always compatible with given examples.
(2) Any wrong assumption is not compatible with sets with examples large
enough or all sets.
In order to compute enumeration approach, enumeration
d 1, d 2, d 3 , must be
computable, it must compute that given description is compatible with given
example set.
Algorithm 7.12 Enumeration identification algorithm
Input:
• The set of a group of expressions E = e 1 ,e 2 ,
• Oracle TE to provide enough objective example set.
• Oracle LE of ordering information.
Output:
A series of hypotheses H 1 , H 2 , …, each hypothesis H i is in E , and is consistent with the
ith example.
Procedure:
1. Initialize:
1;
2. examples emptyset;
3. Loop:
4. call TE(), add example to set examples;
i
Search WWH ::




Custom Search