## 2 Conditional Random Fields
### CRF Learning
#### 2.1.1 Estimation of Model Parameters 0 Using Markov Chain Monte Carlo  
The broad topic of inference schemes based on Markov Chain Monte Carlo [54] (MCMC) for CRFs are another type of approximate inference, because numerical methods are used to approximate the true posterior distribution of each CRF model parameter. Here, the term \"approximate inference\" refers to approximate methods to estimate CRF model parameters; there are several interpretations of approximate inference, depending on whether the likelihood is somehow approximated, or the estimation scheme is an approximate one based on the approximate or true likelihood. In many models, one relatively straightforward option to estimate model parameters \(\theta\) is a numerical Bayesian option such as MCMC. In fact, if \(Z\) were a known function of the unknown \(\theta\) in Equation (2), then standard implementation MCMC which requires knowledge only of the ratio of probabilities (see the next paragraph) would be a good option to avoid having to compute \(Z\)[50; 51]. MCMC examines many candidate parameter values \(\theta^{\prime}\) and accepts those candidate values as an observation from the posterior distribution with a probability that depends on the value \(\frac{P\left(Y\middle|X;\,\theta^{\prime}\right)}{P\left(Y\middle|X;\,\,\theta _{current}\right)}\times\frac{Z\left(\theta\right)}{Z\left(\theta^{\prime} \right)}\). Because MCMC accepts a finite number of candidate \(\theta^{\prime}\) values, the MCMC-based posterior has approximation error, even in situations where \(Z\) is a known function of the unknown \(\theta\) in Equation (2). Also, in any application of MCMC, one must check whether the chain has converged to the posterior distribution [50,54]. For situations such as CRFs where the ratio \(\dfrac{P\big{(}Y|X;\theta^{\prime}\big{)}}{P\big{(}Y|X;\theta_{\text{current}} \big{)}}\) depends on the unknown ratio, Z(\(\theta\))/Z(\(\theta\))/Z(\(\theta\)), one of the first approximate estimation options developed was reverse logistic regression [55]. In parameter estimation for CRFs, suppose we have a collection of \(m\) normalizing constants, Z(\(\theta_{1}\)), Z(\(\theta_{2}\)), \(\ldots\), Z(\(\theta_{m}\)), simply by trying different values of \(\theta\) on a grid of values. For each value of \(\theta\) denoted \(\theta_{k}\), MCMC can be used to generate random samples each of size \(n\) from the unnormalized (does not sum to 1) distribution denoted here as \(P(Y|X;\theta_{k})\), and \(P(Y|X;\theta_{k})=P^{\prime}(Y|X;\theta_{k})/Z_{k}\). The collection \(P^{\prime}(Y|X;\theta_{1})\), \(P^{\prime}(Y|X;\theta_{2})\),\(\ldots\), \(P^{\prime}(Y|X;\theta_{m})\) can be combined as in mixture distributions as \(\sum\limits_{j=1}^{m}P^{\prime}\big{(}Y|X;\theta_{1}\big{)}e^{\eta_{j}}\), where \(e^{\eta_{j}}\) is introduced to satisfy \(\eta_{j}=-\log(Z_{k})+\log(\dfrac{n}{mn})=-\log(Z_{k})+\log(\dfrac{1}{m})\) and then \(p_{k}(Y|X;\theta_{k})=\dfrac{P^{\prime}(Y|X;\theta_{k})e^{n_{k}}}{\sum \limits_{k=1}^{m}P^{\prime}(Y|X;\theta_{k})e^{n_{k}}}\) is the probability that a simulated value \(Y\) from the mixture probability \(\sum\limits_{j=1}^{m}P^{\prime}\big{(}Y|X;\theta_{1}\big{)}e^{\eta_{j}}\) occurred in the \(j\)th sample (there are \(mn\) samples) in the mixture distribution. Reverse logistic regression can then be applied to the \(n\) samples from each of \(P^{\prime}(Y|X;\theta_{1})\), \(P^{\prime}(Y|X;\theta_{2})\),\(\ldots\), \(P^{\prime}(Y|X;\theta_{m})\) to estimate the \(\eta_{j}\) values, which determine the normalizing constants \(Z_{k}\). For the \(mn\) samples \(Y_{\text{ij}}\), the likelihood for reverse logistic regression is \(l(\eta_{1},\eta_{2},\ldots,\eta_{m})=\sum\limits_{j=1}^{m}\sum\limits_{i=1}^{ n_{i}}\log(p_{j}(Y_{i}\eta_{1},\eta_{2},\ldots,\eta_{m}))\), which can be maximized to solve to the estimate the \(\eta\) values. This use of reverse logistic regression involves approximating the normalizing constants, \(Z_{k}\), so it is one type of approximate inference.