2.5. Hidden Markov Models 25The computational complexity for evaluating Q at all time frames T is T · S · N if S isthe number of states and N is the number of transitions. The memory requirementsfor the Viterbi Algorithm are determined by the size of the backpointer array whichis given by T · S.The best matching sequence with the maximum joint probability p( x1T, sT1) is foundby evaluation of Q at the final time frame T. The last position sTof that sequenceis decided by:sT= argmax Q( T, s)sStarting with sT, the full sequence sT1is reconstructed by recollecting the storeddecisions from the backpointer array. This can be formalized by:S( T)= sTS( t)= B( t, S( t+ 1))so finally:s1T= argmaxp( xT1, s1T)=[ S(1), S(2),.., S( T)]sT1Assuming large models, as the presented UMIC model, with S= 2 · 106possiblestates and T= 100, the backpointer array can become large. By using a 4-byteint32 state space, this leads to 400MB memory usage. Although this can further bereduced by storing only the compact transition indexes i 1.. 125 for the(5, 5, 5)-model. With only 125 distinct values, a 1-byte int8 datatype is enough, whichreduces the memory usage down to 100MB(see 5.2.2 for more details).2.5.3 Higher Order ModelsIncorporating more history in the transition probabilities leads to HMMs of higherorder. The presented first order HMM uses only the present state for deciding whichfuture state is the most probable. A second order HMM uses the first state ofthe history as well. Thus, the next state s is now dependent on two predecessorstates instead of one(see figure 2.10). The transition probability is now given byp( s| s, s). The number of states for a second order HMM grows by the factor of Ntransitions. For each state, N new states are needed that have a configured historyof the corresponding transition. The computational complexity is therefore T · S · N2.The memory requirements due to the backpointer array grow to T · S · N.Although the increase in complexity is quite significant, only with higher order mod-els it is possible to model the probability of movements like turning left. It would beplausible to increase the probability of transitions that change directions in crosswaysand lower them in pathways. So from a computational standpoint, the enhancementseems feasible, but higher order models have not been fully implemented in thethesis.2.5.4 LogspaceThe recursion equation Q of the Viterbi Algorithm multiplies probabilities. Prob-abilities are defined to be 0<= p<= 1. Therefore, the application of many such