A 'microscopic' study of minimum entropy search in learning decomposable Markov networks

Several scoring metrics are used in different search procedures for learning probabilistic networks. We study the properties of cross entropy in learning a decomposable Markov network. Though entropy and related scoring metrics were widely used, its 'microscopic' properties and asymptotic behavior in a search have not been analyzed. We present such a 'microscopic' study of a minimum entropy search algorithm, and show that it learns an I-map of the domain model when the data size is large. Search procedures that modify a network structure one link at a time have been commonly used for efficiency. Our study indicates that a class of domain models cannot be learned by such procedures. This suggests that prior knowledge about the problem domain together with a multi-link search strategy would provide an effective way to uncover many domain models.