The topological K-best search

for MDHMMs was tested and described in Publication 5 as an example of a way for utilizing the topology of an organized codebook of mixture densities for a fast approximative search algorithm for large codebooks. Briefly, the search begins by re-ranking the set of K best matches obtained from search regarding to the previous observation vector. Then the neighbors of the new best match are checked and if a new best match is found, the neighbors of it are checked as well. The local search process for the new set of K best matches similar to the fast winner search algorithms for SOM [Kohonen, 1996,Kohonen et al., 1996c,Lampinen and Oja, 1989] continues then until no more new best matches are found (see Figure 6). A complete search through the codebook is performed periodically to react for abrupt feature changes [Lopez-Gonzalo and Hernandez-Gomez, 1993].

In [Lampinen and Oja, 1989] the local search process starts from an initial guess based on the best match approximation obtained by the projections to the first few vector components [Friedman et al., 1975] and in [Zhao and Rowden, 1991] the search begins always from the center of the codebook. In [Kohonen, 1996,Kohonen et al., 1996c] a pointer to the previous best match is assigned for each training vector, which are used several times in the training. The use of similar pointer tables to bypass layers in a tree-search SOM was suggested by [Koikkalainen, 1995]. In Publication 5, only the set of K best matches for the previous observation vector is stored and it is assumed that because the successive observations in the sequence resemble each other, the new set of best matches can be found starting from the previous set. An important note is that the real K best matches are not necessarily found at every time instant, but rather a set of them that is related to the assumed best match. The presented method is expected to work well for the particular type of density estimation discussed in this work, but not for non-SOM codebooks or SOM applications in general.