Human Engineering for Applied Natural Language Processing

1 RYJ NG ELLl PSIS :

khen the f'lliptical £nr lysis routine is invoked. lf el lipt icP1 EnEl ysis is successful, thPn, as an additional fe edback to the user, th~ ~ystem's exprns ion of tne elliptical input is printed ~ fter the "TRYl NG ELLIPSIS:" messrge, repl adng the "PARSED !" meese>ge printrd for complete inputs.

Input s 2 through 5 of Figure 1 arc different rlliptic~l variations on the same b2sic sentence p1.tt ern, ttJ~e pe>t tern of input 1. Input c C?US~C:" 2 substitution for the attribute~ :'ought. Input~ , through 5 subs.t itut f' for· the irdividu;-1~ whosf attributes 2rr sought. Note that input 5 seeks the position ~ nd di'J\f. hired for E "''hOlf· c l ?s!' of individucle ..

D. SPELLI NG CORRECTION

A significant consideration -when dealing with hum?n-generated inputs is t.h'lt t.h<cy often contain Spelling Errors. whE thE'r thE USf·r ?Ctuf-lly misspells a -.:ord or simply mistypes it, th~ df('ct is thE same: gil rbled input. In constructing a l<Jngu?gf· system for the se>kf.' of studying lc;r:guege und€retandlng, there il" no reel need for ? sp~lling correctior: cepebility. But users of cpplication system! a r e ju~tly irritEted when spflling e rror~ cause ?borti on of processing ard n sul t i.n d el~ys and t edious retyping.

LIFER's spelling correction ability, which makes use cf INTERLISP's spelling corrector, is illustr2-ted by interaction 6. A me~sage is print ed indicating thet e spelling correction has been made, ?nd the respelling is printed directly belo-.: the origin?lly misspelled word.

E. ~MESSA�ES

Inter?c tion 8 illustrates how LIFER responds when it cannot successfully intt>rpret an input. Having filil ed to perse at both the sentEnce lE:vf'l and the ellipsis level, end being unable to proceEd through spelling correction, LIFER givEs up and prints an error message. This error mess~ge is not such cryptic nonsense as

ERROR TRAP AT LOC 137~0,

but is a piece of useful information that can help a neivt> user understand the problem plaguir:g his input and aid in a reformulation. (Intrrfi?ce builders may ce>ll special di!gnostic routines for sophisticated error information, but the>t is

··· This wzs done, for example, in the SRl Speech Understanding SystE:m. See welke r (1916).

···· But this operation mey be skipped by typing a comma as the first character in an input that is only to be processed elliptically.

arothFr ~tc~y.) Thr current ·rror m r~~~gc (onr of ~"vn· o-l) i r (fiC" tE:> th?t LH"ER unuErstood hHA1 A~~CCJATE PHOFE8SCH l N

but thFn hPd trouble with th~ ~ord COMP~Cl. lt ~~ ~ ~Xp<"Cti rw <; < DEPPRWENT-N ~ME> .

At th is pcir.t, tltf t; :oc r m2y r·e.? lize th"t COMPSCI mi ght net br i ncludrd in the ~yst em's l~xiccr.. Pnothrr ~2 y cf rxprrs~ing thr dep? rtm ~nt nPmf --~uch : ! CCMPUTER SCl~NCE-- could bP t r lrd . On th" othF r h2ncl , the u~ c r mc- y be ~·tumprd , r.Pving r.0 idrc; 1-'h:o t <DEPftRTt~ENT- ~~ P.t·' E> J~. Tr.J~ b r i!'/1;~ t·p t hr next topi c , r nd 5rtr r Fcti cn 9.

F. INSP!ICTlCN IT lill:: LANGUAGE .QEF!NlTJCN

LIFER provid~ ! f FSY ?CCc ss to lnform2tior Jbout thr undrrlying l fnRurgP defin i tion through nr- t ur<>l li1r.gu~g,r. Soph i ~lic,· tro UfPr:o ;: nd intrrf2cr bui ld·rs m~ y u~r this rnFChPnism to rF fr r!h thrir m·mcrir~ on the undrrlying structurr~ "rc' c =- · pc b il it~ : ~. r-.: .... ~r · · t'~fr' !=': :. ~ ili l'str ;-; t~o j :-: thP lnPt i nt r r·2c tion, ~? Y n0rd ACCE~~ tc the lingusgr dr f i~ition to ~ id ir the un drrP t ~ nd irg c f rrror m-:sr. pgr:s .

Intrr~rtior 9 Phew~ on~ typ~ of que~ticn thFt providr s ~ccc ~P to th~ underlying :o tructures . The rePpons£ to t his inp~ t indicPLEs both ~ord s ~ nd phrr!Es th< t m?y bP substi tut r d for <DEPAPTMENT­ NH~ E> .

G. EXPLlClT SUB$'! JTUTlON~:

When <.> user ~o: i shr~ to r· sk somr f"imp lP var iant of rn <"< rliEr qursticn but is not in t.hr correct context for using rll i ps is ( e.g., there f re intrrven!ng sentrncrs), direct rrfercncc may br m2dr to t he rrrli·r i nput, a s i s illustr2trd by intrr2·Ct i on 10. Such r·e frrrn ce ~ and subst!.tuti.cns m~ y SPVP t yp in~ Fnd so r cd ucr both the usrr 's work end thr likelihood of typinv errors. lhi~ if 2 st 2nd<>r·d fr i'tllr f' of lNTERLISP r nd is not uniquP to LIFER.

H. PRONC~il NFL REFERENCE

The r escl ut ion of 11 n3phoric r·c f cr·en:?r , r spec iFlly pronouns, prfs~nt~ complex probl rms for lenguagr processing sy~t ems.* LIFER h ~ s no m2gic P ns ~rrs to these problFms, but does provide f<c ilit ies for hrndling somr of the simpler cases . Onf' such C<.:'lf· i~ illu~trPtfd by intcrc: c tion 11.

I . DEF lNl NG SYNONYMS

Jn i nteraction 12, thr user ag2i n nt t empts to use COI>iPSCJ il nd e>gain rr cPiVP! ?.n error mf"ssrge . It m~y very \-'ell be thPt he is ~ccu~tomed to using this ?bbrrviFtion for computer' science <nd does not W?nt to i!da pt to ?ny of thr synonyms curTPnLly <'CCFptPd by t.hP systf"m. Ra ther, hf' want~ the system to <.<dnpt. to HI S pn:fPrFncrs . Ir. int~r2ct.icn 13, thF user tell~ thF sy~tem tc define CO~PSCI l i ke CS. iHI Hence forth, the s f" ~o.·ords ~o.ill bf' ::ynol'y:ts.

* Sf'f" Grosz (1977) for Pn int.ere!ting discussion of dl scoursc pr'oblems ?nd sophistic?t.ed mcchc. nisms for dFaling with th~m .

Jr. inte·r flc tion 1~, into·;:;cticn 12 is r·f"itwoiH'd ttn·ough lNH.RL ISP' s R~DO f"<' t t:rc. Tnif· t~ m c· , COI'iPSCl is ~ndF'rftcod. Jn i nt cr<:c tion 1:, CO~ ; PSCJ ls used in~ r ew input.

J. Dt.f"iNJNG PARAPHRASES

1h" s yr.onym fr-;=t ur.- pn .sf r.tco '.bcve c. ll c~· s LIFER to ~d< pt t o lndi viduPl ll~rrs by lrPrnir.g new r:ord~. Tnf' p<·r~phr 7 SP f p<> tL·re Pllo..,~ LI FER to A~8 pt to nFk gr[ mmEt icPl ccnetruc tions. fer exampl e. P user mPy grow tlr.-n cf typing syntPct!r~lly "correct" Engli sh cu~riP! ;=no wish to usc P.r·~ ~ bbrf'Vi?tcd form<l t. . Jn int cr<·c t'ior. 16 , thr­ user r> tt cmp t:o t o use 2 c cnd r n~e d formet 2nd i~ confrontEd ..,it h rn rr ror mrss2gc . In inter?clion 17 , ~ n ordin~ry Ene.l ish const ruc tion i s rmplcycd to tell thE' ~. yst"'m th ~ t thE' Pbbrevicttd fcr·m i s ncncefor·th t,c be rcc<.pt nl is lfg it imt tf. LJE'ER 2n~lyzes thr ~pFcific prr Pphresc it h E ~ b~e n givrn c~ s an f:!X?mpl c , ~rrk inp. tC' ~t=lll:"r;-· .Lizr tb.-: p,-n· ph r·r>~ ir.g tc otr.Fr· cr ~ e :: . (!>:or( ~o .. j ll be s<id about this l ~tfr . ) Production r ule s ~hewing th~ r r sults of this gen€rPli~~ tion are printed for the bfre f it of thf' mer~ :oophlst!cPted u!·r.

ln int£r~ction 12 , the new 2bbrevi EtPO form2t is tcst rd . J~tcr2ct ion 19 illustr~te ! En elllpUl'i'l o pursicin b 2 s~d on the t· se t·-defined form2t . l ntEr?ction 20 illu:otrnt£s thE fact th?t LlFER h2s gE·nrr?li2Ed the o:·igin<l pPr aphr<·SE cxFmplc to cover other ebbrFvir tfd construct i ons that er r !imilFr.

lntrr6cticns 21 ~ nd 22 prev iae further illustrAtions of LIFER's pPrEphrE! C Pbili t y. Through i nteraction 21,

DUMPALL x

comrs to hRv~ the ffi !Fning 1NDJCA1E 1HE lD, POSITION, DEPARTMENT, .AND SP.LARY 01' x

K. ACCeSSI NG ~ .I:1Q.a Ll1NGUAGE

1hP u~ e r who knows JNTERLISP mpy wifh to mix i ntr r 2ctions with the Ll FER pa r~rr ~nd interPctions 1-'ith lNTERLJSP. As illustr at ed in interection 2~, this i~ €i'Sily done by pr E'cPding inputs for INTERLISP with the s ymbol "!".

'* Synonyms m2y 2lso be drfined thr ough the mor·f7 genPrPl concept cf p? r?phra!P. A pa r2 phr~se inter2c ticn equiv alent to thE use of synonyms in inter2ct ion 1 ~ is thE following:

1?-Let "How many assoc i a t ( professors 2re there i n the COt'.PSCl dep;;rtme.nt" be a paril phrasf' of "Ho..,, m"ny 2ssociate pr-ofessors c. rf! the rE: in thP CS dEpa rtment."

PARSED!

MAY LIFER ASSUME THAT "COMPSC1" MAY AL\o.J!YS BE USED

FOR "CS"

( 1 YPE YES OR NO)

YES

<DEPP.HTMENT-NAME> => CS finished

14- ...

L. PROVIDJNG COMFORTABLE LJNGUJSTlC COVERAGE

Jn the fin:cl 11r12lysi s, t hP l!'o~t import?nt pircr cf humi'n enginreril"g for unrs i~ th.:ot of ~upplying ~n i ntrr fEcr languPgr covfring the rEngr of ljngu.i!'Otic str·ucturrs rredf'-<i to communici't~ com fortr.bly ;,it!l thr r:pplic,.tion 1<0ftOJ< r-E. Such f~Pturr~ 8 ~ ~pelling correction 8nd ellipticrl procr!sing, al1.hough importPnt, cn n nEvrr m~kr up for d~ficirnctrs in basic l i ngui~t . i c c? p2bilit i e!.

Given the currr nt slate of thr <rt In l~ngua gr procr~sing, it 1mu1d br futil e to .~tt.r. mrt to pr'ovidc "'dr:finitiv· specHic?tiOI" of Engli.sh h2ving sufficient grneralit.y to covEr all potrntiFl PpplicAtions. LJF~R' s rppro~ ch to adrqu2te covrrpge is not to pursue & de finitivr sprcificetion , but rathrr to supply th~ framEwcrk, guid&ncr , ?nd mi"Ch:'!nisms thct ;; l lN· :>n i rl f:'rf.~cr buildFr, in ? rP P son ~bl e emount o f timt , tc c r PPtF R solid, pr actic?bl e , speciPl purpo!E JangPRgr df:fin i tior, ccvprjng thE sprctrum of linguistic structur'P! most relt'Vc>nt to z pn·ticull'r ;-pplici.>ti on .·

No ~ ttf'mpt c~>n be made hrre to dPtHil th~ particul a r !et of interFctive func tions that LIFER provictPs for spt'cifyi ng Pn ?pplication lc>ngu?ge,** but H . fpw ke y points mr y be menti0ned:

• ( 1) lnter·facP bu i ld l" rs ~·ork Fi thin the fram~work of INTERLJSP, F powerful Fnd flexible host langu?ge Fith advanced debugging f~ cilitiPs. Lo w~r l evel l e nguagP~ may ~?ve fpster ~xEcut ion, but fl exibil ity ~nd progr?mming c?se 2re what count in building workable systems with rPason~ble 8mounts of e ffort.
• ExtPnsions 2nd modificPtions tc the lFnguPge speci ficPt ion m?y be fr eel y mixed with csll s to the pRrser . There is no gr'Fmm<> r compil aU on phase . This allows i ntc·rf<·CE: bui lder! to opPr?tP in a rapid, extend-and­ test modc , and supports fe ?tur<·s thFt modify t he l angu2gr at p<1 rse time , such ;os thoc p?r?phr c>se r.
• ( 3 ) ThF. interf?ce buildr r is isol~ted from the intern2l structures that LIFER builds for purposes of incrPasing p?rsing dficif'ncy. ln p;or·ticulc>r, thE' user communic;ctE:s ~:i.th LIFER in terms of simpl e production rules mc>i nt <> ined internally <'! tr8nsition networks (Woods 1970).
• LIFER hc> s 2 powPrful grcmm?r-edi ting facility (which usel' the lNTERLJ.SP editor).
• LIFER hc>s a package of functions for grammHr .interrogation and debugging.
• Elliptical constructions erE' handl ed r.utom"tically and so neE'd never bP considered by thP interf2ce builder.

· Speci?l purposP languages are pe rhaps most e?sily created with LIFER by adopting the notion of 8 "semcntic .gri'lmm;or," ~> S r:dvocated by Brow-n and Burton (1975).

·· A thorough discussion of this topic is contained in The LIFER Manual (Hendr i x, 1977).

• (~) l~erE iz ~ r!~sonF bl r mP nu~ l dEscribing how tc u~c the system.

l ll JMPLE~EN1~TJCN CF fPEClA L FEATURE~

ThiP src tion pr·tLnts Fn ovrrvirw of LlFER 'e lmpl cm~nt e tion of th~ !pr ll i ng correction, <l lipt.ic <> l ~rocrssor, ?nd P<' l <O phrrser .

P. lt'.PLEt·:EN1P1lCN OF ;Pt.LLlNG CQHRECT.i(oN

Ll.FER u:o r- ~ " l f'ft - to- right pPrS€r follo>.ing ~ simplificPtion of the ATN systrm of ~oods 11 9~0). E<: ch timE th<. p<crs1r discov e r~ lr1 c- t il c ;o n ro longer follow transition~ Plong t~r currrnt p~th, it r-ecords the f;;ilur'r on,. f? il.roi.nt li:o.t. E:;-cr. entry on thi! llst indicntf'! thf st2tr of thr system ~!lFn th~ fAi lure occurrFd (i.r., the position in tn· trPns ition net Pnd \he v?lUES of v"rious stBcks 2nd registers) end th~ currfnt position in the input string . Loc:> l ;cmbigdtics and fFl~c pr ths m?k~ it quite norm' l for f <' ilpoints tc be not.Fd E'Vrn when P pFrfectly rc cr pt r bl~ irpul is procrsscd.

lf F complrtr pfr!E is found for en input , the f<'ilpoint! <' rf ignorc-d. !Jut if rn input c;onnot. bF p2rsed, the list of f r ilpcints is used by thE spPlling corrector , ~hic h sr lrcts those feilpoints ?ssocia tca ~ith thE rightmost position in thr input at whi ch (Ri lpoint s were r~cordra . It i! e ssumed that fa ilpoints occurring to the lf:'ft were no t caused by s pelling er ror~, sincE: ~orne tr~nsitions using the words at those position! must h<:v< beEn succr:s~ful for· t.hErf' to be- fail points to their right.

ThE spelling corrector further rE~tricts the rightmost feilpoints by locking for c a ~e~ in which ? rightmost fc>ilpoint G is domina tFd by Pnot her rightmost fHilpoint. F. G is dom inateo by F if G ie a f2 ilpoint in r.; subgrcmmar that. 1-12:0 PUSHt·d tc in 2 futile ?ttempt to follow ~ PUSH arc from F. Since G end F ?rf:' both rightmost f'2ilpo ints , G represents n stPll at thP start node of the PUSHed-to subgrammar. (Had any transition been made, G would be to thE right of F.) Hence, if F is re~t a rtcd, G is r eattempt ed PS one means of transferring from F. G, ther~forr, does not nee-d tc be cons iderEd indFpendentl y. All domi.n? ted rightmost fc;il poi nts <lre dropped fr·om considera tion.

Working with the rightmost, domin~ting f c ilpoints, the spelling corrector examine~ th( associated ?res to find 211 categori es of wor ds th~t woulj allow a transition. (Fer PUSH zrcs, this requires an exploration of subgrammars.) Using the lNTERLlSP spelling corrector , the word cf the input string ?ssociated with the rightmost fail poicts is compa red with the lexical items of thE' catPgories just found. If thE "misspell ed" word is sufficiently simil r.r to any of these l exicc>l items, the- closest metch is substituted. F<~il points associ;: te-d with l exical categorie·s that include t he new word are t hen sequentially restert€d until onE' l eads to a successful parse. (This m~ y produce more spelling correction further to the rir,ht .) If illl rcstilrts f?il, othE:r close lexical items Pre substituted for the "misspelled" word. lf these elso fAil, LIFER prints an error rness2ge.

LIFER encourE~Ef the use of semantically oriented syntactic cetegories, such as <EMPLOYEE> and <DEPARTMENT-I'AME>, r;other then s.uch st2nd2rd cPter,ories as <NOUN>. The usc of these more !pecialized categories greEtly fPcilitatef spFllin~ correction by severely restricting the number of - possibly vPlid ~ords ~t any point in the parse.·

E. IMPLEMENT/\ TION OF ELLIPSIS

LIFER's m!'chanism for tree>ting rlliptic<'l inputs takes advRntege of the e~sumption that specificPtions for ~pplic2tion languages tend to encode P corsidPrable 2mount of semantic irformPtior in the syntactic categories. Thus, similar synt2ctic constructions tend to be simil<'r semantically. LIFER's treptment of ellipsis is based on this notion of si.mU.?rit.y. During elliptical processing, LIFER is prepared to accept any string of ~·ords that is synti'ctically <Jn::-logou:;< to any contiguous substring of words in the laft input .. (I~ the last input was elliptical, its expamnon 1nto e complete sentence is used.)

LIFER's concept of analogy <ppeals to the ::ynt.?x tr<e of the LAST input th?t ;.;es successfully en:>ly:z.ed by the system. For <>ny contiguous substring of words in the LAS1 input, an "anPlogy pattern" m~y be defined by an abstraction process that works backwc. rds through the old syntax tree from the ;.;ords of th10 substring tow11rd the root. ~h~nevcr ~he syntax tree shows a portion of the sub~tring to be a complete expansion of a syntactic cet.egory, the category ne>me is substituted for that portion. The analogy pattern is the final result sfter all such sub~titutions.

For example, consider how an onalogy pEttern m?y be found for· the substring OF MARTIN DEVINE,

~~~~~-!~e syntax tree·· shown in Figure 2 for a

* An exc-mple LIFER system (described by Sacerdoti, 1977) has a vocabulary of over 1000 words, excluding numbers and coded symbols. This vocabulary is divided e>mong 131 categories, 113 of which contain 10 or less .words. 15 categories contain 11 to 50 words, and the largest contains 144.

·· "PRESENT" is used in the sense of "to show for inspection."

previou~ input, hH~T IS 1HE SALARY 0F MARTIN DEVINE? Since the !I'.ARTH. DEVINE portion cf the sub~tring is a complete f~xpanslon of <NAME>, . thE­ sub!trirg is rewritten as OF <NAM~>. Simil~rly, sJnce <EI'IPLOYEE> EXp<.n<is to <NAI'IE>, the subst.rir.~r is rcwritten 2s CF <i~PLOYEE>. Since no oth€r - ~ortior.s of the substring are complete expansions of other s.yntactic ca tegoriEs in the tree, the process stops a nd OF <EMPLOYEE> is accepted PS the most llfneral 2nelogy pa ttern. lf the current input matchPS this analogy p?ttern, LIFER ~ill accept it zs :> legit imE>tf' <11 iptical input. F'or €Xi'mph, the· analogy p2ttern OF <EMPLOYEE>, extract~d from the lPst input, may be used to match such currFnt . elliptic~! inputs PS

OF ERIC JOI:NSON OF EMPLOYEE 494-81-7207 2nd OF PROfESSORS IN THE l'it.TH DEPAHTMENT

Note th2t the fXp<·nsion of <~MPLOYE.E> ne ed not pPr<>llel its expa ~sion In the old input that originated the analogy pattern. For example, OF EMPLOYEE 494-81-7207 is not metched by expanding <EMPLOYEE> to <NAME> but by expending <EMPLOYEE> to EMPLOYe£ <I D-~U~IBER>.

To compute responses for elliptical inputs matching OF <EMPLOYEE>, LH'ER -..crks its I>'<'Y back through the old syntax tree from tr:e common p.:rent of OF <EMPLOYEE> toward the root. First, the routir.e for computing the value. of an <1TE~1> from constituents of the production

<ITEM> => THE <AT1RIBU1£> is I nvokcd, using thE' new nl ue of <E~. PLOYEE> (which appe~red in the current elliptical input) and the old value of <ATTklBU1E> from the l ast sentence. Then, using the newly computed v2luc for <ITEM> end thc old value fer <PRESENT>, z ne-.. value is simil~rly computed for <LIFER. TOP.GRAMMAR>, the root of the syntax tree.

Scme other substrings with their essoci<"ted analogy pet tErns a rf' shmm bfloli, illong wi.th possible new ellipticBl inputs matching the pet terns.

substring:

P<'tt.ern:

a m?tch:

substring:

pa ttern:

a m2.tch:

substring:

pattern:

a match:

substring:

pattern:

a match:

THE SALARY

THE <ATTRlEUTr;>

THE ftGE AND DATE HIRED

SALARY OF MARTIN DEVINE <ATTRIBUTE> OF <EMPLOYEE>

AGE OF CS .SECRETARJES

WHA1 IS THE SALARY <PRESENT> THE <ATTRIBUTE> PRINT THE DATE HIRED

wHAT IS THE SALARY OF MARTIN DEVINE <LIFER.TCP.GRAMMAR> [any complete sentence]

For· purposes of efficiency, LIFER's elliptical routines have been coded in such a way that the ~ctu2l generation of analogy pBtterns is avoided.* Nevertheless, the effect is conceptually equivelent !~-~!!~~pting parses based on the analogy patterns of rFch of the contiguo~s ~ubstrings of the last input.

· [Footnote is printed on next page.]

C. lf:JPLEMENTATION .Q[ PARAPHRASE

LIFER's pc>rc>phrase m€chanism also takes ?dv8nt age of sem<mtic<~lly oriented syntact.ic cat~gories end m2ke·s use of syntax trees. In the typical cc>se, the parc>phr?s·er ls giv ~n a model sentence, ~hich the system can already understand, and 2 paraphrc>se. The paraphraser's general strategy i s to ?nalyze the model sentence and then look for similar structures in the paraphrase strinp;.

1 · ~ ]tliQ ..t:1tlhsW.

In particular, the paraphraser invokes the parsE:'r to produce a syntax tree cf the modecl. Using this tree, the paraphr?ser de.termines ell proper subphrases of the model, i.e., all substrings th~t a re complete exp~nsions of one of thP syntactlc cc>tegories listPd in the tree. Any of these model subphrases th2t also ? pp~a r in the pa r ?phrase string are assumed to pl?y the same role in the paraphrase c>s in the model itself. Thus, the semPntically oriented syntactic c2tegories that account for these subphrases i.n the model 2re reused to account for the corresponding subphrases of the pa raphrase. MoreovFr, the relc>tionship

· [Footnote from last page.] Abstractly, the actual algorithm is as fellows. If the last input w<>s per~ed by the top-l evel production

<LIFER.TOP.GRAMMAR> => <X1> <X2> ... <XN> then elliptical processing begins by attempting to match the new input to the left portion of the right side of this production. If the new input matches <X1> ... <Xj>, Ie2ving <Xj+1> ..· <Xn> unused, then <Xj+1> ... <Xn> are a~sumed from the old input. If the new input does not match the left portion of the pattern <X1> ... <Xn>, then the process restarts, using the left-t.runcnted pe ttern <X2> ..· <Xn>. In general, if the new input matches subpattern <Xi> ... <Xj>, then the old <X1> ... <Xi-1> and <Xj+1> ... <Xn> are used to expand the elliptical input into r new top-level sentence.

The process is complicated by the fact that <~ny of the <X> may itself have been expended in the last input by a production

<X> => <Y1> <Y2> ... <Ym>

If t.he new input does not account for <Xi> ~;hen attempting the m~tch <Xi> ... <Xn>, then <Y1> ... <Yn> is substituted for <Xi>, with the hope that the elliptical input may begin somewhere in the middle of the expansion of the old <Xi>. Only after the <Y> have been exhausted by left truncation tdll <Xi+ 1> become the 1 e ft.-most symbol for a matching attempt. Similarly, if <Xi> ... <Xi+m> has <>ccountcd for the left portion of <>n elliptical input, but <Xi+m+1> does not match the left part of the remainder of the input, then the exp;>nsion .of <Xi+m+1>, taken from the last input, is substituted for <X+m+1> and the match continues. As sometimes happens, the elliptical input may end somewhere in the middle of the expansion of <Xi+m+ 1>.

between the syntectic categories th?.t is expressed in the synte~x tree of the model forms a basis for Establishing the relationship between the corrrcsponding syntactic units inferred for the par a phrase.

<>. Defining ll. Pare> phrase Production

To find correspondences between the model ilnd the paraphrase, the subphreses of the model ~ re first sortFd. Longer phrc>ses have prEference over shorter phrases, end for t-;.·o phrases of the same length, the leftmost is t aken first. For example, the sorted phrEses for the tree of Figure 2 are

1. <ITEM>

THE SALARY OF MARTIN DEVINE

1. <PRESENT>

WHAT IS

1. <NAME>

MARTIN DEVINE

--not used

• 4.

<EMPLOYEE> MARTIN DEVINE

1. <AT1RIBUTE> SALARY

Since the syntax tree indicates <EMPLOYEE> => <NAME> => MARTIN DEVINE, both <NAME> and <EMPLOYEE> account for t.he same subphrPSE. For such cases, only the most general syntactic category (<EMPLOYEE>) is considered.

BEginning with the first (longest) subphrase, the subphrases are matched against sequences of words in the peraphrase string. (If a subphr r. se matches two sequences of words, only the leftmost match is used.) The longer subphrases are given preference since matches for them will lead to generalizations incorporating matches for the shorter phrase~ cont.c>ined within them. Whenever a m2tch is found, the syntactic category a.ssociated with the subphrese is substituted for the matching word sequence in the paraphr2.se. This process continues until matches have been attempted for all subphrases.

For exa.mple, suppose the paraphrase proposed for the question of Figure 2 is

FOR MARTIN Dt::VINE GIVE ~i E THE SALARY Sub phrases 1 and 2, 1 is ted above, do not match substrings in this paraphrase. Subphrase 3 is not considered, since it is dominated by subphrase 4. Subphrase 4 does match a sequence of words in the paraphre>se string. Substituting the associated ca tegory ne>me for the word sequence yields a new paraphrase string:

FOR <EMPLOYEE> GIVE ME THE SALARY Subphrase 5 metchvs a sequence of words in this updated paraphrase string. The associated substitution yields

FOR <EMPLOYEE> GIVE ME THE <JITTRlBUTE> Since there are no more subphrases to try, the structure

<LIFER.TOP.GRAMMAR> =>

FOR <EMPLOYEE> GIVE ME THE <ATTRIBUTE> is created 2s a new production to account for the paraphr?se.

b. Defining ll. Response Function .fQr. ~ Pa ra.phrase Production

A new semantic function indicating how to respond to inputs matching this paraphrase production is programmed automatically from information in the syrt<>x tree of the model. In p<>rticular, the syntax tree indicates which productions were used in the modl'l t.o expand various syntactic categories. Associated with each of these productions is a f~nction fer computing the interpretation of associated subphrases from subphrase constituents. The paraphraser reuses se>le>cted fun:!tions of the model to create a rew function for the paraphrase> production. The m2nne>r in which this is done is best illustrated by example.

Continuing the example of Figure 2, the syntax tree indicates that the production

<LIFER.TOP.�RA~MAR> => <PRESENT> <ITEM> was use>d. Associated with this production is a function F1 (not shown in the figure , but referenced in the act ual tre>e ) that computes 2 value for <LIFER.TOP.GRAMMAR> from the values of <PRESENT> and <ITEM>.* Using the notation "#<X>" t.o indicate "the value of <X>," the role of F1 rney be expressed by the equi1tlon

#<LIFER.TOP.GRAMMAR> = F1(#<PRESENT>, #<ITEM>) Another production indicated by the> model syntax tree is

<ITEM> => THE <ATTRIEUTE> OF <EMPLOYEE> Th is production is associated with a function F2, where

#<ITEM> = F2(#<ATTRIBUTE>, #<EMPLOYEE>)

The paraphraser must define a new function FN for the paraphrase production

<LIFER.TOP.GRAMMAR> :)

FOR <EMPLOYEE> GIVE ME THE <ATTRIBUTE> Moreover, the valuf': computed by FN must be the same as the value computed as a response to the model sentence. Since the categories <EMPLOYEE> and <ATTRIBUTE> appee>r on the right side of the paraphrase. production, the paraphraser assumes that FN is a function of #<EMPLOYEE> and II<ATTRIBUTE>. Since FN must produce the same value as produced by the model call to F1, the paraphraser assumes that

FN(ii<EMPLOYEE>, #<ATTRIBUTE>) F1(#<PRESENT>, II<ITEM>)

The syntax tree indicates that the expension of <PRESENT> is independent of the expensions of <EMPLOYEE> and <ATTRIBUTE>. Hence, the p~raphraser assumes #<PRESENT> to be a constant in the computation of FN. That is, the value of <PRESENT> used in the model will alwAys be used as the value of <PRESENT> in computing FN in terms of F1.

In contrast, the> syntax tree shows <ITEM> to incorporate both <EMPLOYEE> and <ATTRIBUTE>. Hence, both of these parameters to FN may influence #<ITEM>. Function F2 indicates the nature of this influence. Therefore, in the equation defining FN, the paraphraser replaces ii<ITEM> by the expression that computes it:

FN(ii<EMPLOYEE>, #<ATTRIBUTE>)

F1(#<PRESENT>, F2(11<ATTRIBUTE>, II<EMPLOY~E>))

· Since <LIFER.TOP.GRAMMAR> is the sentence-level syntactic category, this value is, in fact, the response to the total input.

This no; equllt.ion comr:-letdy spPcifies FN in t~Tm1' of const<·nts, form2l par?.mEter·s of FN, &nd pr eviously defined functions. Thilt is , FN .is defined in terms of the constant #<PRESENT~ (t~ken from the origir<>l modd input), the forrn?l p2ramders ii<EMPLCYEE> and II<ATTHIEU'lE>, <- nd thf' previously defined functions f1 end f2.

2. Gru.ter GeneraLization

The goel of the pa raphr ase routine is to account for the peraphr?se in the most generel terms possible, so th2t new constructions created to account for 2 particul r>r' pAI'aphraH ~Jill cover 'J mc.ximum rumbPr of n'?w input r:-ossibilitie1'. For certain C<?ses, the coverage produced by the basic method presented above is extended by the pa r il phr<:ser as follov;:c. SuppoH sorH rncd<l 1'Ubphrese S thAt matches a substring of the parephr<'se is 2ssociated with the syntactic unit <M> in the model syntax tree. Such an <M>, in turn, will Pppear in the tree as a direct component of a more gener2l unit <G> such th2t

<G> => X <M> y

Kh@re x 2nd y are some (possibly empty) sequences of linguistic units. Since the ~ubphr H EP for <G> itself was not mptchc·d in thE' pBraphr<.se, eithEr the x or the y or both did not appea r in thf pcraphres~ ( et least not in the necessFry juxtcoposit ion to <M>). Nevertheltss, if the grammar a llows the production

<G> => <tv:>

~nd if the valuE aseigned to <G> is the same for beth

<G> => <M>

and <G> => x <M> y

then <G> is substituted for <M> i~ the paraphrase to produce a construction with broader covcr8ge.

For ex2mple, suppose that the mod~l input

is

WHAT IS THE SALARY OF Etv:PLCYEE MARTIN DEVINE end that the syntax tree is likE that of Figure 2 except that <EMPLOYEE> exp~~ds ~s EMPLOYEE MARTIN DEVlNE

<EMPLOYEE>

Suppose further that the paraphrase is again FOR ~1ARTIN DEVINE Gl VE 1-JE THE SALARY Unlike the earlier example in ~1hich <EMPLOYEE> was substituted for MARTIN DEVINE, the substitution algorithm of the last section now only a llows <NAME> to be substituted. The resultant parephrilse is

FOR <NAME> Gl VE t-iE THE <ATTRIBUTE> This structure accounts for the given paraphrPse,

but not for

FOR' PROFESSOR MARTIN DEVINE GIVE ME THE AGE

However, using the generalization process just outlined, if the system allows

and if the value of <EMPLOYEE> defined in this fashion is the same as the va lue using

<EMPLOYEE> => <NA~E> <EMPLOYEE> => <TITLE> <NAME>

then <EI'iPLOYEE> will be substituted for <NAME> in the paraphrase structure to produce FOR <EMPLOYEE> GIVE ME THE <ATTRIBUTE>

Thi.~ more gene r al construction ~ccounts for the input.~

FOR PROFESSOR MARTIN DEVINE GJVE ME THE AGE FOR El'JPLOYE:E 205-56-1620 GIVE ME THE DATE HlRED FOR ~ATH DEPARTMENT SECRETARIES GIVE ME THE ~ALARY

Confinement 1Q Subgr<>mmers

Consider p;:·r<>phr <> se·s of thE- form "x y z", wh f'r e the model i:: of the form "x S y" and S is a pr·oper subphrese: essocieted with a synt?.ctic category <C>. The peraphr8se r traps this type of condit i on end esks the user if y is Rlways a pa rephra::e of S or is ~imply 2 pa raphr~ ~e in the context of x and y. If the user indic~tes a context dependency, then processing proceeds a s usual. If the user indicPtes that y is a p?raphrPse of S in every context, then LIFER will makE y 2 pPraphrese of S in the subgramrr.ar accounting for <C>. The influence of this p?raphrase will then be felt everywhere that ca tegory <C> is used. (For example, see footnote of section II-1.)

JV CONCLUDING REMARKS

During the l as t ye2 r, 8 number of interfacEs hav£ been constructed using LIFER, and the rEsponse fr·om users has been enthusiastic. It is worth noting tha t interfaces for sever<>l of the simpler applications took less than ? week to create. Most of these simple interf?ces were to sm.?. ll, relctional data bases. However, interfaces were also con~tructed for c t ask scheduling and r esource allocating system, ;: compute·r-b2sed expert system, and <: program that answers questions ?bout the rel 2t ionships bet\.:een procedures in <1 large body of computer code.

LIFER h?s also been used in creRting more ambitious interfaces. One of these, developed with sever?l man-months (but not several man-ye<~rs) of effort, is the INLAND component of the LADDER system described by Sacerdoti (1977). This system, which incorporates a gr?mm<: r with over 600 "productions" and a lexicon with over 1000 words (r.ot to mention numbers and numerous coded symbols), provides natur~l langu8ge access to a relatively large collection of data that is distributed among multiple remote computers on the ARPA net.

In summ<'lry, the experience with LIFER indicates that genuinely useful natural language interf<~ces can be created and that the creation process takes considerably less effort than might be expected. Hum<:n engineering has played a key role in making this possible. The application of simi.lar engineering to more sophisticated l11nguage processing technology, such as that developed in the SRI Speech Understanding Project (Walker 1976), promises to produce pr;:ctical systems h<>ving much ~reater fluency in their user's natural language.

PCKNOwLEDGEMENTS

The work r eported herein 10211 conducted ur:der SRJ 's Internal RN!P'rch ar.d Dev<'lopment Progr·am.