User:Richard163/sandbox

This is the user sandbox of Richard163. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.

Other sandboxes: Main sandbox | Template sandbox

Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

In electrical engineering, computer science, statistical computing and bioinformatics, the Viterbi Path Counting algorithm is used to find the unknown parameters of a hidden Markov model (HMM). It makes use of the Viterbi algorithm.

Explanation

The Viterbi Path Counting algorithm is suited to training on multiple training sequences. The algorithm is a particular case of a generalized expectation-maximization (GEM) algorithm. It can compute maximum likelihood estimates and posterior mode estimates for the parameters (transition and emission probabilities) of an HMM, when given only emissions as training data.

For a given cell $S_{i}$ in the transition matrix, all paths to that cell are summed. There is a link (transition from that cell to a cell $S_{j}$ ). The joint probability of $S_{i}$ , the link, and $S_{j}$ can be calculated and normalized by the probability of the entire string. Call this $\chi$ .

Now, calculate the probability of all paths with all links emanating from $S_{i}$ . Normalize this by the probability of the entire string. Call this $\sigma$ .

Now divide $\chi$ by $\sigma$ . This is dividing the expected transition from $S_{i}$ to $S_{j}$ by the expected transitions from $S_{i}$ . As the corpus grows, and particular transitions are reinforced, they will increase in value, reaching a local maximum. No way to ascertain a global maximum is known.