Learning Discrete Graphical Models

• Activity Number: 599
• Type: Invited
• Date/Time: Thursday, August 4, 2011 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Pradeep Ravikumar*+
• Companies: The University of Texas at Austin
• Keywords: Graphical Models ; Sparsity ; Feature Selection ; High-dimensional ; Consistency

Abstract

We study the problem of learning the graph structure associated with a general discrete graphical model, where each variable can take any of $m > 1$ values and the clique factors have maximum size $c \ge 2$, under high-dimensional scaling where the number of variables $p$ could be larger than the number of samples $n$. We provide quantitative consistency analyses of procedures based on variational approximations and node-wise greedy algorithms.

We first consider general $m$-ary pairwise models -- where each factor depends on at most two variables. We show that when the number of samples scale as $n > K(m-1)^2 d^2 \log ( (m-1)^2(p-1))$ -- where $d$ is the maximum degree and $K$ a fixed constant -- we succeed in recovering the graph with high probability. For general models with $c$-way factors, the natural multi-way extension of the pairwise method quickly becomes very computationally complex. So we studied the effectiveness of using the pairwise method even while the true model has higher order factors. Surprisingly, we show that under slightly more stringent conditions, the pairwise procedure {\em still} recovers the graph structure.