From Partial toward Full Parsing

International Conference RANLP 2009 - Borovets, Bulgaria, pages 71–75 From Partial toward Full Parsing Heshaam Faili Department of Electrical and Computer Engineering University of Tehran Tehran, Iran hfaili@ut.ac.ir Abstract Full-Parsing systems able to analyze sentences robustly and completely at an appropriate accuracy can be useful in many computer applications like information retrieval and machine translation systems. Increasing the domain of locality by using tree-adjoining-grammars (TAG) caused some researchers to use it as a modeling formalism in their language application. But parsing with a rich grammar like TAG faces two main obstacles: low parsing speed and a lot of ambiguous syntactical parses. In order to decrease the parse time and these ambiguities, we use an idea of combining statistical chunker based on TAG formalism, with a heuristically rule-based search method to achieve the full parses. The partial parses induced from statistical chunker are basically resulted from a system named supertagger, and are followed by two different phases: error detection and error correction, which in each phase, different completion heuristics apply on the partial parses. The experiments on Penn Treebank show that by using a trained probability model considerable improvement in full-parsing rate is achieved. Keywords Full Parsing, Partial Parsing, Tree Adjoining Grammar, SuperTagging 1. Introduction In many applications like information retrieval and Rule- based machine translation systems, accurate deep parse structure of a sentence is required; hence a lot of research is being done on introducing methods to produce deep hierarchical syntactical structure of a given natural language sentence [6]. Over the last decade, there has been a great increase in the performance of parsers. Current parsers achieve to a score of about 90% when measuring just the accuracy of choosing these dependencies [4, 5 and 7]. The choice of formalism does not change the parsers’ accuracy significantly, because in all approaches word- word dependencies are used as the only underlying information. But because of the inherent ambiguity in the natural languages, achieving to a full parses of a sentence is a big challenges. Tree-adjoining-grammars (TAG) have some specific features, which are interested by researchers to be used as modeling formalisms in their language application. The parsing methods based on this formalism involve different problems such as a lot of ambiguities and low parsing speed. One of the main parsing algorithms based on TAG formalism is presented by Van Noord [10] which runs in O(n6) time complexity. This complexity in a real-size grammar (like XTAG [9]) is not acceptable, especially for a more complicated system like information retrieval and machine translation systems. Also, because of the ambiguities in the resulted parses, the output of this algorithm must be disambiguated by another approach. To overcome the mentioned problems, we use an alternative approach which is based on statistical partial parsers. One of the partial parser systems which alleviate the TAG formalism problems in time complexity and ambiguity is named supertagging, proposed by (Bangalore and Joshi [2]). The idea behind supertagging is to extend the notion of “tag” from a part of speech …

Content truncated to 500 words