Transactions of the Association for Computational Linguistics, vol. 3, pp. 1–13, 2015. Action Editors: Johan Bos, Lillian Lee.
Submission batch: 6/2014; Revision batch 9/2014; Published 1/2015. c
(cid:13)
2015 Association for Computational Linguistics.
1
ReasoningaboutQuantitiesinNaturalLanguageSubhroRoyUniversityofIllinois,UrbanaChampaignsroy9@illinois.eduTimVieiraJohnsHopkinsUniversitytim.f.vieira@gmail.comDanRothUniversityofIllinois,UrbanaChampaigndanr@illinois.eduAbstractLittleworkfromtheNaturalLanguageProcessingcommunityhastargetedtheroleofquantitiesinNaturalLanguageUnderstanding.Thispapertakessomekeystepstowardsfacilitatingreasoningaboutquantitiesexpressedinnaturallanguage.Weinvestigatetwodifferenttasksofnumericalreasoning.First,weconsiderQuantityEntailment,anewtaskformulatedtounderstandtheroleofquantitiesingeneraltextualinferencetasks.Second,weconsidertheproblemofautomaticallyunderstandingandsolvingelementaryschoolmathwordproblems.Inordertoaddressthesequantitativereasoningproblemswefirstdevelopacomputationalapproachwhichweshowtosuccessfullyrecognizeandnormalizetextualexpressionsofquantities.Wethenusethesecapabilitiestofurtherdevelopalgorithmstoassistreasoninginthecontextoftheaforementionedtasks.1IntroductionEveryday,newspaperarticlesreportstatisticstopresentanobjectiveassessmentofthesituationstheydescribe.Fromelectionresults,numberofcasualtiesinaccidents,tochangesinstockprices,textualrepresentationsofquantitiesareextremelyimportantincommunicatingaccurateinformation.However,relativelylittleworkinNaturalLanguageProcessinghasanalyzedtheuseofquantitiesintext.Eveninareaswherewehaverelativelymaturesolutions,likesearch,wefailtodealwithquantities;forexample,onecannotsearchthefinancialmediafor“transactionsinthe1-2millionpoundsrange.”Languageunderstandingoftenrequirestheabilitytoreasonwithrespecttoquantities.Consider,forexample,thefollowingtextualinference,whichwepresentasTextualEntailmentquery.RecognizingTextualEntailment(RTE)(Daganetal.,2013)hasbecomeacommonwaytoformulatetextualinferenceandwefollowthistrend.RTEisthetaskofdeterminingwhetherthemeaningofagiventextpassageTentailsthatofahypothesisH.Example1T:AbombinaHebrewUniversitycafeteriakilledfiveAmericansandfourIsraelis.H:AbombingatHebrewUniversityinJerusalemkilledninepeople,includingfiveAmericans.Here,weneedtoidentifythequantities“fiveAmericans”and“fourIsraelis”,aswellasusethefactthat“Americans”and“Israelis”are“people”.Adifferentflavourofnumericreasoningisrequiredinmathwordproblems.Forexample,inExample2Ryanhas72marblesand17blocks.Ifhesharesthemarblesamong9friends,howmanymarblesdoeseachfriendget?onehastodeterminetherelevantquantitiesinthequestion.Here,thenumberofblocksinRyan’spossessionhasnobearingontheanswer.Thesecondchallengeistodeterminetherelevantmathematicaloperationfromthecontext.Inthispaper,wedescribesomekeystepsnecessarytofacilitatereasoningaboutquantitiesinnaturallanguagetext.Wefirstdescribeasystemdevelopedtorecognizequantitiesinfreeformtext,inferunitsassociatedwiththemandconvertthemto
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
1
1
8
1
5
6
6
7
3
4
/
/
t
je
un
c
_
un
_
0
0
1
1
8
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
9
S
e
p
e
m
b
e
r
2
0
2
3
2
astandardizedform.Forexample,inExample3Aboutsixandahalfhourslater,Mr.Armstrongopenedthelandingcraft’shatch.wewouldliketoextractthenumber6.5,thecorrespondingunit,“hour”,andalsodeterminethatthequantitydescribesanapproximatefigure,notanexactone.Oneofthedifficultiesisthatanynounornounphrasecanbeaunit,andinferringthemrequiresanalyzingcontextualcuesandlocalsentencestructure.Asweshow,insomecasesdeeperNLPtechniquesarerequiredtosupportthat.Wethendevelopareasoningframeworkforquantitiesthatwebelievecanplayanimportantroleingeneralpurposetextualinference.IsolatingthequantityreasoningcomponentoftheRTEtask,wedefineQuantityEntailment(QE)-thetaskofdeterminingwhetheragivenquantitycanbeinferredfromagiventextsnippet,andthendescribeourapproachtowardssolvingit.ThisallowsustosupporttheinferencepresentedinExample1.Asanadditionalevaluation,wealsoshowtheeffectivenessofoursystemonanapplicationofQE,asearchforrangesofcurrencyvalues.Givenaqueryrange,sayfrom1millionUSDto3millionUSD,wewanttofindallmentionsofmoneywithvaluesinthisrange.Usingstandardsearchenginetechnologytoqueryallvaluesintherange,inthevariousformstheycouldbeexpressed,isnotfeasible.Instead,weuseourproposedapproachtoextractmonetarymentionsfromtextandnormalizethem,andthenweuseQEtoverifythemagainstthequery.Wenextdevelopareasoningframeworkforelementaryschoolmathwordproblems.Ourreasonermakesuseofseveralclassifierstodetectdifferentpropertiesofawordproblem,andfinallycombinesthedecisionsofindividualclassifierstoobtainthecorrectanswer.Wedevelopandannotatedatasets1forevaluation,andshowthatourapproachcanhandletheaforementionedreasoningtasksquitewell.Thenextsectionpresentssomerelatedworkonquantitiesandreasoning.Wethenformallydefineaquantityanddescribeourknowledge1Thedatasetsareavailablefordownloadathttp://cogcomp.cs.illinois.edu/page/resourceview/95.Therelatedsoftwareisavailableathttp://cogcomp.cs.illinois.edu/page/softwareview/Quantifier.representation.Thefollowingsectionsdescribequantitiesextractionandstandardization.WenextpresenttheformulationofQuantityEntailment,anddescribeourreasoningframeworkforit.Wethendescribeourapproachtowardsunderstandingelementaryschoolmathproblems,andconcludewithexperimentalevaluation.2RelatedWorkTheimportanceofreasoningaboutquantitieshasbeenrecognizedandstudiedfrommultipleperspectives.Quantitieshavebeenrecognizedasanimportantpartofatextualentailmentsystem(deMarneffeetal.,2008;MaccartneyandManning,2008;Garoufi,2007;Sammonsetal.,2010),et(deMarneffeetal.,2008)claimsthatdiscrepanciesinnumbersareacommonsourceofcontradictionsinnaturallanguagetext.Theauthorsdescribeacorpusofreal-lifecontradictorypairsfrommultiplesourcessuchasWikipediaandGoogleNewsinwhichtheyfoundthat29%ofthecontradictionswereduetonumericdiscrepancies.Inaddition,theyanalyzedseveralTextualEntailmentdatasets(Daganetal.,2006)andfoundthatnumericcontradictionsconstitute8.8%ofcontradictoryentailmentpairs.Quantitativereasoninghasalsobeenaddressedfromtheperspectiveofformalsemantics.Montague(Montague,1973)investigatesidentityambiguitiesinsentences,e.g.,whether“Thetemperatureisninetybutitisrising.”implies“ninetyisrising”.Hissolutionsuggeststhat“temperature”shouldbetreatedasaconcept,and“temperatureisninety”assertsanattributeoftemperatureataparticularinstanceoftime,andnotanattributeoftheconcept“temperature”.Reasoningaboutquantitiesoftendependsonreasoningaboutmonotonicity.TheroleofmonotonicityinNLreasoninghasbeendescribedin(BarwiseandCooper,1981).Theauthorscategorizenounphrasesasupwardordownwardmonotonic,andalsodetectconstructswheremonotonicitydependsoncontext.Thelargeroleofmonotonicityinreasoningmotivatedattemptstoreasondirectlyatthesurfacelevel(Purdy,1991),ratherthanconvertingfirsttologicalforms.Ourapproachadvocatesthisdirectiontoo.(Kuehne,2004un)investigatesthevariouscasesinwhichphysicalquantitiesarerepresented
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
1
1
8
1
5
6
6
7
3
4
/
/
t
je
un
c
_
un
_
0
0
1
1
8
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
9
S
e
p
e
m
b
e
r
2
0
2
3
3
indescriptionsofphysicalprocesses.Later,dans(Kuehne,2004b),asystemtoextractQualitativeProcessTheory(Forbus,1984)representationsisimplementedforacontrolledsubsetoftheEnglishlanguage.Otherworksthatarerelevanttoquantities,suchasworkonthepluralsemanticsofnounphrases(Schwertel,2003),werealsodoneoncontrolledEnglish.WhiletheseapproachesdonotscaletounrestrictedEnglish,theyhaveinfluencedthequantityrepresentationthatweuse.Theimportanceofquantitieshasalsobeenrecognizedinsomeapplicationareas.Forexample,(Banerjeeetal.,2009)investigatesrankingofsearchresultsinvolvingquantities.Inordertodetectquantitiesintext,theyusearulebasedsystem,comprising150rules.However,theruleswerespecifictothequeriesused,anddonotextendwelltounrestrictedEnglish.Incontrast,oursystemisdesignedtodetectanyquantitymentionedinnaturallanguagetext,aswellasinfertheunitassociatedwithit.Therehasalsobeensomeworkonquantitiesinspecificdomains,suchasthetemporaldomain,themostsignificantbeingtheTimeMLproject(Pustejovskyetal.,2003;Sauretal.,2005;Pratt-Hartmann,2005;Doetal.,2012).Theproblemofautomaticallysolvingmathwordproblemshasalsobeeninvestigated.Approachesrangefromusingrule-basedmethods(Bobrow,1964;Levetal.,2004;MukherjeeandGarain,2008)torecenttemplatematchingtechniques(Kushmanetal.,2014).3RepresentingQuantitiesIngeneral,quantityreferstoanythingwhichismeasurable.Ourquantitiesrepresentationisinfluencedbytheoneproposedin(Forbus,1984)butweproposeasimplerversionoftheirQualitativeProcesstheory:Definition(Quantity-ValueRepresentation)InQuantity-ValueRepresentation(QVR),aquantityisrepresentedasatriple(v,toi,c),whereconstituentsinthetriplecorrespond,respectivement,à:1.Value:anumericvalue,range,orsetofvalueswhichmeasuretheaspect,e.g.morethan500,oneortwo,thousands,March18,1986.Thevaluecanalsobedescribedviasymbolicvalue(e.g.,“belowthefreezingpoint”).Wedonotstoresurfaceformsexplicitly,butconvertthemtoasetorrange.Forexample,“morethan500”isstoredastherange(500,+∞).DetailsoftheseconversionsaregiveninSection4.2.2.Units:anounphrasethatdescribeswhatthevalueisassociatedwith.e.g.,inches,minutes,bananas.Thephrase“USsoldiers”inthephrase“FiveUSsoldiers”isaunit.3.Change:specifieshowtheparameterischanging,e.g.,increasing.Thisconstituentoftenservesasanindicationofwhetherornotthevalueisrelativetoanother.Forexample,“Shewillreceivean[additional50centsperhour]»,“Thestock[increased10percent]»,“Jimhas[5ballsmore]thanTim”.4ExtractionofQuantitiesInthissectionwedescribethefirstcomponentofourapproach,thatofidentifyingquantitiesandunitsintextandstandardizingtheirrepresentation.Weuseaatwostepapproachtoextractquantitiesfromfreeformtext.1.SegmentationThissteptakesrawtextandfindssegmentsofcontiguoustextwhichdescribequantities.2.StandardizationUsingthephrasesextractedinthepreviousstep,wederivetheQVR.AnoverviewofourmethodisgiveninAlgorithm1.Algorithm1QuantityExtraction(T)Input:TextTOutput:SetofQuantity-valuetriplesextractedfromT1:Q←∅2:S←Segmentation(T)3:forallsegments∈Sdo4:q←Standardization(s)5:ifunitofqnotinferredthen6:q←InferUnitFromSemantics(q,s,T)7:endif8:Q←Q∪{q}9:endfor10:returnQWemodelthesegmentationstepasasequencesegmentationtaskbecausequantitiesoftenappear
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
1
1
8
1
5
6
6
7
3
4
/
/
t
je
un
c
_
un
_
0
0
1
1
8
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
9
S
e
p
e
m
b
e
r
2
0
2
3
4
assegmentsofcontiguoustext.WeadaptandcomparetwoapproachesthatwerefoundsuccessfulinprevioussequentialsegmentationworkinNLP:1.ASemi-CRFmodel(SarawagiandCohen,2004),trainedusingastructuredPerceptronalgorithm(Collins,2002),withParameterAveraging(FreundandSchapire,1998).2.Abankofclassifiersapproach(PunyakanokandRoth,2001)thatweretrainwithanewsetoffeatures.Thesamefeaturesetwasusedforbothapproaches.DespitetheadditionalexpressivepowerofCRFs,wefoundthatthebankofclassifiers(whichisfollowedbyasimpleandtractableinferencestep)performsbetterforourtask,andalsorequiressignificantlylesscomputationtime.4.1FeaturesForeachtokenxiintheinputsequenceweextractthefollowingfeatures:1.Wordclassfeatures:xiappearsinalistofknownscientificunits(e.g.,meters,Fahrenheit),writtennumbers(e.g.,two,fifteen),namesofamonths,dayoftheweek,miscellaneoustemporalwords(e.g.today,tomorrow),currencyunits,etc.2.Character-based:xicontainsadigit,isalldigits,hasasuffix(st,nd,rd,ème).3.Partofspeechtags:weusetheIllinoisPOSTagger(RothandZelenko,1998).4.Mostofthefeaturesweregeneratedfromawindowof[−3,3]aroundthecurrentword.Additionalfeaturesweregeneratedfromthesebyconjoiningthemwithoffsetvaluesfromthecurrentword.4.2MappingTextSegmentsintoQVRWedeveloparule-basedstandardizationstep,thatisinformed,asneeded,bydeeperNLprocessing,includingsemanticrolelabeling(SRL,(Palmeretal.,2010))andCo-referenceresolution.Somekeystepsofthisprocedureareasfollows:1.Convertwrittennumberstofloatingpoint:e.g.,threethousandfivehundredtwenty→3520.02.Convertdatestoaninternaldatetype:e.g.,March18th→Date(03/18/XXXX)3.Replaceknownnamesforranges:e.g.,teenage→[13,19]years-old.4.Convertallscientificunitstoastandardbaseunit:e.g.,1mile→1609.344meters.5.Replacenon-scientificunitswithWordNetsynsets6.Rewriteknownunitstoastandardunit:e.g.,USD,US$,dollars→US$.7.Standardizechangingquantity:e.g.,“additional10books”→+10[livre].8.Extractbounds:weusealistofphrases,suchas“morethan”,“lessthan”,“roughly”,“nearly”.Bydefault,ifaboundkeywordisnotpresentweassumetheboundis“=”.9.Modifyvalueusingbounds:Weconvertvalueswhichhaveaboundtoarangeofvalues.Scalarimplicatureistakenintoconsiderationhere.Considerthesentence“Johnbought10books.”,althoughitcanbeinterpretedthatbuying5booksisacorollaryofbuying10,inthiscase,wemaketheassumptionthat5bookswerenotpurchased.Seesection5.2foradiscussiononthesubject.Weusethefollowingrules,wherevisthevalueextractedbeforeusingboundinformation.•≤v→(−∞,v],similarlyfor≥,<,>.•=v→{v}•≈v→[v−c.v,v+c.v],weusec=0.2.4.3ExtractionofUnitsInmostcases,theunitsrelatedtothenumericvaluesappearadjacenttothem.Forexample,inthesentence“Therearetwobooksonthetable”,theunit“book”follows“two”.Thesequencesegmentationgroupsthesewordstogether,fromwhichitiseasytoextracttheunit.However,insomecases,abetterunderstandingofthetextisneededtoinfertheunits.Considerthefollowingexample:
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
1
1
8
1
5
6
6
7
3
4
/
/
t
je
un
c
_
un
_
0
0
1
1
8
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
9
S
e
p
e
m
b
e
r
2
0
2
3
5
Example4AreportfromUNAIDS,theJointUnitedNationsProgramonHIV/AIDS,releasedonTuesday,showsthenumberofadultsandchildrenwithHIV/AIDSreached39.4millionin2004.Here,weneedtoknowthat“39.4million”refersto“thenumberofadultsandchildrenwithHIV/AIDS”.Also,dans:Example5Thenumberofmembernationswas80in2000,andthenitincreasedto95.weneedtoknowthatthepronoun“it”refersto“thenumberofmembernations”.Weemployasequentialprocessinourstandardization.Incasethefirststepdescribedabovefailstoextractunits,wemakeuseofdeeperprocessingofthesentencetoaccomplishthat(seeanevaluationofthecontributionofthisintheexperimentalsection).ThesestepsaredenotedbythefunctionInferUnitFromSemantics()inAlgorithm1.WeapplycoreferenceresolutiontoidentifypronounreferentsandthenapplyaSemanticRoleLabeler,torecognizewhichtermsareassociatedwiththequantity,andcanbepotentialunits.Inthecaseofexample4,theSRLtellsusthatfortheverb“reached”,theassociatedsubjectis“thenumberofadultsandchildrenwithHIV/AIDS”andtheobjectisthemention“39.4million”.Hence,weconcludethatthesubjectcanbeacandidatefortheunitof“39.4million”.Forthepurposeofentailment,wekeeptheentiresetofpossiblewordchunks,whicharelinkedbytheSRLtoourquantitymention,ascandidateunits.Sincemostunitsarefoundinpositionsadjacenttothenumericmention,weoptimizeonruntimebyapplyingtheSRLandcoreferenceresolveronlywhenthesegmentedchunkdoesnothaveadequateinformationtoinfertheunit.WeusetheIllinoisCoreferenceResolver(BengtsonandRoth,2008;Changetal.,2013)andtheIllinoisSRL(Punyakanoketal.,2008),forcoreferenceandsemanticrolelabelling,respectively.5QuantityEntailmentInthissectionwedescribeourapproachtoquantitativereasoningfromnaturallanguagetext.WefirstformulatethetaskofQuantityEntailment,andthendescribeourreasoningframework.Definition(QuantityEntailment)GivenatextpassageTandaQuantity-Valuetripleh(ch,vh,uh),QuantityEntailmentisa3-waydecisionproblem:1.entails:thereexistsaquantityinTwhichentailsh.2.contradicts:noquantityinTentailsh,butthereisaquantityinTwhichcontradictsh.3.norelation:thereexistsnoquantityinT,whichiscomparablewithh.Theneedtoidentifysub-problemsoftextualinference,inthecontextoftheRTEtask,hasbeenmotivatedby(Sammonsetal.,2010).QuantityEntailmentcanbeconsideredasonesuchstep.SinceweenvisionthatourQEmodulewillbeonemoduleinanRTEsystem,weexpectthattheRTEsystemwillprovideitwithsomecontrolinformation.Forexample,itisoftenimportanttoknowwhetherthequantityismentionedinanupwardordownwardmonotoniccontext.SinceweareevaluatingourQEapproachinisolation,wewillalwaysassumeupwardmonotonicity,whichisalotmorecommon.Monotonicityhasbeenmodeledwithsomesuccessinentailmentsystems(MaccartneyandManning,2008),thusprovidingaclearandintuitiveframeworkforincorporatinganinferenceresourceliketheQuantityEntailmentmoduleintoafulltextualentailmentsystem.5.1ReasoningFrameworkOurQuantityEntailmentprocesshastwophases:ExtractionandReasoning.IntheExtractionPhase,wetakeatextpassageTandextractQuantity-Valuetriples(valeur,units,changement)fromit.IntheReasoningphase,weapplyalightweightlogicalinferenceproceduretothetriplesextractedfromTtocheckifhcanbederived.TherearetwotypesofrulesappliedintheReasoningphase:ImplicitQuantityProductionsandQuantityComparisons.ThecombinationoftheserulesprovidesgoodcoveragefortheQEtask.5.1.1QuantityComparisonQuantityComparisoncomparesaquantityt:(vt,ut,ct)extractedfromTandthequantityh:(vh,uh,ch)anddecideswhetherhcanbederivedviasometruthpreservingtransformationoft.There
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
1
1
8
1
5
6
6
7
3
4
/
/
t
je
un
c
_
un
_
0
0
1
1
8
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
9
S
e
p
e
m
b
e
r
2
0
2
3
6
arethreepossibilities:(tentailsh),(tcontradictsh),ou(thasnorelationwithh).TheoverviewisgiveninAlg.2,whichisdesignedunderourassumptionthatentailingquantitiesshouldrespectupwardmonotonicity.Thisrequiresmonotonicityverificationofbothunitsandvalues.Inorderforaquantitytocontradictorentailanother,theirunitsmustbecomparable.Determiningthecomparabilityofscientificunitsisdirectsincetheyformaclosedset.Comparingnon-scientificunitsismoreinvolved.Theinferenceruleusedhereisasfollows:ifthesyntacticheadsoftheunitphrasesmatch(i.e.,thereisanIs-Aorsynonymyrelationineitherdirection),thenthephrasesarecomparable.ThesecomparisonsareencodedasafunctioncomparableUnits(ut,uh),whichreturnstrueiftheunitsutanduharecomparable,orelsereturnsfalse.Iftheunitsarecomparable,thedirectionofmonotonicity(i.e.,thedirectionoftheIs-Arelationbetweentheheadsandtheeffectsofanyrelevantmodifiers)isverified.ThefunctioncheckMonotonicityOfUnits(ut,uh)returnstrue,ifutismorespecificthanuh,falseotherwise.TocomputetheIs-AandsynonymyrelationsweuseWordNet(Milleretal.,1990),anontologyofwordswhichcontainstheserelations.WealsoaugmentWordNetwithtwolistsfromWikipedia(specifically,listsofNationalitiesandJobs).Suivant,wecheckwhetherthevaluesofthequantitiescomparedobeythemonotonicityassumption;wesaythatvtismorespecificthanvhifvtisasubsetofvh.(Notethatvtandvharebothrepresentedassetsandhence,checkingsubsetrelationisstraightforward.)Forexample,“morethan50”⊆“atleast10”.Thisrulealsoappliestodates,e.g.“03/18/1986”⊆“March1986”.Respectingscalarimplicature,weassumethat“5”issubsetof“lessthan10”,butnot“10”.Similartothecaseofunits,weusethefunctioncheckMonotonicityOfValues(vt,vh)whichreturnstrue,ifvtismorespecificthanvh,andfalseotherwise.Aquantitywhichrepresentssomeformofchangeofaquantitycannotbederivedfromaquantitywhichdoesnotrepresentchangeandviceversa.Wesetct=trueiftdenoteschangeinaquantity,otherwisewesetct=false.Algorithm2QuantityComparison(t,h)Input:Quantity-valuetriplest(vt,ut,ct)andh(vh,uh,ch)Output:Returnswhethertentails,contradictsorhasnorelationwithh1:ifct6=chthen2:returnnorelation3:endif4:ifcomparableUnits(ut,uh)=falsethen5:returnnorelation6:endif7:ifcheckMonotonicityOfUnits(ut,uh)=truethen8:ifcheckMonotonicityOfValues(vt,vh)=truethen9:returnentails10:endif11:endif12:returncontradicts5.1.2ImplicitQuantityProductionRulesTherearemanyrelationshipsamongquantitieswhichcanbethesourceofimplicitinformation.Thefollowingisanincomplete,butrelativelybroadcoveragelistofcommonpatterns:1.Rangemayimplyduration,e.g.,“JohnlivedinMiamifrom1980to2000”impliesthatJohnlivedinMiamiforadurationof20years.2.Compatibletermsmaybecombinedandabstracted.Thesentence“Ibought3bananas,2oranges,and1apple”impliesthat6fruitswerepurchased.3.Ratioscanimplypercentages.Thesentence“9outofthe10dentistsinterviewedrecommendbrushingyourteeth”impliesthat90%ofthedentistsinterviewedrecommendbrushing.4.Composition:Quantitiesandunitsmaysometimesbecomposed.Considerthefollowingexamples,thephrase“sixKoreancouples”meansthatthereare12people;thephrase“Johngavesix30-minutespeeches”impliesthatJohnspokefor180minutes.Therulesusedforproducingimplicitquantitiesemployedinoursystemarethefollowing:
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
1
1
8
1
5
6
6
7
3
4
/
/
t
je
un
c
_
un
_
0
0
1
1
8
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
9
S
e
p
e
m
b
e
r
2
0
2
3
7
•(aratiob)ifaisapercentage,thenmultiplyitsvaluewiththevalueofbtoobtainanewquantitywiththeunitsofb.•(aratiob)ifaisnotpercentage,divideitsvaluewiththevalueofbtoobtainanewquantitywiththeunitsofb.•(arangeb)takethedifferenceofthetwovaluestoobtainanewquantitywiththeappropriatechangeofunits,e.g.,time-stampminustime-stampresultsinunitsoftime.Algorithm3QuantityEntailment(T,h)Input:TextTandaquantity-valuetriplesh(vh,uh,ch)Output:ReturnswhetherTentails,contradictsorhasnorelationwithh1:Q←QuantityExtraction(T)2:Q0←GenerateImplicitQuantities(Q)3:Q←Q∪Q04:contradict←false5:forallquantity-valuetripleq∈Qdo6:ifQuantityComparison(q,h)=entailsthen7:returnentails8:endif9:ifQuantityComparison(q,h)=contradictsthen10:contradict←true11:endif12:endfor13:ifcontradict=truethen14:returncontradicts15:else16:returnnorelation17:endif5.1.3LightweightLogicalInferenceTheQEinferenceproceduresimplyapplieseachoftheimplicitquantityproductionrulestotheQuantity-ValuetriplesextractedfromthepassageT,untilnomorequantitiesareproduced.ThenitcompareseachquantitytextractedfromTwiththequantityh,accordingtothequantitycomparisonrulesdescribedinAlgorithm2.IfanyquantityinTentailsh,then“entails”isreported;ifthereisnoquantityinTwhichcanexplainh,butthereexistsonewhichcontradictsh,then“contradiction”isreported;otherwise“norelation”isreported.ThecompleteapproachtoQuantityEntailmentisgiveninAlgorithm3.5.2ScopeofQEInferenceOurcurrentQEprocedureislimitedinseveralways.Inallcases,weattributetheselimitationstosubtleanddeeperlanguageunderstanding,whichwedelegatetotheapplicationmodulethatwilluseourQEprocedureasasubroutine.Considerthefollowingexamples:T:Adamhasexactly100dollarsinthebank.H1:Adamhas50dollarsinthebank.H2:Adam’sbankbalanceis50dollars.Here,TimpliesH1butnotH2.HoweverforbothH1andH2,QEwillinferthat“50dollars”isacontradictiontosentenceT,sinceitcannotmakethesubtledistinctionrequiredhere.T:Tenstudentspassedtheexam,butsixstudentsfailedit.H:Atleasteightstudentsfailedtheexam.Hereagain,QEwillonlyoutputthatTimplies“Atleasteightstudents”,despitethesecondpartofT.QEreasonsaboutthequantities,andthereneedstobeanapplicationspecificmodulethatunderstandswhichquantityisrelatedtothepredicate“failed”.Therealsoexistslimitationsregardinginferenceswithrespecttoeventsthatcouldoccuroveraperiodoftime.In“Itwasrainingfrom5pmto7pm”oneneedstoinferthat“Itwasrainingat6pm”although“6pm”ismorespecificthan“5pmto7pm”.Thereisaneedtounderstandtheroleofassociatedverbsandentities,andthemonotonicityofthepassagestoinfertheglobalentailmentdecision.SomeaspectsofthisproblemishandledinthemathwordproblemsinSection6,butthereisstillaneedtoformalizetheroleofassociatedpredicatesanditsassociationswithquantitiesinnaturallanguage.6SolvingMathWordProblemsInthissection,wedescribeourapproachtowardsautomaticallyunderstandingandsolvingelementaryschoolmathwordproblems.Weconsideredwordproblemshavingthefollowingproperties:1.Thequestionmentionstwoorthreequantities.2.Theanswercanbecomputedbychoosing
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
1
1
8
1
5
6
6
7
3
4
/
/
t
je
un
c
_
un
_
0
0
1
1
8
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
9
S
e
p
e
m
b
e
r
2
0
2
3
8
twoquantitiesfromthequestionandapplyingoneofthefourbasicoperations(addition,subtraction,multiplication,division)onthem.Weuseacascadeofclassifiersapproachforthisproblem.Wedevelopthefollowingthreeclassifierstodetectdifferentpropertiesofthewordproblem.1.QuantityPairClassifierThisclassifierisrelevantonlyforproblemsmentioningthreequantitiesinthequestiontext.TheinputtotheclassifieristhetextofthequestionQoftheproblem,andthequantitiesq1,q2,q3extractedfromthequestionQ.Theoutputistherelevantpairofquantities,thatis,thepairofquantitiesrequiredtogettheanswer,denotedas(qi,qj).Theinferenceproblemcanbewrittenasfollows:(qi,qj)←argmaxp∈PwTqpφqp(Q,p)whereP={(q1,q2),(q2,q3),(q3,q1)},φqp(·)isafeaturefunction,andwqpisalearnedweightvector.2.OperationClassifierThisclassifiertakesasinputthequestionQoftheproblem,andtherelevantquantitypair(qi,qj)(decidedbyQuantityPairClassifierincaseofquestionswiththreequantities),andoutputswhichofthefouroperationsisrequiredfortheproblem.Theinferenceinthiscaseisop←argmaxop∈OwToprφopr(Q,(qi,qj),op)whereO={+,−,×,/}.3.OrderClassifierThisclassifierisrelevantonlyforproblemswhichrequiresubtractionordivision.IttakesasinputthequestionQoftheproblem,therelevantpairofquantities(qi,qj)andtheoperationopbeingperformed,anddecidesthemostlikelyorderofquantitiesintheoperation,thatis,whetherweshouldperform(qiopqj)ou(qjopqi).Theinferencecanbewrittenas(q0i,q0j)←argmaxp∈PwTorφor(Q,(qi,qj),op,p)whereP={(qi,qj),(qj,qi)}Algorithm4SolveWordProblem(Q)Input:TextofquestionQOutput:ReturnsanswertoquestionQ1:(q1,q2,q3)←QuantityExtraction(Q)2:(qi,qj)←QuantityPairClassifier(Q)3:op←OperationClassifier(Q,(qi,qj))4:(q0i,q0j)←OrderClassifier(Q,(qi,qj),op)5:return(q0iopq0j)TheinferenceprocedureisgiveninAlgorithm4.Forourclassifiers,weuseasparseaveragedperceptronimplementedwiththeSNOWframework(Carlsonetal.,1999).Eachclassifieristrainedongoldannotationsforthatparticulartask.Thefeaturesusedareasfollows:1.Unigramsandbigramsfromsentencescontainingquantities.2.POStagsfromsentenceswithquantities.3.Relevantpairofquantities,andwhethertheirunitsmatchandwhethertheirunitsarepresentinthelastsentenceofthequestion.4.Relevantoperationfortheproblem(forOperationandOrderclassifiers)5.Relevantorderofquantitiesfortheoperation(forOrderclassifier).6.Variousconjunctionsoftheabovefeatures.7ExperimentalStudyInthissection,weseektovalidateourproposedmodeling.Weevaluateoursystem’sperformanceonfourtasks:QuantitySegmentation,QuantityEntailment,CurrencyRangeSearch,andAnsweringMathWordProblems.Wedonotdirectlyevaluateoursystem’sabilitytomaprawtextsegmentsintoourrepresentation,butinsteadevaluatethiscapabilityextrinsically,inthecontextoftheaforementionedtasks,sincegoodStandardizationisnecessarytoperformquantitativeinference.7.1DatasetsQE:Duetolackofrelatedwork,anadequatelyannotatedcorpusdoesnotexist.Thus,inordertoevaluateoursystem,weusedtwocollections:
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
1
1
8
1
5
6
6
7
3
4
/
/
t
je
un
c
_
un
_
0
0
1
1
8
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
9
S
e
p
e
m
b
e
r
2
0
2
3
9
1.Sub-corpusoftheRTEDatasets(Daganetal.,2006)Wechoosetext-hypothesispairsfromRTE2–RTE4datasets,whichhavequantitymentionsinthehypothesis.Overall,weselected384text-hypothesispairswithquantitiesinthehypothesis.2.NewswireText600sentencesofnewswiretextwereselected,allcontainingquantitymentions.Boththesedatasetsweremanuallyannotatedwiththephraseboundariesofquantitymentionsandhadaninter-annotatoragreementof0.91.Werestrictedannotationtocontiguoussegmentsoftext.Noinstancesofimplicitquantitieswereannotated.WealsodidnotannotatethesementionswithQVRs.Limitingtheannotationstocontiguousspansoftextresultsinafewinstancesofquantitieswhichcontainmissinginformation,suchasmissingorambiguousunits,andseveralrangeandratiorelationshipswhichwerenotannotated(e.g.,wedonotannotatetherangeexpressedin“from[5million]dans[1995]à[6million]dans[1996]»,butdosoin“[from5millionto6million]»).IntheRTEsub-corpuswealsoannotatedentailmentpairswithinformationaboutwhichquantitiesentail,inadditiontotheboundaryinformation.Foreachquantityinthehypothesiswelabeleditaseither“entails”,“norelation”,or“contradicts”,withaninter-annotatoragreementof0.95.Therewere309entailingquantities,71contradictingquantitiesand56quantitieswhichwereunrelatedtothecorrespondingtext.Wealsomaintainedtheinformationaboutgeneralentailment,thatis,whetherthehypothesiscanbeexplainedbythetext.AnexampleofanannotatedRTEexampleisshownbelow.AnnotationExampleforRTEsub-corpusT:AbombinaHebrewUniversitycafeteriakilled[fiveAmericans]et[fourIsraelis].H:AbombingatHebrewUniversityinJerusalemkilled[ninepeople],y compris[fiveAmericans].“ninepeople”:entails“fiveAmericans”:entailsGlobalentailmentdecision:entailsAlthoughwelimitourscopetoinfertheentailmentdecisionforindividualquantitiesmentionedinhypothesis,wehopetoseefutureapproachesusetheseindividualdecisionsandcombinethemappropriatelytoobtaintheglobalentailmentdecision.CurrencySearchWedevelopedanewdatasetforevaluatingcurrencysearch.Queriesofvariousamountsofmoneylike“1000$”,“USD2million”,etc.weremadeonasearchengine,andparagraphscontainingmonetarymentionsweretakenfromthetopsearchresults.Wecollected100paragraphscontainingvariousmentionsofmonetaryvalues,andlabeledthemwiththeamountmentionedinthem.WerestrictedthedenominationstoUSdollars.Theinter-annotatoragreementwas0.98.MathWordProblemsWecreatedanewdatasetwithelementarymathwordproblems.Theproblemswerecollectedfromhttp://www.k5learning.com/andhttp://www.dadsworksheets.com/.Thelistwasfurtherprunedtokeepproblemswiththepropertieslistedinsection6.Wealsomanuallyremovedproblemsrequiringbackgroundknowledge,forexample,“Rogerreads2bookseachday.Howmanybookswillhereadin3weeks?»,whichrequiresknowingthataweekcomprises7days.Problemswithroundingissueswerealsoexcluded.Forexample,“Eachbasketcanhold9apples.Howmanybasketsarerequiredtohold10apples?”.Eachproblemwasannotatedwiththeoperationrequiredtosolvetheproblem,andthefinalanswer.Table1showssomestatisticsofourdataset.#quantitiesRelevantOperationAddSubtractMultiplyDivide2228214257260310713275131Table1:Statisticsofmathwordproblemsdataset7.2QuantitySegmentationWeevaluatethephraseboundaryrecognizerontheannotatedRTEandnewswiredatasetsdescribedintheprevioussection,usingthephrase-basedF1score.WecomparetheaccuracyandrunningtimesoftheSemi-CRFmodel(SC)(SarawagiandCohen,2004)andthebankofclassifiersmodel(C+I)(PR)(PunyakanokandRoth,2001),using10-foldcross-validation.Notethatthestandardizercanoftenrecoverfrommistakesmadeatthesegmentationlevel.Therefore,thisperformancedoesnotnecessarilyupperboundtheperformance
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
1
1
8
1
5
6
6
7
3
4
/
/
t
je
un
c
_
un
_
0
0
1
1
8
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
9
S
e
p
e
m
b
e
r
2
0
2
3
10
ofthenextstepinourpipeline.Thesegmentationweareaimingfordoesnotdirectlyfollowfromsyntacticstructureofasentence.Forexample,inthesentence“Theunemploymentrateincreased10%”,wewouldliketosegmenttogether“increased10%”,sincethistellsusthatthequantitydenotesariseinvalue.Also,inthesentence“ApplerestorespushemailinGermany,nearlytwoyearsafterMotorolashutitdown”wewouldliketosegmenttogether”nearlytwoyearsafter”.Weconsideraquantitytobecorrectlydetectedonlywhenwehavetheexactphrasethatwewant,otherwiseweconsiderthesegmenttobeundetected.ModelP%R%F%TrainTestTimeTimeSemi-CRF(SC)75.677.776.615.81.5C+I(PR)80.379.379.81.01.0Table2:10-foldcross-validationresultsofsegmentationaccuracyandtimerequiredforsegmentation,thecolumnsforruntimehavebeennormalizedandexpressedasratiosTable2describesthesegmentationaccuracy,aswellastheratiobetweenthetimetakenbybothapproaches.Thebankofclassifiersapproachgivesslightlybetteraccuracythanthesemi-CRFmodel,andisalsosignificantlyfaster.7.3QuantityEntailmentWeevaluatethecompleteQuantityEntailmentsystem,determiningtheoveralllossduetothesegmentation,aswellasthecontributionoftheCoreferenceResolverandSRL.Weshowtheperformanceof4systems.1.GOLDSEG:Usesgoldsegmentation,anddoesnotuseSRLandCoreferenceResolver.2.GOLDSEG+SEM:Usesgoldsegmentation,andalsousesSRLandCoreferenceResolvertoinferunits.3.PREDSEG:Performssegmentation,anddoesnotuseSRLandCoreferenceResolver.4.PREDSEG+SEM:Performssegmentation,andusesSRLandCoreferenceResolver.Thebaselineisanexactstringmatchingalgorithm.Itanswers“entails”ifthequantityunitandvaluearepresentinthetext,andanswers“contradicts”ifonlytheunitmatchesandthevaluedoesnot.Otherwise,itreturns“norelation”.TheresultsareshowninTable3.Notethatexactmatchonlysupports43.3%oftheentailmentdecisions.ItisalsoevidentthatthedeepersemanticanalysisusingSRLandCoreferenceimprovesthequantitativeinference.TaskSystemP%R%F%EntailmentBaseline100.043.360.5GOLDSEG98.588.092.9+SEM97.888.693.0PREDSEG94.976.284.5+SEM95.478.386.0ContradictionBaseline16.648.524.8GOLDSEG61.692.974.2+SEM64.391.575.5PREDSEG51.979.762.8+SEM52.881.164.0NoRelationBaseline41.871.952.9GOLDSEG81.176.778.8+SEM80.078.579.3PREDSEG54.075.462.9+SEM56.372.763.5Table3:ResultsofQE;AddingSemantics(+SEM)consistentlyimprovesperformance;Only43.3%ofentailingquantitiescanberecoveredbysimplestringmatching7.4CurrencyRangeSearchTable4showstheperformanceofoursystemindetectingcurrencyphrases.Weevaluateoursystemontheproportionofmonetarymentionsitrecognizedandstandardizedcorrectlyfromqueriedrangesofcurrencyvalues,andreportmicro-averagedscores.NotethatrangesearchisadirectapplicationofQE,wherethequantityisarangeofvalues,andthetextisthecorpuswewanttosearch.Allinstancesof“entails”correspondtosearchhits.Thebaselinehereisalsoastringmatchingalgorithm,whichsearchesfornumbersinthetext.SystemP%R%F%Baseline72.069.270.5PREDSEG+SEM96.093.594.8Table4:Micro-averagedaccuracyindetectingmonetarymentions
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
1
1
8
1
5
6
6
7
3
4
/
/
t
je
un
c
_
un
_
0
0
1
1
8
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
9
S
e
p
e
m
b
e
r
2
0
2
3
11
7.5ElementaryMathWordProblemsTable5showstheperformanceofindividualclassifiersaswellastheabilityofoursystemtoanswercorrectlymathwordproblems,usingtheoutputoftheclassifiers.Theresultsarereportedwithrespectto2-foldcross-validation.Theaccuracyofeachclassifierisbasedonlyontherelevantexamplesforthatparticularclassifier.Forexample,QuantityPairclassifierisevaluatedonproblemswiththreequantitiesinitsquestiontext,andOrderclassifierisevaluatedonproblemsconcerningsubtractionordivision.CorrectAnswerdenotestheendtoendsystem,whichoutputstheanswer,afterreceivingasinputthequestiontextoftheproblem.ModuleAccuracyQuantityPair94.3Operation91.8Order95.9CorrectAnswer86.9Table5:2-foldcross-validationresultsofmathwordproblemunderstanding.CorrectAnswerindicatesperformanceofendtoendsystem,othersrepresentindividualclassifierperformanceWefindthattheindividualclassifiershavehighaccuracy,andhenceoursystemperformswellontheendtoendtask.Apotentialfuturedirectioncanbetopropagatetheuncertaintyineachclassifier,whichmightfurtherimproveperformanceofthesystem.7.6QualitativeAnalysisThesegmentationmodulemademistakesindetectingexactboundariesforuncommonphrases,e.g.,“hundredsofthousandsofpeople”,and“mid-1970’s”.Detectionofmissingunitsisproblematicincaseslike“Threeeggsarebetterthantwo”.TheSRLreturns“Threeeggs”asacandidateunit,whichneedstobeprunedappropriatelytoobtainthecorrectunit.Theprimarylimitationofthereasoningsysteminbothtasksisthelackofanextensiveknowledgebase.Wordnetbasedsynsetsprovetobeinsufficienttoinferwhetherunitsarecompatible.Also,therearecertainreasoningpatternsandvariousimplicitrelationsbetweenquantitieswhicharenotcurrentlyhandledinthesystem.Forexample,inferringfromthesentence“MilitantsinRwandakilledan[averageof8,000peopleperday]pour[100jours]”that“around800,000peoplewerekilled”.Also,implicationofratioscanbeinvolved.Forexample,thesentence“[Oneoutof100participatingstudents]willgettheaward”impliesthattherewere“100participatingstudents”,whereas“[9outof10dentists]recommendbrushing”doesnotimplytherewere10dentists.Incaseofwordproblems,oursystemmissednon-standardquestioningpatternswithinvolvedreasoning.Forexample,“Bryanhas50skittles.Benhas20M&Ms.Whohasmore?Howmanymoredoeshehave?”8ConclusionWestudiedreasoningaboutquantitiesinnaturallanguagetext.WehaveidentifiedanddefinedaninterestingandusefulsliceoftheTextualEntailmentproblem,theQuantityEntailmenttask,andstudiedalsoquantitativereasoningproblemsthatariseinelementarymathwordproblems.OurabilitytosupportquantitativereasoningbuildsonamethodweproposedfordetectingandnormalizingquantitiesinunrestrictedEnglishtext;wedevelopedaframeworktoremovevariabilityandambiguityfromunstructuredtextbymappingitintoarepresentationwhichmakesreasoningmoretractable.OncequantitiesaremappedintoourrepresentationwecansupportthereasoningrequiredbyQuantityEntailmentandelementaryschoollevelmathwordproblems.Ourexperimentsexhibitquiteimpressiveperformanceonarangeofquantitativereasoningproblems,including87%successonsolvingmathwordproblemsthataretargetedatelementaryschoolkids.OurfutureworkwillfocusonalleviatingsomeofthelimitationsoftheinferencemoduledescribedinSection5.2.Wewouldalsoliketoextendthescopeofreasoningtothecaseofpartially-orderedquantities,andfocusondeepersemanticanalysistohandlemoreinvolvedmathwordproblems.AcknowledgmentsThisresearchwassponsoredbytheArmyResearchLaboratory(ARL)(underagreementW911NF-09-2-0053),DARPA(underagreementnumberFA8750-13-2-0008),andagrantfromAI2.Anyopinions,résultats,conclusionsorrecommendationsarethoseoftheauthorsanddonotnecessarilyreflecttheviewoftheagencies.
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
1
1
8
1
5
6
6
7
3
4
/
/
t
je
un
c
_
un
_
0
0
1
1
8
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
9
S
e
p
e
m
b
e
r
2
0
2
3
12
ReferencesS.Banerjee,S.Chakrabarti,andG.Ramakrishnan.2009.Learningtorankforquantityconsensusqueries.InProceedingsofthe32ndinternationalACMSIGIRconferenceonResearchanddevelopmentininformationretrieval,SIGIR’09,pages243–250,NewYork,New York,USA.ACM.J.BarwiseandR.Cooper.1981.Generalizedquantifiersandnaturallanguage.LinguisticsandPhilosophy,4(2):159–219.E.BengtsonandD.Roth.2008.Understandingthevalueoffeaturesforcoreferenceresolution.InEMNLP.D.Bobrow.1964.Naturallanguageinputforacomputerproblemsolvingsystem.Technicalreport,Cambridge,MA,USA.A.Carlson,C.Cumby,J.Rosen,andD.Roth.1999.TheSNoWlearningarchitecture.Technicalreport,UIUCComputerScienceDepartment.K.-W.Chang,R.Samdani,andD.Roth.2013.Aconstrainedlatentvariablemodelforcoreferenceresolution.InEMNLP.M.Collins.2002.DiscriminativetrainingmethodsforhiddenMarkovmodels:Theoryandexperimentswithperceptronalgorithms.InEMNLP.I.Dagan,O.Glickman,andB.Magnini,editors.2006.ThePASCALRecognisingTextualEntailmentChallenge.I.Dagan,D.Roth,M.Sammons,andF.Zanzotto.2013.Recognizingtextualentailment:Modelsandapplications.Marie-CatherinedeMarneffe,AnnaN.Rafferty,andChristopherD.Manning.2008.Findingcontradictionsintext.InACL.Q.Do,W.Lu,andD.Roth.2012.Jointinferenceforeventtimelineconstruction.InEMNLP.K.Forbus.1984.Qualitativeprocesstheory.ArtificialIntelligence,24:85–168.Y.FreundandR.Schapire.1998.LargemarginclassificationusingthePerceptronalgorithm.InCOLT.K.Garoufi.2007.Towardsabetterunderstandingofappliedtextualentailment:Annotationandevaluationoftherte-2dataset.Master’sthesis,SaarlandUniversity,Saarbrucken.S.Kuehne.2004a.Ontherepresentationofphysicalquantitiesinnaturallanguagetext.InProceedingsofTwenty-sixthAnnualMeetingoftheCognitiveScienceSociety.S.Kuehne.2004b.Understandingnaturallanguagedescriptionsofphysicalphenomena.Ph.D.thesis,NorthwesternUniversity,Evanston,Illinois.N.Kushman,L.Zettlemoyer,R.Barzilay,andY.Artzi.2014.Learningtoautomaticallysolvealgebrawordproblems.InACL(1),pages271–281.I.Lev,B.Maccartney,C.Manning,andR.Levy.2004.Solvinglogicpuzzles:Fromrobustprocessingtoprecisesemantics.InInProc.of2ndWorkshoponTextMeaningandInterpretation,ACL-04.BillMaccartneyandChristopherD.Manning.2008.Modelingsemanticcontainmentandexclusioninnaturallanguageinference.InProceedingsofthe22ndInternationalConferenceonComputationalLinguistics(Coling2008).G.Miller,R.Beckwith,C.Fellbaum,D.Gross,andK.J.Miller.1990.Wordnet:Anon-linelexicaldatabase.InternationalJournalofLexicography.R.Montague.1973.Thepropertreatmentofquantificationinordinaryenglish.InPatrickSuppes,JuliusMoravcsik,andJaakkoHintikka,editors,ApproachestoNaturalLanguage,volume49,pages221–242.Dordrecht.A.MukherjeeandU.Garain.2008.Areviewofmethodsforautomaticunderstandingofnaturallanguagemathematicalproblems.ArtificialIntelligenceReview,29(2):93–122.M.Palmer,D.Gildea,andN.Xue.2010.SemanticRoleLabeling.I.Pratt-Hartmann.2005.FromtimemltoTPL.InAnnotating,ExtractingandReasoningaboutTimeandEvents,10.-15.April2005.V.PunyakanokandD.Roth.2001.Theuseofclassifiersinsequentialinference.InNIPS.V.Punyakanok,D.Roth,andW.Yih.2008.Theimportanceofsyntacticparsingandinferenceinsemanticrolelabeling.ComputationalLinguistics.W.Purdy.1991.Alogicfornaturallanguage.NotreDameJournalofFormalLogic,32(3):409–425,06.J.Pustejovsky,J.Castao,R.Ingria,R.Saur,R.Gaizauskas,A.Setzer,andG.Katz.2003.TimeML:Robustspecificationofeventandtemporalexpressionsintext.IninFifthInternationalWorkshoponComputationalSemantics(IWCS-5.D.RothandD.Zelenko.1998.Partofspeechtaggingusinganetworkoflinearseparators.InCOLING-ACL,The17thInternationalConferenceonComputationalLinguistics.M.Sammons,V.G.Vydiswaran,andD.Roth.2010.”asknotwhattextualentailmentcandoforyou…”.InACL.SunitaSarawagiandWilliamW.Cohen.2004.Semi-markovconditionalrandomfieldsforinformationextraction.InNIPS.R.Saur,R.Knippen,M.Verhagen,andJ.Pustejovsky.2005.Evita:arobusteventrecognizerforqasystems.InProceedingsoftheconferenceon
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
1
1
8
1
5
6
6
7
3
4
/
/
t
je
un
c
_
un
_
0
0
1
1
8
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
9
S
e
p
e
m
b
e
r
2
0
2
3
13
HumanLanguageTechnologyandEmpiricalMethodsinNaturalLanguageProcessing,HLT’05,pages700–707,Stroudsburg,Pennsylvanie,USA.AssociationforComputationalLinguistics.U.Schwertel.2003.PluralSemanticsforNaturalLanguageUnderstandingAComputationalProof-TheoreticApproach.Ph.D.thesis,UniversityofZurich.
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
1
1
8
1
5
6
6
7
3
4
/
/
t
je
un
c
_
un
_
0
0
1
1
8
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
9
S
e
p
e
m
b
e
r
2
0
2
3