A Latent-Variable Lattice Model
This work addresses the computational bottleneck in MRF learning for computer vision applications, offering a faster alternative for robust learning from small datasets, but it is incremental as it focuses on a specific subset rather than a broad breakthrough.
The authors tackled the problem of intractable and computationally expensive Markov random field (MRF) learning by targeting a small subset used in computer vision, characterized by Lattice, Homogeneity, and Inertia, and designed a non-Markov model as an alternative, resulting in a learning algorithm with time complexity O(U log U) for a dataset of U pixels, which is much faster than general-purpose MRF.
Markov random field (MRF) learning is intractable, and its approximation algorithms are computationally expensive. We target a small subset of MRF that is used frequently in computer vision. We characterize this subset with three concepts: Lattice, Homogeneity, and Inertia; and design a non-markov model as an alternative. Our goal is robust learning from small datasets. Our learning algorithm uses vector quantization and, at time complexity O(U log U) for a dataset of U pixels, is much faster than that of general-purpose MRF.