Viterbi algorithm We can use dynamic programming on a

Chapter 15, Problem 15-7

(choose chapter or problem)

We can use dynamic programming on a directed graph G = (V, E) for speech recognition. Each edge \((u, v) \in E\) is labeled with a sound \(\sigma(u, v)\) from a finite set \(\Sigma\) of sounds. The labeled graph is a formal model of a person speaking for a restricted language. Each path in the graph starting from a distinguished vertex \(v_{0} \in V\) corresponds to a possible sequence of sounds produced by the model. We define the label of a directed path to be the concatenation of the labels of the edges on that path.

a. Describe an efficient algorithm that, given an edge-labeled graph G with distinguished vertex \(v_{0}\) and a sequence \(s=\left\langle\sigma_{1}, \sigma_{2}, \ldots, \sigma_{k}\right\rangle\) of sounds from \(\Sigma\), returns a path in G that begins at \(v_{0}\) and has s as its label, if any such path exists. Otherwise, the algorithm should return NO-SUCH-PATH. Analyze the running time of your algorithm. (Hint: You may find concepts from Chapter 22 useful.)

Now, suppose that every edge \((u, v) \in E\) has an associated nonnegative probability \(p(u, v)\) of traversing the edge \((u, v)\) from vertex u and thus producing the corresponding sound. The sum of the probabilities of the edges leaving any vertex equals 1. The probability of a path is defined to be the product of the probabilities of its edges. We can view the probability of a path beginning at \(v_{0}\) as the probability that a “random walk” beginning at \(v_{0}\) will follow the specified path, where we randomly choose which edge to take leaving a vertex u according to the probabilities of the available edges leaving u.

b. Extend your answer to part (a) so that if a path is returned, it is a most probable path starting at \(v_{0}\) and having label s. Analyze the running time of your algorithm.