Question

Viterbi algorithm

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 s(u, v) from a finite set S of sounds. The labeled graph is a formal model of a person speaking a restricted language. Each path in the graph starting from a distinguished vertex v0 in V corresponds to a possible sequence of sounds produced by the model. The label of a directed path is defined to be the concatenation of the labels of the edges on that path. 1

(a) Describe an efficient algorithm that, given an edge-labeled graph G with distinguished vertex v0 and a sequence L = (s1, s2, ..., sk) of characters from S, returns a path in G that begins at v0 and has L as its label, if any such path exists. Otherwise, the algorithm should return NO-SUCH PATH. Analyze the running time of your algorithm. Now, suppose that every edge (u, v) in E has also been given 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 v0 as the probability that a ”random walk” beginning at v0 will follow the specified path, where the choice of which edge to take at a vertex u is made probabilistically 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 staring at v0 and having label L. Analyse the running time of your algorithm.