2.5. Hidden Markov Models 27of RSSI readings from D Access Points. The RSSI readings are assumed to bestochastically independent. The analytical form of p( x| s) is given by:Dp( x| s)= p( x1,..., xd,..., xD| s)=p( xd| s)d=1=1Dd=1exp2s2d-1D2d=1xd- µsdsd2The next model assumption is introduced in the form of a constant pooled variancefor all states and dimensions. This leads to a further simplification of the emissionmodel:p( x| s)=1expC1-C22D( xd- µsd)2d=1transforming the equation with the negative logarithm:- log( p( x| s))=C22D( xd- µsd)2+ log( C1)d=1insertion into the recursion equation and dropping the constants C1, C2due to theminimization leads to:DQ( t, s):= min[ Q( t- 1, s)+( xtd- µsd)2- log( p( s| s))]sd=1Thus, in logspace the Gaussian modelled emission probability is simplified to adistance calculation between xtdand the stored µsdcomponents.2.5.5 PruningPruning, also known as Beam Search, is a heuristic approach to make the ViterbiAlgorithm more efficient. The basic idea is to skip the evaluation of Q( t, s) that aredetermined to be unlikely with respect to the global optimum. Therefore, findingthe global optimum, the most probable sequence s1T, is not guaranteed any more.Loosing the global optimum will be more probable if the pruning is too aggressiveand the number of evaluated states becomes too low.There are two pruning strategies. The first strategy discards unlikely hypothesesif their probability drops below a threshold that is determined by the probabilityQtop( t) of the top hypothesis:Qtop( t)= max Q( t, s)sby introducing a factor f, the state hypothesis( s, t) is pruned if:Q( t, s)< f · Qtop( t)With this strategy, the number of unpruned states is variable for each time frame t.The other strategy induces a hard limit N on the number of unpruned states. Duringthe evaluation of Q( t, s) for a given time frame, the top- N states are collected forensuring their further processing in the next t+ 1 time frame. Due to the simplermemory management, this strategy has been chosen in this thesis.