Abstract:
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.

Description:
CROSS REFERENCES TO RELATED APPLICATION 
     This is a Continuation-In-Part of U.S. Ser. No. 07/364,475 filed on June 12, 1989 and entitled Probabilistic Reasoning System. This application is related to U.S. application entitled Neural Networks And Adaptive Reasoning Systems by Murphy and Jeeves having Westinghouse docket number 55,546 and to U.S. Application entitled Neural Network Optimization Method by Murphy and Jeeves having Westinghouse docket number 55,704. All of these applications are incorporated by reference herein. 
    
    
     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. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a Venn diagram representing the intersection set theory function; 
     FIG. 2 is a Venn diagram illustrating the union set theory function; 
     FIG. 3 represents the Venn diagram of the complement function; 
     FIG. 4 illustrates the set gate; 
     FIG. 5 depicts some of the set functions executable by the gate of FIG. 3; 
     FIG. 6 illustrates a high resolution quadratic gate; 
     FIG. 7 illustrates the details of gates 18 and 20; 
     FIG. 8 illustrates a recursive high resolution gate; and 
     FIG. 9 illustrates a selectable constant gate 68. 
    
    
     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 1  and X 2 , where X 1  and X 2  are independent, using the method of the present invention is set forth in equation 1: 
     
         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 1  and A 2  are one and B 1  and B 2  are 0. 
     The NOR set theoretic operation is realized, when X 1  and X 2  are independent, as set forth in equation 2: 
     
         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 1  and A 2  and B 1  and B 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): 
     
         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: 
     
         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: 
     
         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: 
     
         Y.sub.M+1 =A.sub.n-M +Y.sub.M X, Y.sub.o =O, O≦M≦B(7) 
    
     
         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 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: 
     
         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. 
     
         X.sub.out =(ΣA.sub.ij X.sub.i)(Σ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.