3
$\begingroup$

I have a question regarding recursion in Viterbi algorithm.

Define $\pi(k; u; v)$ which is the maximum probability for any sequence of length $k$, ending in the tag bigram $(u; v)$.

The base case if obvious $\pi(0,*,*)=1$

The general case.

$\pi(k,u,v) = max_{w \in K_{k-2} } \pi(k-1,w,u) \cdot q(v|w,u) \cdot e(x_k|v)$

The author justifies the recursion as folllows:

How can we justify this recurrence? Recall that $\pi(k, u, v)$ is the highest probability for any sequence $y_{−1}...y_k$ ending in the bigram $(u, v)$. Any such sequence must have $y_{k−2} = w$ for some state $w$. The highest probability for any sequence of length $k − 1$ ending in the bigram $(w, u)$ is $\pi(k − 1, w, u)$, hence the highest probability for any sequence of length $k$ ending in the trigram $(w, u, v)$ must be $\pi(k − 1,w, u) \cdot q(v|w, u) \cdot e(x_k |v)$

I do not understand why it's actually true, I think it's possible to reach $\pi(n,u, v)$ from any $(n-1,w, u)$ not actually the maximum one $\pi(n-1,w, u)$ just because $q(v|w, u) \cdot e(x_k |v)$ might have a higher influence on the resulting $(n,u, v)$ than any $\pi(n-1,w, u)$.

I would appreciate if anyone could explain me why it's true.

$\endgroup$
1
$\begingroup$

The maximum is over the entire expression $\pi(k-1,w,u) \cdot q(v|w,u) \cdot e(x_k|v)$, for exactly the same reason that is worrying you. Moreover, under your original interpretation, there is no reason to keep $\pi(k-1,w,u)$ for the non-optimal $w$. We are forced to store $\pi(k-1,w,u)$ for all $w$ exactly for the reason you mention.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.