## Equivalence Classes

If some person subnetworks are identical in structure and parameters, and they are instantiated to the same evidence, then fewer calls to the inference engine are needed. Eq. 3 can be written as:

P(e 11) = P(Pj = ej 11)2 • P(P3 = e211)2, because P1 and P2 share the same evidence, as do P3 and P4.

We define an equivalence class Qj as a pair Qj = (Pi, e. ), where Pi is a person model and ej is a (possibly incomplete) set

3 "never'' means the person is in the population at large and has not recently been admitted to the ED.

of evidence over the variables in P;.4 A given evidence state e for the entire population corresponds to a unique set of equivalence classes and the instance count of each class. Using this set, the general expression for the quantity P(e II) is as follows:

Qi Efl

where Nj is the instance count of equivalence class Qj, that is, it is the number of people for whom we model with person model Pi, and for which the evidence is Ej = e.

If the person model is relatively simple, then there could be many fewer equivalence classes than there are people in the population. For our example, since all person models are identical, the number of equivalence classes is equal to the number of possible ways to instantiate the variables of the person model (including not observing the state for those variables that sometimes have missing values). In this case, we would have at most (101 zip codes) x (2 genders) x (10 age ranges) x (4 relative dates of admission) x (3 respiratory states) = 24,240 states. In practice, the actual number of equivalence classes present at any one time is usually smaller, since rarer equivalence classes often do not appear.

In previous work, object-oriented Bayesian networks (Koller and Pfeffer, 1997) and related work (Srinivas, 1994, Xiang and Jensen, 1999) have been used to improve the efficiency of BN inference. The method we have described in this section takes advantage of those computational savings, as well as the savings that accrue from performing inference only once for objects of a given class that share the same evidence.