A HOPFIELD NETWORK IMPLEMENTATION OF THE VITERBI ALGORITHM FOR HIDDEN MARKOV MODELS

Sreeram V. B. Aiyer and Frank Fallside

June 1992

Treating the Viterbi algorithm as a form of combinatorial optimization, this paper shows how it can be implemented on a Hopfield network. The implementation uses a framework developed in our previous papers [IEEE trans. NN. 6/90, CUED F-INFENG TR55] which ensures the network can achieve valid solutions for a much larger class of combinatorial optimization problem than previously considered. This class includes dynamic programming problems of the type represented by the Viterbi algorithm. The aim here is to present in detail the actual mapping required to implement the Viterbi algorithm on the Hopfield network, together with an analysis and justification of it. Finally, to confirm the theory, results are presented which show the Hopfield network achieving the same solution as a standard dynamic programming based Viterbi algorithm, for a recognition task based on a pre-trained 10 state Hidden Markov model.}

(ftp:) aiyer_tr60.ps.Z (http:) aiyer_tr60.ps.Z

PDF (automatically generated from original PostScript document - may be badly aliased on screen):

(ftp:) aiyer_tr60.pdf | (http:) aiyer_tr60.pdf

If you have difficulty viewing files that end `'.gz'`

,
which are gzip compressed, then you may be able to find
tools to uncompress them at the gzip
web site.

If you have difficulty viewing files that are in PostScript, (ending
`'.ps'`

or `'.ps.gz'`

), then you may be able to
find tools to view them at
the gsview
web site.

We have attempted to provide automatically generated PDF copies of documents for which only PostScript versions have previously been available. These are clearly marked in the database - due to the nature of the automatic conversion process, they are likely to be badly aliased when viewed at default resolution on screen by acroread.