A Preferential Constraint Satisfaction Technique for Natural Language Analysis

Katashi NAGAO
Dept. of Information Engineering, School of Engineering, Nagoya University


In this paper, we present a new technique for the semantic analysis ofsentences, including an ambiguity-packing method that generates a packedrepresentation of individual syntactic and semantic structures. Thisrepresentation is based on a dependency structure with constraints thatmust be satisfied in the syntax-semantics mapping phase. Completesyntax-semantics mapping is not performed until all ambiguities have beenresolved, thus avoiding the combinatorial explosions that sometimes occurwhen unpacking locally packed ambiguities. A constraint satisfactiontechnique makes it possible to resolve ambiguities efficiently withoutunpacking. Disambiguation is the process of applying syntactic andsemantic constraints to the possible candidate solutions (such asmodifiees, cases, and word-senses) and removing unsatisfactorycandidates. Since several candidates often remain after applyingconstraints, another kind of knowledge to enable selection of the mostplausible candidate solution is required. We call this new knowledge apreference. Both constraints and preferences must be applied tocoordination for disambiguation. Either of them alone is insufficient forthe purpose, and the interactions between them are important. We alsopresent an algorithm for controlling the interaction between theconstraints and the preferences in the disambiguation process. Byallowing the preferences to control the application of the constraints,ambiguities can be efficiently resolved, thus avoiding combinatorialexplosions.