Agenda-BasedChart Parser for Arbitrary Probabilistic Context-FreeGrammars
While methodsfor parsingprobabilistic context-free grammars(PCFGs)are well known, a tabular parsingframework for arbitrary PCFGswhich allows for botton-up,topdown, andotherparsingstrategies, hasnotyet beenprovided.Thispaperpresentssuchanalgorithm,andshows its correctnessandadvantagesover prior work. The paperfinishesby bringingout theconnectionsbetweenthealgorithm andwork onhypergraphs,whichpermits us to extendthepresentedViterbi (bestparse) algorithmto an inside(total probability)algorithm. 1 Intr oduction and RelatedWork Agenda-basedactive chart parsing (Kay, 1973; Kay, 1980; Pereiraand Shieber , 1987) provides an elegant unification of the central ideasof tabular methodsfor context-free grammarparsing. Earley (1970)-styledotted itemsin the chartarespecifiedto combinevia “the fundamental rule” in anorder-independent manner , such that the samebasic algorithm supportstop-down and bottom-upparsing,and the parserdealscorrectly with thedifficult casesof left-recursi verules,emptyelements, andunaryrules,in anaturalway. However, while methodsfor parsingprobabilistic context-freegrammars(PCFGs)arewell known (Baker, 1979; Jelineket al., 1992; Stolcke, 1995), an elegant generaltabular parsingframework for PCFGs, correspondingto active chartparsingfor CFGs,hasnot yet beenprovided. Producinga probabilisticversionof an agenda-dri ven chart parseris not trivial. A central ideaof suchparsersis that the algorithmis correctand completeregardlessof the order in which itemson the agendaareprocessed.Achieving this is straightforward for categorical parsers,but problematicfor probabilistic parsers,because, whenanedgeis first discovered,it mayor maynot becorrectlyscored.For example,considerextendingan active edgeVP V.NP PP:[1,2] with anNP:[2,5] to form anedgeVP V NP.PP over [1,5]. In a categoricalchartparser(CCP),we canasserttheexistenceof this edgeassoonasbothcomponentedgesare found. Any NP will do; it neednot be a bestNP over thatspan.However, if we wish to scoreedgesaswe go along,thereis a problem.In a Viterbi chartparser , if we later find a betterway to form the NP, we will have to updatenot only the scoreof that NP, but alsothe score of any edgewhosecurrentscoredependson that NP’s score. This can potentially lead to an extremely inefficient upward propagationof scoresevery time a new traversalis explored. The agenda-based chartparserof CaraballoandCharniak(1998)(usedfor determininginsideprobabilities)suffers from exactly this problem: In AppendixA, they notethat suchupdates“can be quite expensi ve in termsof CPU time”, but merelysuggesta methodof thresholdingwhich delaysprobabilitypropagationuntil theamountof unpropagatedprobabilitymass hasbecomesignificant,andsuggesthatthisallowsthem to keeptheperformanceof theparser“as empirically.” Goodman(1998)providesaninsightful presentation unifying many categoricalandprobabilisticparsing algorithmsin termsof theproblem’ssemiringstructure, but hemerelynotes(p. 172) theabove problem,andon this basisputs probabilisticagenda-based chart parsers aside. Most PCFG parsing work has used the bottom-up CKY algorithm (Kasami, 1965; Younger , 1967) with Chomsky Normal Form Grammars(Baker, 1979; Jelinek et al., 1992) or extendedCKY parsersthat work with -arybranchinggrammars,but still not with empty constituents(Kupiec, 1991; Chappelierand Rajman, 1998). Suchbottom-upparsersstraightforwardly avoid the above problem, by always building all edgesover shorterspansbefore building edgesover longer spans whichmakeuseof them.However, suchmethodsdonot allow top-down grammarfiltering, andoftendo nothandle emptyelements,cyclic unaryproductions,or -ary rules. Stolcke (1995)presentsa top-down parserfor arbitrary PCFGs,which incorporateselementsof thecontrol strategiesof Earley’s (1970)parserandtheGrahamHarrison-Russoparser(Grahamet al., 1980). Stolcke providesacorrectandefficient solutionfor parsingarbitrary PCFGsavoiding theproblemof left-recursi ve predictionsandunary rule completionsthroughthe useof precomputedmatricesgiving valuesfor the closureof theseoperations. However, the add-onsfor grammars with suchrulesmaketheresultingparserrathercomplex, andagainwehaveamethodonly for asingleparsingregimen,ratherthanageneraltabular parsingframework. In this paperwe show how to do agenda-basedactive chartparsingof arbitraryPCFGsin time,essentiallyby extendingthe key ideaof Dijkstra’s (1959) shortestpathalgorithmto chartparsing.TheresultingalgorithmhandlesarbitraryPCFGsanda rangeof parsing strategiesin a simplerandmoreintuitive way thanpreviously presentedalgorithms. For preciselythe reason mentionedabove, our parserwill necessarilylosesome of the agendaprocessingflexibility of a standardchart parser , however we preserve the flexibility with regard to selectionof parsingintroductionstrategies(e.g. topdown, bottom-up,etc.).1 Wealsodescribehow to extend this algorithmto calculateinsideprobabilities. 2 Viterbi Parsing Algorithm Our algorithmhasmany of the samedatastructuresof a standardactive CCP. The fundamentaldatastructure is the chart, which is composedof nodes, placedbetween words, and edges. Edges are labeledspansof nodes.Therearetwo varietiesof edges,active andpassive. Passiveedgesareidentifiedby a spananda label, suchasNP:[2,5], andrepresenthat thereis someparse of that category over the span. Active edges are identified by a span,a label, anda grammarstate,suchas VP V.NP PP:[1,2], andindicatesthatthegrammarstate is reachableover that span. In the casewheregrammar rulesareencodedaslists, this stateis simply anEarleystyledottedrule,andto reachit onemusthavebeenable to parsethe sequenceof categorieswhich occur to the left of the dot. However, grammarrules can in generalbeencodedby any deterministicfinite stateautomaton andso the label of the active edgesis in generala DFSAstate,with thelist rulesdenotingparticularlysimple, linear DFSAs. The “fundamentalrule” statesthat new edgesareproducedby combiningactiveedgeswith compatiblepassi ve edges,advancingthe active edgein the processto createa new edge.For example,the two edgesdescribedabove can combineto form the active edgeVP V NP.PP:[1,5]. Edgesthemselvesdo not declare what active and passi ve edgescombinedto form that edge;ratherthis information is recordedin traversals, which aresimply an(active edge,passi ve edge,resultedge)triple.2 Aseachedgecanpotentiallybeformed by many differenttraversals,this distinctionbetweenan edgeitself anda traversalof anedgeis a crucialone,althoughoftenlost in pedagogical presentations (e.g.,GazdarandMellish (1989)). The corecycle of a CCPis to processtraversalsinto edgesandto combinenew edgeswith existing edgesto 1Notethatagendaselectionstrategiesin anexhausti ve chartparser merelyre-orderthe work done,while differing introductionstrategies canactuallyimpactthetotal work done. 2Theresultedgeis primarily to simplify proofsandpseudocode; it neednotever bestoredin a traversal. is discovered is finished no traversalof explored ! #"$ % doesnotchange ! #"$ %'&)( * sometraversalexplored + + ! #"$ % only goesup + + ! #"$ % ,.-/"$ % anoptimaltraversalexplored ! "0 +% cannever change ! "0 +%1&2-/"0 +% Figure1: TheLife Cycleof anEdge createnew traversals.Edgeswhich arenot formedfrom other edgesvia traversalsare introductionedges. Passiveintroductionedgesarethewordsandareoftenall introducedduringinitialization. Activeintroductionedges are the initial statesof rules and are introducedin accordancewith thegrammarstrategy (top-down, bottomup, etc.). To hold thetraversalsor edgeswhich have not yet beenprocessed, a CCPhasa datastructurecalledan agenda, which holdsboth traversalsandedgeintroductions. Items from this agendacanbe processedin any orderwhatsoever, even arbitrarily or randomly, without affectingthefinal chartcontents. In a probabilisticchartparser(PCP),the centraldata structuresare augmentedwith scores. Grammarrules, which werepreviously encodedassymbolicDFSAsare weightedDFSAs with a weight for enteringthe initial state,aweightoneachtransition,and,for eachaccepting state,aweighton acceptingin thatstate. Edgesarealsoscored,thoughwith theexceptionof introductoryedgeswhosescoresareknown a priori , edge scoresaremerelycurrentbestestimates.Eachedge is augmentedwith a field 3 4/5 6 . This score, 37485 6 (or 3 4/5 6 9;: at a time : ) is thebestestimateto dateof thatedge’ s true(best)probabilityscore,<= . In our algorithm, this estimatewill alwaysbe lessthanor equal to <= , andwill alwaysin factbeequalfor introductory edges. Thefull algorithmis shown in pseudocodein figure2. It isbroadlysimilarto thestandardcategoricalchartparsing algorithm.However, in orderto solvetheproblemof enteringedgesinto the chart beforetheir correctscore is known, we have a more articulatededgelife cycle (shown in figure1).3 Wedistinguishedgediscoveryfrom edgefinishing. A non-introductoryedgeis discovered the first time we explore a traversalwhich forms that edge(in exploreTraversal).An introductoryedgeis discoveredwhenever our parsingstrategy indicates(during initialize or someother edge’ s finishEdge). Discovery is thepoint whenwe know that theedgecanbeparsed. An edgeis finishedwhenit is insertedinto thechartand actedupon(in finishEdge).Theprimarysignificanceof anedge’ s finishing time is that,aswe will show, our algorithmmaintainsthepropertythatwhenanedgeis finished,it is correctlyscored,i.e., 3 4/5 6 = <= . A CCPstoresall outstandingcomputationtasksin a singleagenda,whetherthe tasksareunexploredtraver3Note that the commentsin the figure apply to non-introductory edges,thoughthetimelineappliesto all edges. salsor uninsertedintroductoryedges.Wehavetwo agendasandour typingis stronger . To storeedgeswhichhave beendiscoveredbut not yet finished,we havea finishing agenda. To storetraversalswhich have beengenerated but not explored,wehaveanexplorationagenda. Thealgorithmworksasfollows. During initialization, all terminalpassi ve edges(oneperword in thesentence or lattice) are discovered,along with any initial active edges(for example,all ROOT .* edgesif weareusinga top-