Can the distribution of emission probabilities of an HMM be swapped out for the re-estimated ones only after all training sequences have been covered?

Regarding the re-estimation procedure of the Baum-Welch algorithm, the sources I looked into so far all describe the process in an abstract manner. Therefore I am wondering the following about actually implementing the algorithm:

The re-estimation of the transition probabilities covers all transitions, every single training sequence, right? Meaning, given the current training sequence, I will go through all transitions $a_{ij}$ with $i, j \in H$ (the set of hidden variables) and re-estimate each $a_{ij}$. While I do so I store the re-estimated probabilities somewhere separate from my current transition probabilities and once I am done with all re-estimations I change out the current probabilities with the re-estimated ones. I cannot modify the individual probabilities in place without storing them temporarily, because inserting them directly one after the other would disrupt the probability distribution. Have I got this right so far?

Okay, but I am confused about re-estimating the emission probabilities, for the following reason:

While the $a_{ij}$ are all re-estimated for every single training sequence, this is not true for the emissions $b_i(O_t)$, because

$$b_i^*(O_k) = \frac{\sum_{t = 1}^T 1_{O_t = O_k} \gamma_i(t)}{\sum_{t = 1}^T \gamma_i(t)}$$

($1_{O_t = O_k}$ being an indicator function that returns true iff $O_t = O_k$.)

Thus only those $b_i(O_t)$ are re-estimated for which $O_t$ is an observed variable from the current training sequence $O$. Therefore

1) The distributions of emissions can only be changed out for the distribution of re-estimated emissions after all training sequences have been covered.

2) Many re-estimated emission probabilities will be repeatedly overwritten (if done naively) if the observed variable $O_t$ occurs in several training sequences.

Are these statements correct? I am not sure if I am missing something about the whole process here.

Both the emission and transition probabilities are calculated as the sum of each sequence's contribution according to its weight in the training set. For example if your training data consist of two sequences:

Sequence 1: H, H, H, T, H, H, T, H, T, H
Sequence 2: H, H, T, T, H, T, H, T, T, H

and are equally weighted, their emission probabilities are

Sequence 1: $P(heads) = 0.7, P(tails) = 0.3$
Sequence 2: $P(heads) = 0.5, P(tails) = 0.5$

and the new emission probabilities to use in the next iteration of the expectation-maximization procedure will be

$P(heads) = (0.5 \times 0.7) + (0.5 \times 0.5) = 0.6$
$P(tails) = (0.5 \times 0.3) + (0.5 \times 0.5) = 0.4$

The same applies when calculating the transition probabilities.

For more details there is a great explanation in chapter 3.3 of Durbin R, Eddy SR, Krogh A, Mitchison G (1998) Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge University Press, Cambridge, United Kingdom.

• Hmm, I don't understand your answer. Consider this: Say I my first training sequence is H H H. So no Tails in that sequence. If I re-estimate my emissions now, the emission distribution for each hidden variable is not guaranteed so sum to 1 anymore, right? Because there were no tails in my sequence, so I could not re-estimate the emissions for T. The emission distributions will only sum to one, once all observed variables from the training data have been observed at least once. This might take until the very last training sequence of the training data. Are these considerations correct? Commented Apr 13, 2017 at 13:17
• In you example I also don't understand where the respective $0.5$ are coming from, as there are two possible sources. Commented Apr 13, 2017 at 13:18
• In your example, assuming there is only one training sequence, your emission probabilities will still sum to 1 since $P(heads) = 1$ and $P(tails) = 0$. This also illustrates why you should always add pseudocount contributions to the probability calculations, particularly for small training datasets. For example you could add the contribution from a single hypothetical sequence whose emission probabilities are 0.5 for heads and 0.5 for tails to your single sequence above, giving $P(heads) = (0.5 \times 1) + (0.5 \times 0.5) = 0.75$ and $P(tails) = (0.5 \times 0) + (0.5 \times 0.5) = 0.25$. Commented Apr 14, 2017 at 1:52
• In this example and the one above the equations are formatted as $(sequence weight \times emission probability)$. Note that here we assume the sum of the sequence weights is 1. Commented Apr 14, 2017 at 1:52
• what exactly do you mean by sequence weight? I never heard that expression in the context of HMMs. Commented Apr 14, 2017 at 2:22