Information Technology Reference
In-Depth Information
atoms do conjunction to form assumption
h
.
(2) If
, else gets the result,
and holds that sample is not in accordance with any pure conjunction concept.
Haussler analyzed this algorithm, and concluded that its sample complexity
( ,
h
does not include negative examples, then returns
h
L
c
S
ε δ
)
is(Haussler, 1988)
1
1
1
L
c
C
(log(
)
+
n
)
/
ε
≤
S
(
ε
,
δ
)
≤
C
(log(
)
+
n
log(
))
/
ε
(7.38)
0
1
δ
δ
ε
where
1
is positive constant.
b) Greedy algorithm of learning pure conjunction concept.
Algorithm 7.14
Greedy Algorithm of Learning Pure Conjunction Concept
C
0
, C
1. As for given samples, finds the minimum main atom of each attribute.
2. At beginning, pure conjunction assumption
h
is empty, when there is negative
examples in samples, do
3. In all attributes, find the minimum main atom, which delete most negative
examples and add them to h. If no minimum main atom, then any negative
example can be deleted. The loop ends.
4. Eliminate deleted negative examples from samples.
5. If there is no negative examples, then return h, else report samples are
inconsistent with any pure conjunction concept.
Haussler discussed the problem of sample complexity of the algorithm in
paper
Haussler, 1988
, and gave the following result:
1
n
1
sn
1
L
c
2
C
(log(
)
+
s
log(
))
/
ε
≤
S
(
ε
,
δ
)
≤
C
(log(
)
+
s
(log(
))
)
/
ε
(7.39)
0
1
δ
s
δ
ε
where
C
0
,C
1
are positive constants,
s
is the maximum number of atoms in pure
conjunction concept.
We can see from above mentioned, Valiant's learning theory only requires
assumption generated by learning algorithm can approach objective concept well
with high probability, and do not require to identify target concept precisely. This
kind of learning theory is “approximately correct” identification, sometimes
simply called PAC(Probably Approximately Correct) Theory. Valiant's learning
theory has more practical significance than Gold's learning theory.
Exercises
1. What is inductive learning? What are its main characteristics?
2. Through examples, explain the application of selective and constructive
