The pruning of nodes

The construction of the tree is iterative and begins with the root node. An empty string $e$ is assigned with the root node. We then add candidates nodes up to a depth $L$. If the probability of a string is small then the node should not be in the tree. We decide whether a probability is small by comparing it with a predefined threshold that represents the accuracy of the model. This threshold is defined by the user. We denote it by $\epsilon$.

There is another reason not to add a node in the tree: if the addition of the node gives a new tree that is statistically equivalent to the previous one. We need a way of checking if two distributions of probability are equivalent. In section 6.3.4 we describe the different measures of distance between probabilities that we have investigated and how they behave. For now, we denote by $D(P_1\Vert P_2)$ a measure of the distance between two probability measures $P_1$ and $P_2$ over the observation space.

The distance $D$ can measure the amount of additional information we gain by adding the suffix $\sigma s$ to the tree instead of pruning the node $\sigma$ and keeping the suffix $s$ to describe the distribution. Given this measure of distance between two probabilities $\tilde{P}(\cdot\vert\sigma s)$ and $\tilde{P}(\cdot\vert s)$, we can construct a statistical error measure by weighting it with the prior probability of observing the suffix $\sigma s$. Indeed, the distance $D\left(\tilde{P}(\cdot\vert\sigma s)\Vert\tilde{P}(\cdot\vert s)\right)$ can be large even if the probability of observing the sequence $\sigma s$ is very small. Weighting the distance by $\tilde{P}(\sigma s)$ allows us to neglect those cases. The statistical difference is then measured by

$$Err(\sigma s,s)=\tilde{P}(\sigma s)\cdot D\left(\tilde{P}(\cdot\vert\sigma s)\Vert\tilde{P}(\cdot\vert s)\right)$$

$Err$ is called the statistical error measure.