From Fields to Trees
We present new MCMC algorithms for computing the posterior distributions and expectations of the unknown variables in undirected graphical models with regular structure. For demonstration purposes, we focus on Markov Random Fields (MRFs). By partitioning the MRFs into non-overlapping trees, it is po...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
AUAI Press
2004
|
| _version_ | 1797059431044743168 |
|---|---|
| author | Hamze, F de Freitas, N |
| author_facet | Hamze, F de Freitas, N |
| author_sort | Hamze, F |
| collection | OXFORD |
| description | We present new MCMC algorithms for computing the posterior distributions and expectations of the unknown variables in undirected graphical models with regular structure. For demonstration purposes, we focus on Markov Random Fields (MRFs). By partitioning the MRFs into non-overlapping trees, it is possible to compute the posterior distribution of a particular tree exactly by conditioning on the remaining tree. These exact solutions allow us to construct efficient blocked and Rao-Blackwellised MCMC algorithms. We show empirically that tree sampling is considerably more efficient than other partitioned sampling schemes and the naive Gibbs sampler, even in cases where loopy belief propagation fails to converge. We prove that tree sampling exhibits lower variance than the naive Gibbs sampler and other naive partitioning schemes using the theoretical measure of maximal correlation. We also construct new information theory tools for comparing different MCMC schemes and show that, under these, tree sampling is more efficient. |
| first_indexed | 2024-03-06T20:04:09Z |
| format | Conference item |
| id | oxford-uuid:2857cafc-68b0-4667-beff-799f3591e2b6 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T20:04:09Z |
| publishDate | 2004 |
| publisher | AUAI Press |
| record_format | dspace |
| spelling | oxford-uuid:2857cafc-68b0-4667-beff-799f3591e2b62022-03-26T12:12:24ZFrom Fields to TreesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:2857cafc-68b0-4667-beff-799f3591e2b6Department of Computer ScienceAUAI Press2004Hamze, Fde Freitas, NWe present new MCMC algorithms for computing the posterior distributions and expectations of the unknown variables in undirected graphical models with regular structure. For demonstration purposes, we focus on Markov Random Fields (MRFs). By partitioning the MRFs into non-overlapping trees, it is possible to compute the posterior distribution of a particular tree exactly by conditioning on the remaining tree. These exact solutions allow us to construct efficient blocked and Rao-Blackwellised MCMC algorithms. We show empirically that tree sampling is considerably more efficient than other partitioned sampling schemes and the naive Gibbs sampler, even in cases where loopy belief propagation fails to converge. We prove that tree sampling exhibits lower variance than the naive Gibbs sampler and other naive partitioning schemes using the theoretical measure of maximal correlation. We also construct new information theory tools for comparing different MCMC schemes and show that, under these, tree sampling is more efficient. |
| spellingShingle | Hamze, F de Freitas, N From Fields to Trees |
| title | From Fields to Trees |
| title_full | From Fields to Trees |
| title_fullStr | From Fields to Trees |
| title_full_unstemmed | From Fields to Trees |
| title_short | From Fields to Trees |
| title_sort | from fields to trees |
| work_keys_str_mv | AT hamzef fromfieldstotrees AT defreitasn fromfieldstotrees |