The algorithm: Use of pruning
Top-down search general to specific with pruning
pruning based on minimal support
d(h):=
{
0 if |c(h)| / |r
0
|<s
min
g(h) (p(h) - p
0
) otherwise
pruning with optimistic estimates
optimistic estimate function d
max
:
d(h') d
max
for a h' that are specializations of h
Algorithm maintains a set of k best hypotheses H
if for current hypothesis h
0
, d
max
(h
c
) < min
h in H
d(h), h
0
can safely be pruned.
d(h):=g(h) ^ a * (p(h) - p
0
)
Þ
d
max
:=g(h) ^ a * (1- p
0
)
