# Equivalence between LC-CRF and HMM, and Discriminative Computing of HMM-Based MPM and MAP
## 4 Discriminative Classifiers in Generative HMMs
### Discriminative Computing of HMM-Based MPM  
To show (ii), let us consider Equation (1) with \(p(y_{n}|x_{n})=\frac{p(y_{n})p(x_{n}|y_{n})}{p(x_{n})}\). It becomes,  
\[p(x_{1:N},y_{1:N})=p(x_{1}|y_{1})\prod_{n=2}^{T}p(x_{n}|x_{n-1})\frac{p(x_{n}| y_{n})}{p(x_{n})}\prod_{n=1}^{N}p(y_{n}) \tag{21}\]  
We see that (Equation (21)) is of the form \(p(x_{1:N},y_{1:N})=h(x_{1:N},y_{1:N})\prod_{n=1}^{N}p(y_{n})\), where \(h(x_{1:N},y_{1:N})\) does not depend on \(p(y_{1})\),..., \(p(y_{N})\). This implies that \(h(x_{n},y_{1:N})=\sum_{(x_{1:n-1},x_{n+1}:N)}h(x_{1:N},y_{1:N})\) does not depend on \(p(y_{1})\),..., \(p(y_{N})\) either. Then \(p(x_{n}|y_{1:N})=\frac{p(x_{n}y_{1:N})}{p(y_{1:N})}=\frac{h(x_{n},y_{1:N}) \prod_{n=1}^{N}p(y_{n})}{\left[\sum_{n}h(x_{n},y_{1:N})\right]\prod_{n=1}^{N}p( y_{n})}=\frac{h(x_{n},y_{1:N})}{\left[\sum_{n}h(x_{n},y_{1:N})\right]}\), so that  
\[p(x_{n}|y_{1:N})=\frac{\sum_{(x_{1:n-1},x_{n+1:N})}p(x_{1}|y_{1})\prod_{t=2}^{N }p(x_{n}|x_{n-1})\frac{p(x_{n}|y_{n})}{p(x_{n})}}{\sum_{(x_{1:N})}p(x_{1}|y_{1 })\prod_{t=2}^{N}p(x_{n}|x_{n-1})\frac{p(x_{n}|y_{n})}{p(x_{n})}} \tag{22}\]neither depends on \(p(y_{1}),\ldots,p(y_{N})\). Thus, the HMM-based classifier MPM also verifies the \"discriminative classifier\" definition. How to compute \(p(x_{n}|y_{1:N})\)? It is classically computable using \"forward\" probabilities \(\alpha_{n}(x_{n})\) and \"backward\" ones \(\beta_{n}(x_{n})\) defined with  
\[\alpha_{n}(x_{n})=p(x_{n},y_{1:n}) \tag{23}\]  
\[\beta_{n}(x_{n})=p(y_{n+1:N}|x_{n}) \tag{24}\]  
then  
\[p(x_{n}|y_{1:N})=\frac{\alpha_{n}(x_{n})\beta_{n}(x_{n})}{\sum_{x_{n}}\alpha_{ n}(x_{n})\beta_{n}(x_{n})} \tag{25}\]  
with all \(\alpha_{n}(x_{n})\) and \(\beta_{n}(x_{n})\) computed using the following forward and backward recursions [21]:  
\[\alpha_{1}(x_{1})=p(x_{1})p(y_{1}|x_{1});\,\alpha_{n+1}(x_{n+1})=\sum_{x_{n}} p(x_{n+1}|x_{n})p(y_{n+1}|x_{n+1})\alpha_{n}(x_{n}) \tag{26}\]  
\[\beta_{N}(x_{N})=1;\,\beta_{n}(x_{n})=\sum_{x_{n+1}}p(x_{n+1}|x_{n})p(y_{n+1}| x_{n+1})\beta_{n+1}(x_{n+1}) \tag{27}\]  
Setting \(p(y_{n}|x_{n})=\frac{p(y_{n})p(x_{n}|y_{n})}{p(x_{n})}\) and recalling that \(p(x_{n}|y_{1:N})\) does not depend on \(p(y_{1}),\ldots,p(y_{N})\), we can arbitrarily modify them. Let us consider the uniform distribution over \(\Omega\), so that \(p(y_{1})=\ldots=p(y_{N})=\frac{1}{\delta\Omega}=c\). Then (Equation (26)) and (Equation (27)) become  
\[\alpha_{n+1}^{*}(x_{n+1})=\sum_{x_{n}}p(x_{n+1}|x_{n})\frac{cp(x_{n+1}|y_{n+1} )}{p(x_{n+1})}\alpha_{n}^{*}(x_{n}) \tag{28}\]  
\[\beta_{n}^{*}(x_{n})=\sum_{x_{n+1}}p(x_{n+1}|x_{n})\frac{cp(x_{n+1}|y_{n+1})} {p(x_{n+1})}\beta_{n+1}^{*}(x_{n+1}) \tag{29}\]  
and we still have  
\[p(x_{n}|y_{1:N})=\frac{\alpha_{n}^{*}(x_{n})\beta_{n}^{*}(x_{n})}{\sum_{x_{n} }\alpha_{n}^{*}\beta_{n}^{*}(x_{n})} \tag{30}\]  
Finally, we see that \(p(x_{n}|y_{1:N})\) is independent from \(c\), so that we can take \(c=1\). Then we can state the following proposition. Proposition 2: _Let \(X_{1}\),\(\ldots,X_{N}\),\(Y_{1}\),\(\ldots,Y_{N}\) be an HMM Equation (1).