java.txt

Viterbi in java. ViterbiViterbiViterbiViterbiViterbiViterbiViterbiViterbiViterbiViterbiViterbiViterb

HMM    V i t e r b i   A l g o r i t h m .
  
  1. MAIN CLASS   
  
  package nb_viterbi;

  import java.util.*;
  import java.util.Map.Entry;

  /**
   *
   * @author pepe subirana
   */
  public class Main {
    private static Vector states = new Vector();
    private static Vector events = new Vector();
    private static TreeMap start_p = new TreeMap();
    private static TreeMap transition_p = new TreeMap();
    private static TreeMap emission_p = new TreeMap();
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        
        init(); //FEED COLLECTIONS WITH VALUES.
        //PRINT();
        forward_viterbi();
    }

    private static void forward_viterbi(){

      HashMap T1 = new HashMap();
      //ITERATE OVER start_p to FEED T
      
    
      for(String state : states){
        
        Double start_prob = (Double) start_p.get(state);
        Vector v_pth = new Vector();
        v_pth.add(state);
        Tracking t = new Tracking(start_prob, v_pth,  start_prob);

        T1.put(state, t);
        
      }

      for(String output : events){

        HashMap U = new HashMap();
        
        for(String nextState : states){
          Tracking nextTracker = new Tracking(0.0, new Vector(),0.0 );
           
           for(String sourceState: states){

             Tracking T1t = T1.get(sourceState);  //TO AVOID MODIFYING T1
             Tracking sourceTracker = new Tracking(T1t.prob, T1t.v_path, 
                  T1t.v_prob);

             String s_out = sourceState+ "-" + output; //eg. Rainy-clean
             String s_next = sourceState + "-"+ nextState; // eg. Rainy
                                                           //     -Sunny
      
             Double p = emission_p.get(s_out) * transition_p.get(s_next);

             //MULTIPLY sourceTracker * this probability;

             sourceTracker.prob *= p;
             sourceTracker.v_prob *= p;


             //INCREASE nextTracker + this probability:
             nextTracker.prob = nextTracker.prob + sourceTracker.prob;


             if(sourceTracker.v_prob > nextTracker.v_prob){
                nextTracker.v_path = new Vector (sourceTracker.v_path);
                
                nextTracker.v_path.add(nextState);
                nextTracker.v_prob = sourceTracker.v_prob;
             }
           }
         U.put(nextState, nextTracker);
        
        }
        T1 = U;
      }

      //Apply sum/max to the final states:
      
      Tracking finalTracker = new Tracking(0.0, new Vector(), 0.0);;
      for(String st: states){
        Tracking T1t = (Tracking) T1.get(st);
        Tracking tracker = new Tracking(T1t.prob, T1t.v_path, T1t.v_prob);
       
        finalTracker.prob += tracker.prob;
        if(tracker.v_prob > finalTracker.v_prob){
          finalTracker.v_path = tracker.v_path;
          finalTracker.v_prob = tracker.v_prob;
        }
      }

      //OUTPUT:

      System.out.println("Total probability of the observation sequence:" 
           + finalTracker.prob);
      System.out.println("Probability of the Viterbi path:" 
          + finalTracker.v_prob);
      System.out.println("The Viterbi path:");
      for(String st: finalTracker.v_path){
        System.out.println(st);
      }
     
    }

    private static void init(){
      //FEED COLLECTIONS:
        states.add("Rainy");
        states.add("Sunny");

        //in order:
        events.add("walk");
        events.add("shop");
        events.add("clean");

        start_p.put("Rainy", 0.6);
        start_p.put("Sunny", 0.4);

        //CONDITIONAL PROBABILITIES:
        transition_p.put("Rainy-Rainy", 0.7);
        transition_p.put("Rainy-Sunny", 0.3);
        transition_p.put("Sunny-Rainy", 0.4);
        transition_p.put("Sunny-Sunny", 0.6);

        emission_p.put("Rainy-walk", 0.1);
        emission_p.put("Rainy-shop", 0.4);
        emission_p.put("Rainy-clean", 0.5);
        emission_p.put("Sunny-walk", 0.6);
        emission_p.put("Sunny-shop", 0.3);
        emission_p.put("Sunny-clean", 0.1);

    }

    public static void PRINT(){
      System.out.println("STATES");
      for(String s: states){ System.out.println(s);}

      System.out.println("EVENTS");
      for(String e: events){ System.out.println(e);}

      System.out.println("START PROBS");
      Set> s1 = start_p.entrySet();
      for(Map.Entry me: s1){
          System.out.println(me.getKey()+" > "+me.getValue());
      }

      System.out.println("TRANSITION PROBS");
      Set> s2 = transition_p.entrySet();
      for(Map.Entry me: s2){
          System.out.println(me.getKey()+" > "+me.getValue());
      }


      System.out.println("EMISSION PROBS");
      Set> s3 = emission_p.entrySet();
      for(Map.Entry me: s3){
          System.out.println(me.getKey()+" > "+me.getValue());
      }

    }
}

 
  2. TRACKER CLASS
    
  package nb_viterbi;

  import java.util.*;

  /**
   *
   * @author pepe subirana
   */
  public class Tracking {
   public double prob = 0.0;
   public double v_prob = 0.0;
   public Vector v_path = new Vector();

   public Tracking(Double p, Vector v_pth, Double v_p ){
    prob = p;
    v_prob = v_p;
    v_path = v_pth;
   }

   @Override public String toString(){
     String ret = prob + " / " + v_prob + " path: ";
     for (String iter : v_path) ret = ret.concat(iter);
     return ret;

   }
  }