Automatic acquisition of two-level morphological rules

Theron, Pieter Zacharias (1999-02)

Dissertation (Ph.D.) -- University of Stellenbosch, 1999.

Thesis

ENGLISH SUMMARY: There are numerous applications for computational systems with a natural language processing capability. All these applications, which include free-text information retrieval, machine-translation and computer-assisted language learning, require a detailed and correctly structured database (or lexicon) of language information on all the levels of language analysis (phonology, morphology, syntax, semantics, etc.). To hand-code this information can be time-consuming and error prone. An alternative approach is to attempt the automation of the lexicon construction process. The contribution of this thesis is to present a method to automatically construct rule sets for the morphological and phonological levels of language analysis. The particular computational morphological framework used is that of two-level morphology. The lexicon, which contains the language specific information of two-level analyzers/ generators, consists of two components: (1) A morphotactic description of the words to be processed, as well as (2) a set of two-level phonological (or spelling) rules. The input to the acquisition process is source-target word pairs, where the target is an inflected form of the source word. It is assumed that the target word is formed from the source through the optional addition of a prefix and/or a suffix. There are two phases in the acquisition process: (1) segmentation of the target into morphemes and (2) determination of the optimal two-level rule set with minimal discerning contexts. In phase one, an acyclic deterministic finite state automaton (ADFSA) is constructed from string edit sequences of the input pairs. Segmentation of the words into morphemes is achieved through viewing the ADFSA as a directed acyclic graph (DAG) and applying heuristics using properties of the DAG as well as the elementary string edit operations. For phase two, the determination of the optimal rule set is made possible with a novel representation of rule contexts, with morpheme boundaries added, in a new DAG. We introduce the notion of a delimiter edge. Delimiter edges are used to select the correct two-level rule type as well as to extract minimal discerning rule contexts from the DAG. To illustrate the language independence of an acquired rule set, results are presented for English adjectives, Xhosa noun locatives, Afrikaans noun plurals and Spanish adjectives. Furthermore, it is shown how rules are acquired from thousands of input source target word pairs. Finally, the excellent generalization of an acquired rule set is shown by applying a slightly manually modified rule set to previously unseen words. The recognition accuracy on unseen words was 98.9% while the generation accuracy was 97.8%.

AFRIKAANSE OPSOMMING: Daar is baie toepassings vir rekenaarstelsels met 'n natuurlike-taal verwerkingsvermoe. Al hierdie toepassings, wat vrye teks inligtingonttrekking, masjien vertaling en rekenaargesteunde taalonderrig insluit, benodig 'n gedetailleerde en korrek gestruktureerde databasis (of leksikon) van taalinligting oor al die vlakke van taalanalise (fonologie, morfologie, sintaks, semantiek, ens.). Om hierdie taalinligting per hand te kodeer kan tydrowend wees en foute kan maklik gemaak word. 'n Alternatiewe benadering is om die leks ikon konstruksie proses te probeer outomatiseer. Die bydrae wat hierdie tesis maak is om 'n metode te beskryf vir die outomatiese aanleer van reels vir die morfologiese en fonologiese vlakke van taalanalise. Die spesifieke rekenaarlinguistiese raamwerk wat gebruik is, is die van twee-vlak morfologie. Die leksikon, waar die taalspesifieke inligting van twee-vlak analiseerders / genereerders gestoor word, bestaan uit twee komponente: (1) 'n Morfotaktiese beskrywing van die woorde wat verwerk sal word en (2) 'n stel van twee-vlak fonologiese (of spel) reels. Die invoer van die aanleerproses is bron-teiken woordpare, waar die teikenwoord 'n infleksie van die bronwoord is. Dit word aanvaar dat die teikenwoord gevorm word deur die opsionele byvoeging van 'n voorvoegsel en/of 'n agtervoegsel by die bronwoord. Twee fases kan onderskei word in die aanleerproses: (1) Segmentasie van die teikenwoord in die morfeme waaruit dit bestaan en (2) die bepaling van die optimale stel twee-vlak reels met die kortste moontlike onderskeidende kontekste. In fase een word 'n asikliese deterministiese eindige-toestand outomaat (ADETO) gekonstrueer van die string-redigeringsreekse (E. "string edit sequences") van die invoer woordpare. Die teikenwoorde word gesegmenteer in die morfeme waaruit dit bestaan deurdat die ADETO as 'n gerigte asikliese grafiek (GAG) beskou word en deur die toepassing van heuristiese reels wat die eienskappe van die GAG benut sowel as die eienskappe van die element ere string-redigeringsreeks operasies. In fase twee word die vasstelling van die optimale stel twee-vlak reels moontlik gemaak deur 'n unieke voorstelling van die reelkontekste, met morfeemgrense bygevoeg, in 'n nuwe GAG. Ons skep die konsep "afbakeningsboog" (E. "delimiter edge"). Afbakeningsboe word gebruik om die korrekte twee-vlak reelsoort te bepaal sowel as vir die onttrekking van die kortste onderskeidende kontekste vanuit die GAG. Om die taalonafhanklikheid van die leerproses te illustreer word result ate gegee vir Engelse byvoeglike naamwoorde, Xhosa selfstandige naamwoord lokatiewe, Afrikaanse selfstandige naamwoord meervoude en Spaanse byvoeglike naamwoorde. Verder word gewys hoe reels geleer word vir duisende bron-teiken woordpare. Laastens word gewys hoe goed die aangeleerde reels, met minimale veranderings, veralgemeen om toegepas te word op woorde wat nie gesien is gedurende die leerproses nie. Die herkenningsakkuraatheid vir hierdie woorde was 98.9% en die genereringsakkuraatheid was 97.8%.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/51149
This item appears in the following collections: