1995 RobustParsingAlgForLinkGrammars
- (Grinberg et al., 1995) ⇒ Dennis Grinberg, John D. Lafferty, Daniel Dominic Sleator. (1995). “A Robust Parsing Algorithm for Link Grammars.” In: Proceedings of the Fourth International Workshop on Parsing Technologies.
Subject Headings: Link Grammar
Notes
Cited By
2003
- (Ding et al., 2003) ⇒ Jing Ding, Daniel Berleant, Jun Xu, and Andy W. Fulmer. (2003). “Extracting Biochemical Interactions from MEDLINE Using a Link Grammar Parser.” In: Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2003).
- Grinberg et al. developed a robust parser to implement the link grammar. It has a dictionary of about 60,000 words, and can recognize a wide range of English syntactic phenomena: noun-verb agreement, questions, imperatives, complex and irregular verbs, many types of nouns, past- or present-participles in noun phrases, commas, a variety of adjective types, prepositions, adverbs, relative clauses, possessives, coordinating conjunctions, and others. The parser was tested on a corpus of English telephone conversations. Its robustness was demonstrated by its ability to handle many “ungrammatical” sentences and sentence fragments. If a complete linkage cannot be found, the parser will try to form a “partial linkage” by ignoring one or more of the words in the sentence. The parser has an internal timer. If the timer runs down before a complete or partial linkage has been found, the parser will output whatever it has found so far (termed a fragmented linkage).
Quotes
Abstract
In this paper we present a robust parsing algorithm based on the link grammar formalism for parsing natural languages. Our algorithm is a natural extension of the original dynamic programming recognition algorithm which recursively counts the number of linkages between two words in the input sentence. The modified algorithm uses the notion of a null link in order to allow a connection between any pair of adjacent words, regardless of their dictionary definitions. The algorithm proceeds by making three dynamic programming passes. In the first pass, the input is parsed using the original algorithm which enforces the constraints on links to ensure grammaticality. In the second pass, the total cost of each substring of words is computed, where cost is determined by the number of null links necessary to parse the substring. The final pass counts the total number of parses with minimal cost. All of the original pruning techniques have natural counterparts in the robust algorithm. When used together with memoization, these techniques enable the algorithm to run efficiently with cubic worst-case complexity. We have implemented these ideas and tested them by parsing the Switchboard corpus of conversational English. This corpus is comprised of approximately three million words of text, corresponding to more than 150 hours of transcribed speech collected from telephone conversations restricted to 70 different topics. Although only a small fraction of the sentences in this corpus are "grammatical" by standard criteria, the robust link grammar parser is able to extract relevant structure for a large portion of the sentences. We present the results of our experiments using this system, including the analyses of selected and random sentences from the corpus.
References
,