International Journal on Artificial Intelligence Tools c © World Scientific Publishing Company LEARNING MARKOV NETWORK STRUCTURES CONSTRAINED BY CONTEXT-SPECIFIC INDEPENDENCES

This work focuses on learning the structure of Markov networks. Markov networks are parametric models for compactly representing complex probability distributions. These models are composed by: a structure and numerical weights. The structure describes in-dependences that hold in the distribution. Depending on the goal of learning intended by the user, structure learning algorithms can be divided into: density estimation algorithms, focusing on learning structures for answering inference queries; and knowledge discovery algorithms, focusing on learning structures for describing independences qualitatively. The latter algorithms present an important limitation for describing independences as they use a single graph, a coarse grain representation of the structure. However, many practical distributions present a flexible type of independences called context-specific independences, which cannot be described by a single graph. This work presents an approach for overcoming this limitation by proposing an alternative representation of the structure that named canonical model; and a novel knowledge discovery algorithm called CSPC for learning canonical models by using as constraints context-specific in-dependences present in data. On an extensive empirical evaluation, CSPC learns mor