标题： 高斯马尔可夫随机场的子集选择 显示英文标题

标题： Subset Selection for Gaussian Markov Random Fields

摘要： 给定一个高斯马尔可夫随机场，我们考虑选择一个变量子集进行观测的问题，以最小化未观测变量的总期望平方预测误差。 我们首先表明，即使对于一类称为高斯自由场的高斯马尔可夫随机场的限制类，找到精确解也是NP难的，这些高斯自由场出现在半监督学习和计算机视觉中。 然后，我们给出一个简单的贪心近似算法，用于任意图上的高斯自由场。 最后，我们给出一个消息传递算法，用于有界树宽图上的通用高斯马尔可夫随机场。 显示英文摘要

摘要： 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.