# Equivalence between LC-CRF and HMM, and Discriminative Computing of HMM-Based MPM and MAP
## 3 Equivalence between HMMs and Simple Linear-Chain CRFs  
We will use the following Lemma:  
**Lemma 1**. : _Let \(W_{1:N}=(W_{1},\ldots,W_{N})\) be random sequence, taking its values in a finite set \(\Delta\). Then_  
1. \(W_{1:N}\) _is a Markov chain if and only if (iff) there exist_ \(N-1\) _functions_ \(\varphi_{1},\ldots,\varphi_{N-1}\) _from_ \(\Delta^{2}\) _to_ \(\mathbb{R}^{+}\) _such that_ \[p(w_{1},\ldots,w_{N})\propto\varphi_{1}(w_{1},w_{2})\ldots\varphi_{N-1}(w_{N- 1},w_{N})\] (6) _where \"_\(\propto\)_\" means \"proportional to\";_
2. _For the HMM defined with_ \(\varphi_{1}\)_,_ \(\ldots\) _,_ \(\varphi_{N-1}\) _verifying Equation (_6_),_ \(p(w_{1})\) _and_ \(p(w_{n+1}|w_{n})\) _are given with_ \[p(w_{1})=\frac{\beta_{1}(w_{1})}{\sum_{w_{1}}\beta_{1}(w_{1})};p(w_{n+1}|w_{n} )=\frac{\varphi_{n}(w_{n},w_{n+1})\beta_{n+1}(w_{n+1})}{\beta_{n}(w_{n})}\] (7) _where_ \(\beta_{1}(w_{1})\)_,_ \(\ldots\) _,_ \(\beta_{N}(w_{N})\) _are defined with the following backward recursion:_ \[\beta_{N}(w_{N}){=}\ 1,\ \beta_{n}(w_{n})=\sum_{w_{n+1}}\varphi_{n}(w_{n},w_{n+1}) \beta_{n+1}(w_{n+1})\] (8)  
**Proof of Lemma. **  
1. Let \(W_{1:N}\) be Markov: \(p(w_{1},\ldots,w_{N})=p(w_{1})p(w_{2}|w_{1})p(w_{3}|w_{2})\ldots p(w_{N}|w_{N- 1})\). Then (Equation (6)) is verified by \(\varphi_{1}(w_{1},w_{2})=p(w_{1})p(w_{2}|w_{1})\), \(\varphi_{2}(w_{2},w_{3})=p(w_{3}|w_{2})\), \(\ldots\), \(\varphi_{N-1}(w_{N-1},w_{N})=p(w_{N}|w_{N-1})\). 2. Conversely, let \(p(w_{1},\ldots,w_{N})\) verifies (Equation (6)). Thus \(p(w_{1},\ldots,w_{N})=K\varphi_{1}(w_{1},w_{2})\ldots\varphi_{N-1}(w_{N-1},w_ {N})\) with \(K\) constant. This implies that for each \(n=1\), \(\ldots\), \(N-1\) we have \[ \begin{array}{c}p(w_{n+1}|w_{1},\ldots,w_{n})=\frac{p(w_{1},\ldots,w_{n},w_ {n+1})}{p(w_{1},\ldots,w_{n})}=\\ \frac{\sum_{(w_{n+2},\ldots,w_{N})}\varphi_{1}(w_{1},w_{2})\ldots\varphi_{n}( w_{n},w_{n+1})\varphi_{n+1}(w_{n+1},w_{n+2})\ldots\varphi_{N-1}(w_{N-1},w_{N})}{ \sum_{(w_{n+1},w_{2},\ldots,w_{N})}\varphi_{1}(w_{1},w_{2})\ldots\varphi_{(w_{ n},w_{n+1})\varphi_{n+1}(w_{1},w_{2})\ldots\varphi_{N-1}(w_{N-1},w_{N})}}=\\ \frac{\varphi_{n}(w_{n},w_{n+1})\sum_{(w_{n+2},\ldots,w_{N})}\varphi_{n}+ (w_{n+1},w_{n+2})\ldots\varphi_{N-1}(w_{N-1},w_{N})}{\sum_{(w_{n+1},w_{n+2}, \ldots,w_{N})}\varphi_{n}(w_{n},w_{n+1})\varphi_{n+1}(w_{n+1},w_{n+2})\ldots \varphi_{N-1}(w_{N-1},w_{N})}=p(w_{n+1}|w_{n})\end{array} \] (9) which shows that \(p(w_{1},\ldots,w_{N})\) is Markov. Moreover, let us set \(\beta_{n}(w_{n})=\sum_{(w_{n+1},w_{n+2},\ldots,w_{N})}\varphi_{n}(w_{n},w_{n+1 })\ldots\varphi_{N-1}(w_{N-1},w_{N})\) for \(n=1\), \(\ldots\), \(N-1\). On the one hand, we see that \(\beta_{n}(w_{n})=\sum_{w_{n+1}}\varphi_{n}(w_{n},w_{n+1})\beta_{n+1}(w_{n+1})\). On the other hand, according to (Equation (9)) we have \(p(w_{n+1}|w_{n})=\frac{\varphi_{n}(w_{n},w_{n+1})\beta_{n+1}(w_{n+1})}{\beta_{ n}(w_{n})}\). As \(p(w_{1})=\frac{\beta_{1}(w_{1})}{\sum_{w_{1}}\beta_{1}(w_{1})}\), (Equation (7)) and (Equation (8)) are verified, which ends the proof. \(\square\)Proposition 1 below shows that the LC-CRF defined with (Equation (3)) is equivalent to an HMM defined with Equation (1). In addition, \(p(x_{1})\), \(p(x_{n+1}|x_{n})\), and \(p(y_{n}|x_{n})\) in Equation (1) defining an equivalent HMM are computed from \(V_{n}(x_{n},x_{n+1})\) and \(U_{n}(x_{n},y_{n})\). To the best of our knowledge, except some first weaker results in [19], these results are new. **Proposition 1**. : _Let \(Z_{1:N}=(Z_{1},\ldots,Z_{N})\) be a stochastic sequence, with\(Z_{n}=(X_{n},Y_{n})\). Each \((X_{n},Y_{n})\) takes its values in \(\Lambda\times\Omega\), with \(\Lambda\) and \(\Omega\) finite.