Skip to main content

Viterbi Algorithm in C++ and using STL

To practice my C++ and STL skills, I implemented the Viterbi algorithm example from the Wikipedia page: http://en.wikipedia.org/wiki/Viterbi_algorithm. The original algorithm was implemented in Python. I reimplemented the example in C++ and I used STL (mainly vector and map classes).  This code is in public-domain. So, use it as you want. 

The complete solution for MS Visual C++ 2008 can be found at http://filip.jurcicek.googlepages.com/ViterbiSTL.rar

// ViterbiSTL.cpp : is an C++ and STL implementatiton of the Wikipedia example
// Wikipedia: http://en.wikipedia.org/wiki/Viterbi_algorithm#A_concrete_example
// It as accurate implementation as it was possible

#include "stdafx.h"

#include "string"
#include "vector"
#include "map"
#include "iostream"

using namespace std;

//states = ('Rainy', 'Sunny')
// 
//observations = ('walk', 'shop', 'clean')
// 
//start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
// 
//transition_probability = {
//   'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
//   'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
//   }
// 
//emission_probability = {
//   'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
//   'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
//   }

vector states;
vector observations;
map start_probability;
map> transition_probability;
map> emission_probability;

class Tracking {
public:
  double prob;
  vector v_path;
  double v_prob;

  Tracking() {
    prob = 0.0;
    v_prob = 0.0;
  }

  Tracking(double p, vector & v_pth, double v_p) {
    prob = p;
    v_path = v_pth;
    v_prob = v_p;
  }
};

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

void init_variables(void) {
  states.push_back("Rainy");
states.push_back("Sunny");

  observations.push_back("walk");
  observations.push_back("shop");
  observations.push_back("clean");

  start_probability["Rainy"] = 0.6;
  start_probability["Sunny"] = 0.4;

  transition_probability["Rainy"]["Rainy"] = 0.7;
  transition_probability["Rainy"]["Sunny"] = 0.3;
  transition_probability["Sunny"]["Rainy"] = 0.4;
  transition_probability["Sunny"]["Sunny"] = 0.6;

  emission_probability["Rainy"]["walk"] = 0.1;
  emission_probability["Rainy"]["shop"] = 0.4;
  emission_probability["Rainy"]["clean"] = 0.5;
  emission_probability["Sunny"]["walk"] = 0.6;
  emission_probability["Sunny"]["shop"] = 0.3;
  emission_probability["Sunny"]["clean"] = 0.1;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

void print_variables(void) {
  // print states
  cout << "States:" <<>
  for(vector::iterator i=states.begin();i!=states.end();i++) {
    cout << "S: " << (*i) <<>
  }
  // print observations
  cout << "Observations:" <<>
  for(vector::iterator i=observations.begin();i!=observations.end();i++) {
    cout << "O: " << (*i) <<>
  }

  // print start probabilities
  cout << "Start probabilities:" <<>
  for(map::iterator i=start_probability.begin();i!=start_probability.end();i++) {
    cout << "S: " << (*i).first << " P: " << (*i).second <<>
  }

  // print transition_probability
  cout << "Transition probabilities:" <<>
  for(map>::iterator i=transition_probability.begin();i!=transition_probability.end();i++) {
    for(map::iterator j=(*i).second.begin();j!=(*i).second.end();j++) {
      cout << "FS: " << (*i).first << " TS: " << (*j).first << " P: " << (*j).second <<>
    }
  }

  // print emission probabilities
  cout << "Emission probabilities:" <<>
  for(int i=0; i
    for(int j=0; j
      cout << "FS: " <<>
        " P: " <<>
    }
  }
}

//this method compute total probability for observation, most likely viterbi path 
//and probability of such path
void forward_viterbi(vector obs, vector states, map start_p, 
                     map> trans_p, 
                     map> emit_p) {
  map T;

  for(vector::iterator state=states.begin(); state!=states.end();state++) {
    vector v_pth;
    v_pth.push_back(*state);

    T[*state] = Tracking(start_p[*state], v_pth, start_p[*state]);
  }

  for(vector::iterator output=obs.begin(); output!=obs.end();output++) {
    map U;

    for(vector::iterator next_state=states.begin(); next_state!=states.end(); next_state++) {
      Tracking next_tracker;

      for(vector::iterator source_state=states.begin(); source_state!=states.end(); source_state++) {
        Tracking source_tracker = T[*source_state];

        double p = emit_p[*source_state][*output]*trans_p[*source_state][*next_state];
        source_tracker.prob *= p;
        source_tracker.v_prob *= p;

        next_tracker.prob += source_tracker.prob;

        if(source_tracker.v_prob > next_tracker.v_prob) {
          next_tracker.v_path = source_tracker.v_path;
          next_tracker.v_path.push_back(*next_state);
          next_tracker.v_prob = source_tracker.v_prob;
        }
      }

      U[*next_state] = next_tracker;
    }

    T = U;
  }

  // apply sum/max to the final states
  Tracking final_tracker;

  for(vector::iterator state=states.begin(); state!=states.end(); state++) {
    Tracking tracker = T[*state];

    final_tracker.prob += tracker.prob;

    if(tracker.v_prob > final_tracker.v_prob) {
      final_tracker.v_path = tracker.v_path;
      final_tracker.v_prob = tracker.v_prob;
    }
  }

  cout << "Total probability of the observation sequence: " <<>
  cout << "Probability of the Viterbi path: " <<>
  cout << "The Viterbi path: " <<>
  for(vector::iterator state=final_tracker.v_path.begin(); state!=final_tracker.v_path.end(); state++) {
    cout << "VState: " << *state <<>
  }
}

int _tmain(int argc, _TCHAR* argv[])
{
  cout << "Viterbi STL example" <<>
  
  init_variables();
  print_variables();

  forward_viterbi(observations, 
                  states, 
                  start_probability, 
                  transition_probability, 
                  emission_probability);

cout << "End" <<>

  string end;
  cin >> end;

  return 0;
}

Comments

jiapei100 said…
Viterbi is searching the best possible hidden states under a sequence of observations.

You code looks beautiful and it strictly follows http://en.wikipedia.org/wiki/Viterbi_decoder

However, you testing doesn't even contain an obvious observation sequence.

Which makes your Viterbi searching absolutely wrong.


I mean, only with states, observations, start probability, transition probability, and emit probability, but without a testing observation sequence, how come you are able to test your viterbi algorithm??

So, revise it and make it more clear please.


Rgds
Unknown said…
@jiapei100 - Maybe I'm missing something here, but it looks like the test observation sequence is "walk", "shop", "clean" within the init_variables method?


/blee/
BozdskyFilip said…
Yes, the observation sequence is "walk", "shop", "clean" defined in init_variables method as Brian mentioned.
good job man!
Anthony said…
Hi, nice post. However, I'm new to C++ and don't understand the following:

vector states;
vector observations;
map start_probability;
map> transition_probability;
map> emission_probability;

Two questions: Why aren't you saying what types of vectors and maps these are (you're just writing "vector" instead of "vector")? And what is a "map>"
Anthony said…
Oh nevermind, I see... the template typing has been misinterpreted as an HTML tag.

Popular posts from this blog

Google Testing Blog: TotT: EXPECT vs. ASSERT

Google commented on different types of assertations in their testing framework ( Google Testing Blog: EXPECT vs. ASSERT)   I have found assertations in my code very useful on many occasions; however, I do not see any need for the EXPECT function. If your code is broken then it is broken and there is no point in continuing and testing conditions which are not likely to be met.  It is like with C++ compiler errors. The most important error is the firtst error. The rest of the erorrs is usually rubish and useless. 

how the make HCL and G graphs, and on the fly compositon of HCL and G for KALDI

Well, I had again to do something ;-) The task is to generate/create/update a decoding graph for KALDI on the fly. In my case, I aim at changing a G (grammar) in the context of a dialogue system. One can generate a new HCLG but this would take a lot of time as this involves FST determinization, epsilon-removal, minimization, etc. Therefore, I tried to use on-the-fly composition of statically prepared HCL and G. At first, I struggled with it but later I made it work. See  https://github.com/jpuigcerver/kaldi-decoders/issues/1 Here is a short summary: At the end, I managed to get LabelLookAheadMatcher to work. It is mostly based on the code and examples in opendcd, e.g. https://github.com/opendcd/opendcd/blob/master/script/makegraphotf.sh . First, Here is how I build and prepare the HCL and G. Please not that OpenFST must be compiled with  --enable-lookahead-fsts , see http://www.openfst.org/twiki/bin/view/FST/ReadMe . #--------------- fstdeterminize ${lang}/L_disambig.fst