# Equivalence between LC-CRF and HMM, and Discriminative Computing of HMM-Based MPM and MAP
###### Abstract  
Practitioners have used hidden Markov models (HMMs) in different problems for about sixty years. Moreover, conditional random fields (CRFs) are an alternative to HMMs and appear in the literature as different and somewhat concurrent models. We propose two contributions: First, we show that the basic linear-chain CRFs (LC-CRFs), considered as different from HMMs, are in fact equivalent to HMMs in the sense that for each LC-CRF there exists an HMM--that we specify--whose posterior distribution is identical to the given LC-CRF. Second, we show that it is possible to reformulate the generative Bayesian classifiers maximum posterior mode (MPM) and maximum a posteriori (MAP), used in HMMs, as discriminative ones. The last point is of importance in many fields, especially in natural language processing (NLP), as it shows that in some situations dropping HMMs in favor of CRFs is not necessary. hidden Markov model; linear chain conditional random field; Bayesian classifier; discriminative classifier; generative classifier; maximum posterior mode; maximum a posteriori +
Footnote †: journal:  
0000-0001-9999-4600-3223-  
In this paper, we consider the following basic LC-CRF:  
\[p(x_{1:N}|y_{1:N})=\frac{1}{\kappa(y_{1:N})}exp\Big{[}\sum_{n=1}^{N-1}V_{n}(x_{n},x_{n+1})+\sum_{n=1}^{N}U_{n}(x_{n},y_{n})\Big{]} \tag{3}\]  
with \(\kappa(y_{1:N})\) the normalizing constant. Authors usually consider the two families HMMs and LC-CRFs as different [6; 7; 8; 9; 10; 11; 12; 13]. They classify the former in the category of \"generative models\", while they classify the latter in the category of \"discriminative\" models. In this paper, we investigate the relationship between HMMs (Equation (1)) and LC-CRFs (Equation (3)). We immediately see that if \(p(x_{1:N}|y_{1:N})\) is of the form (Equation (1)), then \(p(x_{1:N}|y_{1:N})\) is of the form (Equation (3)). Indeed, \(p(x_{n+1}|x_{n})\) and \(p(y_{n+1}|x_{n+1})\) in Equation (1) being non-zero, one can take \(V_{1}(x_{1},x_{2})=Log[p(x_{1},x_{2})]\), \(V_{n}(x_{n},x_{n+1})=Log[p(x_{n+1}|x_{n})]\) for \(n=2,\,\ldots,\,N-1\), \(U_{n}(x_{n},y_{n})=Log[p(y_{n}|x_{n})]\), for \(n=1,\,\ldots,\,N\), and \(\kappa(y_{1:N})=p(y_{1:N})\). Thus, the posterior distribution \(p(x_{1:N}|y_{1:N})\) of each HMM (Equation (1)) with the positivity conditions assumed above is a LC-CRF (Equation (3)). Our first contribution is to show the converse: for a given LC-CRF \(p(x_{1:N}|y_{1:N})\) of form (Equation (3)), there is an HMM \(q(x_{1:N},y_{1:N})\) of form (Equation (3)) such that \(q(x_{1:N}|y_{1:N})=p(x_{1:N}|y_{1:N})\). Moreover, we give exact computation of the HMM parameters \(q(x_{1})\), \(q(x_{n+1}|x_{n})\), \(q(y_{n+1}|x_{n+1})\), from the LC-CRF parameters \(V_{n}(x_{n},x_{n+1})\), \(U_{n}(x_{n},y_{n})\). Such a general result, without additional constraints on LC-CRF, is new. Our second contribution is related to the computation of Bayesian classifiers. In some situations, CRFs are preferred over HMMs because the Bayesian classifiers based on CRFs are computed without considering \(p(y_{n}|x_{n})\) distributions, which are difficult to model. This is particularly the case with automatic natural language processing (NLP). Indeed, when considering an HMM (Equation (1)) and calculating the Bayesian classifiers \"maximum posterior margins\" (MPM) and \"maximum posterior\" (MAP) in the standard way, we use \(p(y_{n}|x_{n})\) and this is the reason why LC-CRFs are preferred over HMMs. In this paper, we show that the HMM-based MPM and MAP can also be computed without using \(p(y_{n}|x_{n})\). Also recall that each Bayesian \"discriminative\" classifier based on LC-CRF (Equation (3)) is identical to the \"generative\" Bayesian classifier based on an HMM (Equation (1)), since the posterior distribution \(p(x_{1:N}|y_{1:N})\) of an HMM gives the one of a LC-CRF. Indeed, Bayesian classifiers only depend on the posterior distribution.