The neighborhood lattice for encoding partial correlations in a Hilbert space
The neighborhood lattice for encoding partial correlations in a Hilbert space
复制标题
DOI：
--
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
A. Amini;Bryon Aragam;Qing Zhou
中科院分区：
文献类型：
--
作者：
A. Amini;Bryon Aragam;Qing Zhou
邻域回归在图形和结构方程建模中是一种成功的方法，应用于学习无向和有向图形模型。我们通过定义和研究一种称为邻域格的代数结构来扩展这些思想，该结构基于邻域回归的广义概念。我们证明了这种代数结构有可能为高斯分布中的所有条件独立性语句(或一般的条件不相关)提供一种经济编码，即使在不存在可以对所有这些语句进行“完美”编码的图形模型的情况下也是如此。我们研究了计算这些结构的计算复杂性，并证明了在稀疏性假设下，即使没有图的完备性假设，它们也可以在多项式时间内计算。另一方面，在假设完美的情况下，我们展示了如何使用所谓的偏相关图的分离性质来“图形化”地计算这些邻域格子。我们还利用有向无环图模型和贝叶斯网络建立了联系。我们利用部分不相关的抽象推广得到这些结果，称为部分正交性，它允许我们利用Hilbert空间上的投影算子的代数性质来显著简化和扩展现有的思想和论点。因此，我们的结果适用于广泛的随机对象和数据结构，例如随机向量、数据矩阵和函数。
Neighborhood regression has been a successful approach in graphical and structural equation modeling, with applications to learning undirected and directed graphical models. We extend these ideas by defining and studying an algebraic structure called the neighborhood lattice based on a generalized notion of neighborhood regression. We show that this algebraic structure has the potential to provide an economic encoding of all conditional independence statements in a Gaussian distribution (or conditional uncorrelatedness in general), even in the cases where no graphical model exists that could "perfectly" encode all such statements. We study the computational complexity of computing these structures and show that under a sparsity assumption, they can be computed in polynomial time, even in the absence of the assumption of perfectness to a graph. On the other hand, assuming perfectness, we show how these neighborhood lattices may be "graphically" computed using the separation properties of the so-called partial correlation graph. We also draw connections with directed acyclic graphical models and Bayesian networks. We derive these results using an abstract generalization of partial uncorrelatedness, called partial orthogonality, which allows us to use algebraic properties of projection operators on Hilbert spaces to significantly simplify and extend existing ideas and arguments. Consequently, our results apply to a wide range of random objects and data structures, such as random vectors, data matrices, and functions.