Digital probabilistic reasoning element

A digital set theoretic system is disclosed that expands the reasoning capability from reasoning with probability measures to reasoning with set theory measures and other Venn diagram type operations using linear transformations and power series transformations, and appropriate hardware and software implementations. This expansion also leads to an increase in precision of the output which can be provided by a hardwired power series expansion. A recursive power series expansion increases this precision while reducing the spatial requirements. The system also enhances flexibility by allowing the constants of the power series expansion to be selectable.

BACKGROUND OF THE INVENTION 
1. Field of the Invention 
The present invention is directed to a probabilistic reasoning expert 
system and, more particularly, to a software and hardware implementation 
of an improved expert system which bases conclusions on the mathematics of 
deductive and inductive reasoning using set theory measures, provides 
increased precision in a high ordered combinatorial capability and 
enhanced flexibility with selectable constants. 
2. Description of the Related Art 
Expert systems need a calculus for decision making based on sound 
mathematical principles. Without a solid foundation for such reasoning, 
there is little hope for using this technology to perform critical 
decision-making. These systems not only need to operate in the realm of 
measures of belief and probability but in any set theory measure useful in 
decision making. Precision in providing expert diagnoses in systems with a 
military or human safety application is also critical to acceptance of 
such systems. Providing enhanced programmability will also make the 
systems easier to tailor to a particular application. 
SUMMARY OF THE INVENTION 
It is an object of the present invention to provide a system capable of 
using any set theory measure in the reasoning process to make diagnoses. 
It is another object of the present invention to use polynomial equations 
to represent set theoretic operations. 
It is also an object to produce a system with improved precision without a 
commensurate increase in the necessary hardware and with comparable speed. 
It is an additional object of the present invention to provide a system 
with selectable combinatorial constants allowing increased flexibility. 
The above objects can be attained by a system that expands reasoning 
capability beyond reasoning with probability measures to reasoning with 
other set theory measures such as in traditional Venn diagrams. This 
expansion also warrants an increase in precision of the measures provided 
by performing a power series expansion on an input. Flexibility is 
enhanced by the present invention by allowing constants to be selectable 
These together with other objects and advantages which will be subsequently 
apparent, reside in the details of construction and operation as more 
fully hereinafter described and claimed, reference being had to the 
accompanying drawings forming a part hereof, wherein like numerals refer 
to like parts throughout.

DESCRIPTION OF THE PREFERRED EMBODIMENTS 
The parent application is directed to an expert system that uses 
probability measures in making the inferences on a diagnosis. Probability 
is one of the measures, available in set theory, which can be used to make 
reasoned judgments. Using probabilistic reasoning maps sets with values 
between zero and one onto another set with values between zero and one. 
Other set theory measures, based on traditional Venn diagram theories, can 
also be used to make reasoned judgments. The present invention is designed 
to use polynomial equations to represent the set theoretic operations. The 
three basic set operations are intersection (SET 1 OR SET 2), see FIG. 1, 
union (SET 1 AND SET 2), see FIG. 2, and complement SET 1, see FIG. 3. All 
other set theoretic operations are combinations of these three basic 
operations. In this invention a first set X is transformed into another 
set SET 1 via various combinations of linear transformations or power 
series expansions. For example, the union of sets X.sub.1 and X.sub.2, 
where X.sub.1 and X.sub.2 are independent, using the method of the present 
invention is set forth in equation 1: 
EQU X.sub.1 AND X.sub.2 =(A.sub.1 X.sub.1 +B.sub.1)(A.sub.2 X.sub.2 
+B.sub.2)(1) 
which is a multiplication of two linear transformations and where A.sub.1 
and A.sub.2 are one and B.sub.1 and B.sub.2 are 0. 
The NOR set theoretic operation is realized, when X.sub.1 and X.sub.2 are 
independent, as set forth in equation 2: 
EQU X.sub.1 NOR X.sub.2 =(-A.sub.1 X.sub.1 +B.sub.1)(-A.sub.2 X.sub.2 
+B.sub.2)(2) 
which is a multiplication of two linear transformations where A.sub.1 and 
A.sub.2 and B.sub.1 and B.sub.2 are each one. 
As discussed in the parent application, particularly with respect to 
equation 7 therein, a linear transformation represents a set theoretic 
operation on a set within the universe of discourse. For example, a set 
operation on set X is illustrated in equation (3): 
EQU SET 1+A.sub.1 X+B.sub.1 (3) 
which is the basic single linear transformation discussed in the parent 
application. As discussed above many set operations can be represented by 
higher order transformations such as equation 4 below: 
EQU SET 1=A.sub.1 X.sub.1.sup.2 +B.sub.1 X.sub.1 +C.sub.1 (4) 
The set gate illustrated in FIG. 4, and described in more detail in the 
parent application, can be used to obtain the intersection of or 
conjunction of SET 1 and SET 2. Using this approach, the present invention 
allows the construction of the set theory operations illustrated in FIG. 5 
by appropriately setting the signs and magnitudes of the constants, as 
indicated in FIG. 5, in the gate of FIG. 4. That is, any set theory 
measure which can be represented using a set operation can be reasoned 
with using the discrete bus wide component, software or dedicated 
processor versions of the probabilistic gate discussed in the parent 
application. 
It is often appropriate to increase the precision of the operation thereby 
representing the resulting set more accurately. This can be accomplished 
by providing a high order function gate such as a high-order AND function, 
of course realizing that the other high ordered functions such as NOR, can 
be accomplished with the appropriate constants. A high order AND function 
can be obtained in terms of the high ordered set operation previously 
discussed with respect to equations 1 and 4. A high order set operation 
can also be represented by a polynomial, namely a finite power series 
expansion: 
EQU X.sub.o =A.sub.o +A.sub.1 X.sup.1 +. . . A.sub.n X.sup.n (5) 
The order of this polynomial is determined by a compromise between the 
amount of idle time available in the gate 14 and the accuracy needed to 
represent the implies function or set and the amount of space available 
for storing the coefficients. The high order function can also be written 
as a product of linear transformations: 
##EQU1## 
Since the probabilistic or set gate 14 of FIG. 4 is fundamentally a 
mechanism for multiplying two linear expressions together, if a linear AND 
gate 18 is supplied with the same signal on both inputs, as illustrated in 
FIG. 6, a quadratic AND gate is constructed. A power series expansion gate 
16 is constructed of three quadratic gates 18-20 connected serially. As 
illustrated in FIG. 7, gates 18 and 20 include storage units 30 and 32, 
such as registers, for storing a pair of constants, and multipliers 34 and 
36 for combining the input signal with a first constant. Adders 38 and 40 
combine the second constant with the multiplied result and multiplier 42 
combines the result of addition to obtain the high ordered output. The 
gate 22 of FIG. 6 is the same as illustrated in FIG. 4. 
The power series expansion can alternately be written in terms of a 
recursive formula: 
EQU Y.sub.M+1 =A.sub.n-M +Y.sub.M X, Y.sub.o =O, O.ltoreq.M.ltoreq.B(7) 
EQU X.sub.o =Y.sub.N+1 =A.sub.o +[A.sub.1 +[A.sub.2 [A.sub.3 +[A.sub.4 
+[A.sub.5 +[. . . ]X]X ]X]X]X]X (8) 
This approach to obtaining the higher ordered AND function can be 
implemented using a gate as illustrated in FIG. 8. This gate includes two 
power series expansion units 52 and 54 and a multiplier 56. Each power 
series expansion unit includes temporary storage 58 for the input signal, 
a i register or memory 60 storing the constants, A.sub.i, of equation 8, a 
multiplier 62, adder 64 and storage 66 for performing the recursive 
addition, multiplication and feedback. 
The two approaches to the implementation of a high ordered probabilistic or 
set AND gate have complementary features The product of linear 
transformations requires a large number of storage registers to hold the 
linear transformation coefficients, in fact, twice as many as the 
recursive approach requires Since there is no unique solution for the Bi 
and Ci in terms of the Ai, the terms must satisfy certain constraints As 
previously discussed, the output is the multiplication of two linear 
transformations as illustrated in equation 9: 
EQU X.sub.o =(ax+b)(cx+d)=acx.sup.2 +(bc+ad)x+bd=Ax.sup.2 +Bx+C(9) 
where A=ac,B=(bc+ad) and C=bd=1. Even though other constraints on A, B and 
C could be selected these constraints are preferred and will provide a 
satisfactory solution. The recursive technique is self contained in one 
processing element, is truly systolic and reduces the amount of idle time 
associated with processing elements awaiting the downloading of data 
because plural constants are stored in the element and the element 
provides temporary feedback storage. 
Each of the methods illustrated in FIGS. 6 and 8 can be implemented as 
discrete bus wide units such as bus wide multipliers and adders as 
discussed in the parent application. The implementations can also be 
performed in a single processing unit performing the operations of FIGS. 
6, 7 or 9 of the parent application for each input and multiplying the 
results. For example, the implementation of equation 10 below by a 
computer will perform the function of the gate of FIG. 6. 
EQU X.sub.out =(.SIGMA.A.sub.ij X.sub.i)(.SIGMA.A.sub.ik X.sub.k)(10) 
The flowchart which is FIG. 6 of the parent application can be modified by 
one of ordinary skill to appropriately obtain the high resolution outputs 
discussed above. The system can also be implemented as a special purpose 
dedicated processor such as illustrated in FIGS. 8 and 23 of the parent 
application. A person of ordinary skill in the art can appropriately 
modify the dedicated processors of the parent application to implement the 
high resolution gates as described above. 
To enhance the programmable capability of the system of the present 
invention or of the probabilistic reasoning system of the parent 
application, a selectable constants capability can be provided for a gate 
as illustrated in FIG. 9. This version of the gate substitutes random 
access memories 70-76 for the single constant storage illustrated in FIG. 
4 and additionally provides address registers 78-84 for determining which 
constants stored in the RAMs are output. Although not shown in FIG. 9 each 
RAM is loadable from a bus outside the gate 68. During operation the 
address registers 78-84 are loaded with the address of the constants to be 
used in the current cycle and the output obtained. During the next cycle 
the address registers 78-84 are loaded with the address of the next set of 
constants to be used. It is of course possible to provide a storage RAM 
for the output of multiplier 11. 
If a virtual binary tree of processors is implemented, as discussed in the 
parent application, the cycles of the gates, and therefore the constants 
selected, would be determined by the number of segments into which the 
diagnostic problem is divided. For example, if the expert system 
diagnostic problem had one thousand diagnoses to make and the virtual 
binary tree contained 100 processors, the problem would be segmented into 
ten 100 input cycles, where one set of ten sets of constants are loaded 
into the processors for each cycle. As can be seen, this approach improves 
the utilization efficiency of the virtual binary tree processors at some 
sacrifice in speed of diagnosis. 
The higher ordered set function described herein not only can be used to 
improve probabilistic reasoning for traditional AI (expert) systems or 
neural network systems, but also provides a mechanism for spatial 
combination of information or signals for image recognition, 2D or 3D 
imaging, radar tracking, magnetic resonance imaging, sonar tracking and 
seismic mapping. 
The many features and advantages of the invention are apparent from the 
detailed specification and, thus, it is intended by the appended claims to 
cover all such features and advantages of the invention which fall within 
the true spirit and scope thereof. Further, since numerous modifications 
and changes will readily occur to those skilled in the art, it is not 
desired to limit the invention to the exact construction and operation 
illustrated and described, and accordingly all suitable modifications and 
equivalents may be resorted to, falling within the scope of the invention.