Which graphical models are difficult to learn? Export

@article{citeulike:6091265, abstract = {We consider the problem of learning the structure of Ising models (pairwise binary Markov random fields) from i.i.d. samples. While several methods have been proposed to accomplish this task, their relative merits and limitations remain somewhat obscure. By analyzing a number of concrete examples, we show that low-complexity algorithms systematically fail when the Markov random field develops long-range correlations. More precisely, this phenomenon appears to be related to the Ising model phase transition (although it does not coincide with it).}, archivePrefix = {arXiv}, author = {Bento, Jose and Montanari, Andrea}, citeulike-article-id = {6091265}, citeulike-linkout-0 = {http://arxiv.org/abs/0910.5761}, citeulike-linkout-1 = {http://arxiv.org/pdf/0910.5761}, day = {30}, eprint = {0910.5761}, keywords = {graphical\_model, ising, learning, phase\_transition}, month = {Oct}, posted-at = {2009-11-10 09:10:40}, priority = {2}, title = {Which graphical models are difficult to learn?}, url = {http://arxiv.org/abs/0910.5761}, year = {2009} }

TY - JOUR ID - citeulike:6091265 L3 - citeulike-article-id:6091265 N2 - We consider the problem of learning the structure of Ising models (pairwise binary Markov random fields) from i.i.d. samples. While several methods have been proposed to accomplish this task, their relative merits and limitations remain somewhat obscure. By analyzing a number of concrete examples, we show that low-complexity algorithms systematically fail when the Markov random field develops long-range correlations. More precisely, this phenomenon appears to be related to the Ising model phase transition (although it does not coincide with it). TI - Which graphical models are difficult to learn? KW - graphical_model KW - ising KW - learning KW - phase_transition AU - Bento, Jose AU - Montanari, Andrea PY - 2009/Oct/30/ UR - http://arxiv.org/abs/0910.5761 ER -