On the Use of Independence Relationships for Learning Simplified Belief Networks

this paper, our interest is focused in studying the methods based on independence criteria. The main reason for selecting these methods is that we can obtain general procedures for learning belief networks, regardless of the formalism used for managing the uncertainty. In other words, we are considering independence statements as abstract concepts, reflecting qualitative instead of quantitative properties of the problem, and therefore less dependent of the numerical parameters represented in the network. So, these methods could also be used for learning belief networks in cases where the underlying uncertainty model is different from probability theory (provided that we have an appropriate concept of independence within this formalism, see [15, 3, 16, 17]). However, the learning methods based on independence criteria present two main drawbacks: (1) they usually need an exponential number of conditional independence tests, and (2) these tests involve a great number of variables. Note that testing a conditional independence statement between two variables requires a time which is exponential with the number of variables used in the conditioning set. Considering that the problem of learning general belief networks belongs to the class of NP-Hard problems, and that any attempt for reducing the complexity is welcome, we focus on the following question: suppose that we have a previous knowledge about the kind of model to be recovered. Then, is it possible to obtain an efficient learning algorithm using this information? Being more specific, if the given information limits the type of graph structure to be recovered, may this be used in order to design faster learning algorithms? This approach has been successfully used for singly connected networks (trees and polytrees), wher..