Do re-estimated HMM parameters still need to be normalized?

A few days ago I asked this question. I only got one answer and I did not really understand it. Now I think this question is a special case of a more general question I have, namely: Do re-estiamted HMM parameters still need to be normalized?

In all sources I read, it nowhere says so. However if normalizing was a necessary step after parameter re-estimation my question from the other post would be solved as well, I think.

For instance, the reestimation of a transition probability $a_{ij}$ is defined like so:

$$a_{ij}* = \frac{\text{expected count of taking } a_{ij}}{\text{expected count of going through state } i}$$

and

$$b_{i}(o)* = \frac{\text{expected count of observing o while in state i }}{\text{expected count of going through state } i}$$

However, as asked in my other question, I do not see where this guarantees that the sum of the emission/ transition probabilities of state $i$ still sum to one after the re-estimation:

$$\sum_{o \in O} b_i(o) = 1 \text{ with O the set of observable variables}$$

Do I need to normlize the re-estiamted emissionand transition probabilities for each state like so

$$a_{ij} ** = \frac{a_{ij}*}{\sum_{j = 1}^N a_{ij}*}$$

and

$$b_i(o)** = \frac{b_i(o)*}{\sum_{o' \in O}^N b_i(o')*} \text{ }?$$

In my implememtation I am getting for example the following result after re-estimating all transitions ot of state $0$:

(format: source state, target state, transition probability)

(0)
(0)
0.02038692369
(1)
0.02827691867
(2)
0.1224984127
(3)
0.1769161212
(4)
0.02722449656
(5)
0.09686773213
(6)
0.06621975806
(7)
0.1563805179
(8)
0.2656531668
(9)
0.001414074456
∑ =  0.9618381222

As you can see the re-estimaeted probabilities do not sum to 1, while the original randomized distribution did sum to 1:

(0)
(0)
0.180830546
(1)
0.2397926304
(2)
0.08390362715
(3)
0.0671602972
(4)
0.07536117849
(5)
0.1897902356
(6)
0.0579146584
(7)
0.0912998276
(8)
0.004448007786
(9)
0.009498991412
∑ =  1

It is not necessary to normalize the re-estimated parameters since it is guaranteed that they represent a valid probability distribution. Why in your implementation do the transition probabilities from state 0 not sum to one? I don't know. Maybe some implementation errors. But it is obvious that $a_{ij}$ and $b_i(o)$ sum to one for a particular $i$ without any need to normalization after estimation. For example, $a_{ij}$ is estimated as:
$$a_{ij} = \frac{\text{expected number of transitions from state i to state j}}{\text{expected number of transitions from state i}}$$
$$\text{expected number of transitions from state i} = \sum_j \text{expected number of transitions from state i to state j}$$ The same argument holds for $b_i(o)$.
• Sorry, I have thought about this for quite a while and tried to find the bug, but still... how the re-estimation of the emissions (in particular) is supposed to sum to 1 I still don't see. Say I want to re-estiamte the emissions for a state $s_i$. State $s_i$ has the set of emissions $E$. But assume in my current training sequence there occurs only one elememt $e \in E$. Therefore only one of the emission probabilities of $s_i$ is re-estiamted ($b_i(e)$). The value of the re-estimation will differ from the current value and thus the distribution no longer sums to one... What am I missing here? – lo tolmencre Apr 20 '17 at 6:27
• @lotolmencre Not only $b_i(e)$ is re-estimated, but all emissions are re-estimated. In your example, $b_i(e)$ would be equal to one and all other $b_i(e')$ for $e' \neq e$ would be zero, since the numerator for re-estimating emissions would be zero for $e' \neq e$. – Hossein Apr 20 '17 at 15:27