×

zbMATH — the first resource for mathematics

Conditional random fields for pattern recognition applied to structured data. (English) Zbl 07042264
Summary: 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 “manmade” (such as a building) or “natural” (such as a tree). Suppose the label for a pixel patch is “manmade”; if the label for a nearby pixel patch is then more likely to be “manmade” 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.
MSC:
68 Computer science
94 Information and communication theory, circuits
Software:
L-BFGS; MAXFLOW; mcmc; R
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bolton, R.; Hand, D.; Statistical fraud detection: A review; Stat. Sci.: 2002; Volume 17 ,235-255. · Zbl 1013.62115
[2] Fisher, R.; The use of multiple measurements in taxonomic problems; Ann. Eugen.: 1936; Volume 7 ,179-188.
[3] Koller, D.; Friedman, N.; ; Probabilistic Graphical Models: Principles and Techniques: Cambridge, MA, USA 2009; . · Zbl 1183.68483
[4] Lafferty, J.; McCallum, A.; Pereira, F.; Conditional random fields: Probabilistic models for segmenting and labeling sequence data; Proceedings of the 18th International Conference on Machine Learning: ; .
[5] Sato, K.; Sakakibara, Y.; RNA secondary structural alignment with conditional random fields; Bioinformatics: 2005; Volume 21 ,ii237-ii242.
[6] Hayashida, M.; Kamada, M.; Song, J.; Akutsu, T.; Prediction of protein-RNA residue-base contacts using two-dimensional conditional random field with the lasso; BMC Syst. Biol.: 2013; .
[7] Sankararaman, S.; Mallick, S.; Dannemann, M.; Prufer, K.; Kelso, J.; Paabo, S.; Patterson, N.; Reich, D.; The genomic landscape of Neanderthal ancestry in present-day humans; Nature: 2014; Volume 507 ,354-357.
[8] Kumar, S.; Hebert, M.; Discriminative fields for modeling spatial dependencies in natural images; Advances in Neural Information Processing Systems 16; Proceedings of the Neural Information Processing Systems: ; .
[9] Kumar, S.; Hebert, M.; Discriminative random fields; Int. J. Comp. Vis.: 2006; Volume 68 ,179-201.
[10] He, X.; Zemel, R.; Carreira-Perpinan, M.; Multiscale conditional random fields for image labeling; Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition: ; Volume Volume 2 .
[11] Reiter, S.; Schuller, B.; Rigoll, G.; Hidden conditional random fields for meeting segmentation; Proceedings of the International Conference on Multimedia and Exposition: ; ,639-642.
[12] Ladicky, L.; Sturgess, P.; Alahari, K.; Russell, C.; Torr, P.; What, where and how many? Combining object detectors and CRFs; Proceedings of the European Conference on Computer Vision: ; .
[13] Delong, A.; Gorelick, L.; Veksler, O.; Boykov, Y.; Minimizing energies with hierarchical costs; Int. J. Comp. Vis.: 2012; Volume 100 ,38-58. · Zbl 1254.68276
[14] Pellegrini, S.; Gool, L.; Tracking with a mixed continuous-discrete conditional random field; Comp. Vis. Image Underst.: 2013; Volume 117 ,1215-1228.
[15] Bousmalis, K.; Zafeiriou, S.; Morency, L.; Pantic, M.; Infinite hidden conditional random fields for human behavior analysis; IEEE Trans. Neural Netw. Learn. Syst.: 2013; Volume 24 ,170-177.
[16] He, X.; Gould, S.; An exemplar based CRF for multi-instance object segmentation; Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition: ; .
[17] Raje, D.; Mujumdar, P.; A conditional random field based downscaling method for assessment of climate change impact on multisite daily precipitation in the Mahanadi basin; Water Resour. Res.: 2009; Volume 45 ,20.
[18] Martinez, O.; Tsechpenakis, G.; Integration of active learning in a collaborative CRF; Proceedings of the IEEE Computer Vision and Pattern Recognition Workshops: ; .
[19] Zhang, K.; Xie, Y.; Yang, Y.; Sun, A.; Liu, H.; Choudhary, A.; Incorporating conditional random fields and active learning to improve sentiment identification; Neural Netw.: 2014; Volume 58 ,60-67.
[20] Sha, F.; Pereira, S.; 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: ; ,134-141.
[21] Sutton, C.; McCallum, A.; Piecewise training for undirected models; Proceedings of the Conference on Uncertainty in Artificial Intelligence: ; .
[22] Ammar, W.; Dyer, C.; Smith, N.A.; Conditional random field autoencoders for unsupervised structured prediction; Advances in Neural Information Processing Systems 27 (NIPS 2014), Proceedings of the Neural Information Processing Systems: ; .
[23] Sutton, C.; McCallum, A.; An introduction to conditional random fields; Mach. Learn.: 2011; Volume 4 ,267-373. · Zbl 1253.68001
[24] Besag, J.; Statistical analysis of non-lattice data; J. R. Stat. Soc. Ser. D (Stat.): 1975; Volume 24 ,179-195.
[25] Boykov, Y.; Veksler, O.; Zabih, R.; Fast approximate energy minimization via graph cuts; IEEE Trans. Pattern Anal. Mach. Intell.: 2001; Volume 23 ,1222-1239.
[26] Shimony, S.; Finding MAPs for belief networks is NP-hard; Artif. Intell.: 1994; Volume 68 ,399-410. · Zbl 0818.68097
[27] Celeux, G.; Forbes, F.; Peyrard, N.; EM procedures using mean field-like approximations for Markov model-based image segmentation; Pattern Recognit.: 2003; Volume 36 ,131-144. · Zbl 1010.68158
[28] Pearl, J.; ; Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference: San Francisco, CA, USA 1988; . · Zbl 0746.68089
[29] Frey, B.; MacKay, D.; 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: ; .
[30] Murphy, K.; Weiss, Y.; Jordan, M.; Loopy belief propagation for approximate inference: An empirical study; Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence: ; ,467-475.
[31] Yedidia, J.; Freeman, W.; Weiss, Y.; Constructing free energy approximations and generalized belief propagation algorithms; IEEE Trans. Inf. Theory: 2005; Volume 51 ,2282-2312. · Zbl 1283.94023
[32] Yedidia, J.; Freeman, W.; Weiss, Y.; 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: ; .
[33] Yedidia, J.; Freeman, W.; Weiss, Y.; Understanding belief propagation and its generalizations; Proceedings of the International Joint Conference on Artificial Intelligence: ; . · Zbl 1283.94023
[34] Wainwright, M.; Jaakkola, T.; Willsky, A.; Tree-based reparametrization framework for analysis of sum-product and related algorithms; IEEE Trans. Inf. Theory: 2005; Volume 49 ,1120-1146. · Zbl 1063.68079
[35] Wainwright, M.; Jaakkola, T.; Willsky, A.; MAP estimation via agreement on (hyper) trees: Message-passing and linear programming approaches; IEEE Trans. Inf. Theory: 2005; Volume 51 ,3697-3717. · Zbl 1318.94025
[36] Kolmogorov, V.; Convergent tree-reweighted message passing for energy minimization; IEEE Trans. Pattern Anal. Mach. Intell.: 2006; Volume 28 ,1568-1583.
[37] Ravikumar, P.; Lafferty, J.; Quadratic programming relaxations for metric labeling and Markov random field MAP estimation; Proceedings of the 23rd International Conference on Machine Learning: ; .
[38] Kumar, M.; Kolmogorov, V.; Torr, P.; An analysis of convex relaxations for MAP estimation of discrete MRFs; J. Mach. Learn. Res.: 2008; Volume 10 ,71-106. · Zbl 1235.90092
[39] Peng, J.; Hazan, T.; McAllester, D.; Urtasum, R.; Convex max-product algorithms for continuous MRFs with applications to protein folding; Proceedings of the 28th International Conference on Machine Learning: ; .
[40] Schwing, A.; Pollefeys, M.; Hazan, T.; Urtasum, R.; 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: ; .
[41] Bach, S.; Huang, B.; Getoor, L.; Unifying local consistency and MAX SAT relaxations for scalable inference with rounding guarantees; Proceedings of the 18th International Conference on Artificial Intelligence and Statistics: ; .
[42] Boykov, Y.; Kolmogorov, V.; An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision; IEEE Trans. Pattern Anal. Mach. Intell.: 2004; Volume 26 ,1124-1137. · Zbl 1005.68964
[43] Kolmogorov, V.; Zabih, R.; What energy functions can be minimized via graph cuts?; IEEE Trans. Pattern Anal. Mach. Intell.: 2004; Volume 26 ,147-159. · Zbl 1039.68666
[44] Tarlow, D.; Adams, R.; Revisiting uncertainty in graph cut solutions; Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition: ; .
[45] Ramalingam, S.; Kohli, P.; Alahari, K.; Torr, P.; Exact inference in multi-label CRFs with higher order cliques; Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition: ; .
[46] Kohli, P.; Ladický, L.; Torr, P.; Robust higher order potentials for enforcing label consistency; Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition: ; .
[47] Schmidt, F.; Toppe, E.; Cremers, D.; Efficient planar graph cuts with applications in computer vision; Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition: ; .
[48] Ladický, L.; Russell, C.; Kohli, P.; Torr, P.; Graph cut based inference with co-occurrence statistics; Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition: ; .
[49] Liu, D.; Nocedal, J.; On the limited memory BFGS method for large scale optimization methods; Math. Program.: 1989; Volume 45 ,503-528. · Zbl 0696.90048
[50] Asuncion, A.; Liu, Q.; Ihler, A.; Smyler, P.; Particle filtered MCMC-MLE with connections to contrastive divergence; Proceedings of the 27th International Conference on Machine Learning: ; .
[51] Asuncion, A.; Liu, Q.; Ihler, A.; Smyler, P.; Learning with blocks: Composite likelihood and contrastive divergence; Proceedings of the 13th International Conference on Artificial Intelligence and Statistics: ; .
[52] Hinton, G.; Training products of experts by minimizing contrastive divergence; Neural Comput.: 2002; Volume 14 ,1771-1800. · Zbl 1010.68111
[53] Carreira-Perpiñán, M.; Hinton, G.; On contrastive divergence learning; Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics: ; .
[54] Geyer, C.J.; MCMC Package Example (Version 0.7-3); 2009; .
[55] Burr, T.; Skurikhin, A.; ; Conditional random fields for modeling structured data, Encyclopedia of Information Science and Technology: Hershey, PA, USA 2015; ,6167-6176.
[56] Besag, J.; Efficiency of pseudo-likelihood estimation for simple Gaussian fields; Biometrika: 1977; Volume 64 ,616-618. · Zbl 0372.62067
[57] Lindsay, B.; Composite likelihood methods; Contemp. Math.: 1988; Volume 80 ,221-239.
[58] Burr, T.; Skurikhin, A.; Pseudo-likelihood inference for Gaussian Markov random fields; Stat. Res. Lett.: 2013; Volume 2 ,63-68.
[59] Sutton, C.; McCallum, A.; Piecewise pseudolikelihood for efficient training of conditional random fields; Proceedings of the 24th International Conference on Machine Learning: ; . · Zbl 1253.68001
[60] Friel, N.; Bayesian inference for Gibbs random fields using composite likelihoods; Proceedings of the 2012 Winter Simulation Conference: ; .
[61] Pereyra, M.; Dobigeon, N.; Batatia, H.; Tourneret, J.; Estimating the granularity coefficient of a Potts-Markov random field within a Markov chain Monte Carlo algorithm; IEEE Trans. Image Process.: 2012; Volume 22 ,2385-2397. · Zbl 1383.62210
[62] Barahona, F.; On the computational complexity of Ising spin glass models; J. Phys. A: 1982; Volume 15 ,3241-3253.
[63] Hastie, T.; Tibshirani, R.; Friedman, J.; ; The Elements of Statistical Learning: New York, NY, USA 2001; . · Zbl 0973.62007
[64] Stoehr, J.; Pudlo, P.; Cucala, L.; Adaptive ABC model choice and geometric summary statistics for hidden Gibbs random fields; Stat. Comput.: 2015; Volume 25 ,129-141. · Zbl 1331.62066
[65] Quattoni, A.; Wang, S.; Morency, L.; Collins, M.; Darrell, T.; Hidden conditional random fields; IEEE Trans. Pattern Anal. Mach. Intell.: 2007; Volume 29 ,1848-1853.
[66] Skurikhin, A.; Learning tree-structured approximations for conditional random fields; Proceedings of the IEEE Applied Imagery Pattern Recognition Workshop: ; .
[67] Skurikhin, A.N.; Hierarchical spanning tree-structured approximation for conditional random fields: An empirical study; Adv. Vis. Comput. Lect. Notes Comput. Sci.: 2014; Volume 8888 ,85-94.
[68] ; R: A Language and Environment for Statistical Computing: Vienna, Austria 2012; .
[69] Geman, S.; Geman, D.; Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images; IEEE Trans. Pattern Anal. Mach. Intell.: 1984; Volume 6 ,721-741. · Zbl 0573.62030
[70] Kaiser, M.; Lahiri, S.; Nordman, D.; Goodness of fit tests for a class of Markov random field models; Ann. Stat.: 2012; Volume 40 ,104-130. · Zbl 1246.62179
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.