Application of search algorithms to natural language processing

Application of Search Algorithms to Natural Language Processing Abstract Currently, the most common technique for Natural Language parsing is done by using pattern matching through references to a database with the aid of grammatical structures models. But the huge variety of linguistical syntax and semantics means that accurate real time analysis is very dif- ficult. We investigate several optimisation approaches to reduce the search space for finding an accurate parse of a sentence where individual words can have multiple possible syntactic categories, and catego- ries and phrases can combine together in different ways. The algorithms we con- sider include mechanisms for ordering that reduce the search cost without loss of completeness or accuracy as well as mechanisms that prune the space and may result in eliminating valid parses or re- turning a suboptimal as the best parse. We discuss the development and benchmark- ing of the existing and proposed algo- rithms in terms of accuracy, search space and parse time. Speed up of an order of magnitude was achieved without loss of completeness, whilst decrease of over two orders of magnitude was achieved in the search space. A further order of magni- tude reduction of both time and search space was achieved at the expense of some loss of accuracy in finding the most probable parse. 1 Introduction The complexity and the sizes of the lexical data- bases and grammatical rules contribute to most of the behaviour of Natural Language parsers. By increasing the sizes of the database or including a more complex set of grammatical rules, the parser is able to handle the parsing of more complex sen- tences or is able to include more accurate informa- tion to the parsed sentences, but the introduction of these results in a more complex parsing procedure and the capability to compute for more cases is necessary for the parser. Even without the ex- tended database or rules, parsing of long sentences is often avoided due to the extremely large amount of different possibilities in parsing the sentence. To counteract the increase in the parse time form the application of complex grammatical rules, we explore the effects of applying search algo- rithms to a parser to reduce the search space and hence enhance the parsing speed. To measure the accuracy of the parse, we use a simple scoring sys- tem derived from the probability that a particular structure would exist. This scoring system does not always parse the sentence correctly, but it provides a good indication of the likeliness of the structure from a statistical point of view. The purpose of the project is to provide a faster way of parsing sentences without losing the effect of grammatical structures, or the semantic and syn- tactic information that have been applied to or ex- tracted from the parser. These areas being the key focus of most research done in NLP and will con- tinue to increase in complexity in the future. Takeshi Matsumoto School of Informatics and Engineering Flinders University of South Australia …

Content truncated to 500 words