Dealing with ambiguity in NLP : finding the best tree in the parse forest

Abstract

Samhengisfrjálsar mállýsingar eru ekki almennt notaðar til að þátta mannleg tungumál en eru á hinn bóginn notaðar til að þátta forritunarmál. Í tilviki forritunarmála má mállýsingin ekki vera margræð heldur má þáttari, sem byggir á henni, aðeins skila af sér einu þáttunartré. Þá kröfu er hvorki hægt né æskilegt að uppfylla þegar kemur að málvinnslu þar sem setningar í mannlegum tungumálum eru í eðli sínu margræðar. Þess vegna þarf að velja þáttunarreiknirit sem ræður við margræðni og skilar af sér mörgum þáttunartrjám. Greynir, sem er þáttari fyrir íslensku þróaður af Miðeind ehf., notar þáttunarreiknirit Jay Earleys sem Elizabeth Scott breytti þannig að það skili af sér þáttunarskógi (e. Shared Packed Parse Forest). Eftir þáttun er síðan hverju tré í skóginum gefið einkunn byggt á ákveðnum reglum og því tré skilað sem hæstu einkunnina hlaut. Í þessari rannsókn er skoðað hvort og hvernig megi framkvæma einræðinguna um leið og sjálf þáttunin fer fram. Þetta er gert með frekar breytingum á Earley-Scott reikniritinu. Sett er fram aðferð til að gefa hnútum í þáttunarskóginum einkunn, sýnt hvernig einkunnir hnútaafkvæma eru lagðar saman af hnútaforeldrum með endurkvæmum hætti frá laufbotni skógarins upp til rótar. Þannig er hægt að eyða undirtrjám sem hafa lægri samanlagða einkunn þegar hægt er að velja á milli tveggja eða fleiri trjáa vegna margræðni. Vandamál sem krefst þess að beðið sé með að gefa endahnútum einkunn þar til síðar í þáttunarferlinu er útskýrt og bent á lausn þar að lútandi.Þegar einkunnagjöf endahnúta er frestað, veldur það óásættanlegri lengingu á þeim tíma sem tekur að þátta setningar. Tímaflækjustuðullinn er a.m.k. O(n3) sem veldur því að þáttun getur tekið allt að því 34 sinnum lengri tíma sé miðað við sumar lengri setningarnar sem prófaðar voru.

Context-free grammars (CFGs) are not typically used to parse natural languages, whereas they are commonly used to parse programming languages. In the latter case, the CFG cannot be ambiguous, i.e. a parser based on it should only return a single parse tree. This criteria cannot and should not be fulfilled within natural language processing (NLP) due to the inherent ambiguity of natural languages. Therefore, a parsing algorithm must be selected that can deal with ambiguity and return a set of possible parse trees. Greynir, a parsing tool for Icelandic developed at Miðeind ehf., uses Scott’s enhanced Earley algorithm to return a Shared Packed Parse Forest (SPPF) which is then disambiguated using a custom made scoring mechanism to select the highest scoring parse tree from the forest.This work explores the possibility and feasibility of integrating disambiguation in the parsing process itself by further enhancing the Earley-Scott algorithm. A method of scoring terminal and non-terminal nodes of the SPPF at parse-time is presented where scores of child nodes are summed up by parent nodes recursively from bottom to the top of the SPPF. This allows for discarding lower scoring subtrees when ambiguities are encountered. A problem which requires delaying the scoring of terminal-nodes is explained and the solution to that problem presented. An additional contribution is a visualizer for the Earley-Scott algorithm, which was a helpful aid in understanding it, and which we hope will be of assistance to others usingthat algorithm.We find that the solution to the problem requiring delaying terminal scoring within the parsing process introduces an undesirable time complexity to the processing, rendering the method unfeasible. The time complexity is at least O(n3) and increases the processing timeto up to 34 times for the longer sentences tested.