Exploiting Graphical Structure in Model Search for High Dimensional Data

本研究计划的主要目标是表征子模型关系的等价类的有向无环图中存在的潜在和/或选择变量，并利用学习的结构，在开发一个模型搜索过程。 特别是，我们将提供最大祖先图（MAG）子模型关系的图形标准，并将其扩展到MAG等价类。申请人已经确定了DAG子模型关系的五个图形标准，与先前的公式不同，其依赖于在给定图中保留关于马尔可夫关系的所有信息的配置。第一步是证明这些标准也适用于等价类的有向无环图（DAG），然后将这些结果扩展到更广泛的类的祖先图利用上述配置。 我们将提供一个多项式时间算法来测试两个给定图的标准。 下一步是开发利用子模型关系的模型搜索，并可扩展到高维。 特别是，这些结果将允许第一个搜索和评分程序的结构学习的MAG。新奇和意义：该研究计划的结果将解决DAG等价类子模型关系的长期开放问题，并将该结果扩展到某些节点未被观察到的情况是新颖的。这些结果将允许人们在多项式时间内检查一个模型是否是另一个模型的子模型，询问给定图有多少子模型或超模型，并更好地理解其他模型与假设的模型一致。 这项研究将大大促进开发新的和有效的模型搜索，利用子模型的关系。 迄今为止，利用子模型关系的祖先图的模型选择还没有被认为是在文献中。对这里概述的基础研究的支持将大大有助于人工智能，这是加拿大经济的一个新兴重要领域。

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.****Novelty and Significance: The results of this research program would solve the long-standing open problem of the DAG equivalence class submodel relation and extending this result to the case where some nodes are not observed is novel. These results would allow one to check if one model is the submodel of another in polynomial time, to ask how many submodels or supermodels a given graph has, and to better understand what other models are consistent with a hypothesized one. This research would substantially facilitate the development of novel and efficient model searches that exploit the submodel relation. To date, model selection for ancestral graphs by exploiting the submodel relation has not been considered in the literature. Support for the foundational research outlined here will substantially contribute to artificial intelligence, an area of emerging importance for the Canadian economy.******************