Approximate inference : decomposition methods with applications to networks

Markov random field (MRF) model provides an elegant probabilistic framework to formulate inter-dependency between a large number of random variables. In this thesis, we present a new approximation algorithm for computing Maximum a Posteriori (MAP) and the log-partition function for arbitrary positive pair-wise MRF defined on a graph G. Our algorithm is based on decomposition of G into appropriately chosen small components; then computing estimates locally in each of these components and then producing a good global solution. We show that if either G excludes some finite-sized graph as its minor (e.g. planar graph) and has a constant degree bound, or G is a polynoinially growing graph, then our algorithm produce solutions for both questions within arbitrary accuracy. The running time of the algorithm is linear on the number of nodes in G, with constant dependent on the accuracy. We apply our algorithm for MAP computation to the problem of learning the capacity region of wireless networks. We consider wireless networks of nodes placed in some geographic area in an arbitrary manner under interference constraints. We propose a polynomial time approximate algorithm to determine whether a, given vector of end-to-end rates between various source-destination pairs can be supported by the network through a combination of routing and scheduling decisions. Lastly, we investigate the problem of computing loss probabilities of routes in a stochastic loss network, which is equivalent to computing the partition function of the corresponding MR.F for the exact stationary distribution.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Mathematics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2009

Author dc:creator

• Jung, Kyomin

Advisor dc:contributor.advisor

• Devavrat Shah.

• Mathematics.

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/50595

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/50595