Information Technology Reference
In-Depth Information
6.4.2
Boosting of naïve Bayesian model
In boosting, a series of classifiers will be built, and in each classifier in series,
examples misclassified by previous classifier will be given more attention.
Concretely, after learning classifier
, the weights of training examples that are
misclassified by classifier k will increase, and classifier
k
+1 will be learnt based
on the newly weighted training examples. This process will be repeated
k
T
times.
The final classifier is the synthesis of all the classifiers in series.
Initially, each training example is set with a weight. In the learning process, if
some example is misclassified by one classifier, in the next learning round, the
corresponding weight will be increased, so that the next classifier will pay more
attention to it.
The boosting algorithm for binary classification problem is given out by
Freund and Scbapire as the AdaBoost Algorithm (Freund, 1995).
Algorithm 6.1
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:
2. Initial weight vector of training examples:
(
x
,
y
,
(
x
,
y
)
1
1
N
N
w
=
1/
N i
=
?
1,
,
N
3. for
t
=1 to
T
4. Given weights
t
( )
t
w
H
:
X
→
[0, 1]
, find a hypothesis
(
t
)
H
5. Estimation the general error of hypothesis
:
Ã
N
e
( )
t
=
w
( )
t
|
y
−
h
( )
t
(
x
) |
i
i
i
i
i
=
1
( )
t
e
β
( )
t
=
6. Calculate
( )
t
(1
−
e
)
7. Renew the next round weights of examples with
( )
t
(
t
+
1)
( )
t
( )
t
1 |
−
y
−
h
(
x
)|
w
=
w
(
β
)
i
i
i
i
i
(
t
+
1)
w
8. Normalize
, so that they are summed up to 1
9. End for
10. Output
Ê
i
1
i
Ã
T
t
Ã
T
t
(
t
)
1
if
(log
)
h
(
x
)
≥
(log
)
Ë
(
t
)
2
(
t
)
h
(
x
)
=
=
1
β
=
1
β
Ì
0
otherwize
