Exploiting Graphical Structure in Model Search for High Dimensional Data

在高维数据模型搜索中利用图形结构

• 批准号: 326951-2013
• 负责人: Ali, RebeccaAyesha
• 金额: $ 0.8万
• 依托单位: University of Guelph
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2013
• 资助国家: 加拿大
• 起止时间: 2013-01-01 至 2014-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=526753
• 关键词: Exploiting; Graphical; Structure; Model; Search

The main objective of this research program is to characterize the submodel relation for equivalence classes of directed acyclic graphs in the presence of latent and/or selection variables and to exploit the learned structures in developing a model search procedure. In particular, we will provide graphical criteria for the maximal ancestral graph (MAG) submodel relation and extend them to MAG equivalence classes. The applicant has determined five graphical criteria for the DAG submodel relation that, unlike previous formulations, rely on configurations that retain all the information about the Markov relations in a given graph. The first step is to prove that these criteria are also adaptable to equivalence classes of directed acyclic graphs (DAGs) and then to extend these results to the broader class of ancestral graphs by exploiting the abovementioned configurations. We will provide a polynomial time algorithm for testing the criteria for two given graphs. The next step is to develop model searches that exploit the submodel relations and are scalable to high dimensions. In particular, these results would permit the first search-and-score procedure for structure learning of MAGs.

本研究计划的主要目标是在存在潜在变量和/或选择变量的情况下，表征有向无环图等价类的子模型关系，并利用学习结构开发模型搜索过程。特别地，我们将提供最大祖先图（MAG）子模型关系的图形准则，并将其扩展到MAG等价类。申请人已经确定了DAG子模型关系的五个图形标准，与以前的公式不同，这些标准依赖于保留给定图中有关马尔可夫关系的所有信息的配置。第一步是证明这些准则也适用于有向无环图（dag）的等价类，然后通过利用上述配置将这些结果扩展到更广泛的祖先图类。我们将提供一个多项式时间算法来测试两个给定图的标准。下一步是开发利用子模型关系并可扩展到高维的模型搜索。特别是，这些结果将允许对mag的结构学习进行第一次搜索和评分程序。