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. 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. / Dans cette époque du "big data", les fichiers de données atteignent des tailles très importantes, et il y a un intérêt grandissant pour les algorithmes et les infrastructures de calcul adaptés à de telles quantités de données. Le nombre d'unités de calcul par puce électronique va lui aussi en grandissant. Au lieu de développer des méthodes ingénieuses pour accélérer la convergence et obtenir de meilleures approximations pour des classes de problèmes plus restreintes, il est intéressant de combiner l'utilisation d'algorithmes exacts avec une simple augmentation du nombre de coeurs ("cores") de microprocesseurs dédiés aux caluls et d'obtenir ainsi une accélération proportionelle. Ceci permet à des utilisateurs qui ne sont pas des spécialistes d'utiliser les algorithmes avec plus d'efficacité. Le "framework" MapReduce est un des paradigmes les plus utilisés pour le calcul parallèle. Nous montrons comment formuler les algorithmes de notre modèle spatial spécialisé dans cette infrastructure. On sait que les champs aléatoires de Markov avec des intéractions d'ordre élevé peuvent être utilisés pour représenter les propriétés à grande échelle de motifs spatiaux typiques par la simulation MCMC (Markov Chain Monte Carlo). Nous présentons une paramétrisation des champs aléatoires markoviens telle que la spécification des configurations de cliques qui comprennent des intéractions d'ordre supérieur à deux est prise en compte méthodiquement. Ceci sera utile à l'utilisateur qui voudra spécifier le type d'images qu'il désire produire. L'utilisation d'un champ aléatoire de Markov général requiert des approximations à cause de la constante de normalisation difficilement calculable en pratique, et les techniques d'inférence et de simulation pour les modèles avec dépendances d'ordre élevé par MCMC ont tendance à demander des temps de calculs prohibitifs, et sont parfois basées sur des algorithmes dont les critères de convergence sont sensibles aux données. Ces algorithmes ne sont pas adaptés aux besoins des utilisateurs et modélisateurs sans connaissances approfondies du MCMC. Il est donc préférable pour eux de travailler avec des modèles qui peuvent reproduire les structures spatiales, tout en étant plus faciles d'utilisation. Nous construisons des variantes du champ de Markov aléatoire avec les mêmes objectifs, mais pour lesquelles l'inférence et la simulation peuvent être accomplies sans recours au MCMC, et nous adaptons ces dernières au framework MapReduce. Nous nous intéressons également à la formulation dans MapReduce des algorithmes de simulation MCMC pour les champs aléatoires de Markov pour pouvoir faire usage de la puissance du calcul parallèle.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.114270 |
| Date | January 2013 |
| Creators | Manggala, Putra |
| Contributors | Luc P Devroye (Internal/Cosupervisor2), Roussos G Dimitrakopoulos (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0506 seconds