ERA

Download the full-sized PDF of Exploiting Symmetries to Construct Efficient MCMC Algorithms With an Application to SLAMDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3K35MM2J

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Graduate Studies and Research, Faculty of

Collections

This file is in the following collections:

Theses and Dissertations

Exploiting Symmetries to Construct Efficient MCMC Algorithms With an Application to SLAM Open Access

Descriptions

Other title
Subject/Keyword
symmetry
probability
MCMC
Markov chain Monte Carlo
SLAM
Simultaneous Localization and Mapping
artificial intelligence
Metropolis-Hastings
Type of item
Thesis
Degree grantor
University of Alberta
Author or creator
Shariff, Roshan
Supervisor and department
Szepesvári, Csaba (Computing Science)
Examining committee member and department
György, András (Computing Science)
Schmuland, Byron (Mathematical and Statistical Sciences)
Szepesvári, Csaba (Computing Science)
Department
Department of Computing Science
Specialization

Date accepted
2015-04-02T14:58:19Z
Graduation date
2015-06
Degree
Master of Science
Degree level
Master's
Abstract
Sampling from a given probability distribution is a key problem in many different disciplines. Markov chain Monte Carlo (MCMC) algorithms approach this problem by constructing a random walk governed by a specially constructed transition probability distribution. As the random walk progresses, the distribution of its states converges to the required target distribution. The Metropolis-Hastings (MH) algorithm is a generally applicable MCMC method which, given a proposal distribution, modifies it by adding an accept/reject step: it proposes a new state based on the proposal distribution and the existing state of the random walk, then either accepts or rejects it with a certain probability; if it is rejected, the old state is retained. The MH algorithm is most effective when the proposal distribution closely matches the target distribution: otherwise most proposals will be rejected and convergence to the target distribution will be slow. The proposal distribution should therefore be designed to take advantage of any known structure in the target distribution. A particular kind of structure that arises in some probabilistic inference problems is that of symmetry: the problem (or its sub-problems) remains unchanged under certain transformations. A simple kind of symmetry is the choice of a coordinate system in a geometric problem; translating and rotating the origin of a plane does not affect the relative positions of any points on it. The field of group theory has a rich and fertile history of being used to characterize such symmetries; in particular, topological group theory has been applied to the study of both continuous and discrete symmetries. Symmetries are described by a group that acts on the state space of a problem, transforming it in such a way that the problem remains unchanged. We consider problems in which the target distribution has factors, each of which has a symmetry group; each factor's value does not change when the space is transformed by an element of its corresponding symmetry group. This thesis proposes a variation of the MH algorithm where each step first chooses a random transformation of the state space and then applies it to the current state; these transformations are elements of suitable symmetry groups. The main result of this thesis extends the acceptance probability formula of the textbook MH algorithm to this case under mild conditions, adding much-needed flexibility to the MH algorithm. The new algorithm is also demonstrated in the Simultaneous Localization and Mapping (SLAM) problem in robotics, in which a robot traverses an unknown environment, and its trajectory and a map of the environment must be recovered from sensor observations and known control signals. Here the group moves are chosen to exploit the SLAM problem's natural geometric symmetries, obtaining the first fully rigorous justification of a previous MCMC-based SLAM method. New experimental results comparing this method to existing state-of-the-art specialized methods on a standard range-only SLAM benchmark problem validate the strength of the approach.
Language
English
DOI
doi:10.7939/R3K35MM2J
Rights
Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
Citation for previous publication
Roshan Shariff, András György, and Csaba Szepesvári. Exploiting symmetries to construct efficient MCMC algorithms with an application to SLAM. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (AISTATS), San Diego, CA, USA, May 9–12. JMLR: W&CP volume 38, 2015. Forthcoming.

File Details

Date Uploaded
Date Modified
2015-06-15T07:10:46.958+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 1248305
Last modified: 2015:10:22 06:07:30-06:00
Filename: Shariff_Roshan_201504_MSc.pdf
Original checksum: a6aff1ec8768a293d1073e14f1abc40e
Activity of users you follow
User Activity Date