JPH02210541A - Discrimination network processing method - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] [Field of Industrial Application] The present invention relates to a system using a network similar to a discrimination network for determining whether a condition is met, and which is particularly suitable for a knowledge-based system. The present invention relates to a method of adding data to be added using data of another network to which data has already been added.

[Conventional technology]

One way to quickly determine the truth or falsity of a condition is to represent the rule condition part as a network similar to a discrimination network.
A method is known in which this is used to determine whether a condition is satisfied.

Regarding this, see [Multi-pattern/multi-object high-speed matching algorithm “Rate” (Artificial Intelligence, Vol. 19,
No. 1, 1982) J (“Rate”: A
Fast Algorithm for the Man
y Pattern/Many 0bject Pat
tern MatchProblem (ARTIFI
CIAL IN LIGENCE, voQ, 19. Nc
il.

(1982))) can be referred to.

The above method is called working memory element.
Conditions related to structure data consisting of a working memory element name and a pair of one or more attribute names and attribute values are converted into a network, and the network is used to determine the truth or falsehood of the condition.

For example, rules 501 to 5 as shown in FIG.
The condition part of 03 is converted into a discrimination network as shown in FIG. Next, the process of determining whether a working memory element as shown in FIG. 4 satisfies the condition part of the rule starts from the top node of the discrimination network, in this case node 601. If a certain working memory element satisfies the condition attached to node 601, it moves to a lower node on the discrimination network, such as node 602. In this way, if the lowest node such as node 603 is reached, the condition part of the rule attached to that node is satisfied. Further, the working memory element that satisfies the conditional part is stored in the bottom node.

The above can be explained in detail as follows.

The conditions regarding the working memory element are composed of a plurality of condition terms regarding the attributes of the working memory element, and each condition term corresponds to a node of the network. Furthermore, there is a terminal node at the end of the network, which has a function of holding working memory elements that satisfy all conditions from the vertex node to the terminal node.

To determine if a condition is met, the working memory element is passed through the network, checked to see if it satisfies the condition part stored in each node, and if it is, passed to the next node, and if not Repeat the process of canceling the process. When a certain working memory element reaches the terminal node, the working memory element is added to the terminal node and retained, and then it is determined that the condition part (rule name) written in the terminal node is satisfied, and it is a fast method. Excellent in sex.

A method is known in which a new rule condition part is added to the rule condition parts represented by such a discrimination network, and the rules are merged into one network. Regarding this, please refer to "Sequential Structuring of Knowledge Base - Sequential Construction Method of Rate Network" (IEICE Transactions D Vo
Q, J 71-DN [16pp, 1100-1108.
1988) can be referred to.

[Problem to be solved by the invention]

When creating a rule that behaves as expected, examine the behavior of the rule while performing inference, and if any rules are missing, stop the inference, add a new rule, and then perform the inference again. It is possible that At this time, by using conventional techniques, a new rule condition part can be added to the network representing the rule condition part. This makes it possible to handle cases in which inference is restarted from the beginning, that is, cases in which working memory elements are sent to the network again.

Additionally, if you add a rule during inference and want to continue inference from the point where it was interrupted after adding the rule, you need to add a working memory element that satisfies the conditions up to that point to the terminal node corresponding to the added rule. be. However, there is currently no way to efficiently perform this process.

An object of the present invention is to provide a method of adding data to be added to a discrimination network by using data of a network to which data has already been added.

[Means to solve the problem]

The above object of the present invention is achieved by obtaining a working memory element to be added to a node of a network for an added rule by using a working memory element already attached to a node in another network.

[Effect]

In the present invention, as described above, working memory elements to be added to a network node for an added rule are obtained by using working memory elements already added to nodes in other networks, so all working memory elements There is no need to investigate.

As a result, the number of working memory elements to be subjected to condition determination is reduced, and data addition processing time can be shortened.

〔Example〕

Hereinafter, one embodiment of the present invention will be described in detail based on the drawings.

FIG. 2 is a block configuration diagram showing an inference system to which the present invention is applied. The user views the output from the CPU 203 through the monitor 201 and inputs information from the keyboard 202 to read the output from the disk 204 through the CPU 203.
You can modify the files inside it and control inference execution.

FIG. 3 is a functional block diagram of the CPU 203 and the disk 204. Input/output section 301. Debugger 302. Editor 303. Translator 304, network modification unit 305. The inference unit 306 is a functional block of the CPU 203. Rule file 307. Network file 308. Working memory element file 30
9 is a functional block of the disk 204.

An input/output unit 301 controls the monitor 201 and keyboard 202. Furthermore, the user of the inference system activates the following parts through this input/output unit 301. Editor 3
03, the rule file 307 and the working memory element fighter 304 convert the rules written in the rule file 307 into a network in a format that is easy for the inference unit 306 to handle, and create the network file 3.
Store in 08. The network modification unit 305 modifies the network representing the rule.

The inference unit 306 uses the network in the network file 308 and the working memory element file 3.
After reading the working memory elements in 09 into memory, inferences are made based on them. Debugger 3
02 is an editor 303 degree translator 304 . Network modification unit 305 Controls inference by activating inference unit 306.

It displays the state during inference, adds, modifies, and deletes rules and working memory elements during inference, and restores deleted items.

FIG. 4 shows an example of working memory elements in 309. This working memory element shows store sales data. The working memory element 401 represents a working memory element in which the working memory element is A and the attribute value of the attribute name $number is 1. In other words, it shows that one item of product A was sold.

The same applies to working memory elements 402 to 404.

FIG. 5 shows an example of rules in the file 307.

These rules examine sales and dictate appropriate packaging boxes for sold items. Rule 501 is
If there exists a working memory element whose attribute value of attribute name $product name is B and attribute value of attribute name $number is 2,
Monitor 201 so that box 1 is used to package the product.
This is what is output to.

For example, if the working memory element 402 exists, the condition of the rule 501 is satisfied, and therefore, a message is output to the monitor 201 to package the product with sales 2 using box 1. Here, the part after if and before then is called the conditional part, and the part after then is called the execution part. The same applies to rules 502 and 503. For example, if working memory element 404 exists, rule 502. The condition part of the rule 503 is satisfied, and the output is output to the monitor 201 to use the boxes 22 and 3, respectively.

In FIG. 6, the condition parts of rules 501 and 502 in 307 are expressed in network 1-work, and all the working memory of FIG. 4 stored in 309 is added to what was stored in 308. A diagram showing the flow of elements. The work of streaming working memory elements is done from node 601 at the top of the network. Node 601. A condition is attached to the nodes 602 and 604, and only working memory elements that satisfy this condition are passed to the nodes below. Node 603. The working memory element that has flowed to node 605 is recorded as satisfying all the conditions in the nodes above it. What is recorded in parentheses at node 603 and node 605 is:
This is a working memory element that satisfies the conditions and is indicated by the working memory element name.

FIG. 7 shows a diagram in which the condition part of the rule 503 added by the user through the debugger 302 is expressed by a network, and the working memory element has not yet been sent.

FIG. 8 is a diagram in which the network shown in FIG. 7 is added to the network shown in FIG. 6, and a working memory element is added to node 803 using the working memory element added to node 605 according to the present invention. shows. The working memory elements added here are located above node 803, that is, node 601. This is a working memory element that satisfies the conditions attached to nodes 801 and 802.

First, the outline of the process will be explained using the network shown in FIG.

The newly added node 803 to the network has nodes above node 803, that is, node 601. Node 801.
Consider adding a working memory element that satisfies the conditions attached to node 802. The conditions to be satisfied by the working memory element added to the newly added node 803 are $product name=B of the node 601, $number of the node 801 minus 7, and $number of the node 802>4.

Compared to the conditions that the working memory element attached to node 605 satisfies, $product name=B is the same, $number>4 is tighter than $number>2, and $number>7 has increased. It is a condition.

Therefore, among the working memory elements added to the node 605, those that satisfy the tightened condition $number>4 and the increased condition $number>7 are added to the node 805.
Add to 3.

Next, details of the data addition method will be explained using a flowchart.

FIG. 1 shows the main flow of the data addition method. First, select a copy source node (step 1), and if there is a copy source (step 2), select one of the working memory elements in the copy source that satisfies the stricter conditions and increased conditions in the copy destination. If not, select working memory elements that satisfy the copy destination among all working memory elements and add them to the copy destination (same 5).

The process flow of selecting the copy source (step 1) is explained in the ninth step.
This will be explained using figures.

The terminal node of the copy source is retrieved in order (step 6). If it can be retrieved, it is assumed that there is no copy source (step 10). If it cannot be retrieved, the conditions that are satisfied by the current data in the retrieved terminal node are sequentially retrieved (step 6). 7), if it cannot be extracted, the currently extracted terminal node is used as the copy source (see 11).
), if it can be retrieved, then sequentially retrieve the conditions that the current data to be added to the end node of the copy destination should satisfy (see 8); if it cannot be retrieved, return to step 6; if it can be retrieved, determine the tightness of the two conditions. (Same as 9) If the two conditions are the same or the copy destination is better, the process returns to step 7. If the two conditions are different or if the copying source applies, the process returns to step 8.

Next, an outline of the process of determining the tightness of the two conditions (step 9) will be described using an example.

The severity of two conditions such as ">2" and ">4" is determined. For all real numbers, which are definition examples for determining conditions,
When 〉4'' holds true, if ``〉2'' also holds true, then ``〉4'' holds true.
' can be said to be a stricter condition. However, it is impossible to investigate all real numbers. Therefore, first, we focus on the constants 2 and 4 included in the condition and divide the real number into the following intervals.

Only section 2:2 is smaller than section 1:2, section 3: is larger than 2 and smaller than 4, only section 4:4 is larger than section 5:4.Next, it is checked whether the real numbers in each section satisfy the conditions. Section 3, section 49 and section 5 satisfy ">2", and only section 5 satisfies ">4". "
The section that satisfies “〉4” also satisfies “〉2”,
It is determined that ">4" is a stricter condition.

Next, details of the process of determining the tightness of the two conditions (step 9) will be explained using the flowchart of FIG.

Perform interval division (step 12), check whether the numbers in that interval satisfy the conditions for all intervals (step 13), and if the judgment result of the condition is the same in all intervals (step 14), 2 The two conditions are the same (same 17
), otherwise, if the second condition is also satisfied when the first condition is satisfied (ibid. 15), then the first condition is stricter than the second condition (ibid. 18), then If not,
Assume that the two conditions are different (ibid. 16).

Next, the processing flow of section division (step 12) is
This will be explained using Figure 1.

Compare the fixed values under the two conditions (step 19), and if they are different, set the smaller fixed value as A and the larger one as B (step 19).
), if they are the same, set the fixed value as A and any value larger than A as B (same 21), section 1 is smaller than A, section 2 is only A, section 3 is larger than A and smaller than B, section 4 Assume that only B is larger than B, and section 5 is larger than B (same 22).

Next, the processing flow of another method of section division (step 12) will be explained with reference to FIG.

Compare the fixed values in the two conditions (step 23), if they are different, set the smaller fixed value as A, the larger one as C, and any value between A and C as O (step 24); if the same, set the fixed value. B,
Any value smaller than B is A, any value greater than B is C (same 25), section 1 is smaller than A, section 2 is only A, section 3 is larger than A and smaller than B, section 4 is For B only, section 5 is larger than B and smaller than C, section 6 is only C, and section 7 is larger than C (Same 26).

Next, the processing flow of yet another method of section division (step 12) will be explained with reference to FIG.

Set the planting value under the first condition as B (step 27), compare the fixed value under the second condition with B (step 23), and if B is larger, set the fixed value under the second condition as A. , any value greater than B shall be C (same 29); if they are the same, any value smaller than B shall be A, and any value greater than B shall be C (
30), if B is smaller, the fixed value in the second condition is C, B is smaller than A, section 2 is only A, and section 3 is
is larger than A and smaller than B, section 4 is only B, section 5 is
is larger than B and smaller than C, section 6 is C only, section 7
is larger than C (ibid. 32).

As described above, in this embodiment, the working memory element to be added to the network for the added rule is added by using the data of the network to which the working memory element has already been added. As a result, in the past, it was necessary to make conditional judgments on the four working memory elements shown in FIG. 4, but in this embodiment, two working memory elements as shown in FIG. It is only necessary to perform conditional judgment, and data addition processing time can be shortened.

Furthermore, using the method shown in this embodiment, the user of the inference system can use the debugger 302 to stop inference once in the middle of inference, add rules, add data, and restart inference again. This becomes possible.

Furthermore, the method shown in this embodiment allows the addition of a new rule during inference by specifying it in the rule execution unit.

Furthermore, although working memory elements are copied in the same network in this embodiment, working memory elements can be copied in the same way between different networks.

Further, the data addition process shown in this embodiment can be similarly performed before adding a network or simultaneously with adding a network.

〔Effect of the invention〕

As described above, according to the present invention, a working memory element to be attached to a node of a network for an added rule is obtained by using a working memory element already attached to a node of another network. Since it is no longer necessary to examine all working memory elements, the number of working memory elements to be subjected to condition determination is reduced, resulting in the effect of shortening data addition processing time.

[Brief explanation of the drawing]

FIG. 1 is a diagram showing the main flow of data addition method processing according to an embodiment of the present invention, FIG. 2 is a block diagram showing an inference system of the embodiment, and FIG. 3 is a CPU of the embodiment.
203 and the disk 204, FIG. 4 is an explanatory diagram showing an example of description of a working memory element, FIG. 5 is an explanatory diagram showing an example of rule description, and FIG.
An explanatory diagram showing the network before adding a new rule, Figure 7 is an explanatory diagram showing the network of the newly added rule, and Figure 8 is an explanatory diagram showing the network shown in Figure 6 to the network shown in Figure 7. FIG. 9 is an explanatory diagram showing a network with additional networks and data added.
10 is a flowchart showing details of FIG. 9, FIG. 11 is a flowchart showing details of FIG. 10, FIG. 12 is a flowchart showing other details of FIG. 10, FIG. 13 is a flowchart showing additional details of FIG. 1-32...Processing step, 201...Monitor, 2
02...Keyboard, 203...CPU, 204.
... Distortion, 301 ... Input/output section, 302 ... Debugger, 303 ... Editor, 304 ... Translator, 305 ... Network correction section, 306 ...
- Inference section, 307... Rule file, 308... Network file, 309... Working memory element file, 401-404... Working memory element, 501-503... Rule, 601
-605... Node, 701-704... Node,
801-803... Nodes. N Ward\( α) Shima α)

Claims (1)

[Claims] 1. Composite conditions regarding structure data consisting of a data name and at least one attribute name/attribute value pair are stored in a network in which each condition is a node, and the apex node of the network is In a system that has the function of determining the establishment of complex conditions related to structure data by sequentially performing condition judgments from 1 to 3 and retaining structure data in which all conditions are satisfied up to a certain node on the network, some structures Regarding the first network that has already made a conditional judgment on the data and holds the structure data for which the condition has been met, and the second network that has not yet made the conditional judgment on the structure data for which the condition has been judged in the first network. Let SN1 be the condition that the structure data held by a node on one network satisfies, and let SN2 be the condition that the structure data held by a node on the second network should satisfy, and SN1 and SN2 are When there is a specific relationship, among the structure data SD1 added to the node on the first network, structure data SD2 that satisfies some specific conditions is added to the node on the second network. A processing method for a discrimination network characterized by the following. 2. A discrimination network processing method, characterized in that SN1 and SN2 according to claim 1 are the same including their order, and SD2 is the same as SD1. 3. SN1 and SN2 according to claim 1 have the same content regardless of the order of the conditions, and SD2 is SD
1. A method for processing a discrimination network, characterized in that the method is the same as 1. 4. All conditions in SN1 according to claim 1 are SN
2, and SD2 satisfies a condition in SN2 that is not included in SN1 among SD1. 5. All conditions in SN1 according to claim 1 or conditions stricter than the conditions are included in SN2, and S
A discrimination network processing method characterized in that D2 satisfies a condition in SN2 that is not included in SN1 in SD1 and a condition in SN2 that is stricter than the condition included in SN1. 6. According to claims 1 to 5, if there is no structure data that can be used in the first network, SD2 is set to satisfy SN2 among all the structure data. How to process discrimination networks. 7. A method for processing a discrimination network according to any one of claims 1 to 6, characterized in that either or both of the first network and the second network are each part of a larger network. 8. A method for processing a discrimination network according to claim 1, wherein the first network and the second network are part of the same network. 9. In an open or closed interval of a continuous quantity, the tightness between two conditions representing an interval based on a constant value is divided into an interval containing only the constant value that appears in the condition and a non-overlapping interval containing all other intervals. If the results are the same for all intervals, then the two conditions are the same, and all intervals that satisfy the first condition are considered to be the same in the second. A method for determining the tightness of a condition, characterized in that if the condition is satisfied, the first condition is determined to be stricter than the second condition. 10. A method for determining the tightness of a condition according to claim 9, characterized in that the tightness of a condition on a set that is a discrete quantity and in total order is determined. 11. In claims 9 and 10, in the case of a condition regarding a value on an open interval, the interval from infinity to the smaller of the constant values appearing in the two conditions, the smaller of the constant values appearing in the two conditions. an interval that includes only the larger of the constant values that appear in the two conditions; an interval that includes only the larger of the constant values that appear in the two conditions; an interval that includes only the larger of the constant values that appear in the two conditions; A method for determining the tightness of a condition, which is characterized by dividing the method into five sections, such as the section from the next largest one to infinity. 12. In the above-mentioned claim 11, when the constant value appearing in the two conditions is the same, an interval is provided that includes only that value when the constant value appearing in the two conditions is the same, in the interval from the smaller one to before the larger one of the constant values appearing in the two conditions, A method for determining the tightness of a condition, which is characterized by dividing the method into three sections, and dividing the entire section into seven sections. 13. In the case of the condition on a closed interval, in the case of the condition on a closed interval, the interval including only the minimum value, the interval from the minimum value to the front of the smaller of the constant values appearing in the two conditions, and the interval between the two conditions. An interval that includes only the smaller of the constant values appearing in the condition, an interval from the smaller of the constant values that appear in the two conditions to just before the larger one, an interval that includes only the larger of the constant values that appear in the two conditions, A method for determining the severity of a condition, which is characterized by dividing the condition into seven sections, including the section from the larger constant value that appears in the condition to just before the maximum value, and the section that includes only the maximum value. 14. In claim 13, when the constant value appearing in the two conditions is the same, an interval is provided that includes only that value when the constant value appearing in the two conditions is the same, in the interval from the smaller one to before the larger one of the constant values appearing in the two conditions, A method for determining the tightness of a condition, characterized by dividing it into three sections, and dividing the entire section into nine sections. 15. In the claims 5 to 8, the claims 9 to 14
A method for processing a discrimination network, characterized in that the method for determining the severity of conditions described above is used. 16. By using the discrimination network processing method according to claims 1 to 8 or claim 15, structure data to be retained is added to a network that has not yet undergone condition determination for the structure data. A structure data condition determination method characterized by performing data condition determination. 17. The discrimination network processing method according to any one of claims 1 to 8 or claim 15 is applied to the first network that has already performed the condition determination of the structure data and the second network that has not yet performed the condition determination. A method for merging networks, characterized in that information to be held is added using a method, and then a first network and a second network are merged. 18. The network merging method according to claim 17, characterized in that while merging the two networks, information to be held in the second network is added. 19. The network merging method according to claim 17, characterized in that after merging the two networks, information to be held in the second network is added. 20. Using the network merging method according to claims 17 to 19, based on the result of condition determination of the structure data,
A method for dynamically deforming a network, characterized by dynamically adding complex conditions to the network. 21. Debugging hemlock for a complex condition or a rule whose condition part is a complex condition by using the network merging method according to claims 17 to 19, in which the complex condition is added to the network. How to transform the network. 22. A method for dynamically combining networks, characterized in that a network representing some complex conditions is merged with another network by using the method for merging networks according to claims 17 to 19.