## 5 Research Issues for CRFs  
First, regarding the computational challenges discussed in Section 2, there are open problems for maximum posterior marginal (MPM) estimation and maximum a posteriori (MAP) estimation. The lack of MPM and MAP inference methods that scale up to large data sets severely limits CRF usage. Most of the current approaches to address this challenge focus on approximate inference schemes, e.g., using either approximate optimization function, approximations of the original graph model such as spanning trees or the region graphs, or introducing constraints such as submodularity employed in the graph cuts approach. Second, the MDA performance in Example 2 in Section 4 suggests that it would be valuable to accommodate different forms for the CRF likelihood in models such as Equations (1)-(3). In Example 2, \begin{table}
\begin{tabular}{l l l} \hline  & **Unimodal** & **Bimodal** \\ \hline Logistic regression based classifier & \(14.72\pm 0.02\) & \(23.10\pm 0.04\) \\ \hline KH’06 (DRF, penalized pseudo-likelihood parameter & 2.30 & 6.21 \\ learning, MAP labelings estimated using graph cuts) & \(2.65\pm 0.11\) & \(6.04\pm 0.09\) \\ \hline Ensemble of spanning tree structured CRFs [66] & \(3.38\pm 0.04\) & \(5.80\pm 0.02\) \\ \hline Hierarchical cascade of spanning tree structured CRFs [67] & \(3.06\pm 0.11\) & \(6.00\pm 0.12\) \\ \hline \end{tabular}
\end{table} 
Table 2: Pixelwise classification error (%) for binary denoising task. KH’06 stands for the results published in [9]. Comparisons to logistic classifier and grid-structured CRF model with loopy belief propagation inference (LBP) are also shown. The averaging was done over five different runs each on 160 test samples; mean \(\pm\) standard deviation is shown. we know that the true distribution of the feature vector, X, is bimodal (a mixture of two Gaussians, which is not in the exponential family), so one could select the association potential terms \(\psi_{i}\), and/or the interaction terms \(\psi_{ij}\) in Equation (2) to better accommodate mixture distributions, which are quite general, and can approximate many real-life error distributions. Third, and related to the second, is goodness of fit testing. Cross-validation allows us to evaluate the classification performance of the model. However, it does not show how accurately the learned model captures the target distribution. We are not aware of any efforts to use a fitted CRF to generate simulated data (generate \(Y\)'s conditional on \(X\)), re-apply each candidate estimation strategy, and then see how well the inferred model parameters agree with the true and known model parameters. Given an ability to simulate from a fitted CRF (probably using some type of MCMC strategy as in [69]), goodness of fit tests could be developed, perhaps extending the goodness of fit tests proposed in [70]. Because CRFs have many choices such as the neighborhood structure, and the particular parametric functions \(\varphi_{i}\) and \(\psi_{y}\) in Equation (2), it is important to have a way to assess the quality of the fitted CRF to model the real data. Of course, any CRF can be used for pattern recognition, but if such a simulation-based goodness of fit test indicated a lack of fit, then it is reasonable to assume that a CRF with different modeling assumptions would have a better classification performance in pattern recognition. In summary, three important issues are: (1) developing efficient approximate probabilistic inference in general graphs (e.g., MCMC with reverse logistic regression, generalized belief propagation, decomposition approaches such as tree based approximations of the original general graphical model, and linear programming relaxations of the MAP estimation problem); (2) learning CRF structure simultaneously with estimating CRF parameters; and (3) goodness-of-fit testing. The first issue is a challenge of utmost importance in graphical probabilistic models.