Information Technology Reference
In-Depth Information
Theorem 7.1
Let l
1
and l
2
be learning algorithms, when PA(l
1
)
≥
PA(l
2
) holds,
selecting l1 has more correct bias.
Proof
When PA(
l
1
)
≥
PA(
l
2
) holds, classifier generated by
l
1
can classify more
examples correctly. That is:
P
(
f
( )
a
=
c
)
≥
P
(
f
( )
a
=
c
)
(7.36)
D
l
( )
t
D
l
( )
t
A C
×
1
A C
×
2
After we project bias correctness to distribution D
A
C
, we can get:
×
CorrB
=
P
(
f
(
a
)
=
c
)
D
g
A
×
C
Since target concept is embodied to a large extent by classifier generated by
learning algorithms, bias correctness can be adapted as:
Substituting algorithms
l
1
and
l
2
to above formula and combining with formula
CorrB
=
P
(
f
(
a
)
=
c
)
D
l t
( )
A
×
C
(7.36), we can get following:
CorrB
=
P
(
f
(
a
)
=
c
)
≥
CorrB
=
P
(
f
(
a
)
=
c
)
1
D
l
( )
t
2
D
l
( )
t
A
×
C
1
A
×
C
2
Selecting
l
1
has more correct bias. The Theorem 7.1 was proved.
7.8.2
Bias shift representation
Decision tree learning algorithm is actually efficient, but because of lacking
support of background knowledge, it cannot handle various generalizations. As
for inductive algorithms based on predicate logic (e.g. AQ11, INDUCE), this
function is the most preliminary and inseparable from learning procedure. One
result of lacking background knowledge is that procedure of constructing become
complicated and not easily understood by domain experts.
Many systems attempt to solve this problem. Such as: algorithm PRISM of
Cendrowska, INDUCT algorithm of Gaines, and other techniques introduced by
Quinlan, Lavrac etc. which make decision tree easier and more precise. However,
they only focus on information included in history data, attempt to mine more
useful resource.
We propose a pre-processing algorithm which can make use of learning
algorithm based on representation transform and can handle various
generalizations. This approach firstly pre-processes the primitive training
instances, calls generalization algorithm CGAOI, makes primitive training
instances achieve appointed concept level, then pre-processes the primitive
training instances again.
In order to realize the proposed algorithm, first concept level is introduced.
