Fast method for a bidirectional inference

• US 5,179,632 A
• Filed: 12/12/1988
• Issued: 01/12/1993
• Est. Priority Date: 12/17/1987
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Sasaki, Noriko, Sakaguchi, Seiji, Masui, Shoichi
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): Downs, Robert W.
• Application Number:
  US07/283,179
• Time in Patent Office: 1,492 Days
• Field of Search: 364/513, 395/52, 395/64
• US Class Current: 706/47
• CPC Class Codes: G06N 5/042 Backward inferencing
• CPC Class Codes: G06N 5/046 Forward inferencing; Production systems

Abstract

In an inference method using a rule, a rule condition part network and rule consequence part network are generated, an integral network of both the networks is used for inference. With this information method, the inference is performed at high speed by setting a shortcut arc so as to process the inference along the pattern matchable network portion. Further, use of the integral network of the rule condition and consequence parts enables not only forward and backward inferences but also a bidirectional inference with intimate couple between forward and backward inferences.

Claims

1. A method of operating a data processor for performing a fast bidirectional inference in a computer system, the method comprising the steps of:

(a) transforming, by said data processor, rule condition parts of a set of rules, stored in a memory of said computer system, into a first network comprising;

i) condition part nodes representative of condition clauses constituting said rule condition parts, ii) a first arc set representative of relations between ones of said condition clauses, iii) forward-root node as an input node of the first network, and iv) first terminal nodes as output nodes of the first network;

(b) transforming, by said data processor, rule consequence parts of the set of rules into a second network comprising;

i) second nodes representative of statements constituting said consequence parts of the set of rules, ii) a second arc set representative of relations between ones of said statements, iii) a backward-root node as an input node of the second network, and iv) second terminal nodes as output nodes of the second network;

(c) forming, by said data processor, a third network by coupling said first and second networks at said first and second terminal nodes;

(d) forming, by said data processor, a partial bidirectional network by adding to said third network a bidirectional arc on which data flows bidirectionally and a unidirectional arc on which the data flows only unidirectionally;

(e) performing, by said data processor, the forward inference of said bidirectional inference by applying current data stored in a working memory of said computer system, representative of a status of an object, to said third network from the forward-root node of said first network toward the backward-root node of said second network, and determining if ones of the condition clauses represented by each of said condition part nodes are satisfied; and

,

(f) performing, by said data processor, the backward inference of said bidirectional inference by applying said current data further to said second network to infer new current data for rules having said satisfied condition clauses.

2. A method of operating a data processor for performing a fast bidirectional inference in a computer system, the method comprising the steps of:

(a) transforming, by said data processor, rule condition parts of a set of rules, stored in a memory of said computer system, into a fist network comprising;

i) condition part nodes representative of condition clauses constituting said rule condition parts, ii) a first arc set representative of relations between ones of said condition clauses, iii) a forward-root node as an input node of the first network, and iv) first terminal nodes as output nodes of the first network;

(b) transforming, by said data processor, rule consequence parts of the set of rules into a second network comprising;

i) second nodes representative of statements constituting said consequence parts of the set of rules, ii) a second arc set representative of relations between ones of said statements, iii) a backward-root node as an input node of the second network, and iv) second terminal nodes as output nodes of the second network;

(c) forming, by said data processor, a third network by coupling said first and second networks at said first and second terminal nodes;

(d) performing, by said data processor, the forward inference of said bidirectional inference by applying current data stored in a working memory of said computer system, representative of a status of an object, to said third network from the forward-root node of said first network toward the backward-root node of said second network, and determining if ones of the condition clauses represented by each of said condition part nodes are satisfied;

(e) performing, by said data processor, the backward inference of said bidirectional inference by applying said current data further to said second network to obtain new inferred current data for rules having said satisfied condition clauses;

(f) applying, by said data processor, a goal to be instantiated to said third network from the backward-root node of said second network toward the forward-root node of said first network, identifying a rule by which said goal is guided, applying said goal to said first network coupled to said second network, and obtaining a new sub-goal; and

,

(g) setting, by said data processor, an arc coupling said first and second networks and passing over portions of said third network where any common statement/condition clauses are found in said first and second networks, thereby permitting the current data and said goal to be instantiated to flow via said arc.

3. A method of operating a data processor for performing a fast bidirectional inference in a computer system, the method comprising the steps of:

(a) transforming, by said data processor, rule condition parts of a set of rules, stored in a memory of said computer system, into a first network comprising;

i) condition part nodes representative of condition clauses constituting said rule condition parts, ii) a first arc set representative of relations between ones of said condition clauses, iii) a forward-root node as an input node of the fist network, and iv) first terminal nodes as output nodes of the first network;

(b) transforming, by said data processor, rule consequence parts of the set of rules into a second network comprising;

i) second nodes representative of statements constituting said consequence parts of the set of rules, ii) a second arc set representative of relations between ones of said statements, iii) a backward-root node as an input node of the second network, and iv) second terminal nodes as output nodes of the second network;

(c) forming, by said data processor, a third network by coupling said first and second networks at said first and second terminal nodes;

(d) performing, by said data processor, the forward inference of said bidirectional inference by applying current data stored in a working memory of said computer system, representative of a status of an object, to said third network from the forward-root node of said first network toward the backward-root node of said second network, and determining if ones of the condition clauses represented by each of said condition part nodes are satisfied;

(e) performing, by said data processor, the backward inference of said bidirectional inference by applying said current data further to said second network to obtain new inferred current data for rules having said satisfied condition clauses;

(f) applying, by said data processor, a goal to be instantiated to said third network from the backward-root node of said second network toward the forward-root node of said first network, identifying a rule by which said goal is guided, applying said goal to said first network coupled to said second network, and obtaining a new sub-goal; and

,

(g) setting, by said data processor, an arc coupling said firs and second networks and passing over portions of said third network where common statements/condition clauses are represented, thereby permitting the current data and said goal to be instantiated to flow via said arc.

4. A method of operating a data processor for performing a fast bidirectional inference in a computer system, the method comprising the steps of:

(a) transforming, by said data processor, rule condition parts of a set of rules, stored in a memory of said computer system, into a first network comprising;

i) condition part nodes representative of condition clauses constituting said rule condition parts, ii) a first arc set representative of relations between ones of said condition clauses, iii) a forward-root node as an input node of the first network, and iv) first terminal odes as output nodes of the first network;

(b) transforming, by said data processor, rule consequence parts of the set of rules into a second network comprising;

i) second nodes representative of statements constituting said consequence parts of the set of rules, ii) a second arc set representative of relations between ones of said statements, iii) a backward-root node as an input node of the second network, and iv) second terminal nodes as output nodes of the second network;

(c) forming, by said data processor, a third network by coupling said first and second networks at said first and second terminal nodes;

(d) performing, by said data processor, the forward inference of said bidirectional inference by applying current data stored in a working memory of said computer system, representative of a status of an object, to said third network from the forward-root node of said first network toward the backward-root node of said second network, and determining if ones of the condition clauses represented by each of said condition part nodes are satisfied;

(e) performing, by said data processor, the backward inference of said bidirectional inference by applying said current data further to said second network to infer new current data for rules having said satisfied condition clauses;

(f) applying, by said data processor, a goal to be instantiated to said third network from the backward-root node of said second network toward the forward-root node of said first network, identifying a rule by which said goal is guided, applying said goal to said first network coupled to said second network, and obtaining a new sub-goal;

(g) storing the current data and said goal to be instantiated at an arc in said third network, realizing a forward inference through the flow of said data representative of the status of said object, and realizing a backward inference by controlling the flow of said goal, the current data and said goal to be instantiated being supplied at the same time to said third network to realize both forward and backward inferences in cooperative association.

5. A method of operating a data processor for performing a fast bidirectional inference in a computer system, the method comprising the steps of:

(a) transforming, by said data processor, rule condition parts of a set of rules, stored in a memory of said computer system, into a first network comprising;

i) computer part nodes representative of condition clauses constituting said rule condition parts, ii) a first arc set representative of relations between ones of said condition clauses, iii) a forward-root node as an input node of the first network, and iv) first terminal nodes as output nodes of the first network;

(b) transforming, by said data processor, rule consequence parts of the set of rules into a second network comprising;

i) second nodes representative of statements constituting said consequence parts of the set of rules, ii) a second arc set representative of relations between ones of said statements, iii) a backward-root node as an input node of the second network, and iv) second terminal nodes as output nodes of the second network;

(c) forming, by said data processor, a third network by coupling said first and second networks at said first and second terminal nodes;

(d) performing, by said data processor, the forward inference of said bidirectional inference by applying current data stored in a working memory of said computer system, representative of a status of an object, to said third network from the forward-root node of said first network toward the backward-root node of said second network, an determining if ones of the condition clauses represented by each of said condition part nodes are satisfied;

(e) performing, by said data processor, the backward inference of said bidirectional inference by applying said current data further to said second network to infer new current data for rules having said satisfied condition clauses;

(f) applying, by said data processor, a goal to be instantiated to said third network from the backward-root node of said second network toward the forward-root node of said first network, identifying a rule by which said goal is guided, applying said goal to said first network coupled to said second network, and obtaining a new sub-goal;

(g) storing the current data and said goal at an arc in said third network to control a flow of said data and realizing a forward inference through first a backward inference by the controlled flow of said goal, the current data and said goal to be instantiated being supplied at the same time to said third network to realize both forward and backward inferences in cooperative association.

6. A method of operating a data processor for performing a fast bidirectional inference in a computer system, the method comprising the steps of:

(a) transforming, by said data processor, rule condition parts of a set of rules, stored in a memory of said computer system, into a first network comprising;

i) condition part nodes representative of condition clauses constituting said rule condition parts, ii) a first arc set representative of relations between ones of said condition clauses, iii) a forward-root node as an input node of the first network, and iv) first terminal nodes as output nodes of the first network;

(b) transforming, by said data processor, rule consequence parts of the set of rules into a second network comprising;

i) second nodes representative of statements constituting said consequence parts of the set of rules, ii) a second arc set representative of relations between ones of said statements, iii) a backward-root node as an input node of the second network, and iv) second terminal nodes as output nodes of the second network;

(c) forming, by said data processor, a third network by expressing relations among patterns described by said rule condition and consequence parts by a graph using as its structural element two types of patterns including condition and consequence part patterns and generating said third network using said graph coupling said first and second networks at said first and second terminal nodes;

(d) performing, by said data processor, the forward inference of said bidirectional inference by applying current data stored in a working memory of said computer system, representative of a status of an object, to said third network from the forward-root node of said first network toward the backward-root node of said second network, and determining if ones of the condition clauses represented by each of said condition part nodes are satisfied;

(e) performing, by said data processor, the backward inference of said bidirectional inference by applying said current data further to said second network to obtain new inferred current data for rules having said satisfied condition clauses.

7. The method according to claim 6, wherein the expressing step comprises implementing a hierarchical graph which uses as its structural element said two types of patterns including condition and consequence part patterns, and which uses an arc representative of an inclusion relation between said two pattern types as first data which satisfies a first of said two patterns is included in second data which satisfies the other of said two patterns.

8. The method according to claim 7, wherein said step of transforming into a first network comprises:

deriving only patterns constituting said rule condition parts out of a hierarchical graph which uses said two types of patterns including condition and consequence part patterns and an arc representative of the inclusion;

expressing a difference of conditions between patterns coupled by said arc as a node for said arc; and

, setting a terminal node representative of a satisfied pattern.

9. The method according to claim 7, wherein said step of transforming into a second network comprises:

deriving only patterns constituting said rule consequence parts;

expressing a difference of conditions between patterns coupled by said arc as a node for said arc; and

, setting a terminal node representative of a satisfied pattern.

10. The method according to claim 6, wherein the expressing step comprises using a hierarchical graph which uses as its structural element said two types of patterns including condition and consequence part patterns, and which uses a first arc representative of an inclusion relation between said two pattern types as first data which satisfies a first of said two patterns is included in second data which satisfies the other of said two patterns, and a matchable arc between patterns having marching portions in accordance with said inclusion relation.

11. The method according to claim 10, further comprising setting a shortcut arc i) where arcs from the upper pattern portions to patterns coupled by a matchable arc are present within said first network, and ii) where an arc to a terminal pattern representative of a satisfied pattern and an arc to node for determining if a pattern lower than said satisfied pattern is satisfied are present respectively within said second network.

12. The method according to claim 11, further comprising inhibiting arcs from the forward-root node of said first network to a first occurrence shortcut arc to thereby make said current data flow toward said forward-root node.

13. The method according to claim 11, further comprising inhibiting arcs from the backward-root node of said second network to a first occurrence shortcut arc to thereby make said current data flow toward said backward-root node.

14. The method according to claim 11, further comprising joining together a plurality of arcs each as a junction and selectively inhibiting all but for one arc to thereby make said current data flow toward a one of said each junction.

15. The method according to claim 6, further comprising:

deriving, out of said graph, a pattern constituting a one of said rule condition parts and an arc representative of an inclusion relation between said two pattern types as first data which satisfies a first of said two patterns included in second data which satisfies the other of said two patterns;

expressing a difference of conditions between patterns of the pattern set coupled by said arc as a node for said arc; and

, setting a terminal node representative of a satisfied pattern to thereby generate said first network.

16. The method according to claim 6, further comprising:

deriving, out of said graph, a pattern constituting a one of said rule consequence parts and an arc representative of an inclusion relation between said two pattern types as first data which satisfies a first of said two patterns is included in second data which satisfies the other of said two patterns;

expressing a difference of conditions between patterns of the pattern set coupled by said arc as a node for said arc; and

, setting a terminal node representative of a satisfied pattern to thereby generate said second network.

17. A method of operating a data processor for generating a rule relation graph for a bidirectional inference in a computer system, the method comprising the steps of:

(a) generating, by said data processor, a graph representative of a hierarchic relation between patterns, based on a presence of an inclusion relation between the patterns described by a rule condition part and a rule consequence part the inclusion relation being present when first data which satisfies a first pattern is included in second data which satisfies a second pattern;

(b) detecting, by said data processor, ones of said patterns having matching upper pattern portions in accordance with said inclusion relation in said graph, and setting an arc between said detected ones of said patterns;

(c) selecting, by said data processor, a first pattern pair from said condition part and an arc representative of an inclusion relation between said pattern pair, and using a difference between the first pattern pair coupled by said arc as a node for said arc, to thereby generate a condition part network;

(d) selecting, by said data processor, a second pattern pair from said consequence part and an arc representative of an inclusion relation between said pattern pair, and using a difference between the second pattern pair coupled by said arc as a node for said arc, to thereby generate a consequence part network;

(e) detecting, by said data processor, whether a pattern having a first arc to a terminal node of said condition and consequence part networks and a second arc to a node of a pattern lower than said detected pattern is present within both said condition and consequence part networks;

(f) setting, by said data processor, an arc coupling said first and second arc if said pattern is detected;

(g) detecting, by said data processor, that third arcs to patterns coupled by a matchable arc are present within both said condition and consequence part networks, and setting an arc coupling said third arcs; and

,

(h) performing, by said data processor, the bidirectional inference by applying current data to both said condition and consequence part networks to infer new current data for rules having said satisfied condition clauses.