Non-directionality and Self-Assessment in an Example-based System Using Genetic Algorithms

Non-directionality and Self-Assessment in an Example-based System Using Genetic Algorithms Yves Lepage Bahagian Sains Komputer, PP Sains Matc,natik & Sains Komputer, Universifi Sains Malaysia, I Igo0 Penang, Malaysia e-mail: lepage@cs.usm.jp re,arch done at ATR Interpreting Telecommunications Research L.abs, Hi -Gari-dai 2-2, Seika-cho, Soraku-gun, 619-02 Kyoto, Japan Abstract We show the application of an optimisation technique to natural language processing: genetic algorithms, thanks to the definition of a data structure called board and a formal distance. The system hms two interesting features: non-directionality, whict~ Ls more than hi- directionality, and self-assessment, independently of the inner knowledge. Results of experiments are presented and discussed. Topleal paper: Software for NLP Introduction The purpose of this article is to show that an engine b~ed on an optimisation teclmique, namely genetic al- gorlthras, can perform NLP t~usks: analysis and gener- ation in the frame of example-based approaches. But more than that, the system we have built has interesting properties: • it is truly non-directional, i.e. it performs more than bi-directional tasks; • it evaluates its results relatively to tile input, and not relatively to its internal knowledge. Two original facts make this possible: • the definition of a data structure, called board which is in essence bidirectional. It is the Kssocia- tiou of a sentence pattern m~d its linguistic struc- ture; • the definition of a ,distance on this data structure. 1 Motivations 1.1. Non-direetionality Our mMn motivation was to design a system where not only the formalism but also the system engine is bi- directional. In [Lepage 91], we sketched such an engine tbr a rule-based al)proach. From a theoretical point of view, such a system is also more interesting than a system where, although the formalism would be bi-directional, analysis and genera- Lion would be separate modules resulting from different compilations. In our sketch, a more general property than bi-direc- t:ionality mue,'go,¢: ,ro,>direclioTJagil!l. IGdirectionality is just the property of executing analysis and genera- tion with the same set of specifications, whereas nou- directionality allows more: a complete sentence and its complete analysis can be built from a partial specifica- tion of the sentence and a partial description of tile as- sociated structure. 1.2 Self-assessment A second motivation lles in a flaw of rule-based systems using context-flee parsers, which is that they often fail to deliver a solution for trivia[ reasons such ~ a word missing in a dictionary. On the contrary, our system al.- ways delivers an output for any input, would the solution be "bad". O[" course, this woukl be of no meaning if the quality of outputs wotfid not be evahtated. IIence, when delivering a solution, the system scores it. Some machine translation systems viewed as expert systems may return an evaluation of their work in terms of their knowledge (grammar) [Tong 89], some other may evaluate the result according to thesaurus cl~ssificatlon and statistical frequencies [Furuse and lida 92b1, but all these methods are specific. Ifere, on the contrary, the system delivers a score which is a formal distance be- …

Content truncated to 500 words