## 1 Introduction  
In pattern recognition problems, there can be dependence among samples in the input domain, or between classification labels of samples in the output domain. For example, fraud detection in credit card transactions relies partly on pattern recognition methods that exploit relations among the samples (transactions), both in the input and output domains [1]. Pattern recognition is commonly applied to unstructured data for which the samples are independent with respect to both the input and output domains, as in [PERSON]'s well-known iris data [2], consisting of measurements of sepal and petal length and width, from each of many iris plants as input to be used to predict the output (species). In contrast, when there is structure in the input and output domain, _i.e._, sample input and sample labels are not independent, the problem is referred to as structured machine learning or structured prediction. Several similar terms, including classification, pattern recognition, prediction, and machine learning are used in various technical fields (statistical science, computer science, information science, and various engineering fields) to describe the task of using predictor features (also known as predictors or independent variables) to predict a response. Some examples of structured machine learning include fraud detection in credit card transactions and object recognition in images _i.e._, labeling pixels or pixel patches (also known as superpixels) in images. A broad category of models, known as probabilistic graphical models (PGMs) is being increasingly used to model problems having a structured domain [3]. PGMs are represented by two main categories of models. Directed graphical models are known as Bayesian Networks (BNs) and undirected graphical models are known as Markov random fields (MRFs) and conditional random fields (CRFs). PGMs are used to express dependencies between the input and output domains, as well as dependencies within domains, and to enable probabilistic inferences such as answering queries about the output variables using the probabilistic model (e.g., a model based on a CRF, a MRF or a BN) of the problem. A key task is to compute the probability distribution over the variables of interest (for a test sample called the query), given the observed values of other random variables (the evidence). CRFs were introduced by [PERSON] _et al._[4] for modeling structured data. Since then CRFs have been successfully applied in a broad range of applied domains such as bioinformatics [5; 6; 7], computer vision [6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16], assessment of climate change impact [17], active learning [18; 19], and natural language processing [4; 20; 21; 22]. A good introduction on CRFs is given in [23]. In addition to describing research directions, this paper reviews recent work, outlines the main challenges in learning CRFs, and provides examples of approximate inference, with a focus on a decomposition approach that uses spanning tree based approximations of the original graph model. While a Markov Random field (MRF) models the joint probability distribution, \(P(Y,X)\), and includes a model for \(P(X)\), a CRF directly models a conditional distribution, \(P(Y|X=x)\), without specifying a model for \(P(X)\). In general, modeling \(P(X)\) is difficult because feature functions between parts of the model are often correlated. As a result of direct modeling of conditional distributions, CRFs have been found well-suited to process rich, dependent features without having to model \(P(X)\). Figure 1 illustrates results of object recognition using MRFs and CRFs for man-made object detection [8]. Figure 2 illustrates the \(Y\) and \(X\) values for an image similar to the image in Figure 1. We used the dataset that was presented in [PERSON] and Hebert [8; 9]. The dataset contains 108 training and 129 testing images, each of size 256 \(\times\) 384 pixels, from the Corel image database. Each image wasdivided into non-overlapping patches of 16 \(\times\) 16 pixels.