Exploiting Graphical Structure in Model Search for High Dimensional Data

点击翻译按钮获取中文摘要

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.