LEARNING BAYESIAN NETWORK BY FIRST LEARNING MARKOV NETWORK

Markov network is an another powerful tool besides Bayesian network, which can be used to do uncertain inference. Markov network is an undirected graph, while Bayesian network is a directed acyclic graph. Learning Markov network is easier than learning Bayesian network because it doesn’t need to find the direction of an edge. A method of learning Bayesian network by first learning Markov network is given. Taking advantage of an important conclusion in information theory to test conditional independence, a dependency analysis based Markov network learning algorithm （edge deleting algorithm） is presented. The algorithm requires O（n 2） times CI（conditional independence） test, while the time complexity of a CI test depends on the size of the joint probability table which is obtained from the sample data. It has been proved that if the joint probability obtained from the sample data is strictly positive, the found Markov network must be the minimal I map of the sample. After finding a Markov network, an equivalent Bayesian network can be by representing the same joint probability.