Interactive Word Completion for P lains C ree (2022)

Abstract: The composition of richly-inflected words in morphologically complex languages can be a challenge for language learners developing literacy. Accordingly, Lane and Bird (2020) proposed a finite state approach which maps prefixes in a language to a set of possible completions up to the next morpheme boundary, for the incremental building of complex words. In this work, we develop an approach to morph-based auto-completion based on a finite state morphological analyzer of Plains Cree (nêhiyawêwin), showing the portability of the concept to a much larger, more complete morphological transducer. Additionally, we propose and compare various novel ranking strategies on the morph auto-complete output. The best weighting scheme ranks the target completion in the top 10 results in 64.9% of queries, and in the top 50 in 73.9% of queries.

## introduction the acl 2022 theme track asks how we can scale up current nlp technologies for the rich diversity of human languages. we contend that impactful work, intended to support local language community goals, does not necessarily focus on scale or current nlp technologies. community values and motivations regarding language technology is as rich and varied as human language itself, and solutions which are well received in one community may not be adequate or appropriate in another. context must be considered, from which novel tasks take shape. lane and bird (2020)'s re-imagining of word completion for morphologically-rich languages is an example of work born from a local context. based in kunwinjku-speaking communities in northern australia, we wanted to support people's desire to learn literacy and practice building the language's long polysynthetic words. this led to the idea for a tool that helps users incrementally build complex words by suggesting completions up to the next morph boundary (figure 1 ). while plains cree and kunwinjku speaking communities are thousands of miles apart, the authors of this work noticed some similarities in their respective contexts: both plains cree and kunwinjku are polysynthetic languages, and both are working with communities to support language learning initiatives. other aspects of our situations differ. for example, the fst morphological analyzer for kunwinjku can be described as a field tool, developed by a single researcher over the course of a couple years, while the plains cree morphological analyzer has been in continuous development by a team for over 8 years. the plains cree model is much more extensive, robust and complete. how will the morph completion work transfer to such a large and technically refined project? how can we leverage our unique constellation of resources to adapt morph completion to suit plains cree? these are the question we set out to answer in this work. this work examines the assumptions of morphbased auto-complete, and extends existing work to suit plains cree. our contributions are: an imple-mentation of morph-based completion algorithm for plains cree foot_0 , a discussion of contextual similarities and differences between kunwinjku and plains cree and how this affects the utility of the morph-based completion concept, and a novel ranking algorithm which enables the morph-completion concept to scale to a much larger, more extensive grammar. plains cree (endonymically known as nêhiyawêwin, iso 639-3: crk) is a member of the algonquian family. it is the western-most cree dialect, spoken by about 20,000 speakers in alberta, saskathewan, and northern montana @xcite . years of documentary linguistic work have produced extensive language resources in the form of grammars @xcite @xcite and textbooks @xcite . kunwinjku (iso 639-3:gup) is a member of the gunwinyguan language family. it is spoken by an estimated 1,700 speakers in the west arnhem region of northern australia. kunwinjku has its own documentary resources: grammars @xcite , and a language primer @xcite . despite these volumes, literacy in kunwinjku is quite rare. while by some standards these languages might be classified as "low-resource", the depth and abundance of descriptive linguistic work has paved the way for the development of computational models of kunwinjku and plains cree morphology @xcite @xcite @xcite . based on these computational models of morphology, language technologies are being developed to support the language goals of these communities: smart dictionaries and spellcheckers @xcite , word-builder application @xcite , and intelligent language learning applications @xcite . ## adaptation for plains cree adapting the autocompletion algorithm to plains cree is relatively straightforward, owing in part to the similarities between plains cree and kunwinjku. like kunwinjku, plains cree is a polysynthetic agglutinating language @xcite . also like kunwinjku, plains cree verbs have been described using templatic morphology: according to @xcite , there are 8 prefixal slots plus some amount of reduplication. suffixially, @xcite provides 10 seperate slots, but in practice, these are regularly chunked together into a single portamanteau morph @xcite . for this reason, plains cree is often treated as a mostlyprefixing language, similar to kunwinjku. both kunwinjku and plains cree also exhibit word-internal dependencies as well as noun incorporation. in terms of agreement, kunwinjku verbs exhibit circumfixal markers for tense, where morphemes directly before and after the verb stem must agree for the feature. plains cree, on the other hand, exhibits dependency in its person marking (where the left-most and right-most morphemes of a verb form a circumfix) as well as its comitative derivation (where morphemes immediately to the left and right of the verb stem constitute a circumfix). noun incorporation is present in both languages, though it is more common in kunwinjku, where it occupies a slot in the prefixal morphology. where noun incorporation is present in plains cree, it interrupts the verb stem itself and is rare enough to often be lexicalized as a separate verb all together. these similarities and differences have consequences for each language's underlying fst and thus the autocompletion algorithm. issues of longdistance dependencies are essentially handled in an identical way, through the use of flag diacritics to restrict progression through the model @xcite . in terms of derivational morphology, the kunwinjku fst marks derivational morpheme boundries identically to inflectional ones. with respect to the plains cree fst, we have explored including derivational boundaries within stems, but have left that out of the morpheme completion solution, in part because it increases complexity, size, and speed of model, and in part since making use of derivational boundaries would split stems in a manner that would require users to have an understanding of the derivational morphology of plains cree that most, in particualr learners, do not possess. we opt instead to pre-compile derivational stems, thus ignoring derivational boundaries in favor of providing full-stem-length suggestions to users. ## presentation of plains cree algorithm in this section we give a detailed overview of our implementation, with examples written in the xfst formalism @xcite . our first step is to capture the full lexical side of our morphological analyzer (words) with morph boundaries present (a derivational boundary / is added in conjunction with the occurrence of a lexeme-internal hyphen that is not associated with an inflectional boundary, i.e. < @xmath0: ## evaluating morph completion and ranking the intention is that this model can be deployed to support text entry in a morphologically complex language. we therefore want to measure how often the model is able to deliver a useful set of results. we define a "useful" result set as one which returns at least one completed prefix which is a proper substring of the target full-word, within the top n ranked results. for example, if @xmath1, our target word is nikî-kitêyimikawinân and our query is ni, then a result of nikîappearing in the top 10 results is counted as useful. in order to evaluate the usefulness of the models systematically, we randomly sampled 100 unique fully-inflected word forms from the "dog biscuits" story by solomon ratt which is publicly available online. 4 these words are broken down into their complete set of prefixes, which created a set of 1,322 prefixes. each prefix is used as a query, retrieving result sets at @xmath2, 25, 50, and we report on the percent of queries which return a valid completion in the top n for each of the ranking strategies described in section 4.1 (see ## results we measure the completion space of two versions of the morph completion model. given a large sample of model inputs (prefixes), the x-axis repre- given that the purpose of morph-based completion is to help guide the user to build out complex words, we would prefer to deploy a spellingrelaxed version of the model. however, the magnitude of the measured completion space of this model would make this infeasible, as the median number of completions stays above 100 up until 12 characters of the input have been typed. thus, coming up with an effective weighting strategy is absolutely essential in order to have a model that can handle orthographic variation in the input. the baseline, unweighted strategy can be seen in figure 5 . here, the distribution of rankings roughly imitates the shape of the full completion space (figure 3 ), with the majority of mass occurring above our ideal ranking threshold of 10. to be precise, with the baseline no-ranking strategy, 38.4% of sampled queries result in a valid completion ranked in the top 10 results, 42.7% give a valid completion in the top 20, and 48.0% give a valid completion in the top 50. in contrast, the best weighting scheme is the wfst, which significantly improves the distribution of rankings compared to the baseline, with the majority of queries providing valid completions in the top 10. more precisely, 64.9% of prefix queries result in a a valid completion ranked in the top 10, 69.5% in the top 20, and 73.9% in the top 50 (figure 6 ). ## qualitative evaluation and discussion this section gives an overview of the use of the morphological autocomplete system by one of the authors, an english native, second language learner of plains cree. 5 this use case aligns with a major subset of potential users: literate but nonfluent learners of the language. foot_5 by restricting the autocomplete results to the top 10 most heavily weighted items, we have found the system to perform quite well. the system was evaluated by typing the basic introductory phrase tânisi nitôhtemak! atticus nitisiyihkâson êkwa kêkânistomitanaw ê-tânitahtopiponêyân. nitatoskân amiskwaciy-wâskahikanihk, which translates to "hello friends! my name is atticus and i am 29 years old. i work in alberta." this phrase was chosen as it contains fairly common lexical items while also being a realistic use case. in typing these words, no diacritics were used, as typing a circumflex on a north american keyboard requires a number of extra strokes, and such diacritics are often not included in non-professional plains cree writing. additionally, atticus, was not typed into the autocomplete system as it is not a plains cree word. writing this excerpt reveals interesting user experience data. while most words had the appropriate autocomplete suggestion, the word nitisiyihkâson could only be suggested by typing all but the last two letters: nitisiyihkâs. typing any less did not result in target suggestions. this was likely due to the fact that the system seemed to prefer analysing the string as beginning with the morpheme nitisiyi-, rather than the target morphemes of ni-t-isiyihkâso-. this is particularly notable as introductions are common, especially for language learners. similarly, in autocompleting kêkânistomitanaw results were unexpected. the correct breakdown for this word is kêkâ-nisto-mitanaw; despite this, nistoand -mitanaw are written together orthographically. the morphological autocomplete suggestions when given the input string keka-ni produce only kêka-nîso-, specifically with the final hyphen. if one types kêka-nîstom, the system suggests kêkâ-nistomitanaw. the the previous two cases, the autocomplete and weighting system are working exactly as expected. the issue instead lies with the underlying corpus, which features neither kêkâ-nistomitanaw nor any form of the verb nitisiyihkâson. the corpora used as a base for weighting is mostly lectures or discussion between individuals who are otherwise familiar with each other. unsurprisingly, this did not result in instances of individuals introducing themselves to one another or discussing anyone named atticus. further, in typing only eas an input string is not useful in and of itself, as all verbs can take this morpheme (written as ê-). in addition to the expected benefits of autocompletion, the system empowers users to type the language even if they are not entirely sure of the correct form of a word. as an example, the term nitatoskân comes from the root atoskê-. although person marking morphology in the form of a nit---n circumfix is easy enough for learners to remember, in some conjugations, the final ê becomes an â. this is not consistent among conjugation classes, and some verb classes show the opposite alternation. as a result, second language learners can struggle with knowing whether to write nitatoskân or *nitatoskên. the autocom-plete system solves this problem by suggest only the correct nitatoskâ when the user types nitato. the main drawback of this system from a user perspective is that target completions were rarely the top most suggestions, but this appears to be due to minimal training data for the weighting, and is not critical as long as the user is competent enough to know which suggestions are categorically incorrect. ## conclusion in this paper we presented an approach to morphbased autocompletion for plains cree. informed by our particular context and availability of corpus data, we expanded on their approach by exploring three different weighting schemes to rein in the magnitude of possible completions per query, which are a result of our need to accommodate a more complex fst grammar, and greater orthographic flexibility. our results show that all three weighting schemes go a long way to move target string rank distributions below desired thresholds, with the lexical weighting approach ranking the target completion in the top 10 results in 64.9% of queries, and in the top 50 in 73.9% of queries. the qualitative evaluation highlighted the usefulness of using an underlying fst to generate completions: long-distance dependencies and circumfixes are respected by the autocomplete algorithm, and so morphotactic integrity is preserved. additionally, spelling relaxation rules in the underlying fst mean that the user does not need to worry as much about inputting diacritics, or exact spelling: the algorithm will suggest and rank alternate surface forms which vary along these dimensions. in future work we hope to deploy morph completion models in mobile devices, to support text entry. however, before we get there, we need to do proper user testing with members of the community and get their feedback on a polished demo of the project at this stage. indeed, a limitation of this work is that we chose not to carry out thorough user testing in the cree community at this stage. it is natural for researchers to want to rush prototypes into the hands of prospective users, but this can lead to technology burnout among otherwise willing collaborators @xcite . we performed intrinsic evaluation by measuring the model's completion space to judge the feasibility of moving forward with the concept, and did self-testing to convince ourselves that the user experience is workable. that is the scope of this work. meaningful advances in language technology for low-resource, indigenous, and/or endangered languages entails progress in our recognition and engagement with the context and use cases for such technologies at a community level. morph-based autocompletion is designed to support text entry and word-building for morphologically rich languages. there are myriad factors which affect the usefulness of any approach in the real world. in our experience, connecting with real-world contexts leads to a better understanding of use-cases and problem constraints. this, in turn, fuels creativity and leads to better outcomes for the language communities we work with.