Information Technology Reference
In-Depth Information
naïve Bayesian classifier equals to a perception machine, the combined classifier
equals to a perception network with a hidden layer.
The boosting naïve Bayesian method for multiple classification problems is as
follows:
Algorithm 6.2
Multiple Classification AdaBoost Algorithm
Input:
N training examples
< >
?
Distribution of the N training examples, D: w, where w is the weight vector of
training example.
T: the number of rounds for training.
1. Initialize:
Initial weight vector of training examples
(
x
,
y
,
(
x
,
y
)
1
1
N
N
w
=
1/
N
,
i
=
(1...
N
)
for t
=
1
to T
2.
t
( )
t
w
H
:
X
→
Y
3. Given weights
, find a hypothesis
(
t
)
H
4. Estimation the general error of hypothesis
:
N
Ã
e
( )
t
=
w
( )
t
I y
(
≠
h
( )
t
(
x
))
i
i
i
i
i
=
1
e
( )
t
β
( )
t
=
5. Calculate
( )
t
(1
−
e
)
6. Renew the next round weights of examples with
( )
t
(
t
+
1)
( )
t
( )
t
1
−
I
(
y
=
h
(
x
))
w
=
w
(
β
)
i
i
i
i
i
(
t
+
1)
w
7. Normalize
, so that they are summed up to 1
8. End for
9. Output:
i
T
Ã
h x
( )
=
arg max
(log
) (
I h
( )
t
( )
x
=
y
)
( )
t
t
=
1
β
y Y
∈
I
(
φ
)
=
1
φ
=
T
I
(
φ
)
=
0
Where
otherwise.
if
;
6.4.3
The computational complexity
Suppose a sample in the sample space has
f
features, and each feature takes
v
values. The naïve Bayesian classifier deduced by formula (6.27) will have f
v
+1
parameters. These parameters are accumulatively learnt 2
+2 times. In each
learning process, each feature value of each training example will improve the
final precision. So the time complexity for
fv
n
training examples is O(
nf
),
independent of
v
. Substantially, this time complexity is optimal. For boosting
