Experiments with Learning Parsing Heuristics

Experiments with Learning Parsing Heuristics Sylvain DELISLE Drpartement de mathrmatiques et d'informatique Universit6 du Qurbec ~ Trois-Rivi~res Trois-Rivi~res, Qurbec, Canada, GgA 5H7 Sylvain_Delisle @uqtr.uquebec.ca Sylvain LI~TOURNEAU, Stan MATWlN School of Information Technology and Engineering, University of Ottawa Ottawa, Ontario, Canada, KIN 6N5 sletour@ ai.iit.nrc.ca, stan @site.uottawa.ca Abstract Any large language processing software relies in its operation on heuristic decisions concerning the strategy of processing. These decisions are usually "hard-wired" into the software in the form of hand- crafted heuristic rules, independent of the nature of the processed texts. We propose an alternative, adaptive approach in which machine learning techniques learn the rules from examples of sentences in each class. We have experimented with a variety of learning techniques on a representative in- stance of this problem within the realm of parsing. Our approach lead to the discovery of new heuristics that perform significantly better than the current hand-crafted heuris- tic. We discuss the entire cycle of applica- tion of machine learning and suggest a methodology for the use of machine learn- ing as a technique for the adaptive optimi- sation of language-processing software. 1 Introduction Any language processing program---in our case, a top-down parser which outputs only the first tree it could find--must make decisions as to what processing strategy, or rule ordering, is most ap- propriate for the problem (i.e. string) at hand. Given the size and the intricacy of the rule-base and the goal (to optimise a parser's precision, or recall, or even its speed), this becomes a complex decision problem. Without precise knowledge of the kinds of texts that will be processed, these de- cisions can at best be educated guesses. In the parser we used, they were performed with the help of hand-crafted heuristic rules, which are briefly presented in section 2. Even when the texts are available to fine-tune the parser, it is not obvious how these decisions are to be made from texts alone. Indeed, the decisions may often be expressed as rules whose representation is in terms which are not directly or easily available from the text (e.g. non-terminals of the grammar of the language in which the texts are written). Hence, any technique that may automatically or semi-automatically adapt such rules to the corpus at hand will be valuable. As it is often the case, there may be a linguistic shift in the kinds of texts that are processed, especially if the linguistic task is as general as parsing. It is then interesting to adapt the "version" of the parser to the corpus at hand. We report on an experiment that targets this kind of adaptability. We use machine learning as an artificial intelligence technique that achieves adaptability. We cast the task described above as a classification task: which, among the parser's top- level rules, is most appropriate to launch the parsing of the current input string? Although we restricted ourselves to a subset of a parser, our objective is broader than just applying an existing learning system on this problem. What …

Content truncated to 500 words