Generalized Chart Algorithm: An Efficient Procedure for Cost-Based Abduction

GENERALIZED CHART ALGORITHM: AN EFFICIENT PROCEDURE FOR COST-BASED ABDUCTION Yasuharu Den ATR Interpreting Telecommunications Research Laboratories 2-2 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-02, JAPAN Tel: +81-7749-5-1328, Fax: +81-7749-5-1308, e-mail: denQitl.atr.co.jp Abstract We present an efficient procedure for cost-based ab- duction, which is based on the idea of using chart parsers as proof procedures. We discuss in de- tail three features of our algorithm -- goal-driven bottom-up derivation, tabulation of the partial re- sults, and agenda control mechanism -- and report the results of the preliminary experiments, which show how these features improve the computational efficiency of cost-based abduction. Introduction Spoken language understanding is one of the most challenging research areas in natural language pro- cessing. Since spoken language is incomplete in var- ious ways, i.e., containing speech errors, ellipsis, metonymy, etc., spoken language understanding systems should have the ability to process incom- plete inputs by hypothesizing the underlying infor- mation. The abduction-based approach (Hobbs et al., 1988) has provided a simple and elegant way to realize such a task. Consider the following 3apanese sentence: (1) Sfseki kat- ta (a famous writer) buy PAST This sentence contains two typical phenomena aris- ing in spoken language, i.e., metonymy and the el- lipsis of a particle. When this sentence is uttered under the situation where the speaker reports his experience, its natural interpretation is the speaker bought a SSseki novel. To derive this interpreta- tion, we need to resolve the following problems: • The metonymy implied by the noun phrase S6seki is expanded to a S6seki novel, based on the pragmatic knowledge that the name of a writer is sometimes used to refer to his novel. • The particle-less thematic relation between the verb katta and the noun phrase SSseki is deter- mined to be the object case relation, based on the semantic knowledge that the object case relation between a trading action and a commodity can be linguistically expressed as a thematic relation. This interpretation is made by abduction. For instance, the above semantic knowledge is stated, in terms of the predicate logic, as follows: (2) sem(e,x) C trade(e) A commodity(x) A obj(e,x) Then, the inference process derives the consequent sem(e,x) by hypothesizing an antecedent obj(e,x), which is never proved from the observed facts. This process is called abduction. Of course, there may be several other possibili- ties that support the thematic relation sem(e,x). For instance, the thematic relation being deter- mined to be the agent case relation, sentence (1) can have another interpretation, i.e., Sfseki bought something, which, under some other situations, might be more feasible than the first interpretation. To cope with feasibility, the abduction-based model usually manages the mechanism for evaluating the goodness of the interpretation. This is known as cost-based abduction (Hobbs et al., 1988). In cost-based abduction, each assumption bears a certain cost. For instance, the assump- tion obj(e,x), introduced by applying rule (2), is specified to have a cost of, say, $2. The goodness of the interpretation is evaluated by accumulating the costs of all the assumptions …

Content truncated to 500 words