Groupe d’études et de recherche en analyse des décisions


On Tractable Markov Random Field Models and MapReduce Algorithms: Towards a Practitioner's Toolbox

, et

In the era of big data, data sets have been growing very large, and interest for algorithms and computation framework that handle such large scales is increasing. The number of computing cores per chip has also increased. Instead of developing ingenious ways of speeding up convergences and obtaining better approximations for a smaller subclass of the problems, it is interesting to simply "throw more cores" at exact algorithms and get a speed-up which scales accordingly. This allows practitioners who are not specialists to use the algorithms more efficiently. The MapReduce framework is one of the most widely used paradigms for parallel computation, and we show how to cast the exact deterministic algorithms for our customized spatial model in this framework. Abstract. Higher-order Markov random fields, i.e., Markov random fields with higher-order interactions, have been shown to be able to represent large-scale properties of typical spatial scenes via MCMC simulation. We present a Markov random field parametrization such that the specification of clique configurations that include higher-order interactions is included in a methodical fashion. This ought to be useful for a practitioner with respect to specifying the type of images desired. The general Markov random field model commonly requires approximation techniques due to its intractable normalization constant, and inference and simulation techniques for models with high dependence via MCMC tend to be time-consuming and may involve algorithms with sensitive convergence criteria. These algorithms are not suitable for practitioners or spatial modellers who are not well-versed in MCMC, and it is therefore more desirable for them to work with models that are able to reproduce spatial structures, while still being easier to wield. We construct variants of the Markov random field that seek to achieve the same goal, but whose inference and simulation is tractable without MCMC, and cast the latter in the MapReduce framework. We also consider the MapReduce formulation of MCMC simulation algorithms for Markov random fields in order to leverage the power of parallel computing.

, 28 pages