{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:24:59Z","timestamp":1760243099408,"version":"build-2065373602"},"reference-count":70,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2015,7,14]],"date-time":"2015-07-14T00:00:00Z","timestamp":1436832000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Pattern recognition uses measurements from an input domain, X, to predict their labels from an output domain, Y. Image analysis is one setting where one might want to infer whether a pixel patch contains an object that is \u201cmanmade\u201d (such as a building) or \u201cnatural\u201d (such as a tree). Suppose the label for a pixel patch is \u201cmanmade\u201d; if the label for a nearby pixel patch is then more likely to be \u201cmanmade\u201d there is structure in the output domain that can be exploited to improve pattern recognition performance. Modeling P(X) is difficult because features between parts of the model are often correlated. Therefore, conditional random fields (CRFs) model structured data using the conditional distribution P(Y|X = x), without specifying a model for P(X), and are well suited for applications with dependent features. This paper has two parts. First, we overview CRFs and their application to pattern recognition in structured problems. Our primary examples are image analysis applications in which there is dependence among samples (pixel patches) in the output domain. Second, we identify research topics and present numerical examples.<\/jats:p>","DOI":"10.3390\/a8030466","type":"journal-article","created":{"date-parts":[[2015,7,14]],"date-time":"2015-07-14T10:53:35Z","timestamp":1436871215000},"page":"466-483","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Conditional Random Fields for Pattern Recognition Applied  to Structured Data"],"prefix":"10.3390","volume":"8","author":[{"given":"Tom","family":"Burr","sequence":"first","affiliation":[{"name":"Statistical Sciences, Los Alamos National Laboratory, Los Alamos, NM 87544-87545, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexei","family":"Skurikhin","sequence":"additional","affiliation":[{"name":"Space Data Systems, Los Alamos National Laboratory, Los Alamos, NM 87544-87545, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2015,7,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1214\/ss\/1042727940","article-title":"Statistical fraud detection: A review","volume":"17","author":"Bolton","year":"2002","journal-title":"Stat. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1111\/j.1469-1809.1936.tb02137.x","article-title":"The use of multiple measurements in taxonomic problems","volume":"7","author":"Fisher","year":"1936","journal-title":"Ann. Eugen."},{"key":"ref_3","unstructured":"Koller, D., and Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques, MIT Press."},{"key":"ref_4","unstructured":"Lafferty, J., McCallum, A., and Pereira, F. (July, January 28). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. Proceedings of the 18th International Conference on Machine Learning, Williamstown, MA, USA."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"ii237","DOI":"10.1093\/bioinformatics\/bti1139","article-title":"RNA secondary structural alignment with conditional random fields","volume":"21","author":"Sato","year":"2005","journal-title":"Bioinformatics"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Hayashida, M., Kamada, M., Song, J., and Akutsu, T. (2013). Prediction of protein-RNA residue-base contacts using two-dimensional conditional random field with the lasso. BMC Syst. Biol.","DOI":"10.1186\/1752-0509-7-S2-S15"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1038\/nature12961","article-title":"The genomic landscape of Neanderthal ancestry in present-day humans","volume":"507","author":"Sankararaman","year":"2014","journal-title":"Nature"},{"key":"ref_8","unstructured":"Kumar, S., and Hebert, M. (2003, January 8\u201313). Discriminative fields for modeling spatial dependencies in natural images. Advances in Neural Information Processing Systems 16; Proceedings of the Neural Information Processing Systems, Vancouver, British Columbia, Canada."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/s11263-006-7007-9","article-title":"Discriminative random fields","volume":"68","author":"Kumar","year":"2006","journal-title":"Int. J. Comp. Vis."},{"key":"ref_10","unstructured":"He, X., Zemel, R., and Carreira-Perpinan, M. (July, January 27). Multiscale conditional random fields for image labeling. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Washington, DC, USA."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Reiter, S., Schuller, B., and Rigoll, G. (2007, January 2\u20135). Hidden conditional random fields for meeting segmentation. Proceedings of the International Conference on Multimedia and Exposition, Beijing, China.","DOI":"10.1109\/ICME.2007.4284731"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Ladicky, L., Sturgess, P., Alahari, K., Russell, C., and Torr, P. (2010, January 5\u201311). What, where and how many? Combining object detectors and CRFs. Proceedings of the European Conference on Computer Vision, Hersonissos, Greece.","DOI":"10.1007\/978-3-642-15561-1_31"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/s11263-012-0531-x","article-title":"Minimizing energies with hierarchical costs","volume":"100","author":"Delong","year":"2012","journal-title":"Int. J. Comp. Vis."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1215","DOI":"10.1016\/j.cviu.2012.09.005","article-title":"Tracking with a mixed continuous-discrete conditional random field","volume":"117","author":"Pellegrini","year":"2013","journal-title":"Comp. Vis. Image Underst."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1109\/TNNLS.2012.2224882","article-title":"Infinite hidden conditional random fields for human behavior analysis","volume":"24","author":"Bousmalis","year":"2013","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"He, X., and Gould, S. (2014, January 24\u201327). An exemplar based CRF for multi-instance object segmentation. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Columbus, OH, USA.","DOI":"10.1109\/CVPR.2014.45"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1029\/2008WR007487","article-title":"A conditional random field based downscaling method for assessment of climate change impact on multisite daily precipitation in the Mahanadi basin","volume":"45","author":"Raje","year":"2009","journal-title":"Water Resour. Res."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Martinez, O., and Tsechpenakis, G. (2008, January 23\u201328). Integration of active learning in a collaborative CRF. Proceedings of the IEEE Computer Vision and Pattern Recognition Workshops, Anchorage, AK, USA.","DOI":"10.1109\/CVPRW.2008.4563066"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.neunet.2014.04.005","article-title":"Incorporating conditional random fields and active learning to improve sentiment identification","volume":"58","author":"Zhang","year":"2014","journal-title":"Neural Netw."},{"key":"ref_20","unstructured":"Sha, F., and Pereira, S. (1, January 31). Shallow parsing with conditional random fields. Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, Edmonton, Canada."},{"key":"ref_21","unstructured":"Sutton, C., and McCallum, A. (2005, January 26\u201329). Piecewise training for undirected models. Proceedings of the Conference on Uncertainty in Artificial Intelligence, Edinburgh, UK."},{"key":"ref_22","unstructured":"Ammar, W., Dyer, C., and Smith, N.A. (2014, January 8\u201313). Conditional random field autoencoders for unsupervised structured prediction. Advances in Neural Information Processing Systems 27 (NIPS 2014), Proceedings of the Neural Information Processing Systems, Montreal, Canada."},{"key":"ref_23","first-page":"267","article-title":"An introduction to conditional random fields","volume":"4","author":"Sutton","year":"2011","journal-title":"Mach. Learn."},{"key":"ref_24","first-page":"179","article-title":"Statistical analysis of non-lattice data","volume":"24","author":"Besag","year":"1975","journal-title":"J. R. Stat. Soc. Ser. D (Stat.)"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1222","DOI":"10.1109\/34.969114","article-title":"Fast approximate energy minimization via graph cuts","volume":"23","author":"Boykov","year":"2001","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1016\/0004-3702(94)90072-8","article-title":"Finding MAPs for belief networks is NP-hard","volume":"68","author":"Shimony","year":"1994","journal-title":"Artif. Intell."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/S0031-3203(02)00027-4","article-title":"EM procedures using mean field-like approximations for Markov model-based image segmentation","volume":"36","author":"Celeux","year":"2003","journal-title":"Pattern Recognit."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann.","DOI":"10.1016\/B978-0-08-051489-5.50008-4"},{"key":"ref_29","unstructured":"Frey, B., and MacKay, D. (1997, January 1\u20136). A revolution: Belief propagation in graphs with cycles. Advances in Neural Information Processing Systems 10 (NIPS 1997), Proceedings of the Conference on Neural Information Processing Systems, Denver, CO, USA."},{"key":"ref_30","unstructured":"Murphy, K., Weiss, Y., and Jordan, M. (1\u2013August, January 30). Loopy belief propagation for approximate inference: An empirical study. Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, Stockholm, Sweden."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"2282","DOI":"10.1109\/TIT.2005.850085","article-title":"Constructing free energy approximations and generalized belief propagation algorithms","volume":"51","author":"Yedidia","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_32","unstructured":"Yedidia, J., Freeman, W., and Weiss, Y. (2000, January 28\u201330). Bethe free energy, Kukuchi approximations and belief propagation algorithms. Advances in Neural Information Processing Systems 13 (NIPS 2000), Proceedings of the Conference on Neural Information Processing Systems, Denver, CO, USA."},{"key":"ref_33","unstructured":"Yedidia, J., Freeman, W., and Weiss, Y. (2001, January 4\u201310). Understanding belief propagation and its generalizations. Proceedings of the International Joint Conference on Artificial Intelligence, Seattle, WA, USA."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1120","DOI":"10.1109\/TIT.2003.810642","article-title":"Tree-based reparametrization framework for analysis of sum-product and related algorithms","volume":"49","author":"Wainwright","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"3697","DOI":"10.1109\/TIT.2005.856938","article-title":"MAP estimation via agreement on (hyper) trees: Message-passing and linear programming approaches","volume":"51","author":"Wainwright","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1568","DOI":"10.1109\/TPAMI.2006.200","article-title":"Convergent tree-reweighted message passing for energy minimization","volume":"28","author":"Kolmogorov","year":"2006","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Ravikumar, P., and Lafferty, J. (2006, January 25\u201329). Quadratic programming relaxations for metric labeling and Markov random field MAP estimation. Proceedings of the 23rd International Conference on Machine Learning, Pittsburgh, PA, USA.","DOI":"10.1145\/1143844.1143937"},{"key":"ref_38","first-page":"71","article-title":"An analysis of convex relaxations for MAP estimation of discrete MRFs","volume":"10","author":"Kumar","year":"2008","journal-title":"J. Mach. Learn. Res."},{"key":"ref_39","unstructured":"Peng, J., Hazan, T., McAllester, D., and Urtasum, R. (July, January 28). Convex max-product algorithms for continuous MRFs with applications to protein folding. Proceedings of the 28th International Conference on Machine Learning, Bellevue, WA, USA."},{"key":"ref_40","unstructured":"Schwing, A., Pollefeys, M., Hazan, T., and Urtasum, R. (2012, January 3\u20138). Globally convergent dual MAP LP relaxation solvers using Fenchel-Young margins. Advances in Neural Information Processing Systems 25 (NIPS 2012), Proceedings of the Conference on Neural Information Processing Systems, Lake Tahoe, NV, USA."},{"key":"ref_41","unstructured":"Bach, S., Huang, B., and Getoor, L. (2015, January 9\u201312). Unifying local consistency and MAX SAT relaxations for scalable inference with rounding guarantees. Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, San Diego, CA, USA."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"1124","DOI":"10.1109\/TPAMI.2004.60","article-title":"An experimental comparison of min-cut\/max-flow algorithms for energy minimization in vision","volume":"26","author":"Boykov","year":"2004","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1109\/TPAMI.2004.1262177","article-title":"What energy functions can be minimized via graph cuts?","volume":"26","author":"Kolmogorov","year":"2004","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Tarlow, D., and Adams, R. (2012, January 16\u201321). Revisiting uncertainty in graph cut solutions. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Providence, RI, USA.","DOI":"10.1109\/CVPR.2012.6247958"},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Ramalingam, S., Kohli, P., Alahari, K., and Torr, P. (2008, January 23\u201328). Exact inference in multi-label CRFs with higher order cliques. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Anchorage, AK, USA.","DOI":"10.1109\/CVPR.2008.4587401"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Kohli, P., Ladick\u00fd, L., and Torr, P. (2008, January 23\u201328). Robust higher order potentials for enforcing label consistency. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Anchorage, AK, USA.","DOI":"10.1109\/CVPR.2008.4587417"},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Schmidt, F., Toppe, E., and Cremers, D. (2009, January 20\u201326). Efficient planar graph cuts with applications in computer vision. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Miami, FL, USA.","DOI":"10.1109\/CVPRW.2009.5206863"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Ladick\u00fd, L., Russell, C., Kohli, P., and Torr, P. (2010, January 13\u201318). Graph cut based inference with co-occurrence statistics. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, San Francisco, CA, USA.","DOI":"10.1007\/978-3-642-15555-0_18"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/BF01589116","article-title":"On the limited memory BFGS method for large scale optimization methods","volume":"45","author":"Liu","year":"1989","journal-title":"Math. Program."},{"key":"ref_50","unstructured":"Asuncion, A., Liu, Q., Ihler, A., and Smyler, P. (2010, January 21\u201324). Particle filtered MCMC-MLE with connections to contrastive divergence. Proceedings of the 27th International Conference on Machine Learning, Haifa, Israel."},{"key":"ref_51","unstructured":"Asuncion, A., Liu, Q., Ihler, A., and Smyler, P. (2010, January 13\u201315). Learning with blocks: Composite likelihood and contrastive divergence. Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, Sardinia, Italy."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"1771","DOI":"10.1162\/089976602760128018","article-title":"Training products of experts by minimizing contrastive divergence","volume":"14","author":"Hinton","year":"2002","journal-title":"Neural Comput."},{"key":"ref_53","unstructured":"Carreira-Perpi\u00f1\u00e1n, M., and Hinton, G. (2005, January 6\u20138). On contrastive divergence learning. Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, Barbados."},{"key":"ref_54","unstructured":"Geyer, C.J. MCMC Package Example (Version 0.7-3). Available online: http:\/\/www.stat.umn.edu\/geyer\/mcmc\/library\/mcmc\/doc\/demo.pdf."},{"key":"ref_55","unstructured":"Khosrow-Pour, M. (2015). Conditional random fields for modeling structured data, Encyclopedia of Information Science and Technology, Information Resources Management Association. [3rd ed.]. Chapter 608."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1093\/biomet\/64.3.616","article-title":"Efficiency of pseudo-likelihood estimation for simple Gaussian fields","volume":"64","author":"Besag","year":"1977","journal-title":"Biometrika"},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1090\/conm\/080\/999014","article-title":"Composite likelihood methods","volume":"80","author":"Lindsay","year":"1988","journal-title":"Contemp. Math."},{"key":"ref_58","first-page":"63","article-title":"Pseudo-likelihood inference for Gaussian Markov random fields","volume":"2","author":"Burr","year":"2013","journal-title":"Stat. Res. Lett."},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"Sutton, C., and McCallum, A. (2007, January 20\u201324). Piecewise pseudolikelihood for efficient training of conditional random fields. Proceedings of the 24th International Conference on Machine Learning, Corvallis, OR, USA.","DOI":"10.1145\/1273496.1273605"},{"key":"ref_60","doi-asserted-by":"crossref","unstructured":"Friel, N. (2012, January 9\u201312). Bayesian inference for Gibbs random fields using composite likelihoods. Proceedings of the 2012 Winter Simulation Conference, Berlin, Germany.","DOI":"10.1109\/WSC.2012.6465236"},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"2385","DOI":"10.1109\/TIP.2013.2249076","article-title":"Estimating the granularity coefficient of a Potts-Markov random field within a Markov chain Monte Carlo algorithm","volume":"22","author":"Pereyra","year":"2012","journal-title":"IEEE Trans. Image Process."},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"3241","DOI":"10.1088\/0305-4470\/15\/10\/028","article-title":"On the computational complexity of Ising spin glass models","volume":"15","author":"Barahona","year":"1982","journal-title":"J. Phys. A"},{"key":"ref_63","doi-asserted-by":"crossref","unstructured":"Hastie, T., Tibshirani, R., and Friedman, J. (2001). The Elements of Statistical Learning, Springer.","DOI":"10.1007\/978-0-387-21606-5"},{"key":"ref_64","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s11222-014-9514-9","article-title":"Adaptive ABC model choice and geometric summary statistics for hidden Gibbs random fields","volume":"25","author":"Stoehr","year":"2015","journal-title":"Stat. Comput."},{"key":"ref_65","doi-asserted-by":"crossref","first-page":"1848","DOI":"10.1109\/TPAMI.2007.1124","article-title":"Hidden conditional random fields","volume":"29","author":"Quattoni","year":"2007","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_66","doi-asserted-by":"crossref","unstructured":"Skurikhin, A. (2014, January 14\u201316). Learning tree-structured approximations for conditional random fields. Proceedings of the IEEE Applied Imagery Pattern Recognition Workshop, Washington, DC, USA.","DOI":"10.1109\/AIPR.2014.7041937"},{"key":"ref_67","first-page":"85","article-title":"Hierarchical spanning tree-structured approximation for conditional random fields: An empirical study","volume":"8888","author":"Skurikhin","year":"2014","journal-title":"Adv. Vis. Comput. Lect. Notes Comput. Sci."},{"key":"ref_68","unstructured":"R Core Team (2012). R: A Language and Environment for Statistical Computing, R Foundation for Statistical Computing."},{"key":"ref_69","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1109\/TPAMI.1984.4767596","article-title":"Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images","volume":"6","author":"Geman","year":"1984","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_70","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1214\/11-AOS948","article-title":"Goodness of fit tests for a class of Markov random field models","volume":"40","author":"Kaiser","year":"2012","journal-title":"Ann. Stat."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/8\/3\/466\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T20:49:08Z","timestamp":1760215748000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/8\/3\/466"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,14]]},"references-count":70,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2015,9]]}},"alternative-id":["a8030466"],"URL":"https:\/\/doi.org\/10.3390\/a8030466","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2015,7,14]]}}}