JPH03260834A - Back tracking system for rule base system - Google Patents

Abstract

PURPOSE:To easily instruct a back tracking by providing a back track instructing part which makes a user instruct the back tracking in order to attain the instruction of the back track when the user is not satisfied with the inference result, and a back track processing part where the actual back track processing is carried out. CONSTITUTION:A user interface part 1 is provided to carry out a conversation with a user together with a rule base 2 where the inference knowledge is described, an inference engine 30 which performs an inference with use of the base 2, and a blackboard 4 where the inference result of the engine 30 is recorded. Furthermore a back track instructing part 10 is added to a accept the instruction of the user when the user is not satisfied with the inference result together with a back track processing part 5 where the engine 30 is restarted. In such constitution, a back tracking is carried out based on the instruction of the user. Thus the back tracking is easily instructed.

Description

[Detailed Description of the Invention] [Table of Contents] Overview Industrial Application Fields Conventional Technology and Problems to be Solved by the Invention Means for Solving the Problems Actions Examples Effects of the Invention [Summary] Dialogue with Users A user interface part and a rule base that describes knowledge for inference.

A backtracking method when a user is not satisfied with the inference results in a rule-based system that includes an inference engine that makes inferences using the rule base and a blackboard that records the results inferred by the inference engine. Regarding this, the aim is to build a rule-based system that allows users who do not know the internal structure of the rule-based system or the inference mechanism to easily instruct backtracking. The apparatus is configured to include a backtrack instruction section that receives instructions from a user, and a backtrack processing section that returns the contents of the blackboard and restarts the inference engine according to instructions from the backtrack instruction section. The backtrack instruction unit and backtrack processing unit display the hypotheses derived by the system by level on the screen, and return the blackboard state by instructing the hypothesis to be deleted on the screen, or return to the state of the blackboard during inference. The process of applying the rules is displayed on the screen, and the blackboard status is restored in response to backtracking instructions, or information on the final solution derived by the system is displayed, and the user's A mechanism is provided that allows the user to specify an unsatisfactory solution, returns the inference and blackboard state to the state of the rule that caused the specified attribute, and then re-infers from the blackboard state specified by the user. Configure.

[Industrial application field]

The present invention includes a user interface unit that interacts with a user, a rule base that describes knowledge for inference, an inference engine that performs inference using the rule base, and a recorder that records the results inferred by the inference engine. This paper relates to a backtracking method when the user is not satisfied with the inference result in a rule-based system equipped with a blackboard.

With the recent advances in computer system technology and the diversification of data processing by computers, for example, attempts have been made to have computers perform part of the intellectual judgment and problem-solving work of experts in various fields. It is becoming popular, and so-called expert systems are being developed.

In this expert system, the part corresponding to human knowledge corresponds to a rule base called "Knowledge Base J", and the usage of the rules corresponds to a knowledge base interpretation program called "Inference Engine". This system is called a rule-based system.

The rule-based system applies the contents of the rule-base to given data, for example, an image,
Solving problems, for example, performing image recognition.

The above rules are, for example, IF <condition l>, <condition 2>
, ..., THEN<Consequence 1>, <Consequence 2>, ..., and when there is a request from the user, for example, the above image recognition request, the most appropriate rule is extracted from the rule base. , the contents of the above 11 sentences are the current state,
That is, it is checked whether it exists in the image to be recognized,
If it exists, execute the above THEN statement and get the result (
Hypothesis>.

In such rule-based systems, if the user is not satisfied with the inference results (image recognition results) produced by the system, the user can backtrack the system to find a better solution. In a rule-based system, do you want the system to backtrack automatically?

Alternatively, a method is used in which the user instructs the user how far to go back in the inference, but when the system automatically finds another solution, it is often not possible to immediately obtain a solution that the user is satisfied with. , unless the user is the system builder, it is difficult to have the user instruct the user how far to go back in the inference, and even ordinary users cannot properly give backtrack instructions to the system. An effective backtracking method was needed.

[Prior art and problems to be solved by the invention] FIG. 5 is a diagram explaining a conventional rule-based system.
) shows an example of the tank bottom of the system, and (b) shows an example of a conventional automatic backtracking method.

Rule-based systems, as mentioned above, can be used, for example, if
<Condition 1>, Condition 2>, ~, THEN <Consequence 1>,
<Consequence 2> Rules written in the format of ~ are stored in the rule base 2, and when a user makes a request, for example, the above image recognition request, the most appropriate rule is extracted from the rule base 2. , it is checked whether the content of the above 11 sentences exists in the current state, that is, the image to be recognized, and if it exists, the above THEN statement is executed,
It operates to obtain a result (hypothesis).

In such conventional rule-based systems, if the user is not satisfied with the inference results produced by the system, the user has to backtrack the system to find a better solution.

As for the backtracking method, when the user instructs backtracking, as shown in figure (b), the system returns from the last state (the state where the result was obtained: for example, hypothesis A) and returns to the first branching point. The method is to find A and then choose another option.

When the system automatically finds an understanding in this way, depending on the position of branching point A, the solution is often not much different from the initial solution, and it is often not possible to immediately obtain a solution that satisfies the user. There was a problem.

Also, in a method where the user instructs the user himself how far to go back inference, rather than having the system automatically backtrack, the user does not understand the internal structure of the system, so it is difficult for users who are not system builders to It was difficult to tell them how far to backtrack.

In this way, conventional rule-based systems have had the problem that it is difficult to obtain the solution the user is looking for using the method of automatically backtracking, and that it is difficult to instruct how far back to go when using the method that the user instructs. .

SUMMARY OF THE INVENTION In view of the above-mentioned conventional drawbacks, it is an object of the present invention to provide a backtracking method that allows even a user who does not know the internal structure of a rule-based system or the inference mechanism to easily instruct backtracking. be.

[Means to solve the problem]

FIG. 1 is a diagram explaining the principle of the present invention, in which (a) shows an example of a system tank bottom, and (b) shows an operation flow.

The above problems are solved by a backtracking method using a rule-based system configured as follows.

(1) A user interface unit l that interacts with the user, a rule base 2 that describes knowledge for inference, and an inference engine 3 that performs inference using the rule base 2.
0 and a blackboard 4 for recording the results inferred by the inference engine 30, the backtrack instruction unit 10 accepts instructions from the user when the user is dissatisfied with the inference results. and.

A backtrack processing unit 5 is provided for returning the contents of the blackboard 4 and restarting the inference engine 30 according to instructions from the backtrack instruction unit 10, and is configured to perform backtracking based on the user's instructions.

(2) Hypothesis 41 derived from the above rule-based system
A hypothesis instructing unit 10a is provided as a backtrack instructing unit 10 that displays on the screen by level and receives a user's hypothesis deletion instruction on the screen, and deletes the hypothesis 41 from the blackboard 4 based on the deletion instruction, A hypothesis deletion unit 5a that simultaneously deletes a hypothesis 41 based on the deleted hypothesis is provided as a backtrack processing unit 5, and when the user instructs a hypothesis 41 to be deleted, the specified hypothesis 41 is deleted from the blackboard 4. , and configure it to re-infer based on the result.

(3) JL/- during inference with the above rule-based system
A history storage unit 4a that records an application history 40 of a rule on a blackboard 4, and an inference process instruction unit 10b that displays an inference process based on the history 40 and receives backtrack instructions from the user on the screen. An inference return unit 5b is provided as the backtrack processing unit 5, which returns the inference and the state of the blackboard 4 based on the instruction, and the user can return to the desired state by instructing on the screen the inference process he or she wants to return to. The configuration is configured to go back to the previous point and re-infer.

(4) A history storage unit 4a that records the application history 40 of rules on the blackboard 4 during inference in the rule-based system, and displays information on the final solution derived by the system and allows the user to backtrack instructions for it. Receive solution status indicator 1
0c is provided as a backtrack instruction section 10, and a state return section 5C is provided as a backtrack processing section 5 that infers the state of the rule that caused the specified attribute and returns the state of the blackboard 4. By specifying the desired state on the screen, the system returns to the desired state and re-infers.

[Effect]

That is, according to the present invention, a user interface unit that interacts with a user, a rule base that describes knowledge for inference, an inference engine that performs inference using the rule base, and information that is inferred by the inference engine. In a rule-based system equipped with a blackboard for recording inference results, a backtrack instruction section allows a user to instruct backtracking in order to enable backtracking instructions when the user is not satisfied with the inference results. In addition, a backtrack processing section is provided that performs actual backtrack processing.

A user interacts with the system through a user interface. The inference section uses rules to make inferences, and intermediate and final results of inferences are written on the blackboard, which is memory.

The backtracking instruction section functions as a part of the user interface section, displays a screen for backtracking instructions on the screen, receives information about what the user wants to fix on the screen, and backtracks it. Pass it to the processing section.

The backtrack processing unit performs processing to return the contents of the blackboard based on the received information, and restarts the inference unit for re-inference.

The procedure for this process is shown below (see the operation flow in FIG. 1(b)). (1) Inference is made and intermediate results and history are recorded on the blackboard.

(2) If an instruction is received from the user that the result is unsatisfactory after the inference is completed, the backtrack instruction section displays a backtrack screen and receives the user's backtrack instruction.

(2) Pass the backtrack instruction (2) to the backtrack processing unit and perform backtrack processing.

■ After returning the blackboard to the state desired by the user, restart the reasoning section.

Because it functions in this way, when a user backtracks because he is dissatisfied with the system's inference results, he can indicate the backtrack position on the screen, making it easy for users to backtrack even if they do not know the internal structure of the system or the inference mechanism. It has the effect of directing the track.

〔Example〕

Embodiments of the present invention will be described in detail below with reference to the drawings.

The above-mentioned FIG. 1 is a diagram explaining the principle of the present invention, and FIG. 2 is a diagram showing an embodiment of the present invention, where (a) shows an example of the operation flow, and (b) shows the P! An example of a target drawing is shown, (c
) shows an example of the content of the blackboard at the end of the inference, (d) shows an example of displaying the circle hypothesis, (e> shows an example of the blackboard after backtrack processing, and Cf') shows the content after re-inference. FIG. 3 is a diagram showing another embodiment of the present invention, in which (a) shows an example of the operation flow, and (b) shows an example of the blackboard at the end of the inference. , (c) shows an example of a backtrack instruction screen, (d) shows an example of a blackboard after backtrack processing, and FIG. 4 is a diagram showing another embodiment of the present invention. (a) shows the operation flow, (b) shows an example of the state of the blackboard at the end of inference, (c) shows an example of the backtracking instruction screen, and (d) shows the blackboard after backtracking processing. A backtrack instruction unit 10 that indicates a state example and allows the user to instruct backtracking, and a backtrack processing unit 5 that performs actual backtrack processing are provided. Based on this, the backtrack instruction section 10 displays a screen for backtrack instruction on the screen, allows the user to instruct what he/she wants to fix on the screen, and based on that information, the backtrack processing section 5 The means for returning the contents of the blackboard and restarting the inference section for re-inference are necessary means for carrying out the present invention. Note that the same reference numerals indicate the same objects throughout the figures.

Hereinafter, the backtrack method in the rule-based system of the present invention will be explained with reference to FIG. 1 and FIGS. 2 to 4.

(Example 1) An example in which the backtrack method of the present invention is applied to a drawing recognition rule-based system will be described below with reference to FIG. 2.

This system analyzes shapes from the bottom up, i.e., circles,
From recognition of simple shapes such as triangles, to complex shapes.

The rules for this are described as follows.

Rule A IP (and (X isa loop) (X circularity > 0.8)) TtlEN (create circle' (X
) 0.6) This is when a certain figure X is a loop and the circularity of that figure It means to set it to .6.

Furthermore, suppose we have the following rules.

Rule B IP (and (X isa circle) (Yisa triangle) (X contact Y)) THEN (create figure P '(X Y) 0.7) This means that a certain figure X is a circle, and that figure Y When the degree of circularity is greater than 0.8, it means that a hypothesis for figure P is created from figure X and figure Y, and its confidence level is set to 0.7.

In the case of such a system, the processing is performed according to the following steps (see figure (a)). ■ The inference unit 3 applies the above rules A and B and determines which hypothesis 41 is formed based on what. Record whether the hypothesis is a component in the backward binding slot, and record which hypothesis the hypothesis is a component of in the forward binding slot. The inference process of recording this hypothesis 41 on the blackboard 4 ends when there are no more applicable rules.

■ Display the solution of the system to the user after the inference is completed. If there is a hypothesis 41 that the user wants to delete, he or she instructs it. If there is no deleted hypothesis 41, the process ends.

(See step 10a) ① Search for the hypothesis 41 of the figure specified by the user, and set the hypothesis 41 as a deletion target. Furthermore, the forward connection slots of the hypothesis 41 are followed in order to find the deletion target.

■ When there are no more hypotheses 41 written in the forward-facing slots, the hypotheses 41 on the deletion list up until now are deleted from the blackboard 4. (See step 5a) ■ Restart the inference section 3.

For example, when recognizing the drawing shown in figure (b), the hypothesis 41 inferred to be a circle or figure P based on rule A and rule B is
recorded in

Here, "backward connection" indicates what the hypothesis 41 is based on, and "forward connection" indicates what is made from the hypothesis.

If the inference is completed and the user is not satisfied with the result, and the user indicates this dissatisfaction, the system will sequentially update the hypothesis 41 from the lower level, i.e. from a single drawing such as a circle, a triangle, etc.
For example, it may be displayed in a specific color or as a solid line.

In this case, first, a hypothesis 41 about the circle derived from rule A is displayed. ((d) Solid-line figure in the figure) Here, it is assumed that the user has designated a figure g that he wants to cancel out of the displayed figures.

Then, the system searches for the frame "Circle 2" of the hypothesis 41 indicated by the indicated figure g, traces the forward connection slot of that hypothesis 41, and searches for the hypothesis "Figure P2" described there.
J is also subject to deletion. In this way, the deletion target "Yen 2""
Find the figures P2J and delete them from the blackboard 4 ((e
) Refer to the figure) Next, a hypothesis 41 about the figure P derived from the rule B is displayed. (See figure (f)) At this time, the hypothesis ``Since the figure P2J has already been removed, only the figure P1 is displayed.

When the backtracking process for the hypothesis 41 is finished, the inference unit 3 is restarted and the same rule A is applied.

Perform re-inference based on B.

As a result, for example, the same hypothesis as in Figure (f) above is displayed.

(Example 2) An example in which the backtrack method according to the present invention is applied to a computer graphics (CG) expert system will be described below with reference to FIG.

Assume that the rule is written as follows.

Rule P 1F (and (target surface state curved surface) (target surface field of view conversion processed)) THEN (execution polygon division) state change (target surface state polygon) This means that the type of the target surface is a curved surface and its If the surface has undergone visual field conversion, it means that polygon division is performed and the effect of this is to change the state of the target surface into a polygon.

In this system, the state of the target surface is the above rule POI
The technique described in the TIIEN statement of the rule matching the conditions of the F statement, that is, polygon division, is executed on the target surface, and at the same time, the state of the target surface changes to the state described in the state change section.

The processing steps in this system are shown below.

(See figure (a)!) ■ The inference unit 3, while applying the rule P, determines which rule is applied, which technique is applied to the target surface, and how the state of the target surface is as a result. The change is recorded on the blackboard 4. When the target surface reaches the finished state, the inference is finished. This finished result is sent to a computer graphics (hereinafter referred to as CG) system, not shown.

■ After the inference is completed, the user looks at the CG image displayed by the CG system, and if he or she is not satisfied with the result, the system can update the "state" and "technique" stored on the blackboard by indicating this. Display the changes as a graph on the screen.

■ The user instructs the state to which it should return by pointing to the "technique" or "state." The instructed “technique” or “state” is processed by the backtrack processing unit 5.
, and the blackboard 4 is backtracked to the point where the technique is applied or the state is reached. (
(See processing steps 10b and 5b) ① Restart the inference unit 3.

At the end of the above inference, (b) the inference history 40 as shown in the figure
Suppose that is written on blackboard 4.

At this time, based on the dissatisfaction instruction from the user, the system uses the current rule P and the history 40 to display a graph of the inference process as shown in FIG. Here, O indicates the state of the surface, and →, ·-÷ between O and O indicates the technique. The initial state of the 0 surface is a.

The end status is 2.

The user instructs ``technique'' or ``state of one page'' as a backtrack instruction. Now, assume that the user instructs to return to the technique "field of view transformation".

The instructed technique “view conversion” is performed by the backtrack processing unit 5.
, and "backward processing of the blackboard" is performed to return the state of the target surface to the point where the "view field transformation" has been applied. ((
d) See figure) Then, the inference unit 3 is restarted and a new inference is executed for the same rule.

(Example 3) Next, an example in which the backtrack method of the present invention is applied to an image processing expert system will be described with reference to FIG.

Assume that the rule is written as follows.

Rule When the noise in the target image is large, "Noise Removal 1" is executed, and the effect is that the noise in the target image becomes smaller and the sharpness becomes smaller.

In this system, the state of the target image is the IF condition of rule Change to the state described.

The processing steps in this system are shown below.

(Refer to the operation flow in figure (a)) ■ The inference unit 3 applies the rule
When applying , which process (``noise removal 1'') specified by the THEN statement of rule X is applied to the image,
As a result, the fact that the state of the target image has changed to the state described in the effect is recorded on the blackboard 4 as a history 40. When there are no more applicable rules, the inference is terminated and an image of the processing result is displayed on a display device (not shown).

■ After the inference is completed, the user looks at the displayed image and, if unsatisfied with the result, instructs the system, and the system tells the user the state (attributes) of the image at the time the inference is completed.
Display.

■ The user points out undesirable conditions in the displayed image. The system performs backtracking processing to return the state of the image to the point before the execution of the processing ("noise removal IJ") that caused the indicated state. <Processing step 10
c, 5c) ■ The system restarts the inference unit 3.

In the above process, it is assumed that a history 4a as shown in FIG.

The system calculates the current image state 1 based on the data on blackboard 4 (history 40)! Display (attribute). (See figure (C)) Here, assume that the user points out that the image clarity is low as a point of dissatisfaction.

Therefore, the system restores the image state to the state before applying the above-mentioned "noise removal l" which caused the image clarity to decrease (see figure (d)).Then, the inference unit 3
Restart , select a different method of denoising, and re-inference.

The backtracking method according to the present invention has been described above with respect to three examples. In the backtracking method according to the present invention, when the user instructs the system that he is dissatisfied with the inference result, the system ”, the inference process, or the state of the final solution, and on the displayed screen,
The feature is that the user specifies the backtrack point, and the system performs backtracking based on the instruction.

〔Effect of the invention〕

As described above in detail, the backtrack method in the rule-based system of the present invention includes a user interface unit that interacts with the user.

A rule base that describes knowledge for inference, and an inference engine that performs inference using the rule base.

A backtrack instruction unit that accepts instructions from a user when the user is dissatisfied with the inference results in a rule-based system comprising a blackboard for recording results inferred by the inference engine.

The system is configured to include a backtrack processing unit that returns the contents of the blackboard and restarts the inference engine according to instructions from the backtrack instruction unit, and the system functions as the backtrack instruction unit and the backtrack processing unit. You can display the hypotheses derived by level on the screen and return to the blackboard state by specifying the hypothesis you want to delete on the screen, or display the process of applying the rules during inference and back up on the screen. Return the state of the blackboard in response to instructions from the truck, or display information on the final solution derived by the system, have the user indicate an unsatisfactory solution on the screen, and produce the indicated attributes. A mechanism is provided to return the inference and blackboard state to the state of the rule that has been reached, and re-inference is performed from the state instructed by the user, so if the user is dissatisfied with the system's inference results and backs up. Since backtracking can be instructed on the display screen when tracking, even a user who does not know the internal structure or inference mechanism of the system can easily instruct backtracking.

[Brief explanation of drawings]

FIG. 1 is a diagram explaining the principle of the present invention. FIG. 2 is a diagram showing an embodiment of the present invention. FIG. 3 is a diagram showing another embodiment of the present invention. FIG. 4 is a diagram showing another embodiment of the present invention. FIG. 5 is a diagram explaining a conventional rule-based system. It is. instructions. 2 is the rule base, 3 is the inference part. 30 is an inference engine, 4 is a blackboard. 40 is history, 41 is hypothesis. 5 is a backtrack processing unit or backtrack processing. 10a, 10b, 10c, 5a, 5b, 5c
is a processing step. are shown respectively. In the drawing, 1 is a user interface section. 10 is a backtrack instruction section or backtrack first
Figure (Part 1) Figure (Part 1) 41) Figure 1 (Part 2) (b) Figure (Part 2) (e) Figure (Part 3) Figure (Part 1) Figure (Part 4) Figure 3 (Part 2) Figure 3 (Part 3) Figure (Part 2) Figure (Part 1) Figure (Part 3)

Claims (4)

[Claims] (1) User interface section (
1) and a rule base (2) that describes knowledge for inference.
), an inference engine (30) that performs inference using the rule base (2), and a blackboard (4) that records the results inferred by the inference engine (30). When the user is dissatisfied with the inference result, a backtrack instruction unit (10) that accepts instructions from the user returns the contents of the blackboard (4) according to the instructions of the backtrack instruction unit (10), and a backtrack processing unit (
5) A backtracking method in a rule-based system, characterized in that backtracking is performed based on a user's instruction. (2) Hypothesis derived from the above rule-based system (41)
A hypothesis instruction section (10a) is provided as a backtrack instruction section (10) that displays hypotheses by level on the screen and receives a user's instruction to delete a hypothesis on the screen, and based on the deletion instruction, deletes a hypothesis from the blackboard (4). A hypothesis deletion unit (5a) that deletes the hypothesis (41) and also deletes the hypothesis (41) based on the deleted hypothesis at the same time is provided as a backtrack processing unit (5), and the user instructs the hypothesis (41) to be deleted. 2. The backtrack method in a rule-based system according to claim 1, wherein the indicated hypothesis (41) is deleted from the blackboard (4) and re-inference is performed based on the result. (3) a history storage unit that records the application history (40) of rules on a blackboard (4) during inference in the rule-based system;
An inference process instruction unit (10b) is provided as a backtrack instruction unit (10) that displays the inference process based on the history (40) and receives backtrack instructions from the user on the screen, and makes inferences based on the instructions. An inference return unit (5b) that returns the state of the blackboard (4) is provided as a backtrack processing unit (5), and the user can return to the desired state and re-infer by instructing on the screen the inference process he or she wishes to return to. A backtrack method in a rule-based system according to claim 1. (4) A history storage unit that records the rule application history (40) on the blackboard (4) during inference using the above rule-based system, and displays information on the final solution derived by the system, allowing the user to backtrack on it. A solution state instruction section (10c) that receives instructions is provided as a backtrack instruction section (10), and a state recovery section that infers to the state of the rule that caused the specified attribute and returns the state of the blackboard (4). (5c
) is provided as a backtrack processing unit (5), and by instructing the state the user wants to return to on the screen,
2. The backtracking method in a rule-based system according to claim 1, characterized in that the inference is re-inferred by returning to a desired state.