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

All Papers

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.