# Equivalence between LC-CRF and HMM, and Discriminative Computing of HMM-Based MPM and MAP
###### Abstract
Thus, the distinction between \"generative\" classifiers and \"discriminative\" classifiers is misleading, they are all \"discriminative\", but they can be computed in a \"generative\" way, using \(p(y_{n}|x_{n})\), or in a discriminative manner, without using \(p(y_{n}|x_{n})\). Thus, we can say that our second contribution is to show that the HMM-based MPM and MAP, usually computed in a generative manner, can also be computed in a discriminative manner. This is important because it shows that abandoning HMMs in favor of CRFs in the aforementioned situations is not justified. Indeed, attached to the first contribution, it shows that the use of the MPM or MAP based on HMM (Equation (1)) is as interesting as the use of the MPM or MAP based on LC-CRF (Equation (3)). Let us give some more technical details on the two contributions. 1. We establish an equivalence between HMMs (Equation (1)) and basic linear-chain CRFs (Equation (3)), which completes the results presented in [14]. Let us notice that wanting to compare the two models directly is somewhat misleading. Indeed, HMMs and CRFs are defined with distributions on different spaces. To be precise, we adopt the following definition:  
**Definition 1**. : _Let \(X_{1},\,\ldots,X_{N},\,Y_{1},\,\ldots,Y_{N}\) be the two stochastic sequences defined above._  
1. _We will call \"model\" a distribution_ \(p(x_{1:N},y_{1:N})\)_;_
2. _We will call \"conditional model\" a distribution_ \(p(x_{1:N}|y_{1:N})\)_;_
3. _We will say that a model_ \(p(x_{1:N},y_{1:N})\) _is \"equivalent\" to a conditional model_ \(q(x_{1:N}|y_{1:N})\) _if there exists a distribution_ \(r(y_{1:N})\) _such that_ \(p(x_{1:N},y_{1:N})=q(x_{1:N}|y_{1:N})r(y_{1:N})\)_._
4. _We will say that a family of models_ \(A\) _is \"equivalent\" to a family of conditional models_ \(B\) _if for each model_ \(p(x_{1:N},y_{1:N})\) _in_ \(A\) _there exists an equivalent conditional model_ \(q(x_{1:N}|y_{1:N})\) _in_ \(B\)_._  
According to Definition 1, HMMs are particular \"models\", while CRFs are particular \"conditional models\". Then a particular HMM model cannot be equal to a particular conditional CRF model, but it can be equivalent to the latter. Our contribution is to show that the family of LC-CRFs (Equation (3)) is equivalent to the family of HMMs (Equation (1)). In addition, we specify, for each LC-CRF \(q(x_{1:N}|y_{1:N})\), a particular HMM \(p(x_{1:N},y_{1:N})\) such that \(p(x_{1:N}|y_{1:N})=q(x_{1:N}|y_{1:N})\). Finally, the core of our first contribution is the following. Let \(p(x_{1:N},y_{1:N},\theta)\) be an HMM (Equation (1)), with parameters \(\theta\). Taking \(r(y_{1:N})=p(y_{1:N},\theta)\), it is immediate to see that \(p(x_{1:N}|y_{1:N},\theta)\) is an equivalent CRF. The converse is not immediate. Is a given CRF \(p(x_{1:N}|y_{1:N},\theta)\) equivalent to a certain HMM? If yes, can we find \(r(y_{1:N})\) such that \(p(x_{1:N}|y_{1:N},\theta)r(y_{1:N})\) is an HMM? Moreover, can we give its (Equation (1)) form? Answering to these questions in a simple linear-chain CRF case is our first contribution. More precisely, we show that the family of LC-CRFs (Equation (3)) is equivalent to the family of HMMs (Equation (1)), and we specify, for each LC-CRF \(p(x_{1:N}|y_{1:N})\), a particular HMM \(q(x_{1:N},y_{1:N})\) given in the form (Equation (1)), such that \(p(x_{1:N}|y_{1:N})=q(x_{1:N}|y_{1:N})\). 2. We show that the \"generative\" estimators MPM and MAP in HMM are computable in a \"discriminative\" manner, exactly as in LC-CRF. One of the interests of HMMs and CRFs is that in both of them there exist Bayesian classifiers, which allow estimating \(x_{1:N}\) from \(y_{1:N}\) in a reasonable computer time.