The algorithm

Next: The estimation of observed Up: The learning algorithm Previous: The pruning of nodes Index

The algorithm

Given the statistical error measure, we can easily construct the tree using the following algorithm :

Initialization step:

-

The tree is initialized to a single node : .

-

The set of candidate sequences is initialized to $\left\{ \sigma \vert \sigma \in \Sigma, \tilde{P}(\sigma)\geq \epsilon \right\}$ .
While there is still a sequence to be tested (that is, $S \not= \o$ ), do :

1)

Pick the first candidate sequence $s \in S$ and remove it from the set of candidate sequences .

2)

If $Err\left(s,Suffix(s)\right)\geq\epsilon$ then add to the node corresponding to .

3)

If $\vert s\vert<L$ then for every sequence $\sigma\in\Sigma$ , if $\tilde{P}(\sigma s)\geq \epsilon$ add $\sigma s$ to the end of the candidate sequence set .

franck 2006-10-16