The Universal Parser Architecture for Knowledge-based Machine Translation

1. Introduction

Accurate translation requires a degree of comprehension, and several projects have developed prototype systems to demonstrate the feasibility of knowledge-based machine translation [2, 12, 11). These approaches combine syntactic and semantic information to produce an intermediate knowledge representation of the source text 2 which is then generated In the target language. This paper does not attempt to revisit the ample rationale for the knowledge-based machine translation concept - such discussion may be found in the literature (4, 2, 12) - but rather discusses the universal parser (UP) approach for combining syntactic, semantic and lexical knowledge In order to analyze source text for re-generation in multiple target languages, preserving invarlance of meaning.

First, however, let us review the set of performance objectives that contributed to the design of the universal parser:

• Semantic sccurscy - The translation should maintain semantic invariance above all else. P~ralleling syntactic form, maintaining equivalent length of text, and other such criteria are considered of secondary Importance. Thus, the knowledge-based approach was the only logical choice.

1 Many other members of CMU Center for Machine Translation haw made contribution&, diraetly or indirectly. Teruko Watanabe haa been developing the Japen&H LFG grammar, u well u helping many o1her pans of 1he project. Donna Gatea haa been developing lhe LFG grammar for English. Marion Kee has developed the semantic knowledge for the domain of doctor/patient communication. Lori Levin, Peggy Anderson -.1<1 Yuko Tomita alto contributed in gramniar development and/or semantic knowledge development. Kazuhiro Toyoahima haa implemented 1he run time par~«. HideiD Kagamlda has implemented the aynlsem compiler, the LFG compiler and 1he I:R table compiler. Eric Nyberg, PhH Franklin, Ron Grider and Satoahi Tojo have developed aenl8nee generatora for English and Japanese. Hiroalci Saito helped to port and mainlllin the entire ayslam. Other members who made indirect contributions in l!llWIY waya ana Ralph Brown, Mike Celvin, Alex Hauptmann, Roland Hausser, Fumle Katsu, Kevin Knigh~ Sllllle Morrisson, Hiroaki Musha, Sergei Nitenburg, Raclla Rao, and Michael Witbrock.

Funding for lhia project is provided by several private institutions and governmental agenciea in 1he unned States and Japan.

2rhia inlllrmediate aemantic representation is often caD the intsrlingua, though lhat is a misnomer. The semantic representation is encoded in a completely formal, canonical and unambiguous notation such as first-order logic or frame-based representations. Once the meaning repreaentation is extracted it may be r9ilenerated in multiple languages, paraphrased, summarized, stored, fleshed out by an inference procedure, or olherwiae processed.

2. The Universal Parser: a New Architecture for Multi­ lingual Parsing

Multi-lingual systems require parsing multiple source languages, and thus a universal parser, which can take a language grammar as Input (rather than building the grammar Into the interpreter proper) is much preferred for reasons of extensibility and generality. However, semantic information can remain invariant across languages (though, of course, not across domains). Therefore, It is crucial to keep semantic knowledge sources separate from syntactic ones. H new linguistic information is added it will apply across all semantic domains, and if new semantic information is added it will apply to all relevant languages. The question, of course, is how to accomplish this factoring, without making major concessions to either run-time efficiency or semantic accuracy.

The idea of the Universal Par5er is depicted in figure 2-1. There are two kinds of knowledge sources: one containing syntactic grammars for different languages and the other containing semantic knowledge bases for different domains. Syntactic grammars and domain knowledge bases are written in a highly abstract, human-readable manner. This organization makes them easy to extend or modify. The grammar compiler takes one of the syntactic grammars (say Language ~) and one of the domain knowledge bases (say Domain Di), along with mapping rules (that determine which semantic concept is expressed by what word and what linguistic structure), and produces an object grammar, containing an optimized legal cross-product of both syntactic and semantic in!orrnatK?n. Whereas th~ CO~f!P!Ied grammar is not human-readable, It must IS extremely mach1ne-e~1C1ent in terms of on-line run-time parsing speed. When the user 1nputs sentences in Language ~ (and Domain Dl), the run-time parser parses the sentences very efficiently, referencing only the compiled grammar, and producing semantic representations of the sentences.

3. The System Architecture

Figure 3-1 shows the architecture of the universal parser. We adopt semantic case frames for domain knowledge representation and the functional grammar formalism for syntactic grammar representation. The run-time grammar produced by the multi-phase compiler is an augmented context-free grammar (ACFG) which is further compiled into an augmented LR table to be used by a run-time parser based on the Tomita parsing algorithm. These components are described in detail in the following subsections.

3.1. Semantic Frame Representation

(*ACTION

(ia-a (value *SENTENTXAL)) (:when (aem *TIMB)) (:start (sem *TIMB)) (:end (sem *TIMB)) ( : freq (aem *I'RBQUENCY) ) (:duration (aem *DURATION)) (*PATIENT-ACTION (is-a (value *ACTION)) (:agent (sem *PATIENT)) (*INGEST-MEDICINE (ia-a (value *PATIENT-ACTION)) (:object (sam *MEDICINE)) (:ingest-with (sem *FOOD *MEDICINE)) (*MEDICINE (ia-a (value *PHYSICAL-OBJECT)) ( :quant (sem *MEDICINE-QUANTITY))

We use FrameKit (3) as our knowledge representation language to encode domain semantic knowledge. FrameKit is a compact and fairly efficient general-purpose frame-representation language with rooltiple­ inheritance, procedural attachment, and default semantics. Domain knowledge consists of a set of frames organized into an inheritance hierarchy. Each frame represents a cor~eept such as object, event, state, etc. in the domain with appropriate semantic links to other related frames in the hierarchy. Frames encode typing information, functional dependencies and express compositional constraints used in the parser to block non-productive computations.

Let us consider the domain of simple doctor-patient conversations. Entitles In this domain include an event frame ·INGEST-MEDICINE and ~ject frames ·MEDI<?INE, ·PATIENT and so on. Example frame definitiOns are shown in f~gure 3-2. Sentences with different surface forms that should be recognized as instantiations of these frames Include the following examples.

Take the medicine with three glasses of water . every six hours for two days. What medicine did you take today? I took two aspirin three hours ago.

As a more direct example, the final semantic representation of the sentence "Take the medicine with three glasses of water every six hours for two days· produced by Instantiating frames is shown in the first sample translation In the appendix. This knowledge structure may then be given to any back-end process, whether it be a language generator (to translate into the target language), a paraphraser, a data-base query system, or an expert system.

3.2. The Functional Grammar Formalism

We adopt the functional grammar formalism for syntactic knowledge representation of each particular language. Two well-known functional grammar formalisms are Functional Unification Grammar (UG) (9) and Lexical Function Grammar (LFG) (1). Figure 3-3 is a LFG grammar fragment written In a notation similar to PATR-11 (13).

(<DEC> <-> (<NP> <VP>) ( ( (zl case) · nom) ( (z2 :foz:m) -c :finite) (*OR* ( ( (z2 :tU.) · present) ((zl agr) · (z2 agr))) ( ( (z2 :tU.) · past))) ( (zO) · (z2)) ( (xO :mood) · dec) ((xO subj) · (xl))))

There are two main advantages of using the functional grammar formalism In multi-lingual NLP systems .over more traditional linguistic theories:

• A grammar In this formalism can be used for both parsing and generation. Thus, we do not need to write separate grammars for parsing and generation.
• Functional grammar formalisms such as UG and LFG are well­ known among computational linguists, and therefore they need not be trained (with some justifiable resistance) to write grammars in arcane system-specific formalisms.

3.3. Grammar Compilation and Efficient On-Une Parsing

The previous two sections have described how to represent domain semantics and language syntax. The universal parser unifies both knowledge sources and optimizes the grammar for runtime performance In a series of offline precompilation phases. The first compiler named syn'sem grammar compiler compiles the syntactic and semantic knowledge, as well as morphological rules and dictionary, Into a single large LFG grammar called syn'sem grammar. The compiled syntsem grammar Is basically the same as Its original syntactic grammar except that it acquired many additional semantic equations generated automatically by the compiler. The semantic equations check semantic constraints and build semantic representations rather than syntactic f-structures.

This syntsem grammar In PATR-Iike notation is further compiled into an augmentBd context-free grammar (ACFG) by the second compiler named the LFG compiler. This ACFG grammar Is represented by a set of context-free phrase structure rules, each of which Is augmented with a Lisp program for test and action as in ATNs. All the Lisp functions are generated automatically by the compiler from the constraint equations In the synlsem grammar. Also note that those Lisp functions are further compiled down to machine code by the standard LISP compiler.

Once we have a grammar In this form, we can apply efficient context-free parsing algorithms. In fact, we subject this grammar to a final round of compilation, where the context free rules are compiled Into a large augmented LR table for a generalized shift-reduce parser based on the Tomita algorithm (14, 15). Whenever the parser reduces constituents Into a higher-level nontermlnal using a phrase structure rule, the Lisp program associated with the rule is simply evaluated. The Lisp program handles such tasks as:

• blocking partial parses that violate syntactic or semantic constraints (thus enforcing subject-verb agreement, type checking on the arguments to a proposed semantic relation, etc.),
• constructing a semantic representation of the input sentence from Its constituent parts (an Instantiated frame or causally related set of frames), and
• passing attribute values among constituents at different levels in order to have the information that Is needed to perform the constraint-checking and frame-instantiation tasks.

The Tomita algorithm has three major advantages for real-time parsing over other methods:

• The algorithm is fast, due to the LR table precompilation.
• The efficiency of the algorithm Is not affected very much by the size of Its grammar, once the LR parsing table has been precomputed.
• The algorithm parses a sentence on-line, I.e., strictly from left to right and it starts the moment the user types the first word, without waiting for completion of the sentence.

4. Concluding Remarks

The first pilot integrated implementation of the universal parser was completed and demonstrated in October 1986, demonstrating the computational feasibility of the concept.

We have written a fairly comprehensive English syntactic grammar and Japanese syntactic grammar In LFG, each containing somewhat under 1000 rules of grammar and regular morphology. The English grammar handles declaratives, Imperatives, yes-no questions, "wh"­ questions and other gapped constructions, auxiliary complexes and related phenomena. Additionally we built grammar rules for specialized constructions such as times and dates. The Japanese grammar corresponds roughly In coverage to the English grammar, In addition to having far more comprehensive morphological analysis rules (In LFG notation) required for Japanese. Both grammars are still being refined and extended to achieve full syntactic and morphological coverage. We have started grammar development for a third language. French, to make our system tri-lingual.

We also developed a non-trivial domain semantic knowledge base In FrameKil for certain classes of doctor-patient conversations, plus mapping rules and a corresponding lexicon including over 500 disease names. This domain was chosen as our test bed for developing the universal parser and generator architectures, and we are currently starting on a second domain (small computer manuals).

All modules are programmed in Common Lisp and running on Symbolics 3600s, HP Bobcats, and IBM RTs - the entire system should be portable to any other workstations running Common Lisp (Explorer, Micro Vax, Sun, etc.)

One of our main research activities at present lies In the area of discourse, as our initial system operates only on a sentential basis. First, we Intend to borrow the successful case-frame ellipsis resolution methods developed recently in XCALIBUR (5] LanguageCraft (10), and PSLI-3 [7], and integrate them into the universal parser architecture. These methods rely primarily on case-frame semantics and on functional properties of the syntax. Second, we expect to work on extending and applying the embryonic work on practical anaphora resolution in XCALIBUR and work on handling metallnguistic utterances (6). Third, we will focus attention on default Inference processes to fill in implicit Information lacking in the source text, but required for accurate translation. Such information Includes subjects in Japanese, which are optional when Inferable from context, but which must be stated explicitly in translating to English. At present we utilize a handful of ad-hoc rules to supply default subjects, levels of politeness, etc., but a more principled and systematic approach Is required. Fortunately, the universal parser architecture provides an ideal computational framework Into which new knowledge sources may be Introduced. And, the knowledge-based translation task provides copious and severe empirical tests for our theoretically­ Inspired ideas and methods.

5. References

1. Bresnan, J. and Kaplan, R., Lexical-Functional Grammar: A Formal System for Grammatical Representation, MIT Press, Cambridge, Massachusetts, 1982, pp. 173-281 .
2. Carbonell, J. G., Cullingford, R. E. and Gershman A. G., "Steps Towards Knowledge-Based Machine Translation," IEEE Trans. PAM/, Vol. PAMI-3, No. 4, July 1981 .
3. Carbonell, J. G. and Joseph, R. , "The FrameKit+ Reference Manual", CMU Computer Science Department internal paper.
4. Carbonell, J. G., and Tomita, M., "Knowledge-Based Machine Translation, The CMU Approach," in Machine Translation: Theoretical and Methodological Issues, Nirenberg, S., e~ .· Cambridge, U. Press, 1986.
5. Carbonell, J. G., Boggs, W. M., Mauldin. M. L. and Anick, P. G., "The XCALIBUR Project, A Natural Language Interface to Expert Systems and Data Bases," in Applications in Artificial Intelligence, S. Andriola, ed., Petrocelli Books Inc., 1985.
6. Carbonell, J. G., "Meta-Language Utterances in Purposive Discourse," Tech. report, Carnegie-Mellon University, Computer Science Department, 1982.
7. FrederkillQ. R. E., Natural Langauge Dialog in an Integrated ComputatiOnal Model, PhD dissertation, Carnegie-Mellon University, Computer Science Department, 1987.
8. Hayes, P. J., Hauptmann, A. G., Carbonell, J. G. and Tomita, M., "Parsing Spoken Language: A Semantic Caseframe Approach," 11th International Conference on Computational Linguistics (COLING86), Bonn, U.K., August 1986.
9. Kay, M., "Functional Unification Grammar: A Formalism for Machine Translation," 10th lntemational Conference on Computational Linguistics, Stanford, July 1984, pp. 75-78.
10. Carnegie Group Inc., The LanguageCraft Reference Manual, Pittsburgh, PA, 1985.
11. 11 . Lytinen, S., The Organization of Knowledpe In a Multi-lingual, Integrated Parser, PhD dissertation, Yale Umversity, 1984.
12. Nirenburg, S., Raskin, V and Tucker, A., "On Knowledge-based Machine Translation," Proceedings of the International Conference on Computational Linguistics, COLING86, Bonn, West Germany, August 1986, pp. 39-51.
13. Shieber, S. M., "Using Restriction to Extend Parsing Algorithms for Complex-Feature-Based Formalisms," 23rd Annual Meeting of the Association for Computational LingUistics, Chicago, July 1985, pp. 145-152.
14. Tomita, M., Efficient Parsing for Natural Language: A Fast algorithm for Practical Systems, Kluwer Academic Publishers, Boston, MA, 1985.
15. Tomita, M., "An Efficient Context-free Parsing Algorithm for Natural Lnaguages," 9th International Joint Conference on Artificial Intelligence (/JCA/85), August 1985.
16. Tomita, M. and Carbonell, J. G., "Another Stride Towards Knowledge Based Machine Translation," 11th International Conference on Computational Linguistics (COLING86), Bonn, August 1986.
17. Tomita, M. and Carbonell, J. G., "The Universal Parser Architecture for Knowledge-Based Machine Translation," Technical Report, Center for Machine Translation, Carnegie­ Mellon University, 1987.

1. Sample runs of the Universal Parser and Generator

All of the following example sentences were parsed and generated (translated) in 1 to 6 seconds using the first-generation compiled ~n­ time grammars, which ignore capitalization and do not requ1re punctuation. Each example starts with the source text, sh_ows the internal semantic representation, and concludes w1th the corresponding target text. Japanese is typed in Romaji and converted automatically and unambiguously into Kanji as it is parsed.

1.1. English-to-Japanese Translations

>take the medicine with three glasses o~ water

every ailt hours ~or two days ( ( ( :CJ'NAMB *INGEST-MEDICINE) (:MOOD IMP) (:DURATION ( ( :CJ'NAMB *DURATION) ( :DAY 2))) ( :I'RBQ ( ( :CJ'NAMB *I'REQUZNCY) (:INTERVAL ( ( :CJ'NAMB *DURATION) (:HOUR 6))) (:TIMES 1))) ( : INGBST-WJ:TH ( ( : CJ'NAMB *DRINJtiNG-WATZR) ( :QUANT ( ( : CI'NAME *FOOD-QUANTITY) (:GLASS 3))))) (:OBJECT ( ( :CI'NAME *MEDICINE)))) 3 ~CD*~ 6 ~ 1111-t.>! 1::: .=. 8 Ji 'f- CD A,~ < t!. ~ ~' >when i walk i have a pain in the le~t ~oot ( ( ( :CI'NAMI: *HAVB-A-SYMP'l'OM) (:MOOD DEC) ( :ASSOCIATED-ACTION ( ( :CJ'NAMB *wALlt) (:MOOD DII!C) ( :AGII!NT ((:CJ'NAMB *PATIENT) ( :HUHAH +) (:PRO +) ( :NUMBII!R SG) (:PERSON 1))) ( :TIME PRESENT) ) ) (:AGENT ((:CI'NAMII! *PATIENT) (:HUMAN +) (:PRO +) ( :NtlMBII!R SG) (:PERSON 1))) ( : TIME PRESENT) ( : SYMP'l'OK ( ( :CJ'NAMB *PAIN) (:LOCATION ( ( :CJ'NAMB *BODY-PART) (:CONTRASTIVB-SPII!C((:CI'NAMB *DIRII!CTIONAL-SPII!C) ( :DIRECTION *LD'T) ) ) (:NAMI: *rOOT))))))) :!!><~ ~CD!i!l:::,..ol).;f){~t)lt:T

( ( ( :CJ'NAMB *INGII!ST-MEDICINB) ( :MOOD QUII!S) ( :WHII!N ( ( :CJ'NAMB *TIME) ( :WH -) (:TIME-RELATION ( ( :CJ'NAMB *TIME-RELATION) ( ; INTII!RVAL ( ( : CI"NAMB *DURATION) ( :DAY 0) ) ) (:DIRECTION-))))) (:OBJECT ( ( :CI'NAMI: *MII!DICINB) ( :WH +))) ( :WH +) (:TIME PAST)))

1.2. Japanese-to-English Translations ~kyounannokusurionomimasitaka ~ El {iJCDJ!.f-CD.ol).lt; L,'k."h"WHAT MII!DICINB om YOU TAD TODAY" >aakuyameqahirihiriaimasita flilHU{Uot) 11-t:J t..,:t; t..,'k.

( ( ( :CJ'NAMB *HAW-A-SYMPTOM) ( :MOOD DII!C) ( :WHII!N ( ( : CJ'NAMB *TIMII!) ( : WH -) ( :DAY-SII!GMII!NT ( ( :CFNAMB *NIGHT))) ( :TIME-RELATION ((:CI'NAMII! *TIMII!-RELATION) (:INTERVAL ( ( :CI'NAMII! *DURATION) ( :DAY 1))) (:DIRECTION-))))) (:SYMPTOM ( ( :CI'NAMII! *PAIN) (:LOCATION ((:CI'NAMB *BODY-PART) (:WH -) ( : NAMI: *II:YII!) ) ) ( :PAIN-SPII!C ( ( :CJ'NAMB *BURNING))))) ( :TIME PAST) ) )