Expert Systems and Probabilistic Network Models

In Chapter 6 we introduced graphically specified models using undirected or directed graphs to describe the dependency structures of probabilistic models. We have seen that not every probabilistic model can be specified by a perfect map. Thus, in general, graphs can only be thought of as minimal independence maps (I-maps), from which every conditional independence statement (CIS) derived from the graph holds in the associated probability model, though some CISs in the probability model may not be represented by the graph. Consequently, the main limitation of graphical models is that they can only represent certain types of independence structures. The following example illustrates this limitation.

In Chapter 8, we presented several algorithms for exact propagation of evidence in Markov and Bayesian network models. However, there are some problems associated with these methods. On one hand, some of these algorithms are not generally applicable to all types of network structures. For example, the polytrees algorithm (Section 8.3) applies only to networks with simple polytree structure. On the other hand, general exact propagation methods that apply to any Bayesian or Markov network become increasingly inefficient with certain types of network structures. For example, conditioning algorithms (Section 8.5) suffer from a combinatorial explosion when dealing with large sets of cutset nodes, and clustering methods (Section 8.6) require building a join tree, which can be an expensive computational task; and they also suffer from a combinatorial explosion when dealing with networks with large cliques. This is not surprising because as we have seen in Chapter 8, the task of exact propagation has been proven to be N P-hard (see Cooper (1990)). Thus, from the practical point of view, exact propagation methods may be restrictive or even inefficient in situations where the type of network structure requires a large number of computations and huge amount of memory and computer power.

In the previous chapters we assumed that both the dependency structure of the model and the associated conditional probability distributions (CPDs) are provided by the human experts. In many practical situations, this information may not be available. In addition, different experts can give different and sometimes conflicting assessments due to the subjective nature of the process. In these situations, the dependency structure and the associated CPDs can be estimated from the data. This is referred to as learning.