15-7 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 $\sigma(u, v)$ from a finite set $\Sigma$ 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 $v_0 \in V$ corresponds to a possible sequence of sounds producted 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 = \langle \sigma_1, \sigma_2, \ldots, \sigma_k \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 $\text{NO-SUCH-PATH}$. Analyze the running time of your algorithm. ($\textit{Hint:}$ You may find concepts from Chapter 22 useful.)

Now, suppose that every edge $(u, v) \in E$ has an associated nonnegatve 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 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.

a. Our substructure will consist of trying to find suffixes of s of length one less starting at all the edges leaving $v_0$ with label $\sigma_0$. if any of them have a solution, then, there is a solution. If none do, then there is none. See the algorithm $\text{VITERBI}$ for details.

VITERBI(G, s, v[0])
    if s.length = 0
        return v[0]
    for edges(v[0], v[1]) in V for some v[1]
        if sigma(v[0], v[1]) = sigma[1]
            res = VITERBI(G, (sigma[2], ..., sigma[k]), v[1])
            if res != NO-SUCH-PATH
                return (v[0], res)
    return NO-SUCH-PATH

Since the subproblems are indexed by a suffix of $s$ (of which there are only $k$) and a vertex in the graph, there are at most $O(k|V|)$ different possible arguments. Since each run may require testing a edge going to every other vertex, and each iteration of the for loop takes at most a constant amount of time other than the call to $\text{PROB-VITERBI}$, the final runtime is $O(k|V|^2)$.

b. For this modification, we will need to try all the possible edges leaving from $v_0$ instead of stopping as soon as we find one that works. The substructure is very similar. We'll make it so that instead of just returning the sequence, we'll have the algorithm also return the probability of that maximum probability sequence, calling the fields seq and prob respectively. See the algorithm $\text{PROB-VITERBI}$.

Since the runtime is indexed by the same things, we have that we will call it with at most $O(k|V|)$ different possible arguments. Since each run may require testing a edge going to every other vertex, and each iteration of the for loop takes at most a constant amount of time other than the call to $\text{PROB-VITERBI}$, the final runtime is $O(k|V|^2)$.

PROB-VITERBI(G, s, v[0])
    if s.length = 0
        return v[0]
    sols.seq = NO-SUCH-PATH
    sols.prob = 0
    for edges(v[0], v[1]) in V for some v[1]
        if sigma(v[0], v[1]) = sigma[1]
            res = PROB-VITERBI(G, (sigma[2], ..., sigma[k]), v[1])
            if p(v[0], v[1]) * res.prob ≥ sols.prob
                sols.prob = p(v[0], v[1]) * res.prob and sols.seq = v[0], res.seq
    return sols