# Most efficient algorithm for comparing two paths

I'm working with a Continuous Hidden Markov Model, and using the Viterbi Decoder which finds the best possible path for a given sequence. Here is how my algorithm works:

1) Process the (input) .wav speech signal
2) Extract the MFCC Coefficients (13)
3) Use these values to train the HMM
4) Execute the Viterbi Decoder


And an example input, after step 4 gives the best path of:

0 0 0 0 0 0 0 0 0 0 0 0 0 2 12 6 6 2 2 4 2 2 2 2 2 6 4 2 2 6 6 2 2 2 2 2 2 2 2
8 4 4 2 4 2 2 2 2 6 2 2 4 2 6 2 2 2 2 2 6 2 10 2 6 4 2 2 4 2 2 2 2 2 4 4 2 2 2
6 10 2 2 4 2 2 2 2 2 2 4 2 2 4 2 2 2 2 2 2 4 2 2 2 2 6 2 2 2 2 2 2 4 4 2 2 2 2
2 2 2 2 2 2 2 2 4 2 12 2 6 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 2 1 2 2 2 2 2 2 2 6 2 2 6 2 2 2
2 12 2 2 2 13 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 8 4 4 2 2 2 2 2 2 4 2 2 4
2 6 2 6 6 12 2 2 4 2 12 4 2 2 2 10 4 2 6 8 8 2 2 2 2 12 4 2 2 12 6 2 2 2 8 2 4
2 4 2 2 2 12 2 2 2 2 4 4 6 2 2 6 6 2 4 4 2 2 2 4 2 4 10 10 8 2 2 2 2 6 4 2 4 2
2 2 2 4 2 2 4 2 2 8 2 2 2 2 2 2 8 2 6 2 4 2 10 8 4 2 2 8 2 2 4 4 2 2 8 4 2 6 8
4 2 2 12 2 6 2 4 8 4 2 2 2 2 4 2 2 2 2 2 2 2 2 2 2 4 2 4 2 2 2 2 2 2 2 2 2 2 2
8 2 2 2 2 4 2 2 2 2 8 2 2 4 4 2 2 2 6 2 4 2 2 2 12 2 2 2 2 4 2 12 2 2 2 2 2 2
2 8 2 2 2 6 12 2 2 2 2 2 2 2 2


I find the best possible path for each of my training data (MFCC) against the model, carried out in the steps above. This gives an ok result when comparing myself, in that, if I enter a speech file "Yes" as input, then, the training for "Yes" will show a very simular path, whereas, if I entered "Yes" as input and compared against training for "No" then the best path will be different.

My question is this: Which would give me the most efficient way to compare the viterbi paths? I have only researched the Euclidean Distance algorithm, as well as the Hamming Distance so would prefer to use these. I know it's a very subjective question, but, I am asking in terms of being able to match two possible paths.

Hope someone can help me.

• Which paths do you wish to compare? A Viterbi decoder is an efficient technique for comparing all possible paths through the trellis against each other and returning the best path, that is, it is doing the comparisons for you. In doing the comparisons, the Viterbi decoder doesn't actually generate all possible paths and compare them, but it does a lot of pruning, discarding whole bunches of paths by looking at partial paths and then saying for most of them "This partial path and all its continuations cannot be winners and so I don't need to go down this path any farther" – Dilip Sarwate Mar 10 '13 at 20:24
• @DilipSarwate Hi Dilip, thank you for your reply. I think that what you're explaining here is soft / hard decision. I'm not quite sure what you mean.. The algorithm I'm using gives me: viterbi_decoder(features, model, framesize, q) in which gives me the output in my post. Obviously, from this, I cannot determine what the sample is saying because I am not comparing this to any training data. I therefore thought I would need some hard / soft decision so my initial thought process was the Euclidean distance came into.. I've used DTW for a similar process and was thinking of the same structure. – Phorce Mar 10 '13 at 21:19
• I think we are talking at cross-purposes. What I described is what all Viterbi decoders do regardless of whether they do soft or hard decision decoding. What you seem to be asking is that you have, say, three waveforms, saying Yes, No, and Maybe, stored as three files which you have used to train the decoder; and now the Viterbi decoder spits out a series of numbers (like the one you posted) that you save in a file, and now you want to figure out whether the decoder output matches most closely with the Yes file, the No file or the Maybe file that was used to train the decoder. Is this right? – Dilip Sarwate Mar 10 '13 at 22:16
• Right, your library is a total crap. Read Rabiner book first, then read HTK Book and use HTK to understand the theory first. Only then you can start your own implementation. – Nikolay Shmyrev Mar 11 '13 at 18:14
• You train the HMM HMM1 with 30 people saying "yes". You train another HMM HMM2 with 30 people saying "no". When you get the sample you score that sample with HMM1 and get score1 and with HMM2 and get score2. If score1 > score2 the sample is recognized as yes, otherwise as no. – Nikolay Shmyrev Mar 11 '13 at 21:53