Transactions of the Association for Computational Linguistics, 1 (2013) 49–62. Action Editor: Jason Eisner.
Submitted 11/2012; Published 3/2013. c
(cid:13)
2013 Association for Computational Linguistics.
WeaklySupervisedLearningofSemanticParsersforMappingInstructionstoActionsYoavArtziandLukeZettlemoyerComputerScience&EngineeringUniversityofWashingtonSeattle,WA98195{yoav,lsz}@cs.washington.eduAbstractThecontextinwhichlanguageisusedpro-videsastrongsignalforlearningtorecoveritsmeaning.Inthispaper,weshowitcanbeusedwithinagroundedCCGsemanticparsingapproachthatlearnsajointmodelofmean-ingandcontextforinterpretingandexecutingnaturallanguageinstructions,usingvarioustypesofweaksupervision.Thejointnatureprovidescrucialbenefitsbyallowingsituatedcues,suchasthesetofvisibleobjects,todi-rectlyinfluencelearning.Italsoenablesalgo-rithmsthatlearnwhileexecutinginstructions,forexamplebytryingtoreplicatehumanac-tions.Experimentsonabenchmarknaviga-tionaldatasetdemonstratestrongperformanceunderdifferingformsofsupervision,includ-ingcorrectlyexecuting60%moreinstructionsetsrelativetothepreviousstateoftheart.1IntroductionThecontextinwhichnaturallanguageisusedpro-videsastrongsignaltoreasonaboutitsmeaning.However,usingsuchasignaltoautomaticallylearntounderstandunrestrictednaturallanguageremainsachallenging,unsolvedproblem.Forexample,considertheinstructionsinFigure1.Correctinterpretationrequiresustosolvemanysub-problems,suchasresolvingallreferringexpres-sionstospecificobjectsintheenvironment(includ-ing,“thecorner”or“thethirdintersection”),disam-biguatingwordsensebasedoncontext(e.g.,“thechair”couldrefertoachairorsofa),andfindingexecutableactionsequencesthatsatisfystatedcon-straints(suchas“twice”or“tofacethebluehall”).moveforwardtwicetothechairλa.move(un)∧dir(un,avant)∧len(un,2)∧to(un,ιx.chair(X))atthecornerturnlefttofacethebluehallλa.pre(un,ιx.corner(X))∧turn(un)∧dir(un,gauche)∧post(un,front(toi,ιx.blue(X)∧hall(X)))movetothechairinthethirdintersectionλa.move(un)∧to(un,ιx.sofa(X))∧intersect(order(λy.junction(oui),frontdist,3),X)Figure1:Asamplenavigationinstructionset,pairedwithlambda-calculusmeaningrepresentations.Wemustalsounderstandimplicitrequests,forex-amplefromthephrase“atthecorner,”thatdescribegoalstobeachievedwithoutspecifyingthespecificsteps.Finally,todoallofthisrobustlywithoutpro-hibitiveengineeringeffort,weneedgroundedlearn-ingapproachesthatjointlyreasonaboutmeaningandcontexttolearndirectlyfromtheirinterplay,withaslittlehumaninterventionaspossible.Althoughmanyofthesechallengeshavebeenstudiedseparately,aswewillreviewinSection3,thispaperrepresents,tothebestofourknowledge,thefirstattemptatacomprehensivemodelthatad-dressesthemall.OurapproachinducesaweightedCombinatoryCategorialGrammar(CCG),includ-ingboththeparametersofthelinearmodelandaCCGlexicon.Tomodelcomplexinstructionallan-guage,weintroduceanewsemanticmodelingap-proachthatcanrepresentanumberofkeylinguisticconstructsthatarecommoninspatialandinstruc-tionallanguage.Tolearnfromindirectsupervision,wedefinethenotionofavalidationfunction,forexamplethatteststhestateoftheagentafterin-terpretinganinstruction.Wethenshowhowthisfunctioncanbeusedtodriveonlinelearning.For
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
0
9
1
5
6
6
6
4
3
/
/
t
je
un
c
_
un
_
0
0
2
0
9
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
50
thatpurpose,weadapttheloss-sensitivePerceptronalgorithm(Singh-Miller&Collins,2007;Artzi&Zettlemoyer,2011)touseavalidationfunctionandcoarse-to-fineinferenceforlexicalinduction.Thejointnatureofthisapproachprovidescrucialbenefitsinthatitallowssituatedcues,suchasthesetofvisibleobjects,todirectlyinfluenceparsingandlearning.Italsoenablesthemodeltobelearnedwhileexecutinginstructions,forexamplebytryingtoreplicateactionstakenbyhumans.Inparticular,weshowthat,givenonlyasmallseedlexiconandatask-specificexecutor,wecaninducehighqualitymodelsforinterpretingcomplexinstructions.Weevaluatethemethodonabenchmarknaviga-tionalinstructionsdataset(MacMahonetal.,2006;Chen&Mooney,2011).Ourjointapproachsuc-cessfullycompletes60%moreinstructionsetsrel-ativetothepreviousstateoftheart.Wealsore-portexperimentsthatvarysupervisiontype,findingthatobservingthefinalpositionofaninstructionex-ecutionisnearlyasinformativeasobservingtheen-tirepath.Finally,wepresentimprovedresultsonanewversionoftheMacMahonetal.(2006)corpus,whichwefilteredtoincludeonlyexecutableinstruc-tionspairedwithcorrecttraces.2TechnicalOverviewTaskLetSbethesetofpossibleenvironmentstatesandAbethesetofpossibleactions.Givenastartstates∈Sandanaturallanguageinstruc-tionx,weaimtogenerateasequenceofactions~a=ha1,…,ani,witheachai∈A,thatperformsthestepsdescribedinx.Forexample,inthenavigationdomain(MacMa-honetal.,2006),Sisasetofpositionsonamap.Eachstates=(X,oui,o)isatriple,wherexandyareintegergridcoordinatesando∈{0,90,180,270}isanorientation.Figure2showsanexamplemapwith36states;theonesweuseinourexperimentscon-tainanaverageof141.ThespaceofpossibleactionsAis{LEFT,RIGHT,MOVE,NULL}.Actionschangethestateoftheworldaccordingtoatransitionfunc-tionT:A×S→S.Inournavigationexample,movingforwardcanchangethexorycoordinateswhileturningchangestheorientationo.ModelTomapinstructionstoactions,wejointlyreasonaboutlinguisticmeaningandactionexecu-tion.WeuseaweightedCCGgrammartorankpos-siblemeaningszforeachinstructionx.Section6defineshowtodesignsuchgrammarsforinstruc-tionallanguage.Eachlogicalformzismappedtoasequenceofactions~awithadeterministicexecutor,asdescribedinSection7.ThefinalgroundedCCGmodel,detailedinSection6.3,jointlyconstructsandscoreszand~a,allowingforrobustsituatedreason-ingduringsemanticinterpretation.LearningWeassumeaccesstoatrainingsetcon-tainingnexamples{(xi,si,Vi):je = 1…n},eachcontaininganaturallanguagesentencexi,astartstatesi,andavalidationfunctionVi.ThevalidationfunctionVi:A→{0,1}mapsanactionsequence~a∈Ato1ifit’scorrectaccordingtoavailablesu-pervision,or0otherwise.Thistrainingdatacontainsnodirectevidenceaboutthelogicalformziforeachxi,orthegroundedCCGanalysisusedtoconstructzi.Wemodelallthesechoicesaslatentvariables.Weexperimentwithtwovalidationfunctions.Thefirst,VD(~a),hasaccesstoanobservabledemonstra-tionoftheexecution~ai,agiven~aisvalidiff~a=~ai.Thesecond,VSi(~a),onlyencodesthefinalstates0ioftheexecutionofx,therefore~aisvalidiffitsfinalstateiss0i.Sincenumerouslogicalformsoftenex-ecuteidentically,bothfunctionsprovidehighlyam-biguoussupervision.EvaluationWeevaluatetaskcompletionforsin-gleinstructionsonatestset{(xi,si,s0i):je = 1…n},wheres0iisthefinalstateofanoracleagentfollowingtheexecutionofxistartingatstatesi.Wewillalsoreportaccuraciesforcorrectlyinterpretinginstructionsequences~x,whereasingleerrorcancausetheentiresequencetofail.Finally,wereportaccuracyonrecoveringcorrectlogicalformszionamanuallyannotatedsubsetofthetestset.3RelatedWorkOurlearningisinspiredbythereinforcementlearn-ing(RL)approachofBranavanetal.(2009),andrelatedmethods(Vogel&Jurafsky,2010),butuseslatentvariablemodelupdateswithinasemanticparser.Branavanetal.(2010)extendedtheirRLap-proachtomodelhigh-levelinstructions,whichcor-respondtoimplicitactionsinourdomain.Weietal.(2009)andKollaretal.(2010)usedshallowlinguis-ticrepresentationsforinstructions.Recently,Tellex
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
0
9
1
5
6
6
6
4
3
/
/
t
je
un
c
_
un
_
0
0
2
0
9
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
51
etal.(2011)usedagraphicalmodelsemanticsrep-resentationtolearnfrominstructionspairedwithdemonstrations.Incontrast,wemodelsignificantlymorecomplexlinguisticphenomenathantheseap-proaches,asrequiredforthenavigationdomain.Otherresearchhasadoptedexpressivemeaningrepresentations,withdifferinglearningapproaches.Matuszeketal.(2010,2012)describesupervisedal-gorithmsthatlearnsemanticparsersfornavigationinstructions.ChenandMooney(2011),Chen(2012)andKimandMooney(2012)presentstate-of-the-artalgorithmsforthenavigationtask,bytrainingasupervisedsemanticparserfromautomaticallyin-ducedlabels.Ourworkdiffersintheuseofjointlearningandinferenceapproaches.Supervisedapproachesforlearningsemanticparsershavereceivedsignificantattention,e.g.KateandMooney(2006),WongandMooney(2007),Muresan(2011)andKwiatkowskietal.(2010,2012).Thealgorithmswedevelopinthispa-percombineideasfromprevioussupervisedCCGlearningwork(Zettlemoyer&Collins,2005,2007;Kwiatkowskietal.,2011),aswedescribeinSec-tion4.Recently,variousalternativeformsofsu-pervisionwereintroduced.Clarkeetal.(2010),GoldwasserandRoth(2011)andLiangetal.(2011)describeapproachesforlearningsemanticparsersfromsentencespairedwithresponses,Krishna-murthyandMitchell(2012)describeusingdistantsupervision,ArtziandZettlemoyer(2011)useweaksupervisionfromconversationallogsandGold-wasseretal.(2011)presentworkonunsupervisedlearning.Wediscussvariousformsofsupervisionthatcomplementtheseapproaches.Therehasalsobeenworkonlearningforsemanticanalysistasksfromgroundeddata,includingeventstreams(Liangetal.,2009;Chenetal.,2010)andlanguagepairedwithvisualperception(Matuszeketal.,2012).Enfin,thetopicofexecutinginstructionsinnon-learningsettingshasreceivedsignificantatten-tion(e.g.,Winograd(1972),DiEugenioandWhite(1992),Webberetal.(1995),Bugmannetal.(2004),MacMahonetal.(2006)andDzifcaketal.(2009)).4BackgroundWeuseaweightedlinearCCGgrammarforseman-ticparsing,asbrieflyreviewedinthissection.CombinatoryCategorialGrammars(CCGs)CCGsarealinguistically-motivatedformalismformodelingawiderangeoflanguagephenom-ena(Steedman,1996,2000).ACCGisdefinedbyalexiconandasetofcombinators.Thelexiconcon-tainsentriesthatpairwordsorphraseswithcate-gories.Forexample,thelexicalentrychair‘N:λx.chair(X)fortheword“chair”intheparseinFig-ure4pairsitwithacategorythathassyntactictypeNandmeaningλx.chair(X).Figure4showshowaCCGparsebuildsalogicalformforacompletesen-tenceinourexamplenavigationdomain.Startingfromlexicalentries,eachintermediateparsenode,includingsyntaxandsemantics,isconstructedwithoneofasmallsetofCCGcombinators(Steedman,1996,2000).Weusetheapplication,compositionandcoordinationcombinators,andthreeothersde-scribedinSection6.3.FactoredCCGLexiconsRecently,Kwiatkowskietal.(2011)introducedafactoredCCGlexiconrepresentation.Eachlexicalitemiscomposedofalexemeandatemplate.Forexample,theentrychair‘N:λx.chair(X)wouldbeconstructedbycombiningthelexemechair‘[chair],whichcon-tainsawordpairedwithlogicalconstants,withthetemplateλv.[N:λx.v(X)],thatdefinestherestofthecategorybyabstractingoverlogicalconstants.Thisapproachallowsthereuseofcommonsyntacticstructuresthroughasmallsetoftemplates.Section8describeshowwelearnsuchlexicalentries.WeightedLinearCCGsAweightedlinearCCG(Clark&Curran,2007)ranksthespaceofpossibleparsesunderthegrammar,andiscloselyrelatedtoseveralotherapproaches(Laffertyetal.,2001;Collins,2004;Taskaretal.,2004).Letxbeasentence,ybeaCCGparse,andGEN(X;Λ)bethesetofallpossibleCCGparsesforxgiventhelexi-conΛ.Defineφ(X,oui)∈Rdtobead-dimensionalfeature–vectorrepresentationandθ∈Rdtobeapa-rametervector.Theoptimalparseforsentencexisy∗(X)=argmaxy∈GEN(X;Λ)θ·φ(X,oui)andthefinaloutputlogicalformzistheλ-calculusexpressionattherootofy∗(X).Section7.2de-scribeshowweefficientlycomputeanapproxima-tiontoy∗(X)withinthejointinterpretationandexe-cutionmodel.
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
0
9
1
5
6
6
6
4
3
/
/
t
je
un
c
_
un
_
0
0
2
0
9
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
52
SupervisedlearningwithGENLEXPreviouswork(Zettlemoyer&Collins,2005)introducedafunctionGENLEX(X,z)tomapasentencexanditsmeaningztoalargesetofpotentiallexicalentries.TheseentriesaregeneratedbyrulesthatconsiderthelogicalformzandguesspotentialCCGcategories.Forexample,therulep→N:λx.p(X)introducescategoriescommonlyusedtomodelcertaintypesofnouns.Thisrulewould,forexample,introducethecategoryN:λx.chair(X)foranylogicalformzthatcontainstheconstantchair.GENLEXusesasmallsetofsuchrulestogeneratecategoriesthatarepairedwithallpossiblesubstringsinx,tocreatealargesetoflexicalentries.Thecompletelearningalgorithmthensimultaneouslyselectsasmallsub-setoftheseentriesandestimatesparametervaluesθ.InSection8,wewillintroduceanewwayofusingGENLEXtolearnfromdifferentsignalsthat,crucially,donotrequirealabeledlogicalformz.5SpatialEnvironmentModelingWewillexecuteinstructionsinanenvironment,seeSection2,whichhasasetofpositions.Apositionisatriple(X,oui,o),wherexandyarehorizontalandverticalcoordinates,ando∈O={0,90,180,270}isanorientation.Apositionalsoincludespropertiesindicatingtheobjectitcontains,itsfloorpatternanditswallpaper.Forexample,thesquareat(4,3)inFigure2hasfourpositions,oneperorientation.Becauseinstructionallanguagereferstoobjectsandotherstructuresinanenvironment,weintroducethenotionofapositionset.Forexample,inFigure2,thepositionsetD={(5,3,o):o∈O}representsachair,whileB={(X,3,o):o∈O,x∈[0…5]}representsthebluefloor.Bothsetscontainallori-entationsforeach(X,oui)pair,therebyrepresentingpropertiesofregions.Positionsetscanhavemanyproperties.Forexample,E,inadditiontobeingachair,isalsoanintersectionbecauseitoverlapswiththeneighboringhallsAandB.Thesetofpossi-bleentitiesincludesallpositionsetsandafewaddi-tionalentries.Forexample,setC={(4,3,90)}inFigure2representstheagent’sposition.6ModelingInstructionalLanguageWeaimtodesignasemanticrepresentationthatislearnable,modelsgroundedphenomenasuchasspa-X
oui
1
2
3
4
5
1
2
3
4
5
270
90
0
180
C
D
E
UN
B
(cid:26)D
E
(cid:27)(un)chairλx.chair(X)(cid:26)UN
B
(cid:27)(b)hallλx.hall(X)E
(c)thechairιx.chair(X)C
(d)youyou(cid:26)B
(cid:27)(e)bluehallλx.hall(X)∧blue(X)(cid:26)E
(cid:27)(F)chairintheintersectionλx.chair(X)∧intersect(ιy.junction(oui),X)(cid:26)UN
B
E
(cid:27)(g)infrontofyouλx.infrontof(toi,X)Figure2:Schematicdiagramofamapenvironmentandexampleofsemanticsofspatialphrases.tialrelationsandobjectreference,andisexecutable.OursemanticrepresentationcombinesideasfromCarpenter(1997)andNeo-Davidsonianeventse-mantics(Parsons,1990)inasimplytypedλ-calculus.Therearefourbasictypes:(1)entitiesethatareobjectsintheworld,(2)eventsevthatspec-ifyactionsintheworld,(3)truthvaluest,et(4)meta-entitiesm,suchasnumbersordirections.Wealsoallowfunctionaltypes,whicharedefinedbyin-putandoutputtypes.Forexample,il,tiisthetypeoffunctionfromentitiestotruthvalues.6.1SpatialLanguageModelingNounsandNounPhrasesNounphrasesarepairedwithe-typeconstantsthatnamespecificen-titiesandnounsaremappedtohe,ti-typeexpres-sionsthatdefineaproperty.Forexample,thenoun“chair”(Figure2a)ispairedwiththeexpressionλx.chair(X),whichdefinesthesetofobjectsfor
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
0
9
1
5
6
6
6
4
3
/
/
t
je
un
c
_
un
_
0
0
2
0
9
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
53
whichtheconstantchairreturnstrue.Thedeno-tationofthisexpressionistheset{D,E}inFig-ure2andthedenotationofλx.hall(X)(Figure2b)est{UN,B}.Aussi,thenounphrase“you”(Figure2d),whichnamestheagent,isrepresentedbythecon-stantyouwithdenotationC,theagent’sposition.DeterminersNounphrasescanalsobeformedbycombiningnounswithdeterminersthatpickoutspe-cificobjectsintheworld.Weconsiderbothdefinitereference,whichnamescontextuallyuniqueobjects,andindefinites,whicharelessconstrained.Thedefinitearticleispairedwithalogicalexpres-sionιoftypehhe,ti,ei,1whichwillnameasin-gleobjectintheworld.Forexample,thephrase“thechair”inFigure2cwillberepresentedbyιx.chair(X)whichwilldenotetheappropriatechair.However,computingthisdenotationischallengingwhenthereisperceptualambiguity,forpositionswheremultiplechairsarevisible.Weadoptasim-pleheuristicapproachthatranksreferentsbasedonacombinationoftheirdistancefromtheagentandwhethertheyareinfrontofit.Forourexample,frompositionCouragentwouldpickthechairEinfrontofitasthedenotation.Theapproachdif-fersfromprevious,non-groundedmodelsthatfailtonameobjectswhenfacedwithsuchambiguity(e.g.,Carpenter(1997),HeimandKratzer(1998)).Tomodelthemeaningofindefinitearticles,wedepartfromtheFrege-Montaguetraditionofus-ingexistentialquantifiers(Lewis,1970;Montague,1973;Barwise&Tonnelier,1981),andinsteadin-troduceanewquantifierAthat,likeι,hastypehhe,ti,ei.Forexample,thephrase“achair”wouldbepairedwithAx.chair(X)whichdenotesanarbi-traryentryfromthesetofchairsintheworld.Com-putingthedenotationforsuchexpressionsinaworldwillrequirepickingaspecificobject,withoutfur-therrestrictions.ThisapproachiscloselyrelatedtoSteedman’sgeneralizedSkolemterms(2011).2MetaEntitiesWeusem-typedtermstorepresentnon-physicalentities,suchasnumbers(1,2,etc.)anddirections(gauche,droite,etc.)whosedenotations1Althoughquantifiersarelogicalconstantswithtypehhe,ti,eiorhhe,ti,ti,weuseanotationsimilartothatusedforfirst-orderlogic.Forexample,thenotationιx.f(X)repre-sentsthelogicalexpressionι(λx.f(X))2Steedman(2011)usesgeneralizedSkolemtermsasatoolforresolvinganaphoricpronouns,whichwedonotmodel.arefixed.Theabilitytorefertodirectionsallowsustomanipulatepositionsets.Forexample,thephrase“yourleft”ismappedtothelogicalexpres-sionorient(toi,gauche),whichdenotesthepositionsetcontainingthepositiontotheleftoftheagent.PrepositionsandAdjectivesNounphraseswithmodifiers,suchasadjectivesandprepositionalphrasesarehe,ti-typeexpressionsthatimplementsetintersectionwithlogicalconjunctions.Forex-ampleinFigure2,thephrase“bluehall”ispairedwithλx.hall(X)∧blue(X)withdenotation{B}andthephrase“chairintheintersection”ispairedwithλx.chair(X)∧intersect(ιy.junction(oui),X)withdenotation{E}.Intuitively,theadjective“blue”introducestheconstantblueand“inthe”addsaintersect.WewilldescribethefulldetailsofhowtheseexpressionsareconstructedinSection6.3.SpatialRelationsThesemanticrepresentational-lowsmorecomplexreasoningoverpositionsetsandtherelationsbetweenthem.Forexample,thebi-naryrelationinfrontof(Figure2g)testsifthefirstargumentisinfrontofthesecondfromthepointofviewoftheagent.Additionalrelationsareusedtomodelsetintersection,relativedirection,relativedistance,andrelativepositionbydistance.6.2ModelingInstructionsTomodelactionsintheworld,weadoptNeo-Davidsonianeventsemantics(Davidson,1967;Par-sons,1990),whichtreatseventsasev-typeprimitiveobjects.Suchanapproachallowsforacompactlex-iconwhereadverbialmodifiersintroducepredicates,whicharelinkedbyasharedeventargument.Instructionallanguageischaracterizedbyheavyusageofimperatives,whichwemodelasfunc-tionsfromeventstotruthvalues.3Forexample,animperativesuchas“move”wouldhavethemean-ingλa.move(un),whichdefinesasetofeventsthatmatchthespecifiedconstraints.Here,thissetwouldincludealleventsthatinvolvemovingactions.Thedenotationofev-typetermsisasequenceofninstancesofthesameaction.Inthisway,aneventdefinesafunctionev:s→s0,wheresisthestartstateands0theendstate.Forexample,the3Imperativesarehev,ti-type,muchlikehe,ti-typewh-interrogatives.Bothdefinesets,theformerincludesactionstoexecute,thelaterdefinesanswerstoaquestion.
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
0
9
1
5
6
6
6
4
3
/
/
t
je
un
c
_
un
_
0
0
2
0
9
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
54
denotationofλa.move(un)isthesetofmoveactionsequences{hMOVE1,…,MOVEni:n≥1}.Al-thoughperformingactionsoftenrequireperformingadditionalones(e.g.,theagentmighthavetoturnbeforebeingabletomove),wetreatsuchactionsasimplicit(Section7.1),anddon’tmodelthemexplic-itlywithinthelogicalform.Predicatessuchasmove(seenabove)andturnareintroducedbyverbs.Eventscanalsobemodifiedbyadverbials,whichareintersective,muchlikeprepositionalphrases.Forexampleintheimperative,logicalform(LF)pair:Imp.:movefromthesofatothechairLF:λa.move(un)∧to(un,ιx.chair(X))∧from(un,ιy.sofa(oui))Eachadverbialphraseprovidesaconstraint,andchangingtheirorderwillnotchangetheLF.6.3ParsingInstructionalLanguagewithCCGTocomposelogicalexpressionsfromsentencesweuseCCG,asdescribedinSection4.Figures3and4presentasampleoflexicalentriesandhowtheyarecombined,aswewilldescribeinthissection.ThebasicsyntacticcategoriesareN(noun),NP(nounphrase),S(sentence),PP(prepositionalphrase),AP(adverbialphrase),ADJ(adjective)andC(aspecialcategoryforcoordinators).TypeRaisingTocompactlymodelsyntacticvari-ations,wefollowCarpenter(1997),whoarguesforpolymorphictyping.Weincludethemoresimple,orlowertype,entryinthelexiconandintroducetype-raisingrulestoreconstructtheotherwhennecessaryatparsetime.Weusefourrules:PP:g→N\N:λf.λx.f(X)∧g(X)ADJ:g→N/N:λf.λx.f(X)∧g(X)AP:g→S\S:λf.λa.f(un)∧g(un)AP:g→S/S:λf.λa.f(un)∧g(un)wherethefirstthreeareforprepositional,adjectivalandadverbialmodifications,andthefourthmodelsthefactthatadverbialsareoftentopicalized.4Fig-ures3and4showparsesthatusetype-raisingrules.IndefinitesAsdiscussedinSection6.1,weuseanewsyntacticanalysisforindefinites,follow-4Usingtype-raisingrulescanbeparticularlyusefulwhenlearningfromsparsedata.Forexample,itwillnolongerbenecessarytolearnthreelexicalentriesforeachadverbialphrase(withsyntaxAP,S\S,andS/S).chairinthecornerNPP/NPNP/NNλx.chair(X)λx.λy.intersect(X,oui)λf.Ax.f(X)λx.corner(X)>NPιx.corner(X)>PPλy.intersect(ιx.corner(X),oui)N\Nλf.λy.f(oui)∧intersect(ιx.chair(X),oui)APλa.post(un,intersect(Ax.chair(X),toi))S\Sλf.λa.f(un)∧post(un,intersect(Ax.chair(X),toi))
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
0
9
1
5
6
6
6
4
3
/
/
t
je
un
c
_
un
_
0
0
2
0
9
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
56
ImplicitActionsInstructionallanguagerarelyspecifieseveryactionrequiredforexecution,seeMacMahon(2007)foradetaileddiscussioninthemapsdomain.Forexample,thesentenceinFig-ure4canbesaideveniftheagentisnotfacingabluehallway,withtheclearimplicitrequestthatitshouldturntofacesuchahallwaybeforemoving.Toallowouragenttoperformimplicitactions,weextendthedomainofev-typevariablesbyallowingtheagenttoprefixuptokIactionsequencesbeforeeachexplicitevent.Forexample,intheagent’spo-sitioninFigure2(setC),thesetofpossibleeventsincludeshMOVEI,MOVEI,RIGHTI,MOVEi,whichcontainstwoimplicitsequences(markedbyI).ResolvingActionAmbiguityLogicalformsof-tenfailtodetermineauniqueactionsequences,duetoinstructionambiguity.Forexample,con-sidertheinstruction“goforward”andtheagentstateasspecifiedinFigure2(setC).Theinstruction,whichmapstoλa.move(un)∧forward(un),evalu-atestothesetcontaininghMOVEi,hMOVE,MOVEiandhMOVE,MOVE,MOVEi,aswellasfiveotherse-quencesthathaveimplicitprefixesfollowedbyex-plicitMOVEactions.Toresolvesuchambiguity,weprefershorteractionswithoutimplicitactions.Intheexampleabove,wewillselecthMOVEi,whichincludesasingleactionandnoimplicitactions.7.2JointInferenceWeincorporatetheexecutionproceduredescribedabovewithalinearweightedCCGparser,asde-scribedinSection4,tocreateajointmodelofpars-ingandexecution.Specifically,weexecutelogi-calformsinthecurrentstateandobservetheresultoftheirexecution.Forexample,theword“chair”canbeusedtorefertodifferenttypesofobjects,in-cludingchairs,sofas,andbarstools,inthemapsdo-mains.OurCCGgrammarwouldincludealexicalitemforeachmeaning,butexecutionmightfailde-pendingonthepresenceofobjectsintheworld,in-fluencingthefinalparseoutput.Similarly,allowingimplicitactionsprovidesrobustnesswhenresolv-ingtheseandotherambiguities.Forexample,aninstructionwiththepreconditionphrase“fromthechair”mightrequireadditionalactionstoreachthepositionwiththenamedobject.Toallowsuchjointreasoningwedefineanex-ecutionetoincludeaparsetreeeyandtracee~a,anddefineourfeaturefunctiontobeΦ(xi,si,e),wherexiisaninstructionandsiisthestartstate.Thisapproachallowsjointdependencies:thestateoftheworldinfluenceshowtheagentinterpretswords,phrasesandevencompletesentences,whilelanguageunderstandingdeterminesactions.Finally,toexecutesequencesofinstructions,weexecuteeachstartingfromtheendstateoftheprevi-ousone,usingabeamofsizeks.8LearningFigure5presentsthecompletelearningalgorithm.Ourapproachisonline,consideringeachexampleinturnandperformingtwosteps:expandingthelex-iconandupdatingparameters.Thealgorithmas-sumesaccesstoatrainingset{(xi,si,Vi):je = 1…n},whereeachexampleincludesaninstructionxi,startingstatesiandavalidationfunctionVi,asdefinedinSection2.InadditionthealgorithmtakesaseedlexiconΛ0.Theoutputisajointmodel,thatincludesalexiconΛandparametersθ.CoarseLexicalGenerationTogeneratepo-tentiallexicalentriesweusethefunctionGENLEX(X,s,V;Λ,je),wherexisanin-struction,sisastateandVisavalidationfunction.Λisthecurrentlexiconandθisaparametervector.InGENLEXweusecoarselogicalconstants,asdescribedbelow,toefficientlyprunethesetofpotentiallexicalentries.ThissetisthenprunedfurtherusingmorepreciseinferenceinStep1.TocomputeGENLEX,weinitiallygeneratealargesetoflexicalentriesandthenprunemostofthem.Thefullsetisgeneratedbytakingthecrossproductofasetoftemplates,computedbyfactor-ingoutalltemplatesintheseedlexiconΛ0,andalllogicalconstants.Forexample,ifΛ0hasalexicalitemwiththecategoryAP/NP:λx.λa.to(un,X)wewouldcreateentriesw‘AP/NP:λx.λa.p(un,X)foreveryphrasewinxandallconstantspwiththesametypeasto.5Inourdevelopmentwork,thisapproachoftengeneratednearly100kentriespersentence.Toease5Generalizingpreviouswork(Kwiatkowskietal.,2011),weallowtemplatesthatabstractsubsetsoftheconstantsinalex-icalitem.Forexample,theseedentryfacing‘AP/NP:λx.λa.pre(un,front(toi,X))wouldcreate7templates.
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
0
9
1
5
6
6
6
4
3
/
/
t
je
un
c
_
un
_
0
0
2
0
9
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
57
Inputs:Trainingset{(xi,si,Vi):je = 1…n}wherexiisasentence,siisastateandViisavalidationfunction,asde-scribedinSection2.InitiallexiconΛ0.NumberofiterationsT.Marginγ.Beamsizekforlexicongeneration.Definitions:Letanexecutioneincludeaparsetreeeyandatracee~a.GEN(X,s;Λ)isthesetofallpossibleexecu-tionsfortheinstructionxandstates,giventhelexiconΛ.LEX(oui)isthesetoflexicalentriesusedintheparsetreey.LetΦi(e)beshorthandforthefeaturefunctionΦ(xi,si,e)definedinSection7.2.Define∆i(e,e0)=|Φi(e)−Φi(e0)|1.GENLEX(X,s,V;λ,je)takesasinputaninstructionx,states,validationfunctionV,lexiconλandmodelparam-etersθ,andreturnsasetoflexicalentries,asdefinedinSec-tion8.Finally,forasetofexecutionsEletMAXVi(E;je)être{e|∀e0∈E,hθ,Φi(e0)i≤hθ,Φi(e)i∧Vi(e~a)=1},thesetofhighestscoringvalidexecutions.Algorithm:InitializeθusingΛ0,Λ←Λ0Fort=1…T,je = 1…n:Step1:(Lexicalgeneration)a.SetλG←GENLEX(xi,si,Vi;Λ,je),λ←Λ∪λGb.LetEbethekhighestscoringexecutionsfromGEN(xi,si;λ)whichuseatmostoneentryfromλGc.Selectlexicalentriesfromthehighestscoringvalidparses:λi←Se∈MAXVi(E;je)LEX(ey)d.Updatelexicon:Λ←Λ∪λiStep2:(Updateparameters)a.SetGi←MAXVi(GEN(xi,si;Λ);je)andBi←{e|e∈GEN(xi,si;Λ)∧Vi(e~a)6=1}b.Constructsetsofmarginviolatinggoodandbadparses:Ri←{g|g∈Gi∧∃b∈Bis.t.hθ,Φi(g)−Φi(b)je<γ∆i(g,b)}Ei←{b|b∈Bi∧∃g∈Gis.t.hθ,Φi(g)−Φi(b)i<γ∆i(g,b)}c.Applytheadditiveupdate:θ←θ+1|Ri|Pr∈RiΦi(r)−1|Ei|Pe∈EiΦi(e)Output:ParametersθandlexiconΛFigure5:Thelearningalgorithm.thecostofparsingatthisscale,wedevelopedacoarse-to-finetwo-passparsingapproachthatlim-itsthenumberofnewentriesconsidered.Thealgo-rithmfirstparseswithcoarselexicalentriesthatab-stracttheidentitiesofthelogicalconstantsintheirlogicalforms,therebygreatlyreducingthesearchspace.Itthenusesthehighestscoringcoarseparsestoconstrainthelexicalentriesforafinal,fineparse.Formally,weconstructthecoarselexiconλabyreplacingallconstantsofthesametypewithasinglenewlycreated,temporaryconstant.WethenparsetocreateasetoftreesA,suchthateachy∈A1.isaparseforsentencex,giventheworldstateswiththecombinedlexiconΛ∪λa,2.scoredhigherthaneybyatleastamarginofδL,whereeyisthetreeofe,thehighestscoringexecutionofx,atpositionsunderthecurrentmodel,s.t.V(e~a)=1,3.containsatmostoneentryfromλa.Finally,fromeachentryl∈{l|l∈λa∧l∈y∧y∈A},wecreatemultiplelexicalentriesbyreplacingalltemporaryconstantswithallpossibleappropriatelytypedconstantsfromtheoriginalset.GENLEXreturnsalltheselexicalentries,whichwillbeusedtoformourfinalfine-levelanalysis.Step1:LexicalInductionToexpandourmodel’slexicon,weuseGENLEXtogeneratecandidatelexicalentriesandthenfurtherrefinethissetbypars-ingwiththecurrentmodel.Step1(a)inFigure5usesGENLEXtocreateatemporarysetofpo-tentiallexicalentriesλG.Steps(b-d)selectasmallsubsetoftheselexicalentriestoaddtothecurrentlexiconΛ:wefindthek-bestexecutionsunderthemodel,whichuseatmostoneentryfromλG,findtheentriesusedinthebestvalidexecutionsandaddthemtothecurrentlexicon.Step2:ParameterUpdateWeuseavariantofaloss-drivenperceptron(Singh-Miller&Collins,2007;Artzi&Zettlemoyer,2011)forparameterup-dates.However,insteadoftakingadvantageofalossfunctionweuseavalidationsignal.Instep(a)wecollectthehighestscoringvalidparsesandallin-validparses.Then,instep(b)weconstructthesetRiofvalidanalysesandEiofinvalidones,suchthattheirmodelscoresarenotseparatedbyamar-ginδscaledbythenumberofwrongfeatures(Taskaretal.,2003).Finally,step(f)appliestheupdate.DiscussionThealgorithmusesthevalidationsig-naltodrivebothlexicalinductionandparameterupdates.Unlikepreviouswork(Zettlemoyer&Collins,2005,2007;Artzi&Zettlemoyer,2011),wehavenoaccesstoasetoflogicalconstants,eitherthroughthethelabeledlogicalformortheweaksupervisionsignal,toguidetheGENLEXprocedure.Therefore,toavoidover-generatinglex-icalentries,therebymakingparsingandlearningintractable,weleveragetypingforcoarseparsingtoprunethegeneratedset.Byallowingasingle
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
2
0
9
1
5
6
6
6
4
3
/
/
t
l
a
c
_
a
_
0
0
2
0
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
58
OracleSAIL#ofinstructionsequences501706#ofinstructionsequenceswithimplicitactions431Total#ofsentences26793233Avg.sentencespersequence5.354.61Avg.tokenspersentence7.57.94Vocabularysize373522Table1:Corporastatistics(lower-caseddata).newentryperparse,wecreateaconservative,cas-cadingeffect,whereasalexicalentrythatisintro-ducedopensthewayformanyothersentencetobeparsedandintroducenewlexicalentries.Further-more,groundedfeaturesimproveparseselection,therebygeneratinghigherqualitylexicalentries.9ExperimentalSetupDataForevaluation,weusethenavigationtaskfromMacMahonetal.(2006),whichincludesthreeenvironmentsandtheSAILcorpusofinstructionsandfollowertraces.ChenandMooney(2011)seg-mentedthedata,alignedtracestoinstructions,andmergedtracescreatedbydifferentsubjects.Thecorpusincludesrawsentences,withoutanyformoflinguisticannotation.Theoriginalcollectionpro-cess(MacMahonetal.,2006)createdmanyunin-terpretableinstructionsandincorrecttraces.Tofo-cusonthelearningandinterpretationtasks,wealsocreatedanewdatasetthatincludesonlyaccuratein-structionslabeledwithasingle,correctexecutiontrace.Fromthisoraclecorpus,werandomlysam-pled164instructionsequences(816sentences)forevaluation,leaving337(1863sentences)fortrain-ing.Thissimpleeffortwillallowustomeasuretheeffectsofnoiseonthelearningapproachandpro-videsaresourceforbuildingmoreaccuratealgo-rithms.Table1comparesthetwosets.FeaturesandParserFollowingZettlemoyerandCollins(2005),weuseaCKYparserwithabeamofk.Toboostrecall,weadoptatwo-passstrategy,whichallowsforwordskippingiftheinitialparsefails.Weusefeaturesthatindicateusageoflexicalentries,templates,lexemesandtype-raisingrules,asdescribedinSection6.3,andrepetitionsinlogicalcoordinations.Finally,duringjointparsing,wecon-sideronlyparsesexecutableatsiascomplete.SeedLexiconToconstructourseedlexiconwela-beled12instructionsequenceswith141lexicalen-SingleSentenceSequenceFinalstatevalidationCompletesystem81.98(2.33)59.32(6.66)Noimplicitactions77.7(3.7)38.46(1.12)Nojointexecution73.27(3.98)31.51(6.66)TracevalidationCompletesystem82.74(2.53)58.95(6.88)Noimplicitactions77.64(3.46)38.34(6.23)Nojointexecution72.85(4.73)30.89(6.08)Table2:Cross-validationdevelopmentaccuracyandstandarddeviationontheoraclecorpus.tries.Thesequenceswererandomlyselectedfromthetrainingset,soastoincludetwosequencesforeachparticipantintheoriginalexperiment.Fig-ures3and4includeasampleofourseedlexicon.InitializationandParametersWesettheweightofeachtemplateindicatorfeaturetothenumberoftimesitisusedintheseedlexiconandeachrepeti-tionfeatureto-10.Learningparametersweretunedusingcross-validationonthetrainingset:themar-ginδissetto1,theGENLEXmarginδLissetto2,weuse6iterations(8forexperimentsonSAIL)andtakethe250topparsesduringlexicalgenera-tion(step1,Figure5).Forparameterupdate(step2,Figure5)weuseaparserwithabeamof100.GENLEXgenerateslexicalentriesfortokense-quencesuptolength4.ks,theinstructionsequenceexecutionbeam,issetto10.Finally,kIissetto2,allowinguptotwoimplicitactionsequencesperexplicitone.EvaluationMetricsToevaluatesingleinstruc-tionsx,wecomparetheagent’sendstatetoalabeledstates0,asdescribedinSection2.Weuseasimilarmethodtoevaluatetheexecutionofinstructionse-quences~x,butdisregardtheorientation,sinceendgoalsinMacMahonetal.(2006)aredefinedwith-outorientation.Whenevaluatinglogicalformswemeasureexactmatchaccuracy.10ResultsWerepeatedeachexperimentfivetimes,shufflingthetrainingsetbetweenruns.Forthedevelopmentcross-validationruns,wealsoshuffledthefolds.Asourlearningapproachisonline,thisallowsustoac-countforperformancevariationsarisingfromtrain-ingsetordering.Wereportmeanaccuracyandstan-darddeviationacrossallruns(andallfolds).
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
2
0
9
1
5
6
6
6
4
3
/
/
t
l
a
c
_
a
_
0
0
2
0
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
59
SingleSentenceSequenceChenandMooney(2011)54.416.18Chen(2012)57.2819.18+additionaldata57.6220.64KimandMooney(2012)57.2220.17Tracevalidation65.28(5.09)31.93(3.26)Finalstatevalidation64.25(5.12)30.9(2.16)Table3:Cross-validationaccuracyandstandardde-viationfortheSAILcorpus.Table2showsaccuracyfor5-foldcross-validationontheoracletrainingdata.Wefirstvariedthevalidationsignalbyprovidingthecompleteac-tionsequenceorthefinalstateonly,asdescribedinSection2.Althoughthefinalstatesignalisweaker,theresultsaresimilar.Therelativelylargedifferencebetweensinglesentenceandsequenceperformanceisdueto(1)cascadingerrorsinthemoredifficulttaskofsequentialexecution,and(2)corpusrepe-titions,wheresimplesentencesarecommon(e.g.,“turnleft”).Next,wedisabledthesystem’sabilitytointroduceimplicitactions,whichwasespeciallyharmfultothefullsequenceperformance.Finally,ablatingthejointexecutiondecreasesperformance,showingthebenefitofthejointmodel.Table3listscrossvalidationresultsontheSAILcorpus.Tocomparetopreviouswork(Chen&Mooney,2011),wereportcross-validationresultsoverthethreemaps.Theapproachwasabletocor-rectlyexecute60%moresequencesthentheprevi-ousstateoftheart(Kim&Mooney,2012).WealsooutperformtheresultsofChen(2012),whichused30%moretrainingdata.6Usingtheweakervalidationsignalcreatesamarginaldecreaseinper-formance.However,westilloutperformallprevi-ouswork,despiteusingweakersupervision.Inter-estingly,theseincreaseswereachievedwitharel-ativelysimpleexecutor,whilepreviousworkusedMARCO(MacMahonetal.,2006),whichsupportssophisticatedrecoverystrategies.Finally,weevaluateourapproachontheheldouttestsetfortheoraclecorpus(Table4).IncontrasttoexperimentsontheChenandMooney(2011)cor-pus,weuseaheldoutsetforevaluation.Duetothisdiscrepancy,alldevelopmentwasdoneonthetrain-ingsetonly.Theincreaseinaccuracyoverlearningwiththeoriginalcorpusdemonstratesthesignificantimpactofnoiseonourperformance.Inadditionto6Thisadditionaltrainingdataisn’tpubliclyavailable.ValidationSingleSentenceSequenceLFFinalstate77.6(1.14)54.63(3.5)44(6.12)Trace78.63(0.84)58.05(3.12)51.05(1.14)Table4:Oraclecorpustestaccuracyandstandarddeviationresults.executionresults,wealsoreportexactmatchlogi-calform(LF)accuracyresults.Forthispurpose,weannotated18instructionsequences(105sentences)withlogicalforms.ThegapbetweenexecutionandLFaccuracycanbeattributedtothecomplexityofthelinguisticrepresentationandredundancyinin-structions.Theseresultsprovideanewbaselineforstudyinglearningfromcleanersupervision.11DiscussionWeshowedhowtodogroundedlearningofaCCGsemanticparserthatincludesajointmodelofmean-ingandcontextforexecutingnaturallanguagein-structions.Thejointnatureallowssituatedcuestodirectlyinfluenceparsingandalsoenablesalgo-rithmsthatlearnwhileexecutinginstructions.Thisstyleofalgorithm,especiallywhenusingtheweakerendstatevalidation,iscloselyrelatedtore-inforcementlearningapproaches(Branavanetal.,2009,2010).However,wedifferonoptimizationandobjectivefunction,whereweaimforminimalloss.WeexpectmanyRLtechniquestobeusefultoscaletomorecomplexenvironments,includingsamplingactionsandusinganexplorationstrategy.Wealsodesignedasemanticrepresentationtocloselymatchthelinguisticstructureofinstructionallanguage,combiningideasfrommanysemantictheories,including,forexample,Neo-Davidsonianevents(Parsons,1990).Thisapproachallowedustolearnacompactandexecutablegrammarthatgen-eralizedwell.Weexpect,infuturework,thatsuchmodelingcanbereusedformoregenerallanguage.AcknowledgmentsTheresearchwassupportedinpartbyDARPAun-dertheDEFTprogramthroughtheAFRL(FA8750-13-2-0019)andtheCSSG(N11AP20020),theARO(W911NF-12-1-0197),andtheNSF(IIS-1115966).TheauthorsthankTomKwiatkowski,NicholasFitzGeraldandAlanRitterforhelpfuldiscussions,DavidChenforprovidingtheevaluationcorpus,andtheanonymousreviewersforhelpfulcomments.
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
2
0
9
1
5
6
6
6
4
3
/
/
t
l
a
c
_
a
_
0
0
2
0
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
60
ReferencesArtzi,Y.,&Zettlemoyer,L.(2011).BootstrappingSe-manticParsersfromConversations.InProceed-ingsoftheConferenceonEmpiricalMethodsinNaturalLanguageProcessing.Barwise,J.,&Cooper,R.(1981).GeneralizedQuanti-fiersandNaturalLanguage.LinguisticsandPhi-losophy,4(2),159–219.Branavan,S.,Chen,H.,Zettlemoyer,L.,&Barzilay,R.(2009).Reinforcementlearningformappingin-structionstoactions.InProceedingsoftheJointConferenceoftheAssociationforComputationalLinguisticsandtheInternationalJointConferenceonNaturalLanguageProcessing.Branavan,S.,Zettlemoyer,L.,&Barzilay,R.(2010).Readingbetweenthelines:learningtomaphigh-levelinstructionstocommands.InProceedingsoftheConferenceoftheAssociationforComputa-tionalLinguistics.Bugmann,G.,Klein,E.,Lauria,S.,&Kyriacou,T.(2004).Corpus-basedrobotics:Arouteinstruc-tionexample.InProceedingsofIntelligentAu-tonomousSystems.Carpenter,B.(1997).Type-LogicalSemantics.TheMITPress.Chen,D.L.(2012).FastOnlineLexiconLearningforGroundedLanguageAcquisition.InProceedingsoftheAnnualMeetingoftheAssociationforCom-putationalLinguistics.Chen,D.,Kim,J.,&Mooney,R.(2010).Trainingamul-tilingualsportscaster:usingperceptualcontexttolearnlanguage.JournalofArtificialIntelligenceResearch,37(1),397–436.Chen,D.,&Mooney,R.(2011).LearningtoInterpretNaturalLanguageNavigationInstructionsfromObservations.InProceedingsoftheNationalCon-ferenceonArtificialIntelligence.Clark,S.,&Curran,J.(2007).Wide-coverageefficientstatisticalparsingwithCCGandlog-linearmod-els.ComputationalLinguistics,33(4),493–552.Clarke,J.,Goldwasser,D.,Chang,M.,&Roth,D.(2010).DrivingSemanticParsingfromtheWorld’sResponse.InProceedingsoftheConfer-enceonComputationalNaturalLanguageLearn-ing.Collins,M.(2004).Parameterestimationforstatis-ticalparsingmodels:Theoryandpracticeofdistribution-freemethods.InNewDevelopmentsinParsingTechnology.Davidson,D.(1967).Thelogicalformofactionsen-tences.Essaysonactionsandevents,105–148.DiEugenio,B.,&White,M.(1992).OntheInterpre-tationofNaturalLanguageInstructions.InPro-ceedingsoftheConferenceoftheAssociationofComputationalLinguistics.Dzifcak,J.,Scheutz,M.,Baral,C.,&Schermerhorn,P.(2009).WhattoDoandHowtoDoIt:Trans-latingNaturalLanguageDirectivesIntoTemporalandDynamicLogicRepresentationforGoalMan-agementandActionExecution.InProceedingsoftheIEEEInternationalConferenceonRoboticsandAutomation.Goldwasser,D.,Reichart,R.,Clarke,J.,&Roth,D.(2011).ConfidenceDrivenUnsupervisedSeman-ticParsing.InProceedingsoftheAssociationofComputationalLinguistics.Goldwasser,D.,&Roth,D.(2011).LearningfromNat-uralInstructions.InProceedingsoftheInterna-tionalJointConferenceonArtificialIntelligence.Heim,I.,&Kratzer,A.(1998).SemanticsinGenerativeGrammar.BlackwellOxford.Kate,R.,&Mooney,R.(2006).UsingString-KernelsforLearningSemanticParsers.InProceedingsoftheConferenceoftheAssociationforComputationalLinguistics.Kim,J.,&Mooney,R.J.(2012).UnsupervisedPCFGInductionforGroundedLanguageLearningwithHighlyAmbiguousSupervision.InProceedingsoftheConferenceonEmpiricalMethodsinNatu-ralLanguageProcessing.Kollar,T.,Tellex,S.,Roy,D.,&Roy,N.(2010).TowardUnderstandingNaturalLanguageDirections.InProceedingsoftheACM/IEEEInternationalCon-ferenceonHuman-RobotInteraction.Krishnamurthy,J.,&Mitchell,T.(2012).WeaklySuper-visedTrainingofSemanticParsers.InProceed-ingsoftheJointConferenceonEmpiricalMeth-odsinNaturalLanguageProcessingandCompu-tationalNaturalLanguageLearning.Kwiatkowski,T.,Goldwater,S.,Zettlemoyer,L.,&Steedman,M.(2012).Aprobabilisticmodelofsyntacticandsemanticacquisitionfromchild-directedutterancesandtheirmeanings.Proceed-ingsoftheConferenceoftheEuropeanChapteroftheAssociationofComputationalLinguistics.Kwiatkowski,T.,Zettlemoyer,L.,Goldwater,S.,&Steedman,M.(2010).InducingprobabilisticCCGgrammarsfromlogicalformwithhigher-order
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
2
0
9
1
5
6
6
6
4
3
/
/
t
l
a
c
_
a
_
0
0
2
0
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
61
unification.InProceedingsoftheConferenceonEmpiricalMethodsinNaturalLanguageProcess-ing.Kwiatkowski,T.,Zettlemoyer,L.,Goldwater,S.,&Steedman,M.(2011).LexicalGeneralizationinCCGGrammarInductionforSemanticParsing.InProceedingsoftheConferenceonEmpiricalMethodsinNaturalLanguageProcessing.Lafferty,J.,McCallum,A.,&Pereira,F.(2001).Con-ditionalRandomFields:ProbabilisticModelsforSegmentingandLabelingSequenceData.InPro-ceedingsoftheInternationalConferenceonMa-chineLearning.Lewis,D.(1970).GeneralSemantics.Synthese,22(1),18–67.Liang,P.,Jordan,M.,&Klein,D.(2009).Learningse-manticcorrespondenceswithlesssupervision.InProceedingsoftheJointConferenceoftheAsso-ciationforComputationalLinguisticstheInterna-tionalJointConferenceonNaturalLanguagePro-cessing.Liang,P.,Jordan,M.,&Klein,D.(2011).LearningDependency-BasedCompositionalSemantics.InProceedingsoftheConferenceoftheAssociationforComputationalLinguistics.MacMahon,M.(2007).FollowingNaturalLanguageRouteInstructions.Ph.D.thesis,UniversityofTexasatAustin.MacMahon,M.,Stankiewics,B.,&Kuipers,B.(2006).WalktheTalk:ConnectingLanguage,Knowl-edge,ActioninRouteInstructions.InProceed-ingsoftheNationalConferenceonArtificialIntel-ligence.Matuszek,C.,FitzGerald,N.,Zettlemoyer,L.,Bo,L.,&Fox,D.(2012).AJointModelofLanguageandPerceptionforGroundedAttributeLearning.Pro-ceedingsoftheInternationalConferenceonMa-chineLearning.Matuszek,C.,Fox,D.,&Koscher,K.(2010).Follow-ingdirectionsusingstatisticalmachinetranslation.InProceedingsoftheinternationalconferenceonHuman-robotinteraction.Matuszek,C.,Herbst,E.,Zettlemoyer,L.S.,&Fox,D.(2012).LearningtoParseNaturalLanguageCom-mandstoaRobotControlSystem.InProceedingsoftheInternationalSymposiumonExperimentalRobotics.Montague,R.(1973).TheProperTreatmentofQuantifi-cationinOrdinaryEnglish.Approachestonaturallanguage,49,221–242.Muresan,S.(2011).LearningforDeepLanguageUnder-standing.InProceedingsoftheInternationalJointConferenceonArtificialIntelligence.Parsons,T.(1990).EventsintheSemanticsofEnglish.TheMITPress.Singh-Miller,N.,&Collins,M.(2007).Trigger-basedlanguagemodelingusingaloss-sensitivepercep-tronalgorithm.InIEEEInternationalConferenceonAcoustics,SpeechandSignalProcessing.Steedman,M.(1996).SurfaceStructureandInterpreta-tion.TheMITPress.Steedman,M.(2000).TheSyntacticProcess.TheMITPress.Steedman,M.(2011).TakingScope.TheMITPress.Taskar,B.,Guestrin,C.,&Koller,D.(2003).Max-MarginMarkovNetworks.InProceedingsoftheConferenceonNeuralInformationProcessingSystems.Taskar,B.,Klein,D.,Collins,M.,Koller,D.,&Manning,C.(2004).Max-MarginParsing.InProceedingsoftheConferenceonEmpiricalMethodsinNaturalLanguageProcessing.Tellex,S.,Kollar,T.,Dickerson,S.,Walter,M.,Banerjee,A.,Teller,S.,&Roy,N.(2011).UnderstandingNaturalLanguageCommandsforRoboticNaviga-tionandMobileManipulation.InProceedingsoftheNationalConferenceonArtificialIntelligence.Vogel,A.,&Jurafsky,D.(2010).Learningtofollownav-igationaldirections.InProceedingsoftheCon-ferenceoftheAssociationforComputationalLin-guistics.Webber,B.,Badler,N.,DiEugenio,B.,Geib,C.,Lev-ison,L.,&Moore,M.(1995).Instructions,In-tentionsandExpectations.ArtificialIntelligence,73(1),253–269.Wei,Y.,Brunskill,E.,Kollar,T.,&Roy,N.(2009).WhereToGo:InterpretingNaturalDirectionsUsingGlobalInference.InProceedingsoftheIEEEInternationalConferenceonRoboticsandAutomation.Winograd,T.(1972).UnderstandingNaturalLanguage.CognitivePsychology,3(1),1–191.Wong,Y.,&Mooney,R.(2007).LearningSynchronousGrammarsforSemanticParsingwithLambdaCal-culus.InProceedingsoftheConferenceoftheAs-sociationforComputationalLinguistics.
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
2
0
9
1
5
6
6
6
4
3
/
/
t
l
a
c
_
a
_
0
0
2
0
9
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
62
Zettlemoyer,L.,&Collins,M.(2005).Learningtomapsentencestologicalform:Structuredclassificationwithprobabilisticcategorialgrammars.InPro-ceedingsoftheConferenceonUncertaintyinAr-tificialIntelligence.Zettlemoyer,L.,&Collins,M.(2007).OnlinelearningofrelaxedCCGgrammarsforparsingtologicalform.InProceedingsoftheJointConferenceonEmpiricalMethodsinNaturalLanguageProcess-ingandComputationalNaturalLanguageLearn-ing.