-
-
Save lf94/a020e2aa4e691470a89dc7006b77c680 to your computer and use it in GitHub Desktop.
Viterbi
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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