Exploiting the Limits of Structure Learning via Inherent Symmetry

Peng He, Changshui Zhang
Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, PMLR 33:328-337, 2014.

Abstract

This theoretical paper is concerned with the structure learning limit for Gaussian Markov random fields from i.i.d. samples. The common strategy is applying the Fano method to a family of restricted ensembles. The efficiency of this method, however, depends crucially on selected restricted ensembles. To break through this limitation, we analyze the whole graph ensemble from high-dimensional geometric and group-theoretical perspectives. The key ingredients of our approach are the geometric property of concentration matrices and the invariance of orthogonal group actions on the symmetric Kullback-Leibler divergence. We then establish the connection of the learning limit and eigenvalues of concentration matrices, which leads to a sharper structure learning limit. To our best knowledge, this is the first paper to consider the structure learning problem via inherent symmetries of the whole ensemble. Finally, our approach can be applicable to other graphical structure learning problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v33-he14b, title = {{Exploiting the Limits of Structure Learning via Inherent Symmetry}}, author = {He, Peng and Zhang, Changshui}, booktitle = {Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics}, pages = {328--337}, year = {2014}, editor = {Kaski, Samuel and Corander, Jukka}, volume = {33}, series = {Proceedings of Machine Learning Research}, address = {Reykjavik, Iceland}, month = {22--25 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v33/he14b.pdf}, url = {https://proceedings.mlr.press/v33/he14b.html}, abstract = {This theoretical paper is concerned with the structure learning limit for Gaussian Markov random fields from i.i.d. samples. The common strategy is applying the Fano method to a family of restricted ensembles. The efficiency of this method, however, depends crucially on selected restricted ensembles. To break through this limitation, we analyze the whole graph ensemble from high-dimensional geometric and group-theoretical perspectives. The key ingredients of our approach are the geometric property of concentration matrices and the invariance of orthogonal group actions on the symmetric Kullback-Leibler divergence. We then establish the connection of the learning limit and eigenvalues of concentration matrices, which leads to a sharper structure learning limit. To our best knowledge, this is the first paper to consider the structure learning problem via inherent symmetries of the whole ensemble. Finally, our approach can be applicable to other graphical structure learning problems.} }
Endnote
%0 Conference Paper %T Exploiting the Limits of Structure Learning via Inherent Symmetry %A Peng He %A Changshui Zhang %B Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2014 %E Samuel Kaski %E Jukka Corander %F pmlr-v33-he14b %I PMLR %P 328--337 %U https://proceedings.mlr.press/v33/he14b.html %V 33 %X This theoretical paper is concerned with the structure learning limit for Gaussian Markov random fields from i.i.d. samples. The common strategy is applying the Fano method to a family of restricted ensembles. The efficiency of this method, however, depends crucially on selected restricted ensembles. To break through this limitation, we analyze the whole graph ensemble from high-dimensional geometric and group-theoretical perspectives. The key ingredients of our approach are the geometric property of concentration matrices and the invariance of orthogonal group actions on the symmetric Kullback-Leibler divergence. We then establish the connection of the learning limit and eigenvalues of concentration matrices, which leads to a sharper structure learning limit. To our best knowledge, this is the first paper to consider the structure learning problem via inherent symmetries of the whole ensemble. Finally, our approach can be applicable to other graphical structure learning problems.
RIS
TY - CPAPER TI - Exploiting the Limits of Structure Learning via Inherent Symmetry AU - Peng He AU - Changshui Zhang BT - Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics DA - 2014/04/02 ED - Samuel Kaski ED - Jukka Corander ID - pmlr-v33-he14b PB - PMLR DP - Proceedings of Machine Learning Research VL - 33 SP - 328 EP - 337 L1 - http://proceedings.mlr.press/v33/he14b.pdf UR - https://proceedings.mlr.press/v33/he14b.html AB - This theoretical paper is concerned with the structure learning limit for Gaussian Markov random fields from i.i.d. samples. The common strategy is applying the Fano method to a family of restricted ensembles. The efficiency of this method, however, depends crucially on selected restricted ensembles. To break through this limitation, we analyze the whole graph ensemble from high-dimensional geometric and group-theoretical perspectives. The key ingredients of our approach are the geometric property of concentration matrices and the invariance of orthogonal group actions on the symmetric Kullback-Leibler divergence. We then establish the connection of the learning limit and eigenvalues of concentration matrices, which leads to a sharper structure learning limit. To our best knowledge, this is the first paper to consider the structure learning problem via inherent symmetries of the whole ensemble. Finally, our approach can be applicable to other graphical structure learning problems. ER -
APA
He, P. & Zhang, C.. (2014). Exploiting the Limits of Structure Learning via Inherent Symmetry. Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 33:328-337 Available from https://proceedings.mlr.press/v33/he14b.html.

Related Material