On Learning Discrete Graphical Models using Group-Sparse Regularization

Ali Jalali, Pradeep Ravikumar, Vishvas Vasuki, Sujay Sanghavi
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:378-387, 2011.

Abstract

We study the problem of learning the graph structure associated with a general discrete graphical models (each variable can take any of $m > 1$ values, the clique factors have maximum size $c \geq 2$) from samples, under high-dimensional scaling where the number of variables $p$ could be larger than the number of samples $n$. We provide a quantitative consistency analysis of a procedure based on node-wise multi-class logistic regression with group-sparse regularization. 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 – the procedure succeeds 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 still recovers the graph structure, when the samples scale as $n > K (m-1)^2 d^{\frac{3}{2}c - 1} \log ( (m-1)^c (p-1)^{c-1} )$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v15-jalali11a, title = {On Learning Discrete Graphical Models using Group-Sparse Regularization}, author = {Jalali, Ali and Ravikumar, Pradeep and Vasuki, Vishvas and Sanghavi, Sujay}, booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics}, pages = {378--387}, year = {2011}, editor = {Gordon, Geoffrey and Dunson, David and Dudík, Miroslav}, volume = {15}, series = {Proceedings of Machine Learning Research}, address = {Fort Lauderdale, FL, USA}, month = {11--13 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v15/jalali11a/jalali11a.pdf}, url = {https://proceedings.mlr.press/v15/jalali11a.html}, abstract = {We study the problem of learning the graph structure associated with a general discrete graphical models (each variable can take any of $m > 1$ values, the clique factors have maximum size $c \geq 2$) from samples, under high-dimensional scaling where the number of variables $p$ could be larger than the number of samples $n$. We provide a quantitative consistency analysis of a procedure based on node-wise multi-class logistic regression with group-sparse regularization. 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 – the procedure succeeds 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 still recovers the graph structure, when the samples scale as $n > K (m-1)^2 d^{\frac{3}{2}c - 1} \log ( (m-1)^c (p-1)^{c-1} )$.} }
Endnote
%0 Conference Paper %T On Learning Discrete Graphical Models using Group-Sparse Regularization %A Ali Jalali %A Pradeep Ravikumar %A Vishvas Vasuki %A Sujay Sanghavi %B Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2011 %E Geoffrey Gordon %E David Dunson %E Miroslav Dudík %F pmlr-v15-jalali11a %I PMLR %P 378--387 %U https://proceedings.mlr.press/v15/jalali11a.html %V 15 %X We study the problem of learning the graph structure associated with a general discrete graphical models (each variable can take any of $m > 1$ values, the clique factors have maximum size $c \geq 2$) from samples, under high-dimensional scaling where the number of variables $p$ could be larger than the number of samples $n$. We provide a quantitative consistency analysis of a procedure based on node-wise multi-class logistic regression with group-sparse regularization. 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 – the procedure succeeds 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 still recovers the graph structure, when the samples scale as $n > K (m-1)^2 d^{\frac{3}{2}c - 1} \log ( (m-1)^c (p-1)^{c-1} )$.
RIS
TY - CPAPER TI - On Learning Discrete Graphical Models using Group-Sparse Regularization AU - Ali Jalali AU - Pradeep Ravikumar AU - Vishvas Vasuki AU - Sujay Sanghavi BT - Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics DA - 2011/06/14 ED - Geoffrey Gordon ED - David Dunson ED - Miroslav Dudík ID - pmlr-v15-jalali11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 15 SP - 378 EP - 387 L1 - http://proceedings.mlr.press/v15/jalali11a/jalali11a.pdf UR - https://proceedings.mlr.press/v15/jalali11a.html AB - We study the problem of learning the graph structure associated with a general discrete graphical models (each variable can take any of $m > 1$ values, the clique factors have maximum size $c \geq 2$) from samples, under high-dimensional scaling where the number of variables $p$ could be larger than the number of samples $n$. We provide a quantitative consistency analysis of a procedure based on node-wise multi-class logistic regression with group-sparse regularization. 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 – the procedure succeeds 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 still recovers the graph structure, when the samples scale as $n > K (m-1)^2 d^{\frac{3}{2}c - 1} \log ( (m-1)^c (p-1)^{c-1} )$. ER -
APA
Jalali, A., Ravikumar, P., Vasuki, V. & Sanghavi, S.. (2011). On Learning Discrete Graphical Models using Group-Sparse Regularization. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 15:378-387 Available from https://proceedings.mlr.press/v15/jalali11a.html.

Related Material