Probabilistic inference gate

• US 5,077,677 A
• Filed: 06/12/1989
• Issued: 12/31/1991
• Est. Priority Date: 06/12/1989
• Status: Expired due to Term

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Westinghouse Electric Company LLC (Brookfield Asset Management Incorporated)
• Inventors: Anderson, Arthur A., Murphy, John H., Jeeves, Terry A.
• Primary Examiner(s): MacDonald, Allen R.
• Application Number:
  US07/364,475
• Time in Patent Office: 932 Days
• Field of Search: 364/513, 364/736, 364/754, 364/768, 364/808, 364/841
• US Class Current: 706/62
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06N 5/048 Fuzzy inferencing
• CPC Class Codes: Y10S 706/90 Fuzzy logic

Abstract

The present system performs linear transformations on input probabilities and produces outputs which indicate the likelihood of one or more events. The transformation performed is a product of linear transforms such as P_o =[A_j P_j +B_j ]·[A_k P_k +B_k ] where P_j and P_k are input probabilities, P_o is an output event probability and A_j, B_j, A_k and B_k are transformation constants. The system includes a basic processing unit or computational unit which performs a probabilistic gate operation to convert two input probability signals into one output probability signal where the output probability is equal to the product of linear transformations of the input probabilities. By appropriate selection of transformation constants logical and probabilistic gates performing the functions of AND, NAND, OR, NOR, XOR, NOT, IMPLIES and NOT IMPLIES can be created. The basic unit can include three multipliers and two adders if a discrete component hardwired version is needed for speed or a single multiplier/adder, associated storage and multiplex circuits can be used to accomplish the functions of the hardwired version for economy. This basic unit can also be provided as a software implementation, can be implemented as a hardwired decision tree element implementation or implemented as a universal probabilistic processor and provided with a bus communication structure to create expert systems or neural networks suitable for specific tasks. The basic units can be combined to produce a virtual basic building block which has more virtual processors than physical processors to improve processor utilization. The building blocks can be combined into an array to produce either a high speed expert system or a high speed neural network.

Claims

1. A processing element producing an inference, comprising:

first and second input lines receiving first and second input signals;

a digital universal inference gate connected to said first and second input lines, receiving the first and second input signals, for performing a digital linear transformation and combination of the first and second input signals and producing an output probabilistic inference.

2. An element as recited in claim 1, wherein said gate digitally executes P_o =A_j P_j +B_j ]·

[A_k P_k +B_k ] where P_o is an output probability of P_j and P_k are input probability signals and A_j, B_j, A_k and B_k are transformation constants.

3. An element as recited in claim 1, wherein said first and second input signals are digital probability input signals and said output inference is a probability.

4. An element as recited in claim 1, wherein said gate digitally combines linear transformations of the input signals as the output inference.

5. An element as recited in claim 1, wherein the output is fed back via a digital bus as one of the input signals.

6. An element as recited in claim 1, wherein said gate digitally executes P_o =[A_j P_j +B_j ]·

[A_k P_k +B_k ]+C_m where P_o is the output probability, P_j and P_k are input probabilities and A_j, B_j, A_k, B_k and C_m are transformation constants.

7. An element as recited in claim 1, wherein said gate comprises:

first digital linear transformation means for performing a first digital linear transformation on the first input signal using first and second constants;

second digital linear transformation means for performing a second digital linear transformation on the second input signal using third and fourth constants; and

combination means for digitally combining the first and second digital linear transformations producing an output probability as the output inference.

8. An element as recited in claim 7,

wherein said first digital linear transformation means comprises:

a first multiplier; and

a first adder connected to said first multiplier;

wherein said second digital linear transformation means comprises;

a second multiplier; and

a second adder connected to said second multiplier; and

wherein said combination means comprises a third multiplier connected to said first and second adders.

9. An element as recited in claim 7,

wherein said first digital linear transformation means comprises:

a first digital multiplier circuit digitally multiplying the first input signal times the first constant producing a first output; and

a first digital adder circuit, connected to said first multiplier circuit, digitally adding the second constant to the first output producing a second output;

wherein said second digital linear transformation means comprises;

a second digital multiplier circuit digitally multiplying the second input signal times the third constant producing a third output; and

a second digital adder circuit, connected to said second multiplier, digitally adding the fourth constant to the third output producing a fourth output; and

wherein said combination means comprises a third digital multiplier circuit, connected to said first and second digital adder circuits, digitally multiplying the second output times the fourth output producing the output probability.

10. An element as recited in claim 1, wherein said gate comprises:

first and second universal digital implication elements each performing a digital linear transformation and producing first and second implication outputs from said first and second input signals, respectively; and

first digital combining means for digitally combining the first and second implication outputs to produce a first output inference.

11. An element as recited in claim 10, wherein said universal gate further receives third and fourth input signals and said gate further comprises:

third and fourth universal digital implication elements producing third and fourth implication outputs from said third and fourth input signals, respectively;

second digital combining means for digitally combining the third and fourth implication outputs to produce a second output inference; and

third digital combining means for digitally combining the first and second output inferences to produce a third output inference as the output inference.

12. An element as recited in claim 11, wherein said first through fourth universal digital implication elements each perform digital linear transformations on the first through fourth input signals, said first and second combining means digitally multiplies the first and second implications and second and third implications respectively and said third combining means digitally multiplies the first and second inferences.

13. An element as recited in claim 1, wherein said digital universal inference gate comprises:

a latch register storing the first and second input signals; and

a digital computation unit, connected to said latch register, and performing digital linear transformations on the first and second input signals using constants and digitally combining the linear transformations producing a first output probability as the output inference.

14. A processing element producing an inference, comprising:

a universal inference gate receiving first and second input signals and producing an output inference, said universal inference gate comprising;

a latch storing the first and second input signals; and

a computation unit, connected to said latch, and performing linear transformations on the first and second input signals using constants and combining the linear transformations producing a first output probability, said computation unit comprising a multiplier/adder and said element further comprises;

storage means for storing the constants;

a timing control circuit connected to said multiplier/adder and said storage means, and producing selection and timing signals; and

a first multiplexer, connected to said storage means, said timing control circuit, said latch and said multiplier/adder for selecting one of the input signals and constants.

15. An element as recited in claim 14, further comprising:

a second multiplexer, connected to receive the first and second input signals and third and fourth input signals, and connected to said latch.

16. A processing element producing an implication, comprising:

an input line receiving an input signal; and

a digital universal implication gate connected to said input line, receiving the input signal, for performing a digital linear transformation on the input signal and producing a probabilistic implication output.

17. An element as recited in claim 16, wherein said gate digitally executes

18. An element as recited in claim 16, wherein said gate digitally executes ##EQU9## to produce the implication output P_o where A_j and B_j are transformation constants and P_j is input signals.

19. An element as recited in claim 16, wherein the implication output is fed back as an intermediate implication.

20. An element as recited in claim 16, wherein said gate digitally executes:

space="preserve" listing-type="equation">P.sub.o =[A.sub.i-1 P.sub.i-1 +B.sub.31 1 ]·

[A.sub.i P.sub.i +B.sub.i ]

to produce a probabilistic inference P_o where A_i, B_i, A_i-1 and B_i-1 are transformation constants and P_i is a current input and P_i-1 is a previous input.

21. A method of performing an inference operation, comprising the steps of:

(a) performing a first digital linear transformation on a first input signal using a digital computer;

(b) performing a second digital linear transformation on a second input signal using a digital computer; and

(c) combining the first and second linear transformations using a digital computer to produce a probabilistic inference.

22. A method as recited in claim 21, wherein step (c) comprises digitally multiplying the first linear transformation by the second linear transformation.

23. A method as recited in claim 21, wherein said first and second input signals and said inference are probabilities.

24. A method of performing an implication operation, comprising:

(a) performing a digital linear transformation on an input signal using a digital computer to produce a probabilistic implication.

25. A method as recited in claim 24, wherein step (a) digitally performs P_o =A_j P_j +B_j to produce a probability implication P_o where A_j and B_j are transformation constants and P_j is a probability input signal.

26. A weighted decision gate receiving first through fourth input signals, said gate comprising:

a first digital multiplier circuit digitally multiplying the first and second input signals;

a second digital multiplier circuit digitally multiplying the third and fourth input signals;

a first digital universal gate receiving the output of the first digital multiplier circuit and the second input signal, and for digitally producing a probabilistic inference of a parameter;

a second universal gate receiving the output of the second digital multiplier circuit and the fourth input signal, performing a linear transformation and producing a digital parameter probability; and

a digital divider circuit digitally dividing the probabilistic inference by the probability to produce the parameter.

27. A system, comprising:

a first digital probabilistic gate receiving first and second input signals, for performing a digital linear transformation on and combination of said first and second input signals and producing a first probabilistic inference;

a second digital probabilistic gate receiving third and fourth input signals, for performing a digital linear transformation and combination of said third and fourth input signals and producing a second probabilistic inference; and

a third probabilistic gate connected to said first and second probabilistic gates, for performing a digital linear transformation and combination of the first and second inferences and producing a third probabilistic inference.

28. A system as recited in claim 27, wherein said first, second and third inferences and said first and second input signals are digital probabilities.