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.