Abstract | ||
---|---|---|
Given a Gaussian Markov random field, we consider the problem of selecting a subset of variables to observe which minimizes the total expected squared prediction error of the unobserved variables. We first show that finding an exact solution is NP-hard even for a restricted class of Gaussian Markov random fields, called Gaussian free fields, which arise in semi-supervised learning and computer vision. We then give a simple greedy approximation algorithm for Gaussian free fields on arbitrary graphs. Finally, we give a message passing algorithm for general Gaussian Markov random fields on bounded tree-width graphs. |
Year | Venue | Field |
---|---|---|
2012 | CoRR | Mathematical optimization,Random field,Gaussian random field,Markov model,Gaussian,Gaussian process,Variable-order Markov model,Hidden Markov model,Gaussian function,Mathematics |
DocType | Volume | Citations |
Journal | abs/1209.5991 | 0 |
PageRank | References | Authors |
0.34 | 12 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Satyaki Mahalanabis | 1 | 7 | 2.28 |
Daniel Stefankovic | 2 | 243 | 28.65 |