Information Technology Reference
In-Depth Information
7.8.1
Formalization of bias
First of all, we define basic concepts of bias formally.
Definition 7.1
S is a search space defined in <A
C
F
T
L>, where attribute
vector A={a
1
,
…
,a
m
} has definite or infinite elements; classification vector
C={c
1
,
…
,c
k
} has definite elements. For given A and C, F is set of all concepts; T
is set of training examples with n tuples; L represents a learning algorithm
family.
Definition 7.2
A learning algorithm l defines a map from T to F, that is:
l t f
( ,
)
t t
{
∈
T
}
¾¾¾→
f
{
f
∈
F
},
l
∈
L
(7.31)
Definition 7.3
C
is a probability distribution on A
×
C; t is n tuples which is
defined on A
×
C and suffice D
A
D
A
×
be a probability distribution on
,
and identity of attribute set IA(A
1
,A
2
) means probability that put a random
attribute to same class given concepts f and D
C
. Let D
×
. That is:
(
T
(
A
,
f
))
=
l T
(
(
A
,
f
))),
l
∈
L
∩
T
⊆
T
∩
A
,
A
⊆
A
∩
f
∈
F
0
1
0
2
0
1
2
Definition 7.4
Let f
g
be the target concept, correctness of bias CorrB can be
defined as:
CorrB
=
P
(
f
( )
a
=
f a
( )),
f
∈
F
∩
a
∈
A
(7.32)
D
g
A
Definition 7.5
Let |S| be number of elements in S, then bias strength StrB can be
defined as:
1
|
StrB
=
(7.33)
|
S
Definition 7.6
Let State
0
(S) = <A
0
, C, f, T, l> and State
1
(S) = <A
1
, C, f, T, l> be
two states of search space, bias shift BSR is defined as:
R
BS
State
(
S
)
¾¾ →
State
(
S
)
0
1
Definition 7.7
Let D
A
be a probability distribution on A, and identity of learning
algorithm IL(l
1
, l
2
) means probability that put a random training example t to
same class given concepts f and D
A
. That is:
IL l
( ,
l
)
=
P
( ( ,
l
t
f
)
=
l
( ,
t
f
)),
t
∈
T
∩
l
,
l
∈
L
∩
f
∈
F
(7.34)
1
2
D
1
2
1
2
A
Definition 7.8
Predict accuracy PA of learning algorithm l is defined as:
PA l
( )
=
P
(
f
( )
a
=
c
),
f
∈
F
∩ ∈
t
T
∩
c
∈
C
(7.35)
D
l t
( )
A C
×
Definition 7.9
Let State
0
(S) = <A, C, f, T, l0> and State
1
(S)= <A, C, f, T, l1> be
two states of search space, procedure bias shift BSP is defined as:
P
BS
State
(
S
)
¾¾ →
State
(
S
)
0
1