Transactions of the Association for Computational Linguistics, vol. 3, pp. 571–584, 2015. Action Editor: Chris Callison-Burch.
Submission batch: 5/2015; Revision batch: 9/2015; Published 12/2015.
2015 Association for Computational Linguistics. Distributed under a CC-BY 4.0 license.
c
(cid:13)
SemanticParsingofAmbiguousInputthroughParaphrasingandVerificationPhilipArthur,GrahamNeubig,SakrianiSakti,TomokiToda,SatoshiNakamuraGraduateSchoolofInformationScience,NaraInstituteofScienceandTechnology,Japan{philip.arthur.om0,neubig,ssakti,tomoki,s-nakamura}@is.naist.jpAbstractWeproposeanewmethodforsemanticpars-ingofambiguousandungrammaticalinput,suchassearchqueries.Wedosobybuild-ingonanexistingsemanticparsingframeworkthatusessynchronouscontextfreegrammars(SCFG)tojointlymodeltheinputsentenceandoutputmeaningrepresentation.Wegener-alizethisSCFGframeworktoallownotone,butmultipleoutputs.Usingthisformalism,weconstructagrammarthattakesanambigu-ousinputstringandjointlymapsitintobothameaningrepresentationandanaturallan-guageparaphrasethatislessambiguousthantheoriginalinput.Thisparaphrasecanbeusedtodisambiguatethemeaningrepresenta-tionviaverificationusingalanguagemodelthatcalculatestheprobabilityofeachpara-phrase.11IntroductionSemanticparsing(SP)istheproblemofparsingagivennaturallanguage(NL)sentenceintoameaningrepresentation(MR)conducivetofurtherprocessingbyapplications.OneofthemajorchallengesinSPstemsfromthefactthatNLisrifewithambiguities.Forexample,eventhesimplesentence“WherecanweeatasteakinKobe?”containssyntacticambi-guities(“eatinKobe”or“steakinKobe”?),quan-tifierscopeambiguities(dowealleatonesteak,oreacheatonesteak?),andwordsenseambigui-ties(isKobeacityinJapan;oranNBAbasketball1Toolstoreplicateourexperimentscanbefoundathttp://isw3.naist.jp/~philip-a/tacl2015/index.html.player?).Previousworksusingstatisticalmodelsalongwithformalismssuchascombinatorialcat-egorialgrammars,synchronouscontextfreegram-mars,anddependencybasedcompositionalseman-ticshaveshownnotablesuccessinresolvingtheseambiguities(ZettlemoyerandCollins,2005;WongandMooney,2007;Liangetal.,2011;Kwiatkowskietal.,2013).MuchpreviousworkonSPhasfocusedonthecaseofansweringnaturallanguagequeriestoadatabaseoffacts,wherethequeriesgenerallytaketheformoffullsentencessuchas“WhatistheheightofKobeBryant?”Whileansweringtheseques-tionsprovidesanexcellentfirststeptonaturallan-guageinformationaccess,inmanycasestheinputisnotafullsentence,butsomethingmoreunderspec-ifiedandungrammatical.Forexample,thisisthecaseforkeyword-basedsearchqueries(Sajjadetal.,2012)orshortdialogueutterances(ZettlemoyerandCollins,2007).Specificallytakingtheexampleofsearchqueries,userstendtoomitsomeofthefunctionwordsandgrammaticalconstructsinthelanguagetomakeamoreconcisequery.ThefirstcolumnofTable1illustratesseveralsearchqueriesofthepattern“KobeX”whereXisanotherword.FromthesequeriesandtheirMRsincolumntwo,wecanseethatthereareseveralkindsofambiguity,includingnotonlythedistinctionbetweenKobeascityorabasketballplayerasinthepreviousexample,butalsomoreperniciousproblemsuniquetothemoreambiguousinput.Focusingonthequeries“Kobehotels”and“Kobeflight”wecanseethatitisalsonecessarytoestimatethelatentrelationshipbetween
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
5
9
1
5
6
6
8
1
2
/
/
t
l
a
c
_
a
_
0
0
1
5
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
572
SearchQueryMeaningRepresentationParaphraseKobeHotelλx(hotel(x)∧in(x,kobecity))HotelinKobecityKobeFlightλx(flight(x)∧to(x,kobecity))FlighttoKobecityKobeHeightheight(kobebryant)HeightofKobeBryantTable1:Exampleofasearchquery,MeaningRepresentation(MR),anditsparaphrase.words,suchas“location”or“destination.”Howeveritshouldbenotedthatifwetakethekeywordqueryandre-expressitasamoreexplicitparaphrase,wecanreducethisambiguitytothepointwherethereisonlyonereasonableinterpretation.Forexample,inthesecondline,ifweaddthepreposition“to”theuserislikelyaskingforflightsthatarrivinginKobe,andifweadd“from”theuserisaskingfordepar-tures.Inthispaper,wefocusonSPofambiguousinputandproposeanewmethodfordealingwiththeprob-lemofambiguity.Hereweproposeaframeworkwhereanambiguousinput(Column1inTable1)issimultaneouslytransformedintobothitsMR(Col-umn2)andamoreexplicit,lessambiguouspara-phrase(Column3).Theadvantageofthismethodisthatitisthenpossibletoverifythattheparaphraseindeedexpressestheintendedmeaningoftheunder-specifiedinput.Thisverificationcanbedoneeithermanuallybythesystemuserorautomaticallyusingaprobabilisticmodeltrainedtojudgethenaturalnessoftheparaphrases.Asaconcreteapproach,buildingupontheformal-ismofsynchronouscontextfreegrammars(SCFG).UnliketraditionalSCFGs,whichusuallyonlygen-erateonetargetstring(insemanticparsing,anMR),weintroduceanewvarietyofSCFGsthatgeneratemultiplestringsonthetargetside.ThisallowsustonotonlygeneratetheMR,butalsojointlygen-eratethemoreexplicitparaphrase.Wethenusealanguagemodelovertheparaphrasesgeneratedbyeachderivationtohelpdeterminewhichderivations,andconsequentlywhichMRs,aremorelikely.WeperformanevaluationusingthestandardGeo-querybenchmarkof880query-logicpairs.FirstwenotethatbaselineSCFGparserachievesreasonableaccuracyonregularquestionsbutwhenthesamemethodisusedwithunderspecifiedinput,thesystemaccuracydecreasessignificantly.Ontheotherhand,whenincorporatingtheproposedtri-synchronousgrammartogenerateparaphrasesandverifythemwithalanguagemodel,wefindthatitispossibletorecoverthelossofaccuracy,resultinginamodelthatisabletoparsetheambiguousinputwithsignif-icantlybetteraccuracy.2SemanticParsingusingContextFreeGrammarsAsabaselineSPformalism,wefollowWongandMooney(2006)incastingSPasaproblemoftrans-lationfromanaturallanguagequeryintoitsMR.Thistranslationisdoneusingsynchronouscontextfreegrammars,whichwedescribeindetailinthefollowingsections.2.1SynchronousContextFreeGrammarsSynchronouscontextfreegrammarsareageneral-izationofcontext-freegrammars(CFGs)thatgener-atepairsofrelatedstringsinsteadofsinglestrings.SlightlymodifyingthenotationofChiang(2007),wecanformalizeSCFGrulesas:X→⟨γs,γt⟩(1)whereXisanon-terminalandγsandγtarestringsofterminalsandindexednon-terminalsonthesourceandtargetsideofthegrammar.SCFGshaverecentlycomeintofavorasatoolforstatisticalmachinetranslation(SMT).InSMT,asynchronousrulecould,forexample,taketheformof:X→⟨X0eatsX1,X0waX1wotaberu⟩(2)whereγsisanEnglishstringandγtisaJapanesestring.Eachnon-terminalontherightsideisin-dexed,withnon-terminalswithidenticalindicescor-respondingtoeach-other.GiventheSCFGgrammar,wecanadditionallyas-signascoretoeachrule,wherehigherscoredrulesaremorelikelytoparticipateinaderivation.Giventhegrammarofscoredrules,andaninputsentence
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
5
9
1
5
6
6
8
1
2
/
/
t
l
a
c
_
a
_
0
0
1
5
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
573
Grammarr0QUERY→⟨givemetheCONJ0,answer(x1,CONJ0)⟩r1CONJ→⟨FORM0FORM1STATE2,(FORM0,FORM1,const(x2,stateid(STATE2))⟩r2FORM→⟨cities,city(x1)⟩r3FORM→⟨in,loc(x1,x2)⟩r4STATE→⟨virginia,virginia⟩Derivations⟨QUERY0,QUERY0⟩r0⇒⟨givemetheCONJ1,answer(x1,CONJ1))⟩r1⇒⟨givemetheFORM2FORM3STATE4,answer(x1,(FORM2,FORM3,const(x2,stateid(STATE4))))⟩r2⇒⟨givemethecitiesFORM3STATE4,answer(x1,(city(x1),FORM3,const(x2,stateid(STATE4)))⟩r3⇒⟨givemethecitiesinSTATE4,answer(x1,(city(x1),loc(x1,x2),const(x2,stateid(STATE4)))⟩r4⇒⟨givemethecitiesinvirginia,answer(x1,(city(x1),loc(x1,x2),const(x2,stateid(virginia)))⟩Figure1:Exampleofsemanticparsing(SP)usingsynchronouscontextfreegrammars(SCFGs).Thelefthandandrighthandsidesaregeneratedsimultaneously.S,thehighestscoringparseandoutputsentenceTcanbecalculatedusingtheCKY+algorithm(Chi-ang,2007).2.2SemanticParsingwithSCFGsInthesimplestformofSPwithSCFGs,γsisusedtoconstructanaturallanguagestringSandγtisusedtoconstructtheMRT(WongandMooney,2006).Figure1showsanexampleofusinganSCFGtosi-multaneouslygenerateanaturallanguagestringanditsMR.Inthispicture,theboldsymbolsarenon-terminalswhichcanbesubstitutedwithothernon-terminalproductions.Productionsendwhenallthetokensareterminals.Thecollectionofrulesusedtogenerateaparticular⟨S,T⟩pairisaderivationD=d1,d2,…,d|D|.WongandMooney(2007)furtherextendedthisformalismtohandleλ-SCFGs,whichtreatγsasthenaturallanguagequeryandγtasanMRbasedonλcalculus.SCFGrulesareautomaticallylearnedfrompairsofsentenceswithinputtextandthecorre-spondingMR,wheretheMRisexpressedasaparsetreewhoseinternalnodesarepredicates,operators,orquantifiers.Inthispaper,wefollowLietal.(2013)’sapproachtoextractagrammarfromthisparalleldata.Inthisapproach,foreachpair,statisticalwordalignmentalignsnaturallanguagetokenswiththecorrespond-ingelementsintheMR,thenaccordingtothealign-ment,minimalrulesareextractedwiththeGHKMalgorithm(Galleyetal.,2004;Lietal.,2013).Then,uptokminimalrulesarecomposedtoformlongerrules(Galleyetal.,2006),whileconsideringthere-lationshipbetweenlogicalvariables.Finally,un-alignedNLtokensarealignedbyattachingthemtothehighestnodeinthetreethatdoesnotbreaktheconsistenciesofalignment,asspecifiedinGalleyetal.(2006).2.3AdditionalRulesWhilebasicrulesextractedabovearequiteeffectiveinparsingthetrainingdata,2wefoundseveralprob-lemswhenweattempttoparseunseenqueries.Tomakeourparsermorerobust,weaddtwoadditionalvarietiesofrules.First,weaddadeletionrulewhichallowsustodeleteanyarbitrarywordwwithanyheadsymbolX,formally:X→⟨wX,X⟩.(3)2Weachievealmost100%F-measureinclosedtesting.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
5
9
1
5
6
6
8
1
2
/
/
t
l
a
c
_
a
_
0
0
1
5
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
574
Thisruleallowsourgrammaranoptionofignoringwordsthatitdoesnotknowwhattodowith.Inaddition,toensurethatallofthefactsinthedatabasecanbeaccessedbyoursemanticparser,weprovidesomeadditionalSCFGrulesbasedonthegivendatabaseoffacts.TheGeoquerydatasetpro-videsadatabaseoffactsrepresentedaslogicalasser-tions.Foreveryassertionprovidedinthedatabase,weproduceasingleruleusingthefunctionnameasthelabelofthenon-terminalandoneparameteroftheassertionastheterminal,dependingontheasser-tion’stype.Forexample,GeoqueryprovidessomedetailsaboutthestateofMichiganwiththeformstate(’michigan’,…),andthusweaddSTATE→⟨michigan,michigan⟩asanadditionalruleinthegrammar.3SemanticParsingofKeywordQueriesAsexplainedinSection1,whenusersinputkey-wordqueries,theywilloftenignorethegrammaticalstructureandomitfunctionwords.Basedonthis,atraditionalSPmodelcanbeproblematic.Togiveaconcreteexample,considerthesynchronousparseinFigure1.Ifwetrytoparsewithonlythekeywords(e.g.“citiesvirginia”)withastandardgrammar,theparserwillnotbeabletorecoverthelatentrelation-ship“loc(x1,x2)”betweenthetwowords.Unfortu-nately,wearelackingevidencetorecoverthisre-lationship,becausethetoken“in”associatedwiththepredicate“loc”willoftennotoccurinakeywordquery.Inthiswork,weperformexperimentsonthispar-ticularvarietyofambiguousinput,bothtoexaminetheeffectthatithasonparsingaccuracyunderthebaselinemodel,andtoexaminewhetherthissortofambiguitycanbereduced.Inordertodoso,weneedexamplesofkeywordqueries.Inthiswork,wesim-ulatethekeywordqueryKbyalteringtheoriginalquestionStomakeitmorecloselymatchthestyleofkeywordqueries.Inparticular,followingtheanaly-sisofLeveling(2010),wemaketwochangestotheoriginalqueries:stopworddeletion,andwordordershuffling.Stopworddeletion,asitsnameimplies,simplydeletesallstopwordsfromtheinputsentence.Weuseastopwordlist(Buckleyetal.,1993),mak-ingafewsubjectivechangestomakethesimulatedkeywordoutputmorerealistic.Specifically,weadd“give”and“show,”whichoftenoccurinstatementssuchas“giveme…”or“showme…”butareunnat-uralinkeywordqueries.Wealsoexcludefromthelist“us,”whichoftenrefersto“UnitedStates,”andfunctionwordssuchas“many,”“most,”and“much.”Wordordershufflingpermutestheorderofthekeywordsremainingafterstopworddeletion,tosimulatethefactthatkeywordqueriesoftendon’thavestrictorder.Firstweshuffledthetokensran-domly,thenhadahumanannotatorfixtheorderofthekeywordsmanually,makingtheminimalnum-berofchangesnecessarytoensurethatthequeriesarenaturalandfluent.Thisproducedasinglekey-wordqueryKforaparticularquestion/MRpairintheGeoquerydatabase,whichwillbeusedtotrainandverifyoursystem.Attheendwewillhavea3-parallelcorpusconsistingof880pairsofkeyword,question,andthemeaningrepresentation.Weshouldnotethatwhileshorteningandreorder-ingareprominentfeaturesofsearchqueries(Lev-eling,2010),thesearenottheonlyphenomenondistinguishingqueriesfromstandardtext.Forex-ample,humanstendtoalsochangecontentwordsintoanequivalentandeasierwordoftheirprefer-ence(Gursk´yetal.,2009).Whilecollectingthisdataisoutofthescopeofthepresentwork,ifacor-pusofrealkeywordinputsandquestionparaphraseswereavailable,itistheoreticallypossibleforourproposedmethodtolearnfromthisdataaswell.4JointSemanticParsingandParaphrasingusingTri-SynchronousGrammarsInthissectionwedescribeourproposedmethodtoparseunderspecifiedandungrammaticalinputwhilejointlygeneratingaparaphrasethatcanbeusedtodisambiguatethemeaningoftheoriginalquery.4.1GeneralizedSynchronousContextFreeGrammarsBeforedefiningtheactualparsingframework,wefirstpresentageneralizationofSCFGs,then-synchronouscontextfreegrammar(n-SCFG)(Neu-bigetal.,2015).Inann-SCFG,theelementarystructuresarerewriterulesofn−1targetsides:X→⟨γ1,γ2,…,γn⟩(4)
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
5
9
1
5
6
6
8
1
2
/
/
t
l
a
c
_
a
_
0
0
1
5
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
575
Grammarr0QUERY→⟨CONJ0,givemetheCONJ0,answer(x1,CONJ0)⟩r1CONJ→⟨FORM0STATE1,FORM0inSTATE1,(FORM0,loc(x1,x2),const(x2,stateid(STATE1)))⟩r2FORM→⟨cities,cities,city(x1)⟩r3STATE→⟨virginia,virginia,virginia⟩Derivations⟨QUERY0,QUERY0,QUERY0⟩r0⇒⟨CONJ0,givemetheCONJ0,answer(x1,CONJ0)⟩r1⇒⟨FORM2STATE3,givemetheFORM2inSTATE3,answer(x1,(FORM2,loc(x1,x2),const(x2,stateid(STATE3)))⟩r2⇒⟨citiesSTATE3,givemethecitiesinSTATE3,answer(x1,(city(x1),loc(x1,x2),const(x2,stateid(STATE3)))⟩r3⇒⟨citiesvirginia,givemethecitiesinvirginia,answer(x1,(city(x1),loc(x1,x2),const(x2,stateid(virginia)))⟩Figure2:Anexampleof3-synchronouscontextfreegrammars(3-SCFG)rulesandproductions.Herethereare2targetsides,oneistheparaphraseandtheotheristhemeaningrepresentation(MR).whereXisanon-terminalsymbol,γ1isthesourcesidestringofterminalandnon-terminalsymbols,andγ2,…γnarethetargetsidestrings.Therefore,ateachderivationstep,onenon-terminalinγ1ischo-senandallthecorrespondingnon-terminalswiththesameindexin{γ2,…,γn}arerewrittenusingasin-glerule.4.2Tri-SynchronousGrammarsforJointParsingandParaphrasingBasedonthisframework,weproposeamodelforjointsemanticparsingandparaphrasingusingtri-synchronousgrammars,or3-SCFGs.Inthisframe-work,inputγ1correspondstoakeywordqueryK,andtheoutputsγ2andγ3correspondtothepara-phraseandMRrespectively.Anexampleofjointlygeneratingakeywordquery,question,andMRwitha3-SCFGisshowninFigure2.Inthiswork,weconstructthetri-synchronousgrammarbytransformingthebasicSCFGforse-manticparsingGintoa3-SCFG.Specifically,wefirstassumethatthesourcequestionγsandtargetMRγtoftheoriginalSCFGbecomethetwoout-putsγ2andγ3ofthenew3-SCFGgrammar.γ1isthenewlyaddedkeywordqueryinput.Duringtheprocessofmodeltraining,wefirstex-tractrulesconsistingofγ2andγ3usingthealgo-rithminSection2.2,thengenerateγ1fromγ2byfirstdeletingthestop-wordsthenrearrangingtheor-derofthewordsbasedonwordalignmentsbetweenthekeywordqueryandtheoriginalquestion.ThisisdonebyassigningeachwordinKarangeofwordsinStowhichitisaligned,thensortingwordsinγ1inascendingorderoftheseranges.ItispossibletohavecasesinwhichtherearesomewordsinKthathavenoalignmentinS,andtheserulesarefilteredout.Finally,weusethetuple⟨γ1,γ2,γ3⟩toformrulesinourtri-synchronousgrammar.Becauseofthestopworddeletion,wemayfindthatsomeruleshaveanemptysourceside,andcon-sequentlycannotbeusedinanSCFG.Forexample,inr3inFigure1,“in”isinthestopwordlist,andthuswillbedeletedfromthesourceside,leavingitempty.Inordertosolvethisproblem,wecomposeallruleswithemptyinputstogetherwiththeirparentrule.Itshouldbenotedthatthisintroducesalargeamountofambiguityintothegrammar,asthecon-tentrepresentedbythedeletedcontentwordmustnowbegeneratedessentiallyoutofthinair,basedonlyonitsparentcontext.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
5
9
1
5
6
6
8
1
2
/
/
t
l
a
c
_
a
_
0
0
1
5
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
576
4.3IntegratingLanguageModelswithTri-SCFGsWhenusingSCFGsformachinetranslation,thepoweroflanguagemodels(LM)toimprovethetranslationaccuracyiswidelyacknowledged.TheLMensuresfluentSMToutputbyassigningaprob-abilitytothetargetsentence.Incaseofn-gramlan-guagemodels,thisprobabilityisdefinedas:pLM(W)=l∏i=1p(wi|wi−1,wi−2,…wi−n+1)(5)wheretheprobabilityofsentenceWoflengthliscalculatedastheproductoftheprobabilityofitswords,dependingonthepreviousn−1words.In-tegratingtheselanguagemodelsmakesthesearchspacelarger,precludingtheuseofthefullCKY-styleparsingalgorithm,butefficientapproximatesearchalgorithmssuchascubepruning(Chiang,2007)orincrementalsearch(Heafieldetal.,2013)canhelpamelioratethisproblem.Wecouldalsoconsiderconstructingaprobabilis-ticLMoverMRTforsemanticparsing.However,constructingalanguagemodelfortheMRislessstraightforwardforseveralreasons.First,theorderofthewordsofMRinthesamerootedlogicaltreewillnotmakeadifferenceinthefinalresult(e.g.foracommutativeoperatornode).Second,whilelan-guagemodelsfornaturaltextbenefitfromthelargeamountsoftextdataavailableontheweb,obtainingcorrectMRstotrainamodelislesstrivial.Ontheotherhand,inourtri-synchronousgram-marframework,inadditiontotheMRitself,wearegeneratingaparaphrasethatnonethelessholdssomedisambiguatingpowerovertheMR,asdescribedinSection1.Thenaturalnessofthisparaphraseout-put,liketheoutputoftheMTsystem,caneasilybejudgedbyalanguagemodel,andmighthavesomecorrelationwiththenaturalnessoftheMRitself.Thus,inthisworkweaddalanguagemodelovertheparaphraseoutputasafeatureofthescoringmodeldescribedinthenextsection.5ParseScoringGiventhisSCFG-basedparsingmodel,wemustnowassignascoretodecidewhichscoresarebet-terorworsethanothers.5.1ScoringFunctionOurscoringfunctionisastandardloglinearmodelwithfeaturefunctionsdefinedover⟨K,S,T,D⟩tu-ples:score(K,S,T,D)=w·Φ(K,S,T,D)(6)whereΦ(K,S,T,D)isavectoroffeaturefunctionsandwistheweightvector.5.2FeaturesForthebaselinemodel,ourfeaturevectorΦ(K,S,T,D)issimplydefinedastheelement-wisesumofthefeaturevectorsforeachruleinthederiva-tion:Φ(K,S,T,D)=∑d∈DΦ(d)(7)wheredtakestheforminEquation(4).Wescoreeachbasicruleusingfeatureswidelyusedintranslationasfollows:•ForwardProbability:Thelogprobabil-ityofsourcesidegivenallthetargetsidesp(γ1|γ2,…,γn),calculatedbasedonrulecountsinthetrainingcorpusc(γ1,…,γn)/c(γ2,…,γn).•BackwardProbability:Similarly,thelogprob-abilityofalltargetsidesgiventhesourcesidep(γ2,…,γn|γ1).•JointProbability:Thelogprobabilityofthesourceandtargetp(γ1,γ2,…,γn).•TerminalRule:Equaltooneifthereisnonon-terminalsymbolintherule.Thisfeatureisuse-fultodecidewhetherthemodelprefersentirelylexicalizedrules.•Deletion:Binaryfeaturefordeletionrules.•KnowledgeBaseRule:Binaryfeatureforrulesproducedfromtheknowledgebase.Fortheproposedtri-synchronousgrammarwithLMverification,weadditionallyaddthreefeaturesdefinedoverthegeneratedparaphrase.•LanguageModel:Countstheloglanguagemodelprobabilityoftheparaphrase.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
5
9
1
5
6
6
8
1
2
/
/
t
l
a
c
_
a
_
0
0
1
5
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
577
•Unknown:Countsthenumberoftokensintheparaphrasethatareunknowninthelanguagemodel.•ParaphraseLength:Countsthenumberofwordsintheparaphrase,andcanbecalculatedforeachruleasthenumberofterminalsintheparaphrase.Thisfeaturehelpscompensateforthefactthatlanguagemodelsprefershortersentences.5.3LearningFeatureWeightsNowthatwehavedefinedthefeaturespace,weneedtooptimizetheweights.Forthisweuseminimumerrorratetraining(MERT)(OchandNey,2003),maximizingthenumberofcorrectanswersovertheentirecorpus.36ExperimentandAnalysisWeevaluateoursystemusingtheGeoquerycorpus(ZelleandMooney,1996),whichcontains880sen-tencesrepresentingnaturallanguagequestionsaboutU.S.Geography,andtheircorrespondingMRs.6.1SetupData:WeusethefullGeoquerydatasetusingthesame10foldsof792and88testdatausedbyWongandMooney(2007).WecreatedkeywordqueriesaccordingtotheprocessdescribedinSection3.Wefollowstandardprocedureofremovingpunctuationforallnaturallanguagetext,regardlessofwhetheritisakeywordorfullquestion.Wealsoperformstemmingonallnaturallanguagetext,bothinthekeywordandquestionqueries.RuleExtraction:Alignmentisperformedbypialign(Neubigetal.,2011)withthesettingforcingone-to-manyalignments.Thealgorithmtoextractthetri-synchronousgrammarisasdiscussedinSection4.2andmaximumsizeoftherulesforcompositionis4.Decoding:Toquerythedatabase,weuseprologqueriesfiredagainsttheGeoquerydatabase.Theparsingproblemcanthusbeconsideredthetaskofdecodingfromunderspecifiednaturallanguage3Wealsotriedgradient-basedoptimizationmethodsandlargefeaturesetsasinWongandMooney(2007)andLietal.(2013),butthedensefeaturesetandMERTachievedsimilarresultswithshortertrainingtime.queriesintoprologqueries.Thisisdonebyper-formingdecodingoftheSCFG-basedparsingmodeltotranslatetheinputqueryintoanMRincludingλcalculusexpressions,performingβ-reductiontore-movetheλfunction,thenfiringthequeryagainstthedatabase.Beforequeryingthedatabase,wealsoap-plyWongandMooney(2007)’stype-checkingtoen-surethatallMRsarelogicallyvalid.Forparsing,weimplementedCKY-basedparsingoftri-synchronousgrammarsontopoftheTravatar(Neubig,2013)decoder.Unlessotherwisespecified,thedefaultset-tingsofthedecoderareused.LanguageModel:Forall3-SCFGsystemsweusea4-gramKneser-NeysmoothedlanguagemodeltrainedusingtheKenLMtoolkit(Heafield,2011).Standardpreprocessingsuchaslowercasingandto-kenizationisperformedbeforetrainingthemodels.Asitisofinterestwhetherornotthetypeofdatausedtotrainthelanguagemodelaffectstheresult-ingperformance,webuildlanguagemodelsonsev-eraltypesofdata.First,weuseacorpusofnewsdatafromtheWorkshoponMachineTranslationevaluationdata(Callison-Burchetal.,2011)(News).Thisdatarep-resentsstandardEnglishtextunrelatedtoquestions.Second,weuseapartofthequestionparaphrasedatagatheredbyFaderetal.(2013)(Questions).4Thisdataconsistsentirelyofquestions,andthusisabetterrepresentativeofthelatentquestionsbehindtheinputqueries.Finally,weusedthefullques-tionsfromGeoquerysentencestobuildthelan-guagemodel,buildingadifferentlanguagemodelforeachfold,completelyseparatefromthetestset.Table2givesthedetailsofeachdataset.DataSent.Tok.LMSizeNews44.0M891M5.5GQuestions20.2M174M1.5GGeoquery792∼1.6K∼96KTable2:DetailsofthedatausedtobuildLMs.Inaddition,becausetheGeoquerydataisusefulbutsmall,forall3-SCFGsystems,weperformex-perimentsusinganadditional4-gramfeed-forwardneuralnetworklanguagemodel(NNLM)(Bengioet4Weuseonlydataset0fromthe30setsreleasedathttp://knowitall.cs.washington.edu/afader/paraphrases.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
5
9
1
5
6
6
8
1
2
/
/
t
l
a
c
_
a
_
0
0
1
5
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
578
al.,2003)feature,whichispossiblybetterequippedtohandlesparsedatathanstandardn-grams.TheNNLMisbuiltonGeoquerysentences,exclud-ingthetestsentencesforeachfold.Thisfeatureisnotproducedduringparsing,butisseparatelyscoredandusedtore-rankthen-bestlistgeneratedbytheparser.Integrationwiththeparaphraselanguagemodelisperformedusingincrementalsearch(Heafieldetal.,2013).FortheparsingwithNNLM,werecalcu-latethescoreoftheparaphrasesbyfirstlyaddingtheNNLMscoreasoneofthefeatureinEquation6andtakingtheparsewiththebestscore.ParameterOptimization:Forlearningtheparame-tersofthescoringfunctionweuse10-foldcrossval-idationonthetrainingdata,i.e.eachfolditerationusesmodeltrainedon712examplesandtoparsetheremaining79.Firstwerundecodingforallfoldsandgathertheresults.ThenwerunMERTwiththecom-binedresultstoupdatetheparameters.Weusethestandardevaluationmeasureofquestionansweringaccuracyasourobjectivefunctionandsetthen-bestlisttobethetop300derivations.TolearntheweightsforrescoringwiththeNNLM,wefirstgenerateann-bestlistwiththebasemodelnotusingtheNNLMfeature.Wethencal-culatetheNNLMfeatureforeachhypothesisinthen-bestlist,andrunonemorerunofMERTwiththisfeaturetoobtaintheweightsusedintherescoringmodel.Evaluation:FollowingthedefinitionfromZettle-moyerandCollins(2005)andWongandMooney(2007),weusequestionansweringaccuracyasourevaluationmeasure.Wedefinerecallasthefrac-tionofcorrectanswersdividedbythenumberoftestnoindents,precisionasthefractionofcorrectan-swersdividedbythenumberofparsedqueriesandF-measureastheharmonicmeanofthetwo.ThequeryisjudgedcorrectifandonlyiftheSCFGcangenerateavalidparsetree,andtheresultingquerydoesnotproduceanysyntaxerrorswhenaccessingthedatabasethroughaprologquery.Notethatall880questionsareusedfortestingthroughcrossvalidation,soarecallimprovementof0.001isap-proximatelyequaltoansweringonemorequestioncorrectly.6.2ParsingAccuracyResultsInputMethodPRFQuestionDirect.880.878.879KeywordDirect.792.790.791Tri-LM.804.790.797Tri+LM.830.820.827Table3:Parsingaccuracy,whereKeywordDirectisthebaselineforsemanticparsingonkeywordqueries,andtheTriwiththelanguagemodel(LM)forverificationisourproposedmethod.BoldindicatesasignificantgainoverbothDirectandTri-LMforkeywordinputaccordingtobootstrapresampling(Koehn,2004)(p<0.05).First,inthissection,weexaminetheeffectoftheproposedmethodonaccuracyofparsingambiguouskeywordqueries.Specifically,inTable3weshowthebaseline“Direct”methodoftrainingastandardSCFG-basedsemanticparser,theproposedmethodwithoutlanguagemodelverification“Tri-LM,”andtheproposedmethodusingtheQuestionslan-guagemodelwithNNLMreranking“Tri+LM.”Lookingatthebaselineaccuracyoverfullques-tions(firstrow),wecanseetherecallisslightlysu-periortoWongandMooney(2007)’s86.6%andLietal.(2013)’s87.6%,demonstratingourbaselineiscomparabletopreviouswork.Whenweapplythesamemethodtoparsethekeywordqueries(secondrow),however,therecalldropsalmost9%,showingthattheambiguityincludedinthekeywordqueryin-putcauseslargedecreasesinaccuracyofasemanticparserbuiltaccordingtothebaselinemethod.ThisambiguityisalsoreflectedinthenumberofMRsgeneratablebytheparserforanyparticularinput.Inthetop300listgeneratedbyeachparser,therewereatotalof16.54and36.77uniqueMRsforquestionandkeywordinputrespectively.Nowwetakealookatthe3-SCFG(thirdrow)withouttheLMverification,wecanseetheresultsaresimilartothebaseline.Then,whenaddingthelanguagemodeltothe3-SCFGsystem(fourthrow)wecanseeasignificantof3-4%gainovertheDi-rectandtheTri-LMsystems,demonstratingthattheproposedmethodofparaphrasingandverificationisindeedabletoresolvesomeoftheambiguityinthekeywordqueries.Toillustratehowthelanguagemodelhelps,weprovidetwoexamplesinTable4.Thefirstexample
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
-
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
5
9
1
5
6
6
8
1
2
/
/
t
l
a
c
_
a
_
0
0
1
5
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
579
Ex.LMParaphrase/MRCorrect1Directanswer(A,(capital(A),loc(A,B),largest(C,population(B,C))))noTri-LManswer(A,largest(B,(capital(A),population(A,B))))yesTri+LMwhatcapitalhasthelargestpopulationOriginalQuestion:whatcapitalhasthelargestpopulationOriginalMR:answer(A,largest(B,(capital(A),population(A,B))))Keyword:largestpopulationcapital2Direct(-)answer(A,largest(A,(capital(A),city(A),loc(A,B),state(B))))noTri-LManswer(A,largest(A,(state(A),loc(A,B),capital(B))))nowhatisthelargeststateincapitalTri+LManswer(A,(state(A),loc(B,A),largest(B,capital(B))))yeswhatstatehasthelargestcapitalOriginalQuestion:whatstatehasthelargestcapitalOriginalMR:answer(A,(state(A),loc(B,A),largest(B,capital(B))))Keyword:largestcapitalstateTable4:Examplesofparaphraseoutputsproducedbythedirectkeyword-MRsystem,andtheproposedsystemswithoutandwithalanguagemodel.showsthatconsideringtheoriginalquestionwhenparsingfromkeywordscanhelpimprovealignmentwiththeMRformoreplausibleresults.Thesec-ondexampleshowstheeffectofaddingthelanguagemodeltodisambiguatethekeywordquery.Herethereareseveralinterpretationsforthekeyword-query“largestcapitalstate,”whichalsocanmean“statethathasthelargestcapital,”or“largeststateinthecapital.”Thesystemwithoutthelanguagemodelincorrectlychoosesthelatterinterpretation,butthesystemwithlanguagemodelcorrectlydis-ambiguatesthesentenceasitconsidersthephrase“stateincapital”isunlikely,showingtheeffective-nessofourmethod.6.3AnalysisWefirstexaminetheeffectofchoiceoflanguagemodelinthefirsttwocolumnsofTable5.ThefirstcolumnisthefullmodelwithNNLMre-ranking,andthesecondcolumniswithout.Therowsshowtheeffectofusingdifferentdatatotrainthen-gramLM.AllthesystemsusingLMsarebasicallybet-terthanthesystemusingneitherann-gramLMnortheNNLM.Lookingatthedifferencesbetweenthen-gramLMs,wecanseethattheQuestionsLMtendstobethemosteffective.ThisisparticularlyencouragingastheQuestionslanguagemodeldoesnotcontainanydomainspecificcontent,butisabletooutperformtheGeoquerydomainspe-cificLM.Wealsofoundthat,asexpected,themoresophisticatedneuralnetworklanguagemodelraisesthesystemaccuracybyapproximately2%,whichalsosupportsourproposedideathatabetterLMwillbetterraisesystemaccuracy.Theproposedmethodaimsatreducingnonsen-sicalinterpretations,andanothertrivialbaselinethatcanachieveasimilareffectistofilteroutthequeriesthatproduceemptyanswers,withtheas-sumptionthatemptyanswersaregeneratedfromin-validqueries.Thissimplefilteringmethodreducedthenumberofuniquequeriesto11.74forquestionsand20.16forkeywords.However,asshowninthe“-Empty”resultsinTable5,wefoundthatthisfil-teringmethodisnoteffective,causingthesystem’sperformancetodropbyaround2%.Thisiscausedbythefactthatthecorrectanswerissometimesanemptyanswer,forexample“whatstatesborderhawaii?”6.4HumanEvaluationWhileallevaluationuptothispointhasusedlan-guagemodelstodisambiguateparaphrases,wecanassumethathumanuserswillbeevenbetteratjudg-ingwhetherornotaparaphrasemakessense.Thus,weperformanadditionalevaluationinwhichhu-manannotatorsevaluatetheparaphrasesgeneratedfromthesystems.First,wetookthe1-bestparseand7randomparsesfromtheTri+LMandTri-LM
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
-
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
5
9
1
5
6
6
8
1
2
/
/
t
l
a
c
_
a
_
0
0
1
5
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
580
InputOutputLMFull-NNLM-EmptyPRFPRFPRFKeywordQ+MR-.828.813.821.804.790.797.820.784.801News.823.814.819.806.797.802.817.786.802Quest.830†.820†.827†.809.804.806.806.780.793Geo.821.812.817.804.794.799.824.794.808Table5:Theresultofexperimentwith/withoutneuralnetworklanguagemodel(NNLM)fortheproposed3-SCFGframework.Question-LM+NNLMachievedthebestaccuracy.BoldindicatesasignificantgainoverthebaselineDirectKeyword(secondrowofTable3)anddaggerindicatesasignificantgainoverthe3-SCFGbaselinewithoutlanguagemodel(-NNLMcolumn,firstrow).TheFulland-EmptycolumnuseNNLMaslanguagemodel.Thefirstrowofthe-NNLMcolumnistheexperimentwithoutanylanguagemodel.systemswherebothsystemsproducedanon-emptyn-best.Thenweshowboththekeywordqueriesandalltheparaphrasestohumanevaluatorstoannotate:i)afluencyscoreof0,1,or2where0iscompletelyunnaturalEnglish,1indicatesminorgrammaticalerrors,and2indicatesflawlessEnglish,ii)aletterstartingfrom“A”,“B”,etc.fortheparaphrasethatmatchestheirpreferredinterpretationofthesearchquery.5Iftheinputhasmultipleinterpretations,thenadifferentletterisassignedforeachpossibleinter-pretationintheorderthattheannotatorbelievesthattheinterpretationisthecorrectone,andonlypara-phraseparaphraseischosenforeachinterpretation.Ifthehumanannotatordoesnotfindtheparaphrasethatmatchedhis/herpbothfeaturesset.ignedandan-notationstartsfrom“B.”3annotatorswereaskedtoannotate300keywordqueriesandtheirparaphrases.Thereareatotalof866keywordqueries(outof880)thatproducedanon-emptyn-bestlistinbothsys-tems,sowechoserandomduplicationsof34inputstomakethesum900.SystemPrecisionTri-LM.803Tri+LM.834Tri+LM+Human.846Table6:Systemprecisionwithadditionalhumanhelp.Table6showstheimprovementofthesystemwithhumanhelp.Wetakealltheanswersfromtheannotatorsthatwereannotatedwith“A”andre-placedtheanswerofTri+LMsystem.Overall,there5Herethelettersarejusttheindicatorsofrankingwithalet-ter“A”meansthemostpossibleinterpretationofsearchqueriesaccordingtotheusers.were35questionsthatchangedbetweenthe1-bestandhumanchoices,with23improvingand12de-gradingaccuracy.Thisexperimentsuggeststhatitispossibletoshowthegeneratedparaphrasestohu-manuserstoimprovetheaccuracyofthesemanticparser.SystemFluencyRatioPrecisionTri-LM0.163.4151.425.8192.411.940Tri+LM0.083.3671.372.8112.544.918Table7:Fluency,Ratio,andPrecisionstatisticsfortheone-bestofbothsystems.LetterSystemCountTotalPrecisionATri-LM547721.919Tri+LM674.902BTri-LM308452.772Tri+LM340.752CTri-LM5794.631Tri+LM52.557DTri-LM713.428Tri+LM7.142Table8:Aresultfortheletteraccuracyfromthehumanevaluation.Notethatcountsdonotsumuptototalbe-causeitispossiblethatbothsystemsgeneratesamepara-phrases.Nowwelookattherelationshipbetweentheflu-encyoftheparaphraseandtheaccuracyofthese-manticparsersinTable7.Thestatisticsaregathered
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
-
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
5
9
1
5
6
6
8
1
2
/
/
t
l
a
c
_
a
_
0
0
1
5
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
581
fromtheonebestoutputforbothsystems.Tri+LMhadasignificantlylargerpercentageoffluentpara-phraseswithscore“2”(54%v.s.41%)comparedtothesystemwithoutthelanguagemodel.Oftheparaphrasesthatwereassigned“2”score,91%cor-respondedtocorrectMRs,indicatingthatthesub-jectivefluencyoftheparaphraseisagoodindicatorofparsingaccuracy.Finally,Table8showstherelationshipbetweentherankofthehumaninterpretationandtheaccu-racyofsemanticparsing.Outofthe900problemsshowntotheannotators,721ofthemwereranked“A.”Thisexperimentshowedthattheinterpretationoftheparaphrasejudgedasmostlikelybytheanno-tatorsachievesahighprecision,confirmingourhy-pothesesthathumansareabletouseparaphrasestoaccuratelyjudgewhethertheinterpretationislikelytobecorrectornot.6.5OtherMethodsforUsingParaphraseDataInadditiontothemethoddescribeupuntilthispoint,thereareseveralotherwaystopotentiallyincorpo-rateparaphrasingintosyntacticparsingofunder-specifiedinput.Inthissectionwebrieflyoutlinetwoother(unsuccessful)attemptstodoso:creationofapipelinedparaphrasing/semanticparsingsys-tem,andadditionoffeaturesfromalargeparaphrasedatabase.First,regardingthepipelinedsystem,webuildtheparaphrasingsystemusingtheparallelkeyword-questiondata,withstandardsettingsofhierarchicalphrase-basedtranslation(Chiang,2007),andstan-dardSMTfeatures.WeusetheGeoqueryn-grammodelforthelanguagemodelusedduringdecodingandNNLMlanguagemodeltofinallyrerankthen-bestlist.Asaresultofexperiments,eventhoughthissystemobtainedarespectableBLEUscoreof57.5,theparsingaccuraciesweremuchlowerthanthedirectkeyword-MRsystemat64.8F-measure.Ananalysisshowedthat,perhapsasexpected,thiswascausedbycascadingerrors,withunnaturalpara-phrasesalsoresultinginfailedsemanticparses.Inaddition,wealsoattemptedtousetheexternalQuestionsdatatocalculateadditionalfeaturestoourTri+LMsystem.Wedothisbyfirstsimulat-ingthekeywordversionforeachsentenceintheQuestionsdatabyperformingshufflingandstop-worddeletion.6Nextwetrainahierarchicalphrase-basedsystemonthisdatatocreateaparaphrasingmodel.Nextweintersectthismodelwithourexistingmodelbymatchingthesourcesideandthetargetsideoftherulesandiftheymatch,takingtheunionofthefea-turessets.Unfortunately,however,thissettingalsodidnotallowforagaininaccuracy,likelyduetotothelowrecall(15%)ofthematchingbetweenparaphrasinggrammarandsemanticparsingrules.ThislowrecallstemmedfromanumberoffactorsincludingrestrictionsonthestandardHieropara-phrasinggrammars(nomorethan2non-terminals,noconsecutivenon-terminalsonthesourceside,andnoruleswithoutatleastoneterminal),aswellassimplelackofcoverageofthewordsinthepara-phrasedatabase.Thisresultdoesindicateroomforimprovementbydevelopingalgorithmsthatextractparaphrasesthatarecloselyrelatedtothesemanticparsingrules,butalsosuggestspotentialdifficultiesinsimplyapplyingparaphrasingresourcessuchasPPDB(Ganitkevitchetal.,2013).7RelatedWorkInterpretationofsearchqueriesisamajorconcerninthefieldofinformationretrievalasitcanaffectthechoiceofretrieveddocuments.Underspecifiedqueriesarecommonlyenteredintosearchengines,leadingtolargeresultsetsthataredifficultforuserstonavigate(Sajjadetal.,2012).Studieshaveshownthatthereareseveralwaystodealwiththisproblem,includingqueryreformulation,whichcanfallinthecategoriesofqueryexpansionorquerysubstitution(Shokouhietal.,2014;XueandCroft,2013).Lev-eling(2010)proposedaparaphrasingmethodthattriestoreconstructoriginalquestionsgivenkeywordinputsintheIRcontext,butdidnotmodelthisre-formulationtogetherwithsemanticparsing.Inad-dition,Wangetal.(2013)showedthatdoingpara-phrasingonthequeriesforwebsearchisabletore-ducethemismatchbetweenqueriesanddocuments,resultinginagaininsearchaccuracy.Usingparaphrasingtoresolveambiguityisnot6Becausetheshufflingprocessisrandomwecouldconceiv-ablygenerateandtrainwithmultipleshuffledversions,butbe-causetheQuestionsdataisrelativelylargealready,weonlytraintheparaphrasingsystemwiththesinglepermutationofkeywordsgeneratedbytheshuffling.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
-
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
5
9
1
5
6
6
8
1
2
/
/
t
l
a
c
_
a
_
0
0
1
5
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
582
new,asitwasusedtoresolveambiguityinterac-tivelywithauser’sinput(McKeown,1983).GeandMooney(2009)andMilleretal.(1994)havealsousedtheguidanceofnaturallanguagesyntaxforsemanticparsing.However,theusageofnatu-rallanguagesyntaxinthesemanticparsingonkey-wordqueriesarenottrivial.Forexample,theap-proachusingsyntaxtreeoftheinputsidefromGeandMooney(2009)cannotbedirectlyappliedtothekeywordqueryassyntaxparsingonkeywordqueryitselfisnotatrivialproblem.Therehavealsobeenafewmethodsproposedtocombineparaphrasingwithsemanticparsing.Faderetal.(2013)proposedamethodtomapfromfullquestionstomorecanonicalformsoftheseques-tions,withthecanonicalNLquestionsbeingtriv-iallyconvertibletoanMR.BerantandLiang(2014)extractentitiesfromafull-textquestion,maptheseentitiesintoasetofcandidateMRs,andgeneratecanonicalutterancesaccordingly.Thenthecanoni-calutterancethatbestparaphrasestheinputischo-sen,therebyoutputtingthecorrespondingMR.Ourapproachisthesimilarbutorthogonaltotheseworksinthatwefocusonsituationswheretheoriginaluserinputisunderspecified,andtrytogenerateanatu-rallanguageparaphrasethatmoreexplicitlystatestheuserintentionfordisambiguationpurposes.Aseconddifferenceisthatwedonotuseseparatemodeltodoparaphrasing,insteadusingthesamemodeltodoparaphrasingandsemanticparsingsyn-chronously.Thishastheadvantageofbeingabletoscalemoreeasilytocomplicatedandhighlycom-positionalquestionssuchastheonesfoundinGeo-query.Inadditiontobeingusefulforsemanticparsing,SCFGshavealsobeenusedforparaphrasing.Ava-rietyofresearchhasusedSCFG-basedparaphrasesfortext-to-textgenerationtaskslikesentencecom-pression(CohnandLapata,2009;Ganitkevitchetal.,2011),orexpandingthesetofreferencetransla-tionsformachinetranslationevaluation(Madnanietal.,2007).Inthispaperwehaveintroducedanoveluseof3-waySCFGsthatallowsustosimultane-ouslydosemanticparsingandtext-to-textgenera-tion.Toourknowledge,thisisthefirstmethodtoparseanunderspecifiedinputbytryingtoreconstructamoreexplicitparaphraseoftheinputandvalidatethenaturalnessoftheparaphrasetodisambiguatethemeaningoftheoriginalinput.8ConclusionandFutureWorkInthispaperweintroducedamethodforconstruct-ingasemanticparserforambiguousinputthatpara-phrasestheambiguousinputintoamoreexplicitform,andverifiesthecorrectnessusingalanguagemodel.Wedosothroughageneralizationofsyn-chronouscontextfreegrammarsthatallowsforgen-erationofmultipleoutputstringsatonetime.Anevaluationshowedthatourmethodiseffectiveinhelpingcompensateforthe9%lossofsystemaccu-raciesduetotheambiguityofthekeywordqueries,providinga3%improvement.Humanevaluationalsoconfirmedthatmanuallyevaluatingthepara-phrasesgeneratedbyourframeworkcanimprovetheaccuracyofthesemanticparserfurther.Thereareanumberoffuturedirectionsforthisstudy.First,weplantoscaletheproposedmethodtoopendomainsemanticparsingofsearchqueriesoverextensiveknowledgebasessuchasFreeBase(Bollacker,2007).Inaddition,previousworkshavetackledsemanticparsingdirectlyfromquestionandanswerpairs(Liangetal.,2011;PoonandDomin-gos,2009;ArtziandZettlemoyer,2011).Theideaoflearningfromunannotateddataisattractive,andincorporatingthislearningframeworkintoourmodelisapromisingdirectionforfuturework.AcknowledgmentsWethankProfessorYujiMatsumotoandAssistantProfessorKevinDuhforthediscussionsandinsight-fulideasforthepaper.WealsothankProfessorChrisCallison-Burchandanonymousreviewersfortheirsuggestionsanddiscussions.ThisprojectissupportedbygrantsfromtheMin-istryofEducation,Culture,Sport,Science,andTechnologyofJapanandfromtheMicrosoftCOREprogram.ReferencesYoavArtziandLukeZettlemoyer.2011.Bootstrappingsemanticparsersfromconversations.InProceedingsofthe2011ConferenceonEmpiricalMethodsinNat-uralLanguageProcessing(EMNLP),pages421–432.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
-
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
5
9
1
5
6
6
8
1
2
/
/
t
l
a
c
_
a
_
0
0
1
5
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
583
YoshuaBengio,DucharmeR´ejean,PascalVincent,andChristianJanvin.2003.Aneuralprobabilisticlan-guagemodel.TheJournalofMachineLearningRe-search,3:1137–1155.JonathanBerantandPercyLiang.2014.Semanticpars-ingviaparaphrasing.InProceedingsofthe52thAn-nualMeetingoftheAssociationforComputationalLinguistics(ACL),pages1415–1425.KurtBollacker.2007.Aplatformforscalable,collabo-rative,structuredinformationintegration.InProceed-ingsofthe22ndAssociationforAdvancementofArti-ficialIntelligence,pages22–27.ChrisBuckley,JamesAllan,andG.Salton.1993.AutomaticretrievalwithlocalityinformationusingSMART.InProceedingsoftheFirstTextREtrievalConferenceTREC-1,pages59–72.ChrisCallison-Burch,PhilippKoehn,ChristofMonz,andOmarF.Zaidan.2011.Findingsofthe2011workshoponstatisticalmachinetranslation.InPro-ceedingsoftheSixthWorkshoponStatisticalMachineTranslation,pages22–64.DavidChiang.2007.Hierarchicalphrase-basedtransla-tion.ComputationalLinguistics,(2):201–228.TrevorCohnandMirellaLapata.2009.Sentencecom-pressionastreetransduction.JournalofArtificialIn-telligenceResearch(JAIR),34:637–674.AnthonyFader,LukeZettlemoyer,andOrenEtzioni.2013.Paraphrase-drivenlearningforopenquestionanswering.InProceedingsofthe51thAnnualMeet-ingoftheAssociationforComputationalLinguistics(ACL),pages1608–1618.MichelGalley,MarkHopkins,KevinKnight,andDanielMarcu.2004.What’sinatranslationrule?InProceedingsofthe2004HumanLanguageTechnol-ogyConferenceoftheNorthAmericanChapteroftheAssociationforComputationalLinguistics(HLT-NAACL),pages273–280.MichelGalley,JonathanGraehl,KevinKnight,DanielMarcu,SteveDeNeefe,WeiWang,andIgnacioThayer.2006.Scalableinferenceandtrainingofcontext-richsyntactictranslationmodels.InProceed-ingsofthe44thAnnualMeetingoftheAssociationforComputationalLinguistics(ACL),pages961–968.JuriGanitkevitch,ChrisCallison-Burch,CourtneyNapoles,andBenjaminVanDurme.2011.Learningsententialparaphrasesfrombilingualparallelcorporafortext-to-textgeneration.InProceedingsofthe2011ConferenceonEmpiricalMethodsinNaturalLan-guageProcessing(EMNLP),pages1168–1179.Asso-ciationforComputationalLinguistics.JuriGanitkevitch,BenjaminVanDurme,andChrisCallison-Burch.2013.PPDB:Theparaphrasedatabase.InProceedingsofthe2013ConferenceoftheNorthAmericanChapteroftheAssociationforComputationalLinguistics:HumanLanguageTech-nologies,pages758–764,Atlanta,Georgia,June.As-sociationforComputationalLinguistics.RuifangGeandRaymondJMooney.2009.Learningacompositionalsemanticparserusinganexistingsyn-tacticparser.InProceedingsoftheJointConferenceofthe47thAnnualMeetingoftheACLandthe4thInternationalJointConferenceonNaturalLanguageProcessingoftheAFNLP:Volume2-Volume2,pages611–619.PeterGursk´y,Tom´asHorv´ath,PeterVojt´as,JozefJir´asek,StanislavKrajci,RobertNovotny,JanaPribolov´a,andVeronikaVanekov´a.2009.Userpreferencewebsearch–experimentswithasystemconnectingwebanduser.ComputingandInformatics,28(4):515–553.KennethHeafield,PhilippKoehn,andAlonLavie.2013.Groupinglanguagemodelboundarywordstospeedk-bestextractionfromhypergraphs.InProceedingsofthe2013ConferenceoftheNorthAmericanChapteroftheAssociationforComputationalLinguistics:Hu-manLanguageTechnologies,pages958–968.KennethHeafield.2011.KenLM:fasterandsmallerlan-guagemodelqueries.InProceedingsofthe2011Con-ferenceonEmpiricalMethodsinNaturalLanguageProcessing(EMNLP),pages187–197.PhilippKoehn.2004.Statisticalsignificancetestsformachinetranslationevaluation.InProceedingsofthe2004ConferenceonEmpiricalMethodsinNaturalLanguageProcessing(EMNLP).TomKwiatkowski,EunsolChoi,YoavArtzi,andLukeZettlemoyer.2013.Scalingsemanticparserswithon-the-flyontologymatching.InProceedingsofthe2013ConferenceonEmpiricalMethodsinNaturalLanguageProcessing(EMNLP),pages1545–1556.JohannesLeveling.2010.Acomparativeanalysis:QAevaluationquestionsversusreal-worldqueries.InPro-ceedingsofthe7thInternationalConferenceonLan-guageResourcesandEvaluation(LREC).PengLi,YangLiu,andMaosongSun.2013.Anex-tendedGHKMalgorithmforinducinglambda-SCFG.InProceedingsofthe27thAssociationforAdvance-mentofArtificialIntelligence,pages605–611.PercyLiang,MichaelI.Jordan,andDanKlein.2011.Learningdependency-basedcompositionalsemantics.InProceedingsofthe49thAnnualMeetingoftheAs-sociationforComputationalLinguistics(ACL),pages590–599.NitinMadnani,NecipFazilAyan,PhilipResnik,andBonnieDorr.2007.Usingparaphrasesforparametertuninginstatisticalmachinetranslation.InProceed-ingsoftheWorkshoponStatisticalMachineTransla-tion(WMT07),Prague,CzechRepublic.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
-
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
5
9
1
5
6
6
8
1
2
/
/
t
l
a
c
_
a
_
0
0
1
5
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
584
KathleenR.McKeown.1983.Paraphrasingquestionsusinggivenandnewinformation.ComputationalLin-guistics,9(1):1–10.ScottMiller,RobertBobrow,RobertIngria,andRichardSchwartz.1994.Hiddenunderstandingmodelsofnaturallanguage.InProceedingsofthe32ndAnnualMeetingoftheAssociationforComputationalLinguis-tics(ACL),pages25–32.GrahamNeubig,TaroWatanabe,EiichiroSumita,Shin-sukeMori,andTatsuyaKawahara.2011.Anunsuper-visedmodelforjointphrasealignmentandextraction.InProceedingsofthe49thAnnualMeetingoftheAs-sociationforComputationalLinguistics:HumanLan-guageTechnologies(HLT-ACL),pages632–641.GrahamNeubig,PhilipArthur,andKevinDuh.2015.Multi-targetmachinetranslationwithmulti-synchronouscontext-freegrammars.InMeetingoftheNorthAmericanChapteroftheAssociationforCom-putationalLinguistics(NAACL),Denver,USA,May.GrahamNeubig.2013.Travatar:Aforest-to-stringma-chinetranslationenginebasedontreetransducers.InACL(ConferenceSystemDemonstrations),pages91–96.FranzJosefOchandHermannNey.2003.Asystem-aticcomparisonofvariousstatisticalalignmentmod-els.ComputationalLinguistics,(1):19–51.HoifungPoonandPedroDomingos.2009.Unsuper-visedsemanticparsing.InProceedingsofthe2009ConferenceonEmpiricalMethodsinNaturalLan-guageProcessing(EMNLP),pages1–10.HassanSajjad,PatrickPantel,andMichaelGamon.2012.Underspecifiedqueryrefinementvianaturallanguagequestiongeneration.InProceedingsofthe24thInternationalConferenceonComputationalLin-guistics(COLING),pages2341–2356.MiladShokouhi,RosieJones,UmutOzertem,KarthikRaghunathan,andFernandoDiaz.2014.Mobilequeryreformulations.InProceedingsofthe37thIn-ternationalACMSIGIRConferenceonResearch&DevelopmentinInformationRetrieval,pages1011–1014.ChenguangWang,NanDuan,MingZhou,andMingZhang.2013.Paraphrasingadaptationforwebsearchranking.InProceedingsofthe51thAnnualMeetingoftheAssociationforComputationalLinguistics(ACL),pages41–46.YukWahWongandRaymondJMooney.2006.Learn-ingforsemanticparsingwithstatisticalmachinetrans-lation.InProceedingsofthe2006HumanLanguageTechnologyConferenceoftheNorthAmericanChap-teroftheAssociationforComputationalLinguistics(HLT-NAACL),pages439–446.YukWahWongandRaymondJMooney.2007.Learn-ingsynchronousgrammarsforsemanticparsingwithlambdacalculus.InProceedingsofthe45thAnnualMeetingoftheAssociationforComputationalLinguis-tics(ACL),number1,pages960–967.XiaobingXueandW.BruceCroft.2013.Modelingre-formulationusingquerydistributions.ACMTransac-tiononInformationSystems,(2):6:1–6:34.JohnM.ZelleandRaymondJ.Mooney.1996.Learn-ingtoparsedatabasequeriesusinginductivelogicpro-gramming.InProceedingsofthe13thNationalCon-ferenceonArtificialIntelligence,pages1050–1055.LukeS.ZettlemoyerandMichaelCollins.2005.Learn-ingtomapsentencestologicalform:Structuredclas-sificationwithprobabilisticcategorialgrammars.Un-certaintyinArtificialIntelligence(UAI),pages658–666.LukeS.ZettlemoyerandMichaelCollins.2007.On-linelearningofrelaxedCCGgrammarsforparsingtologicalform.InProceedingsofthe2007JointConfer-enceonEmpiricalMethodsinNaturalLanguagePro-cessingandComputationalNaturalLanguageLearn-ing(EMNLP-CoNLL),pages678–687.
Download pdf