A sampling technique based on LDPC codes

Given an inference problem, it is common that exact inference algorithms are computationally intractable and one has to resort to approximate inference algorithms. Monte Carlo methods, which rely on repeated sampling of the target distribution to obtain numerical results, is a powerful and popular way to tackle difficult inference problems. In order to use Monte Carlo methods, a good sampling scheme is vital. This thesis aims to propose a new sampling scheme based on Low Density Parity Check codes and compare it with existing sampling techniques. The proposed sampling scheme works for discrete variables only, but makes no further assumption of the structure of target distribution. The main idea of the proposed sampling method relies on the concept of typicality. By definition, a strong typical sequence with respect to a distribution can closely approximate the distribution. In other words, if we can find a strong typical sequence, the symbols in the sequence can be used as samples from the distribution. According to asymptotic analysis, the set of typical sequences dominates the probability and all typical sequences are roughly equi-probable. Thus samples from the distribution can be obtained by associating each typical sequence with an index, uniformly randomly picking an index, and finding the typical sequence that corresponds to the chosen index. The symbols in that sequence are the desired samples. To simulate this process in practice, an LDPC code is introduced. Its parity check values are uniformly randomly generated, and can be regarded as the index. Then we look for the most likely sequence that satisfies all the parity checks, and it will be proved that this sequence is a typical one with high probability if the LDPC has appropriate rate. If the most likely sequence found is a typical one, it can be regarded as the one corresponding to the chosen index. In practice, finding the most likely sequence can be computationally intractable. Thus Belief Propagation algorithm is implemented to perform approximate simulation of the sampling process. The proposed LDPC-based sampling scheme is formally defined first. After proving its correctness under maximum-likelihood simulation, we empirically examine the performance of the scheme on several distributions, namely Markov chain sources, Single loop sources, and 2-Dimensional Ising models. The results show that the proposed scheme can produce good quality samples for the aforementioned distributions.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Zhang, Xuhong, Ph. D. Massachusetts Institute of Technology

Advisor dc:contributor.advisor

• Gregory W. Wornell.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/97821

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/97821