Modified Caseframe Parsing for Speech Understanding Systems

ABSTRACT

We suggest for speech understanding systems a case frante parsing strategy which deviates from 'pure' case frame parsing in at least two respects: parsing is not exclusively based on top-down instantiation of casefr81118a, and caaeframes are ooerged before uae with syntactic knowledge. Our strategy has bean dev­ eloped to be executed as an inferential process in which a set of Knowledge Sources cooperate through the blackboard. The Knowledge Sources are aut0111atically defined by ooerging syntac­ tic and semantic knowledge expressed declaratively: this inte­ gration of syntax rules and caaefr81118a 11akea it possible to ex­ ploit aiaultaneoualy both syntactic and seiiBntic constraints.

I. INTROOUCTION

Parsers for spoken natural language and paraera for typed natural language 11uat ooeet different requirements. Parsers for apeech work on a set of lexical hypotheses rather than on se­ quences of words. An (unpleasant) consequence is that it is usually possible to find sequences of hypotheses not cor­ responding to the sequence of words actually uttered but which nevertheless constitute coaplete and correct interpretations. A parser for speech auat be able to work when SOllie words like articles and preposi tiona have not been recognized, and to decide whether two slightly over lapping lexical hypotheses are coapeting or not. For all these reasons, parsing a spoken utterance requires inferences as coooplex as those of eapiri­ cal, inductive enterprises as expert aysteooe and originates aiailar probleooe.

Caaefr81118 parsing has recently been proposed ([Hayes et al. 1986], [Brietzaann, Ehrlich 1986]) as an alternative to the ooethoda developed during the ARPA-SlJI project like se11antic gr-ars ([Hayes-Roth 1980]) or networks ([Lowerre 1976]). Having chosen the blackboard architecture, suiteble to cope with the probleooe of speech parsing sketched above, we have introduced two aodifications to 'pure' case frame parsing to usa it effectively into such a frantework: i. alternating between top-down instantiation of caaefrantea and bott0111-up prediction of caaefr81118B requiring a casefiller already recognized; and ii. using caaefraooea only after they have been ~~erged with syn­ tactic knowledge.

II. A REVIEW OF ClJIRENT RESEAROI IN CASErRAHE PARSING

The basic notion of cesefr81118 is that of a head concept - dified by a set of related concepts ([Fillaore 1968], [Teaniere

* This research has been partially supported by the EEC ESPRIT Project n.26. "Advanced Algorithlla and Architecture for Signal Processing·.

** Current adress of Haaaiao Poeaio is Project WISBER, lk'oiver­ sity of H&~~burg, Postal P.O.Box 302762 0-2000 Hamburg 36 West Geraany.

H.eaiMO Poeeio··, Claudio Rullant

CSELT - Centro Studi a L.txlratori Teleeo.unicazioni Via G.Reiea ROMOli, 274 - 10148 Torino - Italy

19~9 ]) · Each noodifier playa a role (CASE) with reepe~t to the

head concept. Caeefr81118 parsing has been proposed long ago for typed natural language parsers ([Hayes,Carbonell 1981]) and its applicability to parsers for speech has recently becOIIIB an object of study ([Hayes et al. 1986], [Brietzaann ,Ehrlich 1986]). This strategy is pr011illing because the interpretation is anchored to 110st eigni ficant parte of the input, and seMan­ tic expectations generated fr011 these aore IIBaningful parte can be used both to diecriainate between different cendidate fillers and to hypothesize the aeaning of troubleeOIIIB frag­ ments. But current caaefrBIIe parsers for speech are still close to parsers developed for typed text, which causes two ~~&in probleiiB.

The first proble· is that the parsing strategy they use is top-down: in a first stage all potential casefr81118 headers are activated, then casefr81118s are 'instantiated' by flndi "!J suitable f1llera. This strategy would be justif1ed for pars1ng speech only if the recognizer would assign the best scores to LHa corresponding to caaefrBIIIe headers (verba, co,...on and proper nouns); 10 this case the search would always follow the best directions. In a prev1ous version of SUSY we discovered that this assumpllon 1a only partially true. In Italian there are in fact words like "quale" ("which", "what") or "dove" ("where") that very often have a better score than caaefrBIIe headers and can generate useful bott001-up predicllona ("dove·, for 1natance, strongly prefers caaefrBIIIes 1n wh1ch a LOC case is required).

Another probleM of these systems is the 1ntegrallon of syn­ tax end semantics. In the approach followed by ([Hayes at al. 1986]), casefr"""'s are auiJIII!nted with syntactic constraints on case flllers and separate phrase structure rules are developed to COIIIbine the resulting caeefrMee. Another approach ([Bnetzaenn, Ehrllch 1986]) is that of developing d1fferent syntactic interpretations of fra~enta, that are then COIIp&red to flnd the one that flts beet. Neither of these approaches is coapletely satisfying. Our idea 1s that, both for c011pleteness and clarity, the gra.,.ar should be developed independently (using for instance phrase structure rules) and 1ntegrated only in a second -ent with se..;.ntic knowledge (as noted by [Hayes et al. 1986] thea approach gets into trouble when the syntac­ tic coaplexity of the sentence 1ncreases). But we also think 1t is necessary to reduce the size of the inferential activity, by apply1ng both eyntacllc end ee11antic constraints siMulta­ neously even when aggregating the smaller fra~ents.

III. THE SUSY SYSTEM

The Speech Understand1ng SYste11 (SUSY) understands and an­ swers continuous speech queries about Italian geography. SUSY receives a lattice of lex1cal hypotheses produced by an inde­ pendent word recogn1tion 110dule ( [Lafece at al. 1987 ]) ·

We have adopted for SUSY the blackboard approach, very ef­ fecllve in such complex problem solving tasks ([Erman et al. 1980 ]) , and developed SUSY 's parsing strategy by modifying 'pure' case frame parsing to overcome the problems prev10usly descubed and make it work in the blackboard framework . Our 'impure' methodology can be su,..auzed as follows:

• A set of Knowledge Sources (KSs) bu1ld and validate hypo­ theses about utterance fragments(Deduct1on Instances) that are put on the blackboard. Each DI represents a sentence fragment at some stage of aggregat10n, and it 1s supported by a set of leXIcal hypotheses (the Dis are an elaboration of the HWIH 1dea of ~ [Woods 1982]). Dis have a ~ derived fr0111 those of the assoc1aled LHs by using the score combw1ng methods descubed 1n [Woods 1982].
• Only sentence fragments that can be characterized both syn­ tactically and semantically are aggregated. This way we can exploit syntactic and semantic constra1nts simultaneously even at the lowest levels of aggregation. Syntacllc and semant1c knowledge are parllt1oned 1nto KSs following the principle. that each KS owns the syntactic and semanllc com­ petence necessary to deal w1th a particular class of sentence fragments.
• Top-down, expectation-based pars1ng actiVIties are merged with bottom-up, predictive actiVIties. An incomplete Dl (~ DI) can originate a search for m1ss1ng components, causing the activation of the KSs (and of those only) that deal with the classes of fragments that are requued; VICe versa, complete Dis (1.e. covering completely a llme wterval) when put on the blackboard activate KSs requiring a DI of their class as a e0111ponent (for instance, a e0111plete case filler will activate KSs building caseframes requiring that par­ ticular case f1ller).
• A complete DI d carues on an 1nterpretallon of the fragment 1t . represents; this Interpretation is used by other KSs to generate interpretallons of larger fragments hav1ng d as s component. An interpretation is not necessarily a caseframe. Also fragments whose interpretation is a casef1ller or a definite descupt1on are aggregated : these Dis can be shared by several Dis to avo1d repeating the same pars1ng steps more than once.
• Neither syntactic rules nor caseframes are used as such, but compiled to get the KSs. Syntacllc and semantic knowledge are, however, expressed declaratlVely and independently deve­ loped. Us1ng this approach ·we get more flexibility than either co11pletely c0111piled systems like HARPY or systems that make use of semantic grammars, while maintaining an effi­ ciency and a constraining ability superior to those that can be obta1ned by using the two forms of knowledge Independently and declaratively.

IV. REPRESENTATIONS fOR SYNTAX AN> SEMANTICS

for syntactic rules we have used the formahsm of Dependency Gra111111ara ([Hays 1964]). There are two advantages in using DGs: structures based on 'governors' and 'dependents' can be easily mapped onto casefra11es (which is not casual, as both dependency gr-ar and valency theory trace back to the work by [Tesn1ere 1959 ]) , and parsing is strongly anchored to input since, for a DG rule to be applied, it ia necessary to f1nd a suitable can­ didate for the governor.

We have adopted Conceptual Graphs (CG) [Sowa 1984] to repre­ sent casefr-a. The pu10lli ves representable in CGs are Indi­ VIduals and relations. Each indiVIdual is characteuzed by a ~ and an 1ndivtdual marker (~ for short) . Types are organized 1n a type hierarchy where any two types tl and t2 have a maxi mal common subtype ll*t2. An i ndividual I confor11s to type t if 1t IS an i nstance of a type tl <= t. A Conceptual Graph 1s recurs ively defined as either a concept , or a concept connected to other concepts by Conceptual Relations (CR). The Canonical Graph (CAGR), 1a a spec1al CG associated to types to represent selections! restnct i ons .

Sows's theory has the advant age of fo rmal CAGRs un1ftcallon operations that conserve the select10na l restrictions. for the purposes of this paper we are Interest ed In three of these operations: by ~. two CAGRs are um fled over a 'common' con­ cept (a concept appear i ng 1n both CAGRs); by type restriction, the type of a concept can be substituted by any of Its sub­ types; by referent restrtct10n, a generic referent in a concept can be substi t uted by an 1marker.

Caseframes are represented In SUSY as CAGRs 1n wh1ch one concept, called the head, represent s the head of the caseframe: for instance, the caseframe we use for the pred1cate LOCATED­ IN-REGION (one of the interpretations of the verb "trovarsi", "to be located"***) 1s represented by the canonical graph

[LOCATED- IN-REG ION]

• ->(AGNT :Obhgatory)->[MOUNT+PROVINCE+LAKE];
• ->( LOC :Obligatory )->[REGION].

f1g. 1 - The caseframe for LOCATED-IN-REGION

In wh1ch cases are represent ed as CRs. In this framework both caseframes connection and case filling are reduced to join ope rat ions, cepts ( 1.e. since simple casefillers are represented as con­ conceptual graphs wi t hout CRs) and complex essefillers are caseframes themselves .

V. COMBINING CASE fRAMES AN> SYNTAX TO DEfiNE KNOWlEDGE SOIJICES

All KSs share a common body of procedural knowledge ( rou­ tines to check te~~porsl constraints, functions that compute the score of a DI); they all 1nclude knowledge about syntactic and semant1c constraints on case f11lers, and must return an inter­ pretation, that is always butlt using joins and restrictions only. The behav10ur of a KS 1s then completely deflned by spe­ cifying I. the class of Dis it can aggregate, ii. Its acti­ vation condillons, 11i. the set of constraints and iv. the way caseframes must be Instantiated to get the interpretallon.

Since only fragments that can be classified both fr0111 a semantic and from a syntactic po1nt of view are aggregated, a DI d could be classified twice: w1th a syntactic category C (syntactic categones are types in the type hierarchy) and with a type T of the domain. The type that IS effectively used to classify d is therefore Y = C*T (for instance, the KS above will produce Dis of class VERB*LOCATED-IN-REGION). The defini­ tion of KS23 .1 in fig. 2 includes a descnption of the C0111posilional structure of the fragment in ter11s of semantic ty­ pes, that IS used together w1 th the (Isomorph) C0111posillonal structures of associated syntactlc rules for expectallons and predictions purposes: the KS above, for instance, will aggre­ gate sequences whose first element 1s of class ADV*REGION or NOLN*REGION, the second element of class PART-RifL*.llLLY or BE* .llLL Y, etc. The type .llLL Y 1s used to classify words whose -

Since in our domain there are restrictlons on what entitles can be conts1ned in others (an island can only be located 1n a sea, for 1nstance) and representing these restuclions In CAGRs would lead to unecessary complexities, we have introduced dif­ ferent subtypes of· LOCATED for each 'containing' enllty.

8yntacllc classi flcation only 18 relevant (lind that can even­ tually be sktpped).

(DefKS KS2J .1 11 Co11poai lionel Constraints LOCATED-IN-REGION = REGION .liLLY <I£AOER> MOLtH+PROVINCE+lAKE ;; Associated Syntactic Rules (Dr2J Or2Ja Dr2Jb Dr2Jc Or2Jd OR2Je) ;;VERB NO~ PART-RIFl. <GOVERNOR> NOUN ; ; VERB : NO~ BE <GOVERNOR> NO~ 1 ;VERB NO~ PART-RIFL <GOVERNOR> PROPER-NOUN ;;VERB AOV PART-RIFL <GOVERNOR> NO~ ; ; VERB AOV BE <GOVERNOR> NOI.Jj ;;VERB AOV PART-RIFl. <GOVERNOR> PROPER-NOUN 1; Activahon Condihon G( ?X) ==> ACTION (?X LOCATED) 1; Casefra11es Instantiation Rule *RIS( (LOCATED I * ACNT ?Z LOC ?Y)) <:: RIS(REGION (ACTION I * ?X ?Z)) RIS(MOI.JjT+PROVINCE+lAKE (ACTION I * ?W ?Y)))

KS defln1tions are the result of a rot~pilallon. They are produced fr011 dependency rules, casefr-a and ·apping rules. For ex&~~ple, the deftnition of KS2J.l has been obtained fr011 the set of aaaociated dependency rules in Fig. 2, one of which ia shown in fig. J.a with its 1011pping rule (F1g. J.b), and fr011 the casefr- in F1g.l.

a. (Dr2J (VERB = NO~ PART-RIFL <GOVERNOR> NO~) VERB (MODO (INOIC)) (TEII'O (PRES)) (PERS (J)) (NlJ4 I ?N) (TRANS (VIT)) (COII'LD£NTO I (STATO-LlllGO)) (Rirt (RIFL)) NO~ (T-COHPL I (STATO-LlllGO)) PART-RIF'L NIL NO~ (NlJ4 I ?N)) b. (Hr2J ((LOCATED-REGION LOCATED-PROVINCE WASH) : LOC (.liLLY) <I£AOER> ACNT))

The COIIPilahon is facilltated by the structural ai111larity between dependency rules and caaefr-· (both are essentially baaed on the idea of a 'head' 110dif1ed in 110M way). The COli­ positional part of the KS 1s derived fr011 that of the depen­ dency rule by substituting ayntachc types with the value reatnctione on ease ftllere specified in the caaefr-; the posi lion of c·ae· in the frag~~Bnt is spec1 fted 1n the Mpping rule. Only thoss eaaea that can be ftlled using inforMtion present in the frag~~~ent are included; thia pre-aalaction avoids aearching for infor·ation that could not be found. The acttva­ tion condihona are aaaociated to types in the knowledge base.

Having partitioned the knowledge in independent chunks, when a new syntactic rule ia added it ie never necessary to reCOil­ pile the anti re eel of KSaa either a previously def1ned KS ia IIOdifted to take into account the new rule, or new KSa are lidded to the existing set. In this latter caae, since not all eyntachc/ee·antic COIIbinahona are adlliaaible, the nUIIber of KSe that are generated lB Ji111ted. The case in which a new type is added to the doola1n has 110re senous consequences: with our current set of about 1~0 dependency rules in the average about 1~ new KSa are def1ned when adding a new entity type. These probleM are typi-cal of ·-ntic gr...,.ara; in our case there is the advantage that it ia the ayate· itself that generates the new KSa.

VI. CASErRN€ INSTANTIATION

The ~Haning of a word in the d1ctionary 1s a aet of predi­ cates able to actlvate the appropriate KSaa for instance, the ·aning of the word "trove" includes the pred1cate

ACTION(TROVA LOCATED)

that achvatea KS2J.l of Fig.2. That KS 1ncludea a casefr­ inatantiation rule that produces the instantiated caeefr-a constituting the interpretation of the sentence frag~~enta it analyzes. By thia approach, 1nforution duplication ia avoided, aince a single caaefr- ia shared by uny warda, and ca8efra­ IIB8 in8tantiation ia 110re eff1ctent, since the in8tant1ation rule apeciftea 'a pnon· how the caaafr- aaaocuted w1th the header IIIUat be joined w1 th those associated with the c:otlponent Die.

Only two operations are needed to build the interpretation! referent re8tnctiona are used to f11l concepts, and joins are uaed to ·rge concepts representing caaea with canonical graphs repreaenhng case f 11lere. Representing a canonical gr·ph aa a ter· and generic referents aa logic variables, joins can be ef­ fectively i!lple·nted as unification operations ua1ng · PRotOG interpreter after all COIIponenta indicated in the rot~poa1 han rule have been found. The instantiation rule of KS2J.l (reproduced in Fig.4.a) together with the CGa earned by Dis of clue MOI.JjT+f'ROVINCE+lAKE (4.b) and REGION (4.c) produces the instantiated casefr- in (4.d). This un1fication has a vary low coat, since the interpreter rune in a special context in which only the reaulte earned by accepted CO!IpOnenta (the "ria" predicates in fig.4) have been a11erted.

1. RIS((LOCATEO I *
2. c. d. ACNT ?Z LOC ?Y)) <:: RIS(MOUNT+PROVINCE+lAKE (ACTION I * ?X ?Z)) RIS(REGION (ACTION I * ?W ?Y)) RIS(MOUNT+PROVINCE+lAKE (ACTION I · ACNT (MOI.JjT I ROSA))) RIS(REGION (ACTION I * LOC (REGION I ?r))) (LOCATED I * ACNT (MOUNT LOC (REGION ROSA) ?II)))

F1g.4 - Casefr- instantiation

VII. INTEGRATING TOP..oowN NG IIOTTOM-lP CASErRN€ PARSING

Suey alwaya 110vea fr011 the beat Lexical Hypothesis or Deduc­ tion Instance. A top..down, expectation baaed activity ia started if a caaefr- header is aelectad; a bott011-up pred1C'­ tive activity i.e 1n1tiated when a 01 representing a caeeftller or a LH representing a ca11 ·arkar are selected.

Lat us cona1der the sentence (translated word by . word) 1 IN QUALE REGIONE 51 TROVA IL MONTE ROSA? (In which region is located 110unt Roaa?)

The LHs involved In the solution, ordered by scores (the best first) are:

1. QUAL (which) 1.267
2. IN (In)
3. 1.301
4. I«JNTE (mount)
5. 1.371
6. SI 1.485
7. REG I ONE (region)

1.560

1. TROVA (is located) 1.610
2. ROSA (Rosa)

1.629

Fig.5 - The LHs Involved in the solullon

The process leadwg to the solution IB displayed in Flg.6:

• The best LH, "qual" is not a case frame header but an interro­ gative adjective that acta as a casemarker together with the preposition "In". The KSs whose activation conditions are satisf1ed by the predicates associated with the word "qual" are triggered. One of these KSa requires no other coroponents and produces the complete Deduction Instance dl of class ADJitSPEC, that IS put on the blackboard.
• Since dl h~s a good score the analysis proceeds along this path, causing a boltoro-up activation of all tha KSs having a component of class ADJitSPEC. The activation of one of these, a KS of class NDl.ti*REGION, generates d2. d3 is generated when a suitable case frame header is found (the LH ·regione"); later, also tha casemarker "In" IS found, and the complete DI d4 is generated.
• As the score of d4 is worse than that of the LH ·monte", this branch of the Inferential process is moroentarily abandoned. The caseframe header "monte" causes the activation of all KSs instantiating l«l~T ·ype casefrBIIII!s. The KS of Interest requnes only an individual referent, that is found (the LH "Rosa"). This process ends In the Dl d7 of class NOl.tl*l«l~T.
• The score of d7 IS not very good, due to the bad quality of the LH "Rosa". The deduction path that had produced d4 (with score 1.4369, better than that of d7) is resuoned. The KSa requiring a LOC case to be filled by an entity of type REGION are activated; among these, KS2J.l. The DI dB is generated by KS23.1 when d4 IS accepted as casefiller; d9 when the header of the caseframe for the type LOCATED-IN-REGION is found (the LH "trova").
• The casefr- for LOCATED-IN-REGION also requi rea the AGNT case to be filled. A suitable filler is dll (derived fr011 d7 after the mggregation of the article "il"). The final, complete DI dl2 is obtained; note that this last step involves the confluence of two deductive processes that developed independently. The three canonical graphs of KS2J.l. are joined to give the final interpretation, the instantiated casefraroe of hg. 4d.

VIII. roNCLUSIONS

Two 110di f1cations have been proposed to casefr- parsing in order to roake it work effectively In a blackboard fraroework: a more fle·ible strategy allernallng top-down and bottoao-up pars­ Ing, and the coaopilation into the a- knowledge source of syn­ tactic and semantic knowledge. Due to the integration of syn­ tactic rules in the casefraroe approach, the system is able to handle fairly comple· sentences with a reasonable efficiency.

This approach has been impl-nted and tested and we are now improving the COtiiPiler and the overall blackboard architecture.

I X. REFERENCES

• Brietzmann, A., Ehrlich, U., "The role of semantic pro­ ceasing in an automatic speech understanding system", Proc. COLING-86, Bonn, West Germany, 1986
• Erman, L.D., Hayes-Roth, F., lesser, V., Raj Reddy, D, "The Hearaay-I I Speech Understanding System: Integrating Knowledge to Resolve lklcerta1nty·, C011puting Surveys, v .12, n.2, June 1980
• 3 Fillmore, C.J., "Tha case for case·, In Bach, Harris (Eda·;), Universals In Linguistic Theory, Holt, Rinehart, and Winston, New York 1968, 1:90
• 4 Hayes, P.J., Carbonell, J.G., "Multi-Strategy Conatruction­ Speci fic Parsing for Fle·ible Data Base Query and Update·, Proc. IJCAI-81, Vancouver, August 1981, 432:439
• 5 Hayes, P.J., Hauptmann, A.G., Carbonell, J.G. - Toroita, H., "Parsing Spoken language: a Semantic Caaefraroe Approach", Proc. COLING-86, Bonn, West Germany, 1986
• 6 Hayes-Roth, r., "Synta·, semantics, and pragmatics in speech understanding systems", 1n W.lea (ed.), Trends in speech Recognition, Prentice-Hall, Englewood Cli ffa (NJ), 1980
• Hays D.G., "Dependency theory 1 a for·aliam and some observa­ tions", Memorandum RH4087 P.R., Tha Rand Corporallon, 1964
• 8 Laface, P., Hicca, G., Pieraccini, R., "Experimental results on a large lexicon access task", in Proc. ICASSP-87, Dallas, 1987
• 9 Lowerre, B., The HARPY Speech Recognition Syate11. Co·puter Science Department, Carnegie-Me lion Uni varsity, April, 1976
• 10 Sows, J.F., Conceptual Structures, Addison-Wesley, Reading (HA), 1984
• 11 Teaniere, L., Elements de syntaxe structurale, 1st edition, ltbrairie C.Klincksieck, Paris, 1959
• 12 Woods, W.A., "Optimal Search Strategiea for Speech Understanding Control", ArttflclBl Intelligence, v .18, 1982, 295:326