Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Guelph

$11,000.00

Exploiting Graphical Structure in Model Search for High Dimensional Data

EF 2013-14

Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
326951-2013
Name nom
Ali, RebeccaAyesha
Department département
Mathematics and Statistics
Organization id
24
Institution établissement
University of Guelph
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2013
Competition year année de concours
2013
Award amount
11000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
3011
Research subject group en
Statistics and probability
Research subject group fr
Statistique et probabilité
Research subject en
Multivariate analysis
Research subject fr
Analyse multivariée
Partie
1
Nb partie
5
Application title
Exploiting Graphical Structure in Model Search for High Dimensional Data
Keyword
NSERC
Application summary
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.