IBM Research Report SINCO - A Greedy Coordinate Ascent Method for Sparse Inverse Covariance Selection Problem
IBM Research Report SINCO - A Greedy Coordinate Ascent Method for Sparse Inverse Covariance Selection Problem
复制标题
IBM 研究报告 SINCO - 稀疏逆协方差选择问题的贪婪坐标上升法
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
I. Rish
中科院分区：
文献类型：
--
作者：
K. Scheinberg;I. Rish
本文研究等价于高斯变量上马尔可夫网络结构恢复的稀疏反协方差选择问题。我们介绍了一种简单而有效的贪心算法，称为SINCO，用于求解稀疏逆协方差问题。我们的方法基于坐标上升法，自然地保持了逆协方差矩阵的稀疏性。我们将我们的算法与最先进的方法glasso[5]进行了比较，评估了两种方法的计算效率和结构重建精度。我们表明，这两种方法在速度和精度上通常是相当的，然而，在某些情况下，我们的方法在计算时间和结构重建误差（特别是假阳性误差）方面都明显优于玻璃。我们的方法还有一个额外的优点，就是易于并行化。我们还表明，该方法的贪婪性质使得人们可以通过仅将该方法应用于正则化参数的一个实例来再现正则化路径行为。数值实验证明了我们的方法在模拟网络上的优势，无论是随机的还是“结构化的”（无标度）网络，其中的真值结构是可用的。我们还报告了在现实生活中具有未知基真结构的问题上有希望的经验结果，例如从fMRI数据中分类精神状态。
In this paper, we consider the sparse inverse covariance selection problem which is equivalent to structure recovery of a Markov Network over Gaussian variables. We introduce a simple but efficient greedy algorithm, called SINCO, for solving the Sparse INverse COvariance problem. Our approach is based on coordinate ascent method which naturally preserves the sparsity of the inverse covariance matrix. We compare our algorithm to the state-of-art method called glasso [5], evaluating both computational efficiency and structure-reconstruction accuracy of both methods. We show that the two methods are often comparable in speed and accuracy, however, in some regimes, our method can significantly outperform glasso in terms of both computational time and structure reconstruction error (particularly, false positive error). Our method has an additional advantage of being easily parallelizable. We also show that the greedy nature of the method is such that one can reproduce the regularization path behavior by applying the method to one instance of the regularization parameter only. Numerical experiments demonstrate advantages of our approach on simulated networks, both random and “structured” (scale-free) ones, where the ground-truth structure is available. We also report promising empirical results on real-life problems with unknown ground-truth structure, such as classification of mental states from fMRI data.