Skip to content

Instantly share code, notes, and snippets.

@methodin
Created January 7, 2012 21:59
Show Gist options
  • Star 5 You must be signed in to star a gist
  • Fork 4 You must be signed in to fork a gist
  • Save methodin/1576192 to your computer and use it in GitHub Desktop.
Save methodin/1576192 to your computer and use it in GitHub Desktop.
Viterbi
// Viterbi algorithm for finding hidden relationships
function Viterbi(data) {
var V = [{}];
var path = {};
// Initialize base cases (t == 0)
for(var i=0;i<data.states.length;i++) {
var state = data.states[i];
V[0][state] = data.start_probability[state] * data.emission_probability[state][data.observations[0]];
path[state] = [state];
}
// Run Viterbi for t > 0
for(var t=1;t<data.observations.length;t++) {
V.push({});
var newpath = {};
for(var i=0;i<data.states.length;i++) {
var state = data.states[i];
var max = [0,null];
for(var j=0;j<data.states.length;j++) {
var state0 = data.states[j];
// Calculate the probablity
var calc = V[t-1][state0]
* data.transition_probability[state0][state]
* data.emission_probability[state][data.observations[t]];
if(calc > max[0]) max = [calc,state0];
}
V[t][state] = max[0];
newpath[state] = path[max[1]].concat(state);
}
path = newpath;
}
var max = [0,null];
for(var i=0;i<data.states.length;i++) {
var state = data.states[i];
var calc = V[data.observations.length-1][state];
if(calc > max[0]) max = [calc,state];
}
return [max[0], path[max[1]]];
}
var result = Viterbi({
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},
}
});
document.write(result[0]+'<br>');
for(var i=0;i<result[1].length;i++)
document.write((i==0?'':'->')+result[1][i]);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment