Open Collections

Scalable sequential Monte Carlo methods and probabilistic approach to combinatorial problems

University of British Columbia

In this thesis, we consider two combinatorial problems arising in phylogenetics and computational forestry. We develop sequential Monte Carlo based inference methods to tackle the challenges arising from these applications. In the phylogenetics application, the SMC is placed under stringent restrictions in terms of computer memory to the point where using sufficient number of particles may be prohibitive. To that end, a new method, streaming particle filter (SPF), is proposed which alleviates this problem and study some of the theoretical properties of the algorithm, including L² convergence of the estimators derived from the SPF simulation. In the case of the computational forestry, the combinatorial problem that is tackled in this thesis is referred to as the knot matching problem. This problem is formulated as a graph matching problem on a K-partite hypergraph. A model for graph matching that admits efficient parameter inference is proposed along with a sequential Monte Carlo sampler for graph matching based on this model. A detailed background on each of the two problems are presented and evaluated on simulated and real data.

Text

2018-01-05

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/64277

Statistics

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/