Unsupervised Learning of Morphology: Survey, Model, Algorithm and Experiments
Harald Hammarström · 2007
This thesis contains work on a specific problem in field of LanguageTechnology. The problem can be described as follows:"Can a computer extract a description of word conjugation in a naturallanguage using only written text in the language?"The problem is often referred to as Unsupervised Learning ofMorphology (ULM) and has a wide variety of Language Technologyapplications, including Machine Translation, Document Categorizationand I nformation Retrieval. The ULM problem is also relevant forlinguistic theory, and can serve to boost empirical investigations insubfields as Quantitative Linguistics and Linguistic Typology,The first part of the thesis contains a comprehensive survey of workdone on the ULM problem. All the minor and major lines of work arementioned with a reference and a very brief characterization.Different approaches that have been prevalent in the field as a wholeare highlighted and critically discussed. The general pictureresulting from the survey is that much work has been repeated over andover, with little exchange and evolution of techniques.The second part of the thesis describes a simple model ofconcatenative affixation, i.e., how stems and affixes are stringedtogether to form words. The model says that words consist ofhigh-frequency strings (``affixes'') attached to low-frequency strings(``stems''), e.g., as in the English play-ing. Then it isshown that from a set words constructed according to the model, theaffixes can be extracted with their correct segmentation. Thealgorithm for extraction is impressionistically evaluated on a diverseset of natural languages.The affix extraction algorithm does not output a full-fledged description ofconjugational patterns -- it only produces a list of affixes. The third andfourth parts of the thesis show how it can be used in further morphologicalanalysis.In the third part, an algorithm is presented that decidesif two given words are conjugations of the same stem. The key part isthe development of a metric for quantifying which endings tend to attachto the same set of stems. The algorithm has no parameters or human inputand works equally well for languages with widely different morphologicaltypology. It achieves almost perfect accuracy on word pairs selected fromrunning text. In the fourth part, the affix extraction model is exploited for thewritten language identification problem, i.e., to decide which naturallanguage a given text is written in. Existing state-of-the-arttechniques to identify the language of a written text most often use a3-gram frequency table as basis for 'fingerprinting' a language. Whilethis approach performs very well in practice (99\\%-ish accuracy) ifthe text to be classified is of size, say, 100 characters or more, itcannot be reliably used to classify even shorter input, nor can itdetect if the input is a concatenation of text from several languages.Therefore a more fine-grained model is presented which aims at reliableclassification of input as short as one word. In essence, thelanguage of an unseen word is guessed based on any salient affixesthat appear on it. Many practical applications do not need this finelevel of granularity, but Multilingual Information Retrieval is amajor target area where input is usually only one or a few words.The algorithm is given a rigorous evaluation on a 32-language parallelbible corpus showing competitive accuracy on short input as well asmulti-lingual input, and not only for a set of European languages withsimilar morphological typology.