## 2 Conditional Random Fields
The distribution is then defined as  
\[P\left(Y|X;\theta\right)=\frac{1}{Z\left(X;\theta\right)}\prod_{i\in Y}\psi_{ i}\left(Y_{i},X;\theta_{i}\right)\prod_{(i,i)\in E}\psi_{i}\left(Y_{i},Y_{j},X; \theta_{i}\right) \tag{2}\]  
and can be rewritten as \[P(Y|X;\ \theta)=\frac{1}{Z}\exp\left(\sum_{t\in S}\psi_{i}(y_{i},X,\theta)+\sum_{t\in S }\sum_{j\in N_{i}}\psi_{ij}\big{(}y_{i},y_{j},X,\theta\big{)}\ \right)\]  
where \(\theta\) is the parameter vector, \(Z\) is the partition function that is used to ensure that \(\sum_{y}P(Y\mid X;\theta)=1\), \(S\) indexes CRF nodes that correspond to random variables, \(\psi_{i}\) is the association (also called pairwise) potential (usually a function in the exponential family) involving individual samples, and \(\psi_{ij}\) is the interaction potential (usually a function in the exponential family) involving samples in the neighborhood \(N_{i}\) of site \"\(i\).\" If we consider only the association potential term \(\psi_{i}\), the model reduces to the logistic regression. The introduction of the interaction \(\psi_{ij}\) potential accounts for the fact that interlinked random variables impact each other's states. Example applications of CRFs that use pairwise cliques in computer vision include [8, 9] and many others. Now that Equation (2) is introduced, we point out that the term \"inference\" can either include all aspects of model formulation, including choosing a model, choosing a neighborhood structure, estimating the corresponding model parameters, and the final step of inferring the class label of a sample (see Sections 4 and 5). In Equation (2), this means one must choose the association and interaction potential functions, the neighborhood structure, and then some type of estimation method to estimate the model parameters \(\theta\). We point out, however, that in the PGM literature, \"inference\" is not such a broad term, but refers only to computing the probability distribution over the unobserved variables \(y_{i}\in Y\) given the observables, which include values for \(X\)s and possibly some subset of \(Y\). A sample label is then inferred based on the computed probability distribution. In the statistics literature, \"inference\" is the broader task of choosing a model and estimating the model parameters. This paper clarifies with each usage the meaning of the term \"inference\". Schemes for parameter estimation in CRFs are described in Section 2.1. It is known that inference in general graphical models is NP-hard, unless the models have tree-like structures or the model size is small [25, 26]. Probabilistic inference in CRFs based on trees is computationally efficient and exact. However, the expressiveness of a tree-structured model for approximating a general probabilistic graphical model is limited. A challenge in CRF model structure construction and parameter optimization (learning) is to balance the expressive power of the models with the computational complexity of inference in the models, because the inference has to be performed both during model learning and for answering probabilistic queries based on the optimized model. This requires developing computationally-efficient inference algorithms that provide a reasonable approximation to the inference over the original computationally-intractable model. A growing effort in recent years has been devoted to developing approximate probabilistic inference algorithms that can broadly categorized as: (1) variational algorithms, that cast the inference problem as an optimization problem. This category includes the mean-field approach [27], energy minimization using loopy belief propagation (LBP) [28, 29, 30, 31], generalized belief propagation [32, 33], tree reweighted approaches for maximum posterior marginals (MPM) estimation and maximum a posteriori (MAP) inference [34, 35, 36], and linear programming relaxations of MAP estimation [37, 38, 39, 40, 41] and (2) techniques that constrain the original problem using methods such as graph cuts [25, 42, 43].