Finite Trellises, Viterbi, and Sequence Decoding

A finite weighted trellis has an integer length $T\ge 0$. If $T=0$, it is the empty structure, with no vertex layers, edges, or endpoint weights. If $T\ge 1$, it consists of finite vertex sets $V_1,\dots ,V_T$, edge sets $E_t\subseteq V_{t-1}\times V_t$ for $2\le t\le T$, positive edge weights $w_t:E_t\to (0,\mathrm{\infty })$, and initial and terminal weights $\alpha :V_1\to [0,\mathrm{\infty })$ and $\beta :V_T\to [0,\mathrm{\infty })$. The sets $V_t$ may be empty. A zero initial or terminal weight disables that endpoint; every edge in $E_t$ is allowed and has positive weight.

A path for $T\ge 1$ is a tuple $(v_1,\dots ,v_T)$ with $v_t\in V_t$, $\alpha (v_1)>0$, $\beta (v_T)>0$, and $(v_{t-1},v_t)\in E_t$ for every $2\le t\le T$. Its score is $\alpha (v_1)({\prod }_{t=2}^T{w}_t(v_{t-1},v_t))\beta (v_T),$ where the empty product for $T=1$ is $1$. For $T=0$, the unique path is the empty tuple, with score $1$ (the empty product).

A prefix path through layer $t$, for $1\le t\le T$, satisfies the same conditions through $v_t$, without a terminal-weight condition. For $T=0$, the empty tuple is the unique prefix path through no layers, with score $1$. A vertex $v\in V_t$ is reachable if some prefix path ends at $v$; otherwise it is unreachable. There are finitely many paths. If at least one path exists, its maximum score is attained; if none exists, the trellis has no admissible path.

A finite discrete hidden Markov model (HMM) is a tuple $(S,Y,\pi ,A,B)$, where $S$ is a finite nonempty hidden-state set, $Y$ is a finite nonempty observation alphabet, $\pi :S\to [0,1]$ is an initial probability distribution, $A:S\times S\to [0,1]$ is a transition matrix, and $B:S\times Y\to [0,1]$ is an emission matrix. The parameters satisfy ${\sum }_{s\in S}\pi (s)=1,{\sum }_{s^{\mathrm{\prime }}\in S}A(s,s^{\mathrm{\prime }})=1(s\in S),{\sum }_{y\in Y}B(s,y)=1(s\in S)\mathrm{.}$

For each length $T\ge 1$, hidden path $z=(z_1,\dots ,z_T)\in S^T$, and observation sequence $y=(y_1,\dots ,y_T)\in Y^T$, define the joint mass $p(z,y)=\pi (z_1)B(z_1,y_1){\prod }_{t=2}^{T}A(z_{t-1},z_t)B(z_t,y_t)\mathrm{.}$ The evidence of $y$ is $p(y)={\sum }_{z\in S^T}p(z,y)$. When $p(y)>0$, the conditional path mass is $p(z\mid y)=p(z,y)\mathrm{/}p(y)$, and a sequence MAP (maximum-a-posteriori) path is any $z$ maximizing this conditional mass. If $p(y)=0$, the conditional path mass is undefined, so there is no posterior sequence MAP path for that observation sequence. A zero transition or emission factor gives that hidden path zero joint mass.

For a finite weighted trellis with $T=0$, the unique prefix path through no layers is empty and has score $1$. For $T\ge 1$, define $D_1(v)=\alpha (v)$ and, for $2\le t\le T$, $D_t(v)=\max (\{D_{t-1}(u)w_t(u,v):(u,v)\in E_t\}\cup \{0\})\mathrm{.}$ Then $D_t(v)$ is the maximum score of a prefix path ending at $v$; if no such prefix exists, $D_t(v)=0$.

For every finite discrete HMM and each integer $T\ge 1$, the joint masses $p(z,y)$ in the Definition sum to $1$ over all hidden paths $z\in S^T$ and observation sequences $y\in Y^T$.

Input: A finite weighted trellis and a total order on each vertex set.

Output: “No admissible path,” or an admissible path and its score.

If $T=0$, return the empty path with score $1$. Otherwise perform the following steps:

1. Set $D_1(v)=\alpha (v)$ for all $v\in V_1$. For each layer $t=2,\dots ,T$ and each $v\in V_t$, compute $D_t(v)=\max (\{D_{t-1}(u)w_t(u,v):(u,v)\in E_t\}\cup \{0\})\mathrm{.}$ If $D_t(v)>0$, store as $p_t(v)$ the first predecessor $u$ in the supplied vertex order attaining this maximum; if $D_t(v)=0$, leave $p_t(v)$ undefined.
2. Compute $Q(v)=D_T(v)\beta (v)$ for all $v\in V_T$. If every $Q(v)=0$, return “no admissible path.”
3. Otherwise choose the first $v_T$ in the supplied order maximizing $Q(v)$, and follow the stored pointers $p_T(v_T),p_{T-1}(v_{T-1}),\dots ,p_2(v_2)$ backwards. Return the resulting path and its score $Q(v_T)$.

The stored predecessor at each layer is a backpointer. Following these pointers backward from a maximizing terminal vertex is called traceback. The given orders make the returned path deterministic when several paths have the same maximum score. The empty path at $T=0$ is the unique path and is therefore the unique maximum-score output in that case.

For every finite weighted trellis, the algorithm returns “no admissible path” exactly when the trellis has no path. Otherwise it returns an admissible path whose score is maximal among all admissible paths. If $V={\sum }_{t=1}^T\mathrm{\mid }{V}_t\mathrm{\mid }$ and $E={\sum }_{t=2}^T\mathrm{\mid }{E}_t\mathrm{\mid }$ (with empty sums taken as $0$), then when each real multiplication and comparison is counted as one operation the running time is $O(1+T+V+E)$ and the auxiliary storage is $O(1+V)$. In the $T=0$ case the algorithm returns the unique empty path with score $1$.

Input: A finite discrete HMM $(S,Y,\pi ,A,B)$, an observation sequence $y=(y_1,\dots ,y_T)\in Y^T$ with $T\ge 1$, and a total order on $S$.

1. Form a trellis with $V_t=S$ at every layer. Set ${\alpha }_y(s)=\pi (s)B(s,y_1)$ and terminal weights ${\beta }_y(s)=1$.
2. For every $t=2,\dots ,T$, include the edge $(r,s)$ exactly when $A(r,s)>0$ and $B(s,y_t)>0$, and give it weight $w_t(r,s)=A(r,s)B(s,y_t)$.
3. Run Max-product Viterbi decoding on a finite trellis on this trellis using the supplied state order. If it returns no admissible path, return “zero evidence; no conditional sequence MAP.” Otherwise return its path as the decoded hidden-state sequence.

Zero transition or emission factors are omitted from the trellis, so every trellis path has positive joint mass.

Given a finite discrete HMM and an observation sequence of positive length, the sequence-decoding algorithm returns no conditional MAP path exactly when the observation evidence is zero. When the evidence is positive, it returns a hidden-state sequence maximizing the posterior probability of the entire sequence, including when there are ties.