Information Technology Reference
In-Depth Information
6. while there is an α S
false such that
7. or there is an α i ∈ S true such that
do
8.
k
=
k
+1
9. output
T k
10. Forever
Where, α 1 , α 2 , α 3 , ··· are a fixed effective enumeration of all sentences of
L
o ,
T 1 ,
T 2 , T 3 , ··· are a fixed effective enumeration of all finite sets of sentences of
L h , and
M
is a model for
L
. Symbol
denotes that can derive α in n derivation
steps or less,
steps or less.
Algorithm 7.13 is not feasible because of its global nature. Whenever it finds
that a set of sentences is not an axiomatization of the model it simply discards it
and searches through all finite sets of sentences until it finds the next plausible
conjecture. In order to overcome this problem, Shapiro developed an incremental
inference algorithm which is called the contradiction backtracing algorithm, since
it can trace a contradiction between a conjecture and the facts back to its source,
which is a false hypothesis (Shapiro, 1981).
denotes that T can not derive α in
n
7.9.3 Valiant's learning theory
Valiant claims that a learning machine must have following properties (Valiant,
1984):
(1) Machine can learning concept of all classes. Furthermore, these classes can
be characterized.
(2) Concept class is proper and uncommon for general knowledge.
(3) Computational procedure that Machine deducts expected program required in
feasible steps.
Learning machine is composed of learning protocols and deduction procedure.
Learning protocols prescribe the approach to get information from outer.
Deduction procedure is a mechanism, and correct recognition algorithm of
learning concept is deductive. From a general point of view, approach to study
learning is to prescribe a possible learning protocol. Using this learning protocol
to study concept class, recognition program can be deducted in multinomial time.
Concrete protocol permits to provide two kind of information. The first is access
to typical data, which are positive examples of concepts. To be precise, assume
that these positive examples essentially have an arbitrary probability distribution,
it calls subprogram EXAMPLES to generate positive examples whose relative
Search WWH ::




Custom Search