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.