JPH01259426A - Method and device for hypothesis generation - Google Patents

Abstract

PURPOSE:To reduce the frequency in generation of unnecessary hypotheses by using constant terms included in respective predicates and a list of their weights and using a community of constant terms as an evaluation measure to retrieve another predicate related to a certain predicate and constituting a logical hypothesis. CONSTITUTION:A community of constant terms is checked to evaluate and calculate the strength of relations between predicates, and priority levels are added to predicates as candidates. Since predicates can be screened before generation of a hypothesis, it is unnecessary to combine all candidate predicates in round robin algorithm in a conventional method to constitute a hypothesis logical expression. When the object is limited to candidate predicates having higher priority levels, the calculation volume is reduced furthermore.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a hypothesis generation method and an apparatus thereof, and in particular, 1.
The present invention relates to a method and apparatus for generating a hypothesis, which is a component of an inductive reasoning process, which is an example of a method for automatically acquiring rules stored in a knowledge base expressed by predicate logic.

[Conventional technology]

As an inductive inference method based on first-order predicate logic, the model inference method of Shapiro (Ehud Y, 5hapiro) is known. In this hypothesis generation method, predicates that are candidates for hypothesis construction are prepared in advance, and a hypothesis logical formula is constructed by combining these predicates in a round-robin formula.

[Problem to be solved by the invention]

However, according to this method, when generating a hypothesis,
This method generates a large number of useless hypotheses, and also has problems in terms of the amount of calculation required.

In other words, in the method described above, all candidate predicates are treated as targets without being distinguished from others during hypothesis construction;
Moreover, since the method of combining these into a brute force formula is used, as the number of candidate predicates increases, the number of hypothetical logical formulas constructed increases in a combinatorial manner, resulting in the generation of useless hypotheses. There are problems in that the frequency of doing this increases and the amount of calculation also increases in combination.

An object of the present invention is to provide a hypothesis generation method and apparatus that can reduce the frequency of generating useless hypotheses and suppress combinatorial explosion of calculation amount.

[Means to solve the problem]

The hypothesis generation method of the present invention is a hypothesis generation method in inductive reasoning for a knowledge base expressed by a first-order predicate logical formula, and uses a list of constant terms included in each predicate and their weights to It is characterized by using commonality as an evaluation measure to search for other predicates related to a certain predicate and construct a logical hypothesis.

In addition, the hypothesis generation device of the present invention uses a knowledge base expressed by a first-order predicate logical formula, a list of constant terms included in each predicate and their weights, and a list to determine between predicates based on the commonality of the constant terms. The present invention is characterized by having means for calculating the degree of coincidence between the predicates, and means for selecting related predicates by determining priorities based on the degree of coincidence between the predicates.

[Effect]

In the present invention, the strength of the relationship between predicates is evaluated and calculated by examining the commonality of constant terms, and further, priority is assigned to candidate predicates.

Since it is possible to screen out predicates before generating a hypothesis, there is no need to construct a hypothesis logical formula by combining all candidate predicates in a brute force formula as in the past. When narrowing down the candidates to those with high priority, it is possible to further reduce the amount of calculation.

〔Example〕

Next, the present invention will be explained with reference to the drawings.

1 to 3 show an embodiment of the hypothesis generation method and hypothesis generation device of the present invention, FIG. 1 shows the case of constant table updating, and FIG. 2 shows the case of ranking of related predicates. FIG. 3 is a block diagram.

In hypothesis generation according to the present invention, when acquiring rules to be stored in a knowledge base expressed by first-order predicate logical formulas, basically a list of constant terms included in each predicate and their weights is used, Hypothesis generation is performed by utilizing the commonality of constant terms.

The list can be stored in an appropriate storage means or storage unit, and in the case of FIGS. 1 and 2, constant table storage means 2 and 12 are used, and in the case of FIG. In this case, the constant table storage section 33 is used.

Hereinafter, the present invention will be described in detail by first showing a simple example.

The purpose of inductive reasoning is to organize miscellaneous knowledge and find regularities. For example, when asked, ``Give me an example of a bird,'' people respond with ``a hawk.''

They answer "pigeon", "pheasant", etc., and when asked "what kind of crow is", they answer "a creature that flies in the sky", "
Answer with general regularities such as "It's an organism that has a beak and lays eggs."Inductive reasoning is "a hawk."

It is an inference method that creates a simple rule that ``crows are creatures that fly in the sky'' from examples such as ``pigeons.''

As a knowledge base expressed by a first-order predicate logical formula,
Now, let's specifically consider the knowledge base of zoos.

Bird (hawk), example (1) This is knowledge expressed in a predicate, “A hawk is a bird.”
It is read as. “Bird” is called a predicate, and “hawk” is called a constant term.

Bird (pigeon), example (2) bird (pheasant), example (3) bird (peacock), example (4) is a mammal (fox), example (5) is a mammal (monkey), example (6) is Mammals (Tiger), Example (7) Mammals (Lion) Example (8) Flying (Hawk), Example (9) Flying (Pigeon), Example (1o) Flying (Swallow), Example (11) Running (Wolf), Example (12) Running (tiger), Example (13) Running (lion), Example (14) Roaring (tiger),
Example (15) Roaring (Leopard), Example (16) Roaring (Lion) Example (17) In addition to the above predicates, it is assumed that there is a large amount of knowledge about animal classifications and attributes.

The purpose of inductive reasoning is to create general rules from these examples. An example of the rules is shown below.

Crow (X) ← Fly (X).

Hypothesis (1) This rule is read as "If X flies, then X is a bird" or "Birds fly." Moreover, X is called a variable term. As an example of another rule, ``mammals run and bark'' Hypothesis (2) ``Mammals run and bark''.

These rules are referred to here as hypotheses or hypothetical logical formulas, because the rules created by inductive reasoning are only provisional rules that do not contradict the examples given so far.

The examples described above are the results of observations at zoos. As will be described later, in this embodiment, every time an example is observed, a table of constant terms included in the predicate and their weights is created and updated. This table will be called the constant table. For example, an example (
From the observations of 1) to (4), for the predicate “bird”, bird: inset, 1), (pigeon, 1), (pheasant, 1), (peacock,
1)) Table (1) Obtain the constant table. Here, all weights were set to 1.

Next, we introduce the quantity - political change. This is the sum of all the weights of constant terms commonly included in the constant tables of the two predicates. For example, if the constant table for "fly" is: fly: ((hawk, 1), (dove, 1), (swallow, 1)), then the -political change of "bird" and "fly" is 4.

Now, when creating a hypothesis to explain birds by inductive reasoning, the degrees of agreement with birds are determined for all predicates, and the hypotheses are arranged in descending order of their values. In this way, the priority order of the predicates is obtained, which is used in constructing a hypothesis in order of priority.

As a result, plausible hypotheses such as "birds fly" are created early, and useless hypotheses such as "crows run" are lowered in the generation ranking.

The method of the present invention is based on the above-mentioned principle,
1. In inductive reasoning for a knowledge base expressed by a logical formula, a list of constant terms included in each predicate and their weights is used to evaluate the commonality of the constant terms as an evaluation measure. Search for predicates and construct logical hypotheses. The constant table is updated every time an example is observed.
This can be done by following the procedure shown in the flowchart shown in FIG.

In Fig. 1, the symbol l indicates an observed example, and first,
In step S101, a constant table is extracted. That is,
When the example (1) is observed, the constant table corresponding to the predicate of the example (1) is retrieved from the constant table storage means (2), and then updated in step 5102. That is, if a constant term included in the example exists in the constant terms, its weight is increased by 1, and if it does not exist, it is added to the constant table with a weight of 1, and then stored in the constant storage means 2 (step 5103). .

Ranking of related predicates can be done as follows.

In FIG. 2, reference numeral 11 indicates a target predicate to be hypothesized, and 14 is a priority predicate table. This priority predicate table 14 is used in each process of priority predicate table blanking, registration, and hypothesis generation described later. used.

The procedure is as shown in the flowchart shown in FIG. 2, when determining the priority of predicates regarding target predicate 11,
First, the constant table of the target predicate is taken out from the constant table storage means 12 (step S213), and the priority predicate table 14 is made blank (step S215). Furthermore, the following steps a, b, and c are repeated for all predicates (step 5219).

a: Retrieve the constant table of predicates from the constant storage means 12 (step S216).

b: Compare the constant table of the target predicate and this predicate to determine the degree of matching (step S21?).

C: Register in the priority predicate table 14 in descending order of degree of matching (step 3218).

In step 5219, in this process, it is monitored whether the above-mentioned processing has been completed for all predicates, and if it is determined that it has been completed for all predicates and a determination result of Yes is obtained, then priority is given to Predicates are taken out in order from the beginning of the predicate table 14 to generate a hypothesis (step S
220).

Since hypotheses can be generated in this way, as mentioned above, it is possible to reduce the frequency of generating useless hypotheses such as "birds run", and even if the number of candidate predicates increases, It is possible to avoid a combinatorial increase in the number of hypothetical logical formulas constructed as in the past.

The configuration of the hypothesis generation device will be explained with reference to FIG.

The constant table update unit 32 in this device updates the observed example 31
For example, in the case of the zoo knowledge base mentioned above, examples expressed in the form of birds (pigeons) are used as in example (2), and the constant table storage unit 33 is used to This means updates the constant table in the constant table storage section 33 according to the constant table update flowchart shown in FIG.

Furthermore, the -degree calculation unit 35 and the hypothesis generation unit 34 calculate the degree of agreement between predicates based on the commonality of constant terms using a constant table, determine priorities from the degree of agreement between predicates, and select related predicates. The purpose is to select and generate hypotheses, and here the processing is as follows:
It can be executed according to the flowchart for ranking related predicates shown in FIG. 2 above.

In FIG. 3, if an example 31 such as a bird (pigeon) is observed, each time the example 31 is observed, the constant table updating unit 3
2 updates the constant table and sends it to the constant table storage section 33. At the time of inductive reasoning, the predicate name is transferred from the hypothesis generation unit 34 to the political change calculation unit 35.
The -growth calculation section 35 creates a priority table 37 of related predicates, that is, a ranking of related predicates, while referring to the constant table in the constant table storage section 33, and sends it to the hypothesis generation section 34. and,
The hypothesis generation unit 34 creates a hypothesis 38 using the priority table 37.

In this way, as mentioned above, for example Bird (X) - Fly (X) An observation, or hypothesis, is generated.

When generating a hypothesis, irrelevant predicates can be screened out before hypothesis generation, and furthermore, it is possible to narrow down the target predicate candidates to those with high priority, instead of using brute force as in the past. There is no need to do any combination processing.

〔Effect of the invention〕

As explained above, according to the present invention, it is possible to provide a hypothesis generation method and device that does not require combining candidate predicates in a brute force formula to construct a hypothesis logical formula. Since predicates are filtered out, the frequency of generating useless hypotheses is reduced, and furthermore, by narrowing down the target predicate candidates to those with high priority, it is possible to suppress the combinatorial explosion of the amount of calculation.

[Brief explanation of the drawing]

FIG. 1 is a flowchart for updating a constant table showing an example of the hypothesis generation method of the present invention, FIG. 2 is a flowchart showing an example of a procedure for ranking related predicates, and FIG. 3 is an example of a hypothesis generation device. FIG. 1.31...Observed example 2.12...Constant table storage means 11...Target predicate that is the target of hypothesis 14...
・Priority predicate table 32...constant table update unit 33...constant table storage unit 34...hypothesis generation unit 35...-growth calculation unit 37... Related predicate priority table 38...Hypothesis Figure 3

Claims (2)

[Claims] (1) A hypothesis generation method in inductive reasoning for a knowledge base expressed by a first-order predicate logical formula, which uses a list of constant terms included in each predicate and their weights to evaluate the commonality of the constant terms. A hypothesis generation method characterized by searching for another predicate related to a certain predicate and constructing a logical hypothesis. (2) A knowledge base expressed by a first-order predicate logical formula, a list of constant terms included in each predicate and their weights, and a means for calculating the degree of agreement between predicates from the commonality of the constant terms using the list A hypothesis generation device comprising: and means for determining priority based on the degree of agreement between predicates and selecting related predicates.