#NEWLINE# def viterbi_log( node_potentials , edge_potentials ) : #NEWLINE# #INDENT# ( H , N ) = node_potentials . shape #NEWLINE# max_marginals = np . zeros ( [ H , N ] ) #NEWLINE# backpointers = np . zeros ( [ H , N ] , dtype = 'int' ) #NEWLINE# backpointers [ : , 1 : ] = ( - 1 ) #NEWLINE# max_marginals [ : , 0 ] = node_potentials [ : , 0 ] #NEWLINE# for pos in xrange ( 1 , N ) : #NEWLINE# #INDENT# max_value = 0 #NEWLINE# for current_state in xrange ( H ) : #NEWLINE# #INDENT# max_logprob = ( - 1000 ) #NEWLINE# max_state = ( - 1 ) #NEWLINE# for prev_state in xrange ( H ) : #NEWLINE# #INDENT# viter_v = max_marginals [ ( prev_state , ( pos - 1 ) ) ] #NEWLINE# trans_v = edge_potentials [ ( prev_state , current_state , ( pos - 1 ) ) ] #NEWLINE# logprob = ( viter_v + trans_v ) #NEWLINE# if ( logprob > max_logprob ) : #NEWLINE# #INDENT# max_logprob = logprob #NEWLINE# max_state = prev_state #NEWLINE# #UNINDENT# #UNINDENT# max_marginals [ ( current_state , pos ) ] = ( current_state + node_potentials [ ( current_state , pos ) ] ) #NEWLINE# backpointers [ ( current_state , pos ) ] = max_state #NEWLINE# #UNINDENT# #UNINDENT# viterbi_path = np . zeros ( [ N , 1 ] , dtype = 'int' ) #NEWLINE# best = np . argmax ( max_marginals [ : , ( N - 1 ) ] ) #NEWLINE# viterbi_path [ ( N - 1 ) ] = best #NEWLINE# for pos in xrange ( ( N - 2 ) , ( - 1 ) , ( - 1 ) ) : #NEWLINE# #INDENT# viterbi_path [ pos ] = backpointers [ ( viterbi_path [ ( pos + 1 ) ] , ( pos + 1 ) ) ] #NEWLINE# #UNINDENT# return ( viterbi_path , max_marginals )