Automatic acquisition of two-level morphological rules
Date
1999-02
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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%.
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%.
Description
Dissertation (Ph.D.) -- University of Stellenbosch, 1999.
Keywords
Computational linguistics, Two-level morphology, Two-level phonology, Dissertations -- Computer science