A Decision Theoretic View on Choosing Heuristics for Discovery of Graphical Models

Yang Xiang

Discovery of graphical models is NP-hard in general, which justifies using heuristics. We consider four commonly used heuristics. We summarize the underlying assumptions and analyze their implications as to what graphical models they can and cannot discover. In particular, we consider discovery of pseudo-independent (PI) models, a subclass of probabilistic models where subsets of a set of collectively dependent variables display marginal independence. We show that some heuristics essentially exclude PI models other than the simplest from the model search space. We argue for a decision theoretic perspective for choosing heuristics and emphasize its implication to mission critical applications.

Subjects: 12. Machine Learning and Discovery; 3.4 Probabilistic Reasoning

Submitted: Jan 29, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.