The following implementations of thew:Viterbi algorithm were removed froman earlier copy of the Wikipedia page because they were too long and unencyclopaedic - but we hope you'll find them useful here!
publicclassViterbi{privatestaticString[]states={"#","NN","VB"};privatestaticString[]observations={"I","write","a letter"};privatestaticdouble[]start_probability={0.3,0.4,0.3};privatestaticdouble[][]transition_probability={{0.2,0.2,0.6},{0.4,0.1,0.5},{0.1,0.8,0.1}};privatestaticdouble[][]emission_probability={{0.01,0.02,0.02},{0.8,0.01,0.5},{0.19,0.97,0.48}};privatestaticclassTNode{publicint[]v_path;publicdoublev_prob;publicTNode(int[]v_path,doublev_prob){this.v_path=copyIntArray(v_path);this.v_prob=v_prob;}}privatestaticint[]copyIntArray(int[]ia){int[]newIa=newint[ia.length];for(inti=0;i<ia.length;i++){newIa[i]=ia[i];}returnnewIa;}privatestaticint[]copyIntArray(int[]ia,intnewInt){int[]newIa=newint[ia.length+1];for(inti=0;i<ia.length;i++){newIa[i]=ia[i];}newIa[ia.length]=newInt;returnnewIa;}// forwardViterbi(observations, states, start_probability,// transition_probability, emission_probability)publicint[]forwardViterbi(String[]y,String[]X,double[]sp,double[][]tp,double[][]ep){TNode[]T=newTNode[X.length];for(intstate=0;state<X.length;state++){int[]intArray=newint[1];intArray[0]=state;T[state]=newTNode(intArray,sp[state]*ep[state][0]);}for(intoutput=1;output<y.length;output++){TNode[]U=newTNode[X.length];for(intnext_state=0;next_state<X.length;next_state++){int[]argmax=newint[0];doublevalmax=0;for(intstate=0;state<X.length;state++){int[]v_path=copyIntArray(T[state].v_path);doublev_prob=T[state].v_prob;doublep=ep[next_state][output]*tp[state][next_state];v_prob*=p;if(v_prob>valmax){if(v_path.length==y.length){argmax=copyIntArray(v_path);}else{argmax=copyIntArray(v_path,next_state);}valmax=v_prob;}}U[next_state]=newTNode(argmax,valmax);}T=U;}// apply sum/max to the final states:int[]argmax=newint[0];doublevalmax=0;for(intstate=0;state<X.length;state++){int[]v_path=copyIntArray(T[state].v_path);doublev_prob=T[state].v_prob;if(v_prob>valmax){argmax=copyIntArray(v_path);valmax=v_prob;}}System.out.print("Viterbi path: [");for(inti=0;i<argmax.length;i++){System.out.print(states[argmax[i]]+", ");}System.out.println("].\n Probability of the whole system: "+valmax);returnargmax;}publicstaticvoidmain(String[]args)throwsException{System.out.print("\nStates: ");for(inti=0;i<states.length;i++){System.out.print(states[i]+", ");}System.out.print("\n\nObservations: ");for(inti=0;i<observations.length;i++){System.out.print(observations[i]+", ");}System.out.print("\n\nStart probability: ");for(inti=0;i<states.length;i++){System.out.print(states[i]+": "+start_probability[i]+", ");}System.out.println("\n\nTransition probability:");for(inti=0;i<states.length;i++){System.out.print(" "+states[i]+": {");for(intj=0;j<states.length;j++){System.out.print(" "+states[j]+": "+transition_probability[i][j]+", ");}System.out.println("}");}System.out.println("\n\nEmission probability:");for(inti=0;i<states.length;i++){System.out.print(" "+states[i]+": {");for(intj=0;j<observations.length;j++){System.out.print(" "+observations[j]+": "+emission_probability[i][j]+", ");}System.out.println("}");}Viterbiv=newViterbi();v.forwardViterbi(observations,states,start_probability,transition_probability,emission_probability);}}
(* Nick Heiner *)(* Viterbi algorithm, as described here: http://people.ccmr.cornell.edu/~ginsparg/INFO295/vit.pdf priorProbs: prior probability of a hidden state occuring transitions: probability of one hidden state transitioning into another emissionProbs: probability of a hidden state emitting an observed state observation: a sequence of observed states hiddens: a list of all possible hidden states Returns: probability of most likely path * hidden state list representing the path*)letviterbi(priorProbs:'hidden->float)(transitions:('hidden*'hidden)->float)(emissionProbs:(('observed*'hidden)->float))(observation:'observed[])(hiddens:'hiddenlist):float*'hiddenlist=(* Referred to as v_state(time) in the notes *)(* Probability of the most probable path ending in state at time *)letrecmostLikelyPathProb(state:'hidden)(time:int):float*'hiddenlist=letemission=emissionProbs(observation.[time],state)matchtimewith(* If we're at time 0, then just use the emission probability and the prior probability for this state *)|0->emission*priorProbsstate,[state](* If we're not at time 0, then recursively look for the most likely path ending at this time *)|twhent>0->letprob,path=Seq.maxByfst(seq{forhiddenStateinhiddens->(* Recursively look for most likely path at t - 1 *)letprob,path=mostLikelyPathProbhiddenState(time-1)(* Rate each path by how likely it is to transition into the current state *)transitions(List.headpath,state)*prob,path})emission*prob,state::path(* If time is < 0, then throw an error *)|_->failwith"time must be >= 0"(* Look for the most likely path that ends at t_max *)letprob,revPath=Seq.maxByfst(seq{forhiddenStateinhiddens->mostLikelyPathProbhiddenState((Array.lengthobservation)-1)})prob,List.revrevPath(* example using data from this article: *)typewikiHiddens=Healthy|FeverletwikiHiddenList=[Healthy;Fever]typewikiObservations=Normal|Cold|DizzyletwikiPriors=function|Healthy->0.6|Fever->0.4letwikiTransitions=function|(Healthy,Healthy)->0.7|(Healthy,Fever)->0.3|(Fever,Healthy)->0.4|(Fever,Fever)->0.6letwikiEmissions=function|(Cold,Healthy)->0.4|(Normal,Healthy)->0.5|(Dizzy,Healthy)->0.1|(Cold,Fever)->0.3|(Normal,Fever)->0.1|(Dizzy,Fever)->0.6viterbiwikiPriorswikiTransitionswikiEmissions[|Dizzy;Normal;Cold|]wikiHiddenList
(nsident.viterbi(:use[clojure.pprint]))(defstructhmm:n:m:init-probs:emission-probs:state-transitions)(defnmake-hmm[{:keys[states,obs,init-probs,emission-probs,state-transitions]}](struct-maphmm:n(countstates):m(countobs):statesstates:obsobs:init-probsinit-probs;; n dim:emission-probsemission-probs;;m x n:state-transitionsstate-transitions))(defnindexed[s](map vector(iterate inc0)s))(defnargmax[coll](loop[s(indexedcoll)max(firsts)](if(empty?s)max(let[[idxelt](firsts)[max-indxmax-elt]max](if(>eltmax-elt)(recur(rests)(firsts))(recur(rests)max))))))(defnpprint-hmm[hmm](println"number of states: "(:nhmm)" number of observations: "(:mhmm))(print"init probabilities: ")(pprint(:init-probshmm))(print"emission probs: ")(pprint(:emission-probshmm))(print"state-transitions: ")(pprint(:state-transitionshmm)))(defninit-alphas[hmmobs](map(fn[x](*(aget(:init-probshmm)x)(aget(:emission-probshmm)xobs)))(range(:nhmm))))(defnforward[hmmalphasobs](map(fn[j](*(reduce(fn[sumi](+sum(*(nthalphasi)(aget(:state-transitionshmm)ij))))0(range(:nhmm)))(aget(:emission-probshmm)jobs)))(range(:nhmm))))(defndelta-max[hmmdeltasobs](map(fn[j](*(apply max(map(fn[i](*(nthdeltasi)(aget(:state-transitionshmm)ij)))(range(:nhmm))))(aget(:emission-probshmm)jobs)))(range(:nhmm))))(defnbacktrack[pathsdeltas](loop[path(reversepaths)term(first(argmaxdeltas))backtrack[]](if(empty?path)(reverse(conjbacktrackterm))(recur(restpath)(nth(firstpath)term)(conjbacktrackterm)))))(defnupdate-paths[hmmdeltas](map(fn[j](first(argmax(map(fn[i](*(nthdeltasi)(aget(:state-transitionshmm)ij)))(range(:nhmm))))))(range(:nhmm))))(defnviterbi[hmmobservs](loop[obs(restobservs)alphas(init-alphashmm(firstobservs))deltasalphaspaths[]](if(empty?obs)[(backtrackpathsdeltas)(float(reduce +alphas))](recur(restobs)(forwardhmmalphas(firstobs))(delta-maxhmmdeltas(firstobs))(conjpaths(update-pathshmmdeltas))))))
usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;namespaceViterbi{classProgram{//Weather statesstaticStringHEALTHY="Healthy";staticStringFEVER="Fever";//Dependable actions (observations)staticStringDIZZY="dizzy";staticStringCOLD="cold";staticStringNORMAL="normal";staticvoidMain(string[]args){//initialize our arrays of states and observationsString[]states={HEALTHY,FEVER};String[]observations={DIZZY,COLD,NORMAL};varstart_probability=newDictionary<String,float>();start_probability.Add(HEALTHY,0.6f);start_probability.Add(FEVER,0.4f);//Transition probabilityvartransition_probability=newDictionary<String,Dictionary<String,float>>();vart1=newDictionary<String,float>();t1.Add(HEALTHY,0.7f);t1.Add(FEVER,0.3f);Dictionary<String,float>t2=newDictionary<String,float>();t2.Add(HEALTHY,0.4f);t2.Add(FEVER,0.6f);transition_probability.Add(HEALTHY,t1);transition_probability.Add(FEVER,t2);//emission_probabilityvaremission_probability=newDictionary<String,Dictionary<String,float>>();vare1=newDictionary<String,float>();e1.Add(DIZZY,0.1f);e1.Add(COLD,0.4f);e1.Add(NORMAL,0.5f);Dictionary<String,float>e2=newDictionary<String,float>();e2.Add(DIZZY,0.6f);e2.Add(COLD,0.3f);e2.Add(NORMAL,0.1f);emission_probability.Add(HEALTHY,e1);emission_probability.Add(FEVER,e2);Object[]ret=forward_viterbi(observations,states,start_probability,transition_probability,emission_probability);Console.WriteLine((float)ret[0]);Console.WriteLine((String)ret[1]);Console.WriteLine((float)ret[2]);Console.ReadLine();}publicstaticObject[]forward_viterbi(String[]obs,String[]states,Dictionary<String,float>start_p,Dictionary<String,Dictionary<String,float>>trans_p,Dictionary<String,Dictionary<String,float>>emit_p){varT=newDictionary<String,Object[]>();foreach(Stringstateinstates){T.Add(state,newObject[]{start_p[state],state,start_p[state]});}foreach(Stringoutputinobs){varU=newDictionary<String,Object[]>();foreach(Stringnext_stateinstates){floattotal=0;Stringargmax="";floatvalmax=0;floatprob=1;Stringv_path="";floatv_prob=1;foreach(Stringsource_stateinstates){Object[]objs=T[source_state];prob=((float)objs[0]);v_path=(String)objs[1];v_prob=((float)objs[2]);floatp=emit_p[source_state][output]*trans_p[source_state][next_state];prob*=p;v_prob*=p;total+=prob;if(v_prob>valmax){argmax=v_path+","+next_state;valmax=v_prob;}}U.Add(next_state,newObject[]{total,argmax,valmax});}T=U;}floatxtotal=0;Stringxargmax="";floatxvalmax=0;floatxprob;Stringxv_path;floatxv_prob;foreach(Stringstateinstates){Object[]objs=T[state];xprob=((float)objs[0]);xv_path=((String)objs[1]);xv_prob=((float)objs[2]);xtotal+=xprob;if(xv_prob>xvalmax){xargmax=xv_path;xvalmax=xv_prob;}}returnnewObject[]{xtotal,xargmax,xvalmax};}}}