# Equivalence between LC-CRF and HMM, and Discriminative Computing of HMM-Based MPM and MAP
## 3 Equivalence between HMMs and Simple Linear-Chain CRFs
If \(Z_{1:N}\) is a LC-CRF with the distribution \(p(x_{1:N}|y_{1:N})\) defined by_  
\[p(x_{1:N}|y_{1:N})=\frac{1}{\kappa(y_{1:N})}exp\left[\sum_{n=1}^{N-1}V_{n}(x_{ n},x_{n+1})+\sum_{n=1}^{N}U_{n}(x_{n},y_{n})\right] \tag{10}\]  
_then (Equation (10)) is the posterior distribution of the HMM_  
\[q(x_{1:N},y_{1:N})=q_{1}(x_{1})q(y_{1}|x_{1})\prod_{n=1}^{N-1}q(x_{n+1}|x_{n}) q(y_{n+1}|x_{n+1}) \tag{11}\]  
_with_  
\[q(x_{1},y_{1})=\frac{\beta_{1}(x_{1},y_{1})}{\sum_{(x_{1},y_{1})}\beta_{1}(x_ {1},y_{1})} \tag{12}\]  
_and, for \(n=1,\ldots,N-1\):_  
\[q(x_{n+1}|x_{n})=\frac{\psi(x_{n+1})exp[V_{n}(x_{n},x_{n+1})]}{\sum_{x_{n+1}} \psi(x_{n+1})exp[V_{n}(x_{n},x_{n+1})]} \tag{13}\]  
\[q(y_{n+1}|x_{n+1})=\frac{exp[U_{n+1}(x_{n+1},y_{n+1})]\beta_{n+1}(x_{n+1},y_{n+ 1})}{\psi(x_{n+1})} \tag{14}\]  
_where_  
\[\psi(x_{n+1})=\sum_{y_{n+1}}exp[U_{n+1}(x_{n+1},y_{n+1})]\beta_{n+1}(x_{n+1},y _{n+1}) \tag{15}\]  
_and \(\beta_{1}(x_{1},y_{1})\),... \(\beta_{N}(x_{N},y_{N})\)are given by the backward recursion_  
\[\beta_{N}(x_{N},y_{N})=1\]  
\[\beta_{n}(x_{n},y_{n})=\sum_{(x_{n+1},y_{n+1})}\exp[V_{n}(x_{n},x_{n+1})+U_{n +1}(x_{n+1},y_{n+1})]\beta_{n+1}(x_{n+1},y_{n+1}) \tag{16}\]  
**Proof of Proposition 1. ** Let us consider functions \(\varphi_{1}\),..., \(\varphi_{N}\) defined on \(\left[\Lambda\times\Omega\right]^{2}\) by  
\[\varphi_{1}(x_{1},y_{1},x_{2},y_{2})=exp[V_{1}(x_{1},x_{2})+U_{1}(x_{1},y_{1} )+U_{2}(x_{2},y_{2})] \tag{17}\]  
\[\varphi_{n}(x_{n},y_{n},x_{n+1},y_{n+1})=\exp[V_{n}(x_{n},x_{n+1})+U_{n+1}(x_ {n+1},y_{n+1})],\text{ for }n=2,\ldots,N-1 \tag{18}\]  
According to the lemma, they define a Markov chain \(Z_{1:N}=(Z_{1},\ldots,Z_{N})\), with \(Z_{n}=(X_{n},Y_{n})\). Let us denote its distribution by \(q(z_{1:N})=q(x_{1:N},y_{1:N})\). As \(q(x_{1:N},y_{1:N})=Kexp\left[\sum_{n=1}^{N-1}V_{n}(x_{n},x_{n+1})+\sum_{n=1}^{ N}U_{n}(x_{n},y_{n})\right]\) with \(K\) constant, we have \(q(x_{1:N}|y_{1:N})=p(x_{1:N}|y_{1:N})\). Let us show that \(q(x_{1:N},y_{1:N})\) verifies (Equations (11)-(16)). According to the lemma, considering \(\beta_{1}(x_{1},y_{1})\),..., \(\beta_{N}(x_{N},y_{N})\) defined with (Equation (16)), and \(\psi(x_{n+1})\) defined with (Equation (15)), we have  
\[ \begin{array}{c}q(x_{n+1},y_{n+1}|x_{n},y_{n})=\frac{\varphi_{n}(x_{n},y_{n},x _{n+1},y_{n+1})}{\sum_{(x_{n+1},y_{n+1})}\varphi_{n}(x_{n},y_{n},x_{n+1},y_{n+1 })\beta_{n+1}(x_{n+1},y_{n+1})}=\\ \frac{\exp[V_{n}(x_{n},x_{n+1})+U_{n+1}(x_{n+1},y_{n+1})]\beta_{n+1}(x_{n+1},y_ {n+1})}{\sum_{(y_{n+1},y_{n+1})}\exp[V_{n}(x_{n},x_{n+1})+U_{n+1}(x_{n+1},y_{n+1 })]\beta_{n+1}(x_{n+1},y_{n+1})}=\end{array}  \tag{19}\]\[\frac{\exp[V_{x_{1}(x_{n},x_{n+1})]\exp[U_{n+1}(x_{n+1}y_{n+1})]\beta_{n+1}(x_{n+1 }y_{n+1})}}{\sum_{x_{n+1}}\psi(x_{n+1})\exp[V_{x_{n}(x_{n},x_{n+1})]}}=\] \[\left[\frac{\exp[V_{y_{1}(x_{n},x_{n+1})]}}{\sum_{x_{n+1}}\psi(x_{n +1})\exp[V_{x_{n}(x_{n},x_{n+1})]}}\right]\left[\exp[U_{n+1}(x_{n+1},y_{n+1})] \beta_{n+1}(x_{n+1},y_{n+1})]=\] \[\left[\frac{\psi(x_{n+1})\exp[V_{y_{n}(x_{n},x_{n+1})]}}{\sum_{x_{n +1}}\psi(x_{n+1})\exp[V_{y_{n}(x_{n},x_{n+1})]}}\right]\left[\frac{\exp[U_{n+1}( x_{n+1},y_{n+1})]\beta_{n+1}(x_{n+1},y_{n+1})}{\psi(x_{n+1})}\right]=\] \[q(x_{n+1}|x_{n})q(y_{n+1}|x_{n+1})\]  
(12) being directly implied by the lemma, this ends the proof. \(\square\)