Emergent Computation for Semantic Interpretation by Rule-Based Equivalent Transformation

Hiroshi Mabuchi, Kiyoshi Akama, Hidekatsu Koike

In Proc. of the International Workshop on Functional and (Constraint) Logic Programming (WFLP 2001) , Report No. 2017, University of Kiel


The meaning of a sentence must be interpreted properly by using not only the given sentence, but also factors such as the situation in which the sentence was uttered and background knowledge in the domain of the topic. One of the problems when an algorithm, in which the computation order is fixed, is used is the need to assume a variety of cases and describe a number of separate algorithms that are suitable for each case. In order to separate cases properly, the situation in which a sentence was uttered and background knowledge must be considered in combination. However, since the number of possible combinations is extremely large, it is difficult to correctly describe them. Moreover, the maintenance required due to the addition of situations and the revision of background knowledge is costly. Another problem is the efficiency of the computation. In natural language understanding, since a number of different kinds of constraints are related complicatedly, selection and flexible processing of an appropriate constraint are required at each stage of constraint elimination in order to handle the constraints efficiently. When attempting to execute this processing using an algorithm in which the computation order is fixed, an appropriate constraint that should be solved at each stage can not be selected from among the whole possible constraints, and the volume of unnecessary computations becomes very large. In order to solve these problems, we propose a new method for semantic interpretation. In this method, creation of individual algorithms written to handle various situations is avoided, and the basic knowledge in the object domain and the situation in which a sentence was uttered as well as the given sentence are described as a declarative program. The semantic interpretation is then performed by equivalent transformation using correct rules. With this method, efficient processing matched to changing conditions emerges naturally in the computation process. The framework of the computation is referred to as Rule-Based Equivalent Transformation (RBET), which is based on a new model called the declarative computation model. In RBET, a given problem is formalized as a problem which transforms one declarative program into another declarative program. The program is successively transformed into different programs by selecting and applying an appropriate rule from a number of equivalent transformation (ET) rules. The answer can be obtained from the final version of the program. RBET does not fix the computation order beforehand and aims to achieve flexible and efficient computation by selecting the rule to apply using controls, such as minimizing the number of clauses.