Local Learning of Markov Networks Structures Constrained by Context-Specific Independences

EDERA, ALEJANDRO; STRAPPA, YANELA; BROMBERG, FACUNDO

Santiago de Chile

Conferencia; IBERAMIA; 2014

Sociedad Iberoamericana de Inteligencia Artificial

This work treats on learning the structure of Markov net- works. Markov networks are probabilistic models for compactly repre- senting complex probability distributions. These models are composed by two elements: a structure and a set of numerical weights. In a Markov network, its structure qualitatively describes independence assumptions that hold in the represented distribution. In this sense, a structure can be seen as a source of knowledge. Using such structure, the described independences can be exploited to achieve a compact representation of the distribution. Thus, a main application for learning structures is to discover new knowledge automatically from data. In practice, structure learning algorithms focus on knowledge discovery present an important limitation: they use a coarse grain representation of the structure. As a result, in many practical distributions, this representation cannot de- scribe a flexible type of independences called context-specific indepen- dences. Very recently, an algorithm called CSPC was designed to over- come this limitation in knowledge discovery algorithms, using an alterna- tive representation of the structure called canonical model. However, in contrast to knowledge discovery algorithms, CSPC presents an important downside: it has a high computational complexity. This work tries to mit- igate this downside presenting CSGS, an algorithm for learning canoni- cal models that uses an alternative strategy search to avoid unnecessary computation. On an empirical evaluation, the canonical models learned by CSGS achieve competitive accuracies and lower computational com- plexity with respect to those obtained by CSPC. As expected, the canon- ical models learned by CSGS results more accurate than the structures learned by several state-of-the-art structure learning algorithms.