1 

, I' 

, , ' 

~i' 

NASA Technical Memorandum 88224 

NASA-TM-8822419860019155 

Automatic Probabilistic Knowledge 

Acquisition from Data 

William B. Gevarter 

April 1986 

NI\S/\ 

National Aeronautics and 

Space Administration 

1111111111111 1111 11111 11111 1I111 I1I11 11111111 

NF00940 

APR :~ () l~tJti 

LANGLEY RLSSi'\RCH CENTER 

LIBRARY, NASA 

HAMPTON, VIRGINIA 
NASA Technical Memorandum 88224 

,Automatic Probabilistic Knowledge 

,Ac(~uisition from Data 

William B. Gevarter, Ames Research Center, Moffett Field, California 

April 198:6 

INI\S/\ 

National Aeronautics and 

Space Administration 

Ames Research Center 

Moffett Field, California 94035 
A1JTOMATIC PROBABILISTIC KNOWLEDGE 

ACQUISITION FROM DATA 

William B. Gevarter 

ABSTR.ACT 

This memorandum documents an outiline for a computer program for extracting significant 

correlations of attributes from masses of data. This information can then be used to develop a 

knowledge base for a probabilistic "expert system." The method determines the "best" estimate 

of joint probabilities of attributes from data put into contingency table form. A major output 

from the program is a general formula for calculating any probability relation associated with 

thEl data. These probability relations can be utilized to form IF-THEN rules with associated 

probability, useful for expert systems. 

IN'TRo:nUCTION 

Knowledge acquisition is a major bottleneck in developing "expert systems." Thus a recent 

focus of the artificial intelligence (AI) community has been on "machine learning." Though 

this has been a theme in AI for several decades, it has only been in the last few years, spurred 

on by the popularity of expert systems, that machine learning has received major attention. 

Because of the emergence of sophisticated expert system building tools such as KEE (Intellicorp, 1985) and ART (Williams, 1985), and a host of follow-on simpler systems, the main 

difficulty in building conventional expert systems has now shifted to knowledge acquisition 

and. choosing the most appropriate knowledge structures and representations. Thus knowledge 

acquisition is an important and timely research area for NASA to investigate. 

Approaches to knowledge acquisition have included psychological techniques for interviewing 

experts (Boose, 1984 and Kahn et al., 1985) and automatic production of classification-oriented 

expert systems from examples as exemplified by the TIMM (General Research Corp., 1985) 

expert syst1em building tool. Thus far, such approaches have had only a limited range of 

su(:cessful applications. Therefore, methods of knowledge acquisition and knowledge extraction 

from data are important. current AI research topics. Knowledge acquisition can be construed 

as learning. 

AI learning systems can be classified according to the following strategies: 

1. Rote learning 

2. Learning from instruction 

3. Learning by analogy 

1 
4. Learning by examples 

5. Learning from observation and discovery 

The last learning strategy is perhaps the most recent and the most exciting. This strategy is exemplified by Lenat's (1982) AM and EURISKO systems and Langley et al. (1983) 

BACON system. These discovery systems are heavily knowledge-based. The usual focus of 

discovery systems is on discovering concepts. Cheeseman (1984) has explored another facet, 

that of developing specific correlations from data. His approach is probabilistic in nature and is 

primarily procedurally (syntactically) oriented. This approach is particularly appropriate when 

the source of the knowledge is in the form of large masses of undigested data, such as those obtained from wind tunnel tests; spacecraft observations; computer simulations; or psychological, 

medical, and social surveys. 

Commercial AI learning systems such as Expert-Ease (Derfier, 1985) and TIMM are aimed 

at developing decision aids from examples. In general, learning from examples is predicated 

on positive examples, which promote generalization ... and negative examples, which reduce 

generalization. However, commercial l~arning tools are not designed to extract significant 

information from data for which no conclusions have yet been reached. 

Many researchers believe that truly powerful intelligent systems will be difficult to achieve 

without a learning component because of the huge amount of knowledge many future expert systems will require, as well as the need to improve performance by learning new search heuristics 

as the system is used. 

This memorandum outlines an approach to probabilistically determining significant relationships in masses of data. This can be particularly important because NASA has masses of 

unevaluat~d data from its space explorations. Automatic means to find significant correlations 

in these data can begin to reduce this mammoth NASA reserve data bank. The approach 

outlined in. this paper draws on previous work by Cheeseman (1983, 1984) in this. area. Using 

this approach, the resultant information, probabilistically extracted from the data, allows calculations of the conditional probability of any proposition associated with the data, given any 

combination of evidence. This information can be used as clues for discovering more causal explanations. The probabilistically extracted information can also be transformed into IF-THEN 

("condition-conclusion") rules (with associated prob bility) found useful in expert systems. For 

example, the probability of A given Band C is p, written as 

peA I B,C) =p 

can also be written as 

IF B AND C, THEN A (with probability p) 

The system described in this memorandum does not generate rules explicitly. It generates 

and stores significant joint probabilities instead. Particular conditional probabilities can be 

calculated from this information as required by noting that a conditional probability can be 

written as the ratio of correspondingjoint probabilities. Thus, for example 

P( A I B C) = p( A B C) , pCB C) 

2 
P]:tOBL:EM DEFINITION 

The problem explored in this paper if! that of extracting information from data which can 

then be used to form the knowledge base of a probabilistic: expert system. The resultant formulation summarizes all the probabilistic information found from the data and can be used 

to <:alculate any probability associated with the data. The information found is the significant 

joint probabilities of attributes from data (which has resulted from a collection of observations). 

An illustrative example followed in this paper determines the probabilistic relationships of cancer to smoking given a set of observations on people over the age of 60 whose hypothetical case 

histories are obtained from the completion of the following questionaire 

A. SMOKING HISTORY 

1. Smoker 

:~. Non smoker not married to a smoker 

a. Non smoker married to a smoker 

B.CANCER 

1. Yes 

~t No 

C. FAMILY HISTORY OF CANCER 

1.. Yes 

2. No 

A set of data thus obtained from a survey of 3428 individuals might appear as shown in 

Figures la a.nd 1 b (called "contingency tables" 1). 

The numbers shown in each box or cell refer to the total number of individuals who have 

tha.t combination of attributes. Thus, the number of smokers who do not have cancer despite 

a family history of cancer is given as 410. This can be written in a shorthand notation as 

This states that there were 410 individuals that had the attribute values 

A (SMOKING) = 1 

B (CANCER) = 2 

C (FAMILY HISTORY = 1 

OF CANCER) 

(Smoker) 

(No) 

(Yes) 

1 Appendix A indicates how original data can be put into contingency table form. 

3 
A 

SMOKING 

B 

CANCER 

1 2 

Yes No 

1. Smoker 130 410 

2. Non smoker 62 580 

3. Non smoker 78 520 

married to 

a smoker 

C FAMILY HISTORY OF CANCER 

1. Yes 

(a) 

B 

CANCER 

1 2 

Yes No 

1. 110 640 

A 2. 31 460 

SMOKING 

3. 22 385 

C FAMILY HISTORY OF CANCER 

2. No 

(b) 

Figure 1: DATA ON SMOKING AND CANCER IN U.S. POPULATION OF AGE GREATER 

THAN 60. 

In general, we can refer to the number of individuals with the ith value of attribute A, the jth 

value of the attribute B and the kth value of the attribute C, as 

N ABC N iik or iik 

where i,j, k are the numbers associated with the values of the attributes. 

We will assume that the range of values for each attribute is complete (made so by adding 

the value "other," if necessary) so that the the number of people obtained by summing the 

numbers for each of the values of an attribute (e.g., B (CANCER)) will always add up to N 

(the total number of individuals surveyed). 

If We add up the numbers in each row or column of Figures 1a and 1b, we obtain the marginal 

values (placed in the margins) as shown in Figures2a and 2b. If we sum across C (FAMILY 

HISTORY OF CANCER), we obtain Figure 2c, which relates SMOKING to CANCER without 

breaking up the results with respect to family history. 

In equation form, these summations can be simply written as 

Nii = L Niik 

k 

Nik == LNijk 

Nik = LNiik 

i 

4 

(1) 

(2) 

(3) 
B 

CANCER 

marginals 

/ r 

~ B 

CANCER 

A 

SMOKING 

1. Smoker 

2. lion smoker 

3. lion smoker 

married to 

a smoker - -- - - - C 

N 

, ·1 

Yes No I 

N I 

:i.1 . 1 I 2 

130 I 410: 540 

I 

62 580 I _~~_ 

78 520J 598 

I 

- t-- -

I 270 1

151 

I 

/ 

1 

C F~~ILY HISTORY OF CANCER 

1. Yes 

(a) 

B 

CANCER 

J 

1 2 N 

Yes No , 

A 

i 

1. Smoker 240 1050 I 1290 

-.------+--+---1 -.oJ -

.Ii 2. Non smoker 93 1040; ':3~ SMOKING 

3. Non smoker 100 905 I 1005 

married to 

- ~s~ker - ~ - j - rB 

II 

J 

I 433 j29951~~ ; J I\:.:/- N 

RELATION OF SMOKING TO CANCER 

(c) 

1 

A 2. 

SMOKING 

3. 

1 2 1 

Yes No I 

I 

110 640 I 

I 

31 460 I 

22 385 1 

1 L..-- ___ 

AC 

N 

i2 

750 

491 

407 

\ I 1---

NBC 1163 :1485 1~648 j2 1 ( I I I 1 C 

C FAMILY HISTORY OF CANCER 

2. No 

(b) 

N 

2 

Figure 2: CANCER DATA ON U.S. POPULATION OF AGE GREATER THAN 60. 

5 
and 

Ni = 2:: Nif = 2:: 2:: Nif Ie (4) 

i i Ie 

or 

Ni = 2:: Nile = 2:: 2:: Niile (5) 

Ie Ie i 

Similarly, the total number of individuals, N, is simply the summation across all the indices 

(6) 

6 
APPRO.ACH 

The approach taken for finding joint probabilities of attributes is to maximize the entropy of 

the discrete probability distribution while satisfying the constraints imposed by all the known 

probabilities. This can also be thought of as achieving the maximum uncertainty in the values 

of these higher-order probabilities; as any lesser uncertainty would imply further constraints. 

"Ma.ximum entropy" probability values distribute the uncertainty (H) as evenly as possible 

over the underlying probability space in a. way consistent with the constraints. 

The "known probabilities" (constraints) are determined by applying a significance test to 

the data. A "minimum message length" criterion is used as the test for significance between 

the observed values of occurence of higher-order combinations of attributes in the data and the 

values calculated by the maximum entropy approach using the currently known constraints. 

If the minimum message length required to encode an observed value of occurence assuming 

a chance distribution is less than that given by the maximum entropy approach (using the 

constraints t.hus far), then the observed value is deemed significant and the joint probability 

associated with it is added to the list of constraints. Once all the significant joint probabilities 

are determined, any other probability relationships associated with the data can be readily 

calculated from the resulting succinct equation. 

M.AXIM[lZING THE ENTROPY 

The entropy (uncertainty) is given in terms of the joint probabilities as (Jaynes, 1979) 

H - - '" P··L logp··L - ~ '1"',·· '1"'··, (7) 

iik ... 

where iJ,k, .... are the indices of the values of the attributes and Piik is the joint probability 

(probability of the simultaneous occurrence of the ith value of the attribute A, the jth value of 

the attribute B, and the kth value of attribute C). 

For simplicity, in the rest of this paper, we will only consider three attributes - A, B, C. 

The extension to a larger number of attributes is straight forward. 

To maximize the entropy we first add to H the constraints (associated with the prior known 

probabilities) using LaGrange multipliers (w's) to form H'. We then take the derviative of H' 

with respect to each of the unknown variables-the probabilities and the LaGrange multipliersand set them equal to zero to find values for the variables that maximize H'. Thus 

+w(1 - Eiik Piik) 

+Wi(Pi - Eik Pi;k) + Wj(Pj - Eik Pijk) + Wk (Pk - Eij Pijk) 

+wii(Pii - Ek Piik) + Wik(Pi k - Ei Piik) + Wjk(Pik - Ei Pijk) 

+ ... 

Taking derivatives with respect to the probabilities, we obtain 

7 

(8) 
8H'j8Pijk = -logpijk -1- w- Wi - Wj - ... - Wij - ... = 0 

Therefore 

where we have defined 

From Equation 10 

where we have defined 

P.. _ e-(WO+Wi+ ... +Wij+ ... ) 13 k -

wo=w+1 

(9) 

(10) 

(11) 

(12) 

(13) 

Taking the partial derivatives of H' with respect to the W multipliers and setting them equal 

to zero, simply returns our given contraints 

8H'j8w = 0 -t LPijk = 1 

i;1e 

8H'j8wi = 0 -t LPijle = Pi 

;k 

8H'j8w; = 0 -t LPijk = Pj 

ile 

8H'j8wle = 0 -t LPi;1e = Pie 

ii 

8H' j8wii = 0 -t LPiik = Pii 

k 

8H'j8wile = 0 -t LPi;1e = Pile 

; 

8H'j8w;k = 0 -t LPi;k = P;1e 

(and so on for any higher-order known prior probabilities). 

Substituting for Pijk from Equation 12 into Equations 14 - 20, yields 

ao L aiaj···atjaik··· = 1 

ijk 

aOai L ajakaijaik··· = Pi 

jk 

aOaj L aiakaijaik··· = Pj 

ik 

8 

(14) 

(15) 

(16) 

(17) 

(18) 

(19) 

(20) 

(21) 

(22) 

(23) 
aoak:L: aiajaijaik··· = PA: 

ii 

(24) 

ThElse summations are simplified if we group the summations by the indices2 • Thus, for example 

ao L ai I: aiaij L akaikajk = 1 

i i k 

aOai L ajaij L akaikajk =: Pi 

i k 

aoaj I: aiaii L akaikaik =: Pi 

k 

aoak :L: aiaik L aiaiiaik = Pk 

; 

aOaijaiaj L akaikajk = Pii 

k 

aOaikaiak L aiaiiaik = Pik 

i 

aOajkaiak L aiaiiaik = Pjk 

(25) 

(26) 

(27) 

(28) 

(29) 

(30) 

(31) 

AP, will be illustrated later using our example, this set of simultaneous equations is iteratively 

solved for a values. Initially, the a values are calculated from the first-order probabilities 

derived from the data. Then the a values are recalculated using any known prior second-order 

probabilities:. Based on the resulting a va.lues, predicted second-order joint probabilities of the 

attributes are then calculated (using Equation 12 or equivalently Equations 25 - 31) and the 

observed dalGa is evaluated to see whether it differs significantly from the values predicted. 

IT the predicted probabilities of the observed values of the combinations of attributes are 

lesEl than th'e probabilities of their occurence owing to pure chance, then the values observed 

from the data are statistically significantly different from those calculated from the constra.ints 

used thus fa.r. In this case, these significantly different observed values are used to form new 

cOIllstraints a.nd the a values are recalculated. This process is repeated at this level and each 

successive level until all the observed statistically significant correlations are accounted for. 

P]R.EDICTING THE VALUE OF Niik 

The probability of finding the number Nijk of occurences having the ith value of attribute A, 

the jth value of B, and the kth value of C is given by the well-established "binomial distribution" 

P(Niik I Piik, N) == (::k) (Pijk)Niik (1 - Piik)N-Niik (32) 

2 A method for calculating such "sum of products" equations is given by Appendix B. 

9 
where 

N is the total number sampled 

Pijk is the prior probability (calculated from the a values) of the ith value of A, the jth value 

of B, and the kth value of C occurring together in the population being sampled. 

The predicted mean of Nijk is given by 

(33) 

and the associated standard deviation of Nijk is given by 

(34) 

The mean and standard deviation are useful for estimating the significance of the difference 

between the observed value of Nijk and the predicted value. 

SIGNIFICANCE TESTING OF THE OBSERVED VALUES 

OF THE Niik's 

In this section we determine the significance of the observed values of the N's by comparing the probability of their chance occurence with the probability predicted by the probability 

formula, Equation 12, derived from the constraints found thus far. If, for example, the probability of occurence by chance of an observed value of Nijk is greater than that predicted by the 

formula, we regard that Nijk as significant and use it as a constraint to revise our probability 

formula so that it will predict the observed value. The revised formula is then used to predict 

the probability of occurence of the remaining observed values of the N's and the procedure 

recursively repeated until no further significant N's are found. 

The procedure, outlined above, starts by comparing the probabilities of the chance occurence 

of the observed values of the second-order N's with 11e probabilities predicted by Equation 12 

and uses the resultant most significant N to update Equation 12. The remaining second-order 

N's are then evaluated using the new predictions and the procedure is recursively repeated until 

all the significant second-order N's have been determined. This procedure .is then repeated for 

the third-order N's and so on. 

In determining the probability of an observed value of Niik oturring by chance, we note 

that the values in the cells must add up to their constraining marginal values. Thus no cell 

can have a value exceeding its significant marginals minus the values of any other significant 

cells associated with those marginals. This sets a maximum value for a cell. If for a cell all the 

other cells associated with one of its significant marginals have been found to be significant, 

then the cell must have the value observed for it. If the cell is not so constrained, then for the 

chance case it is equally likely that it will have any integer value from zero to its maximum 

value (discussed above). 

We now derive the equation needed for comparing the probabilities of occurence of the 

observed value of Nijk as calculated by Equation 12 and as calculated for chance. 

10 
The well-known "bayesian formula" for calculating the posterior value of a hypothesis, hi, 

given data, D, is 

p(hll D) = P(h.l)~~ I hI) (35) 

where p(hl) is the prior probability of the hypothesis. For our purposes, a more convenient 

relative form of Baye's rule gives the likelihood ratio of the posterior probability of two different 

hypotheses (given the same data) 

p(hll D) p(hl) p(D I hi) 

p(h21 D) = p(h2) p(D I h2) 

Taking the log of the likelihood ratio, we obtain 

(36) 

p(hll D) In p(h2 I D) = [-lnp(h2) -lnp(D I h2)] - [-lnp(hl) -lnp(D I hI)] (37) 

In information theory, the minimum message length required to encode (communicate) a 

particular choice (e.g., hI) from a set of mutually exclusive and exhaustive hypotheses is proportional to -lnp(hl) (Jaynes, 1979). Thus, Equation 37 can be interpreted as proportional 

to the difference in the minimum message lengths required to represent the two hypotheses 

given the data. 

There are two basic hypotheses for the Nijk obtained from the data for a particular cell t"ik. 

Hi Given that we have found M nth-order significant constraints (joint probabilities), there 

are no more nth-order significant constraints. (i.e., Equation 12 adequately predicts the 

probability of occurence of the observed values of the remaining nth-order N's.) 

H2 Given that we have found M nth-order significant constraints (joint probabilities), there 

is at least one more nth-order significant constraint and this cell is the next nth-order 

significant constraint. 

The hypothesis H2 can be broken up into two hypotheses 

H2' There is at least one more nth-order significant constraint. 

H2" This <:ell is the next nth-order significant constraint. 

Thus 

p(H2) = p(H2' 112") = p(H2') p(112" I H2') 

where without any other information 

p(H2" I H2') 1 

remaining available cells at the current order 

1 

no. of cells at this order - M 

For the highest order this is simply 

11 

(38) 

(39) 
.' 1 

'p(H2" I H2') = (IJ K ... _ M) (40) 

where I,J, K are the total number of values of the A, B, and C attributes, respectively. 

For hypothesis H2, 'lacking prior knowledge, the value of Nijk is equally : likely to be any 

integer'in the rangedf'valuesavaiIable to it. Thus, for third':'ordercombinations 

IF 

THEN 

p(D I H2)=p(Nijk I H2) 

[JK - NOi(Nfu~C)J 

[ : ( ABC)J IK - NOi Nzjz 

[IJ - NOk(N:U~C)J 

[J ~ NOi(N;~B)J 

mm [K - NOi(Ni!C)J > 1 

[1 - NOj(Nj/)J 

[K - Noj(Nf!C)J 

[I - N ok(N~C)J 

[J - NOk(N~C)J 

=P(Niik I Ni, Nj, Nk, I, J, K, significant(N~IJc s); H2) 

=1/ { 1 + min 

ELSE 

[Nl- Lllz lI#jk 8ignifi'cant(Nl~fjc s)J 

[N! - Lzz zz, :k sighifico.nt(N~fCa)J 

[Nf - LZII zlI"#ii significa:ht(N~~C s)] 

[significant NjB - I:z #k significcint(N4pC s)J 

[significant Ni1c - LllfJ"#j significatit(N;!~C a)J 

[significant NIta - Lz z"#i significant(N:"fC 8)] 

p(D I H2) == 1 

(41) 

} 

(as the value of Niik is then completely determined from the marginal values and the significant 

values previously found) 

12 
whe:re we ha've defined 

NOi(NilJzS) = number of NilJz's found significant that have the ith value of the A attribute 

(42) 

etc, 

Note tha'~ in Equation 41 our constraints are the first-order marginals - Nt, Nt, Nf -

and any higher-order marginals found significant in our analysis or originally given as significant, 

Using Equation 38 in Equation 37, the hypothesis H1 (that there are no more significant 

nth·,order constraints so that the prior probability calculated from the a's is adequate) is more 

likely than H2 if 

[·-lnp(H2') -lnp(H2" I H2') -lnp(D I H2)] [-lnp(H1) -lnp(D I H1)] > 0 (43) 

or in abreviated form as 

m2 - m1 > 0 

whe:re using Equations 39 and 41 in Equation 43, 

IF 

[J K - N oi(N~~C)] 

[IK - NOi(N:;~C)] 

[IJ - NOk(N:U~C)] 

[J - NOi(N~B)] 

mm [K - NOi(Ni!C)] >1 

[I - N Oi(N:;B)] 

[K - NOi(NJ!C)] 

[I - NOk(N~C)] 

[J - NOk(NJ1C)] 

THEN 

m2 = -lnp(H2') + In (no, of cells at this order - M) 

+In {min 

[Nt - I:lJz IIz-:f;ik significant(N~~C s)] 

[Nt - ):::2:Z zz-:f;ik significant(N:;~c s)] 

[Nf - )::::';11 zll::lii significant(N~~C s)] 

[ ' 'f' NAB" "f ' (NABC)] signa Icant ii - LJz z-:f;k signa Icant iiz S 

[signa ' 'f' Icant NAC " "f ' (NABC)] ik - LJIIII::Ii signa Icant illk S 

[ ' 'f' NBC" "f ' (NABC )] signa Icant ik - LJz z::li signa Icant zik S 

13 

(44) 

+ 1} 

(45) 
ELSE 

m2 = -1n,p(H2') + In (no. of cells at this order - M) 

Similarly, using Equation 32 in Equation 43 

tnl = -1n,p(Hl) - [In (N:k) + Niik In Piik + (N - Niik)ln(l- Piik)] (46) 

For the observed value of Niik to be statistically significant requires (from Equation 44) 

that 

m2~ml < 0 (47) 

If the observed Niik is statistically significant, then it forms a new constraint and a new set 

of a values is calculated that will predict it when using these new values in Equation 12. 

14 
CA.LCU:LATING THE INITIAL a VALUES BASED ON TIlE 

FIRST ORDER PROBABILITIES 

The first order probabilities are readily calculated from the data as 

pt=NtlN 

pf=NflN 

pf=Nf IN 

(48) 

If we start with these as our only initial constraints, then from Equations 25 - 28, we obtain 

for the data from our example 

whe:re we have defined 

aoaAaBaC = 1 

ao ataB a

C 

= pt = .38 

ABC _ A - 33 ao a2 a a - P2 -. 

ao ataB 

a

C = pt = .29 

ao af aAaC = pf = .13 

ao af aAaC = pf = .87 

ao af aAaB = pf = .52 

CAB _ C - 48 ao a2 a a - P2 -. 

a

A 

== at + at + at 

a

B 

= af + af 

a

C = af + af 

It can readily be verified that the solution to Equations 49 - 56 is 

ao = 1 

aA = 1 

at = .38 

af = .13 

af = .52 

aB = 1 

at = .33 

af = .87 

af =.48 

aC = 1 

a~ = .29 

(49) 

(50) 

(51) 

(52) 

(53) 

(54) 

(55) 

(56) 

(57) 

(58) 

(59) 

(60) 

which simply means that for this simple: case where therl~ are no constraining higher-order 

prolbabilities, the a values are just the values of the associated first-order probabilities. 

Substituting these values into Equations 29 - 31, we find that the higher-order probabilities 

are just equal to the product of the corresponding first-order probabilities. This indicates that 

the maximum entropy approach has distributed the higher-order probabilities based on the 

attributes being statistically independent - as we would expect, having no other information. 

Thus from Equation 12 

ABC ABC 

Piik = Pi Pi Pk (61) 

15 
and 

pt/ = ptp? 1: pf :::: ptp? (62) 

It. 

Lacking other information, we will assume that the probability of there being one more 

constraint is equal to the probability that there are no more constraints. (If prior information 

is available about the possibility of remaining constraints, then this is easily incorporated.) 

Assuming equality, 

p(H2') = p(H1) (63) 

resulting in these terms cancelling in Equation 43, simplifying the calculations for (m2 - m1). 

Note (using Equations 45 and 46 for m2 and md that 

If p(H2') :::: .6 so that p(H1) = A, this makes a difference of ~AO III (m2 - m1). 

If p(H2') = .8 so that p(H1) = .2, this makes a difference of -1.39 in (m2 - m1). 

For our example, Table 1 gives the values of the predicted second-order probabilities (calculated from conditional independence), and values for the observed Nii, Nilt., Nilt. and their 

predicted mean and standard deviation. Also given are the values of (m2 ~ m1) - indicative 

of the statistical significance of the observed values ~ and the resulting likelihood ratio of the 

two hypotheses. For our example, there are 16 second order cells from which to choose the 

significant cell. (Note that even p(H2') = .8 only changes the sign of (m2 ~ m1) for one of the 

values in our example.) 

CALCULATING a VALUES FOR HIGHER .. ORDER CON .. 

STRAINTS 

If we select Ntf, from Table 1, as the first statistically significant data value to investigate, 

then (by including the associated aff) we obtain from Equations 25 - 28 and 30 the following 

equations for finding the new values of the a's 

c[afaf + b + (at + at)ac ]:::: 1 

c[ataf + bJ = pt = .38 

cafac = pt = .33 

cataC = pt = .29 

aoaf[ataf + b + (at + at)ac ]:::: pf = .13 

aoaf[ataf + b + (at + at)aC

] = pf = .87 

16 

(64) 

(65) 

(66) 

(67) 

(68) 

(69) 
1 

r--" 

_. Eq 62 

p~B == P~P~ _. " " 

PIll = .376 )( .126 = .048 

PI!! = .376 )( .874 = .329 

P2Jl = .331 )( .126 = .042 

P2!! = .331 )( .874 = .289 

P3Jl = .293 )( .126 = .037 

P3!! = .293 )( .874 = .256 

pBC __ pBpC jk -- j k 

Pll = .126 x .519 = .065 

PI:! = .126 )< .481 = .061 

P2I = .874 )< .519 = .454 

P2:~ = .874 )< .481 = .420 

Pll 

Pn 

P2I 

P2:! 

P3I 

P3:~ 

pAC __ pApC ik -- i k 

= .376 )< .519 = .195 

= .376 x .481 = .181 

= .331 x .519 = .172 

= .331 )< .481 = .159 

= .293 x .519 = .152 

= .293 )< .481 = .141 

2 3 

Fig 2 Eq 33 

N~B 

" N~B 

" m 

240 165 

1050 11.28 

93 1.44 

1040 990 

100 1.27 

905 888 

NBC jk NBC 

jk m 

270 223 

163 209 

1510 1556 

1486 1440 

N AC 

ik N AC ik m 

540 668 

750 6201 

642 5901 

491 545 

598 593 

407 483 

4 5 6 7 

Eq 34 l=.3. Eqs 45,46 em2 - m1 

" NAB pJHI/DJ No. of sd's m2 -mi ij sd p(H2ID) 

12.5 6.03 -11.57 <.1 

27.5 -2.83 1.75 5.8 

11.7 -4.34 -4.74 <.1 

26.5 1.86 3.83 46.1 

11.1 -2.43 2.44 11.5 

25.6 1.07 4.97 144.0 

NBC No. of sd's m2 -mi p(HljD) 

jk sd P(H2ID) 

14.4 3.27 .59 1.8 

14.0 -3.29 -.21 .8 

29.2 -1.59 4.77 118.0 

28.9 1.56 4.62 101.0 

N AC No. of sd's m2 -ml plH1IDJ 

ik sd p(H2ID J 

23.2 -5.54 -10.54 <.1 

22.5 5.75 -9.95 <.1 

22.1 2.37 2.87 17.6 

21.4 -2.52 2.63 13.9 

22.1 .22 -.64 .5 

20.4 -3.75 -1.49 .2 

Table 1: CALCULATED PARAMETER VALUES USEFUL FOR DETERMINING STATISTICALLY S][GNIFICANT SECOND ORDER ATTRIBUTE DATA 

17 
where we have defined 

caf a

A = pf = .52 

c[b + ataf + atafl = pf = .48 

N AC 

cb = (Ptf)diJta = ;.; = .219 

c= aoaB 

b = atafatf 

(70) 

(71) 

(72) 

(73) 

(74) 

Observe that if we add Equations 68 and 69 we obtain Equation 64. Thus Equations 68 

and 69 do not contribute to the evaluation of the other a's. This result is to be expected as the 

B attribute is not part of our latest constraint. 

Incorporating Equations 57 - 59, Equations 64 - 74 can be put in the following order for 

iteratively solving for the a values. 

b = .219 from Equation 72 

c 

.38 

c = af"af + b from Equation 65 

A .33 C a2 = -a from Equation 66 

c 

A .29 C a3 = -a from Equation 67 

c 

(.48 _ b) af = aA + aA from Equation 71 

2 3 

C .52 A 

a1 = - a from Equation 70 

c 

aC = af + af from Equation 59 

A lie - b - (at + at)aC 

al = C from Equation 64 

a l 

aA = at + at + at from Equation 57 

B .13 

a - ~~~~--~~--~~= 

1 - ao[af"af + b+ (at + a~)acJ from Equation 68 

B .87 B 

a2 = .13al from Equation 69 

aB = af + af from Equation 58 

(75) 

(76) 

(77) 

(78) 

(79) 

(80) 

(81) 

(82) 

(83) 

(84) 

(85) 

(86) 

c 

ao = Ii from Equation 73 (87) 

a 

Starting with the initial values given by Equation 60 for the a's without the N ~c constraint, 

Equations 75 - 83 are iteratively solved, in the given order, to obtain a new set of a values that 

18 
A A C C C A A B B B 

ItE!r- b c a2 a3 a2 a1 a a1 a a1 a2 a aO 

atio 

0 1 .33 .29 .48 .62 1 .38 1 .13 .87 1 1 

1 .219 .91 .36 .32 .46 .66 1 .36 1.04 

2 .24 .85 .39 .34 .44 .69 1.03 .31 1.04 

3 .26 .86 .37 .33 .43 .68 1.01 .34 1.04 

4 .26 .84 .39 .34 .43 .69 1.02 .31 1.04 

6 .26 .86 .38 .33 .43 .69 1.02 .33 1.04 .14 .91 1.05 .81 

6 .16 .95 1.10 .77 

7 .16 .96 1.10 .77 

Table 2: ITERATIVE CALCULATION OF a VALUES TO SATISFY THE NtF CONSTRAINT 

satisfy the NtF constraint. Then af, af, aB , and ao are calculated from Equations 84 - 87 

using these values. 

Table 2 presents the results of the iterations to find the new a values. Mter convergence, new 

values of (m2 - m1) are calculated using the probabilities determined from these latest a values. 

The resultant new highest significant NUll is then selected and its associated probability added 

as a. new constraint. Then, starting with the last previously calculated a values, a new set of a 

values is itelratively calculated to satisfy this additional constraint. This procedure is repeated 

until all the significant second-order proba.bilities are accounted for. Starting with the resultant 

latlest set of a values, the procedure is then repeated for the next higher-order combination of 

attributes, etc. The overall procedure for finding significant correlations is outlined by the flow 

dia.gram shown in Figure 3. The procedure for calculating the a values is outlined by the flow 

dia.gram shown in Figure 4. 

19 
Data in original sample form of N samples of 

R attributes A, B, C, . •• with corresponding 

no. of values I,J,K, . .. 

1 

Convert samples into attribute R-tuple form 

. * I Sum R-tuples to obtain Niik •.• values 

Sum up the values of (R - r + 1) order N's 

to get marginal (R - r) order N values 

~ ________________ no (R-7 

yes 

~-----i'-+ Calculate a values from first-order marginals 

and any given or found constraints 

For i = 1 to I 

For j = 1 to J 

For.k = 1 to K 

Calculate (m2-m1)'s for nth-order N's using 

current a values 

Add corresponding Niik ... 

to constraints k'.'------

done 

Figure 3: OVERALL PROCEDURE FOR FINDING SIGNIFICANT CORRELATIONS 

20 
Input: N, Ni, Nj , N,,, ... 

t 

Set ai , aj , ak'''' - 11, Pj , Pk' ... ;] 

aD = 1, aA = 1, a B = 1, aC == ll, ... 

(Initially, all other a values := 1, so that these other a's 

can be ignored at this stage.) 

t ----------,~ Current set of a values 

Any significant N not yet incorporated. No---+-Done 

yes 

1 

-~ 

t dd to the current a's a new a a...,ciated with with the I 

most significant N not yet incorporated 

(e"g., af;B for NjB) 

I tarting with this augmented set of current a's, iteratively 

-- compute new values for the a's using equations such as 

Equations 25- 31. 

Figure 4: CALCULATING a VALUES 

21 
REFERENCES 

• Boose, J. H.; Personal Construct Theory and the Transfer of Human Expertise, Proc. 

National Conference on Artificial Intelligence, Austin, TX, Aug 6-10, 1984, pp. 27-33. 

• Cheeseman, P. C.; A Method of Computing Generalized Bayesian Probability Values 

for Expert Systems, Proc. Eighth International Conference on Artificial Intelligence, 

Karlsruhe, W. Germany, Aug 8-12, 1983, pp. 198-202. 

• Cheeseman, P. C.; Learning of Expert Systems Data, Proc. IEEE Workshop on Principles 

of Knowledge Based Systems, Denver, Dec 3-4, 1984, pp. 115-122. 

• DerHer, F. J.; Expert-Ease Makes Its Own Rules, PC, Vol. 4, No.8, April 16, 1985, pp. 

119-124. 

• Jaynes, E. T.; Where Do We Stand On Maximum Entropy, The Maximum Entropy Formalism, Levine, R. D. and Tribus, M., Eds., MIT Press, Cambridge, 1979. pp. 15-118. 

• Kahn, G.; Nowlan, S; and McDermott, J.; MORE: An Intelligent Knowledge Acquisition 

Tool, Proc. Ninth International Joint Conference on Artificial Intelligence, Los Angeles, 

CA, 1985, pp. 581-584. 

• Langley, P.; Bradshaw, G. L; and Simon, H. A.; Rediscovering Chemistry with the BACON System, in Machine Learning, 1983. 

• Langley, P.; and Carbonell, J. G.; Approaches to Machine Learning, Carnegie Mellon 

University, Pittsburg, CMU-CS-84-108, Feb. 16, 1984. 

• Lenat, D. B.; The Role of Heuristics in Learning: Three Case Studies, Tioga Publishing 

Co., Palo Alto, CA, 1982. 

• Michalski, R. S.; Carbonell, J. G.; and Mitchell, T. M.; Eds.: Machine Learning, Tioga 

Publishing Co., .Palo Alto, CA, 1983. 

• Michalski, R. S.; Carbonell, J. G.; and Mitchel.!, T. M.; Eds.: Machine Learning: Volume 

II, Morgan-Kaufman, Los Altos, CA, 1986. 

• Williams, C.; ART, The Advanced Reasoning Tool - Conceptual Overview, Infererence 

Corp., Los Angeles, CA, 1985. 

• Intellicorp: Technical Summary of the Knowledge Engineering Environment (KEE) System, Mt. View, CA, 1985. 

• General Research Corp.: TIMM - Users Manual, Santa Barbara, CA, Nov 1985. 

22 
A B C 

Sample No 1 2 3 1 2 1 2 

1 x x x 

2 x x x 

3 x x x 

4 x x x 

Figure 5: ORIGINAL DATA :E'ORM 

~. ABC ABC ABC ABC ABC ABC ABC ABC ABC ABC 

Sample No 111 121 112 122 211 221 212 222 311 321 

1 x 2 x 

3 x 4 x 

_. Etc. 

Nt/fo Nt2~O NM.v Nf2~v N:1'tv N:2':v N:l~v N:llzv Ntl':v Nt'2'tv -. sum - 130 410 110 640 62 580 31 460 78 520 -. 

Figure 6: SAMPLI~ DATA IN TRIPLES FORM 

APPENDIX A 

CONVERTING ORIGINAJL DATA TO CONTINGENCY 

TAlBLE FORM 

ABC 

312 

Ntl~V 

22 

For our sample problem, the original data in response to the questionaire might be in the 

form of Figure 5 (or can readily be placed in that form). 

Put into a.ttribute triples form, this data might appear in terms of ijk values of the attributes 

as shown in Figure 6. Note that the summations of the triples are the values of the cellB in 

Figure 1. . 

23 

ABC 

322 

N:2~J 

385 
APPENDIXB 

CALCULATING SUM OF PRODUCTS EQUATIONS INVOLVING a's 

From Equation 12, we have the basic equation for the nth order probability as: 

(88) 

based upon which the basic equations for the a's and the p's are given by Equations 21 - 24. 

These equations all involve the summations of products of a's. If we order these summations, 

we obtain equations such as Equation 25 

1 

- = L ai L ajaij L akaikajk 

ao i j k 

(89) 

A convenient way to handle such summation products is to introduce matrices. 

Let us define the operator X indicating comparable term-by-term matrix multiplication. 

Thus for example 

[ 1 3] X [a b] = [a 3b] 2 4 c d 2c 4d (90) 

The summation operator, E, can be considered to be summing terms in such matrices in 

the following manner 

M, = E . M,· = E. [mll m12] = [ mu + m12] :I J :I m21 m22 m21 + m22 

In this notation, Equation 89 can be written as 

.1..-". a''', a 'a" "k aka'ka'k ao - LJ, ' LJ, 1 '1 LJ ':I 

In Equation 93. for 

1= 3, J = 2, and K = 2 

(corresponding to the number of values of the attributes A, B, and C in our example) 

where 

LQijk = 8ij = 

k 

24 

[

811 812] 

821 822 

831 832 

(91) 

(92) 

(93) 

(94) 

(95) 
and 

where 

and 

where 

qi = ai 

Using this notation, Equation 93 can be written as 

=8 

where 

and 

8 = 81 + 82 + 83 

Observe the recursive nature of these equations by noting that in general 

8 n = >: (Qn+1 X 8 n+d 

n+l indez 

25 

(96) 

(97) 

(98) 

(99) 

(100) 

(101) 

(102) 

(103) 

(104) 

(105) 
where n is the order of the matrix and the nth index is the index of the nth attribute. 

For R being the highest order of the attributes (R = 3 in our example), 

SR = [I] , a unity matrix in our notation so that (106) 

(107) 

IT using Equation 88, we desire to calculate a probability, Pic, then Equation 88 takes the 

form of Equation 28 

ao alc L aiailc E ajaijajlc = Pic 

i j 

or in our matrix notation 

ao QlcL(Qilc X LQijlc) = Pic = [pf pi] 

j 

where 

Thus, for our example 

and 

qijlc = ajaijajlc 

qile = aiailc 

Pie = Pie 

(108) 

(109) 

(110) 

(111) 

(112) 

(113) 

(114) 

(115) 

IT, as an example, none of the Wile'S are significant, then We replace the corresponding aile'S 

with 1 's, as from Equation 13 

(116) 

In this case, Equation 114 reduces to 

(117) 

26 
so that 

becomes 

and 

Sk = 2:) Qik X Sik) 

i 

( 

aA(aBaABaBC + aBaABaBO) ) 1 1 11 11 2 12 21 

-+aA (aB aAB aBC + aB aAB aBC) 2 ,1 21 11 2 22 21 

_+aA(aBaABaBO + aBaABaBC) 3 1 31 11 2 32 21 

( 

aA(aBaABaBC 1 1 11 12 + aBaABaBC) 2 12 22 ) 1 

+aA(aBaABaBC + aBaABaBC) 2 2 21 12 2 22 22 

+aA(aBaABaBO + aBaABaBC) 3 2 31 12 2 32 22 

27 

(118) 

(119) 

(120) 
1. Report No. 2. Government Accession No. 3. Recipient's Catalog No, 

NASA TM-88224 

4. Title and Subtitle 5. Report Date 

AUTOMATIC PROBABILISTIC KNOWLEDGE ACQUISITION FROM April 1986 

DATA 6. Performing Organization Code 

7. Author(s) B. Performing Organization Report No. 

William B. Gevarter A-86154 

10. Work Unit No. 

9. Performing Organization Name and Address T-6125 

Ames Research Center 11. Contract or Grant No. Moffett Field, CA 94035 

13. Type of Aeport and Period Covered 

12. Sponsori ng Agency Name and Address Ii Technical Memorandum 

National Aeronautics and Space Administration 14. Sponsoring Agency Code 

vlashington, DC 20546 506-45-2 

15. Su pplementary Notes 

Point of Contact: William B. Gevarter, Ames Research Center, MS 244-7, 

Moffett Field, CA 94035 (415) 694-6525 or FTS 464-6525 

16. Abstract 

This memorandum documents an outline for a computer program for 

extracting significant correlations of attributes from masses of data. 

This information can then be used to develop a knowledge base for a probabilistic "expert system." The method determines the "best" estimate of 

joint probabilities of attributes from data put into contingency table 

form. A major output from the program is a general formula for calculating 

any probability relation associated with the data. These probability relations can be utilized to form IF-THEN rules with associated probability, 

useful for expert systems. 

17. Key Words (Suggested by Author(s)) lB. Distribution Statement 

Artificial intelligence Unlimited 

Knowledge acquisition 

Expert systems 

Machine learning Subject Category - 59 

19. Security Oassif. (of this report) 20. Security Classif. (of this page) 21. No. of Pages 22. Price' 

Unclassified Unclassified 30 A03 

"For sale by the National Technical Information Service, Springfield, Virginia 22161 
End of Document