Morphological reinflection with weighted finite-state transducers (2023)

Abstract: This paper describes the submission by the University of Arizona to the SIGMORPHON 2023 Shared Task on typologically diverse morphological (re-)infection. In our submission, we investigate the role of frequency, length, and weighted transducers in addressing the challenge of morphological reinflection. We start with the non-neural baseline provided for the task and show how some improvement can be gained by integrating length and frequency in prefix selection. We also investigate using weighted finite-state transducers, jump-started from edit distance and directly augmented with frequency. Our specific technique is promising and quite simple, but we see only modest improvements for some languages here.

## introduction this paper describes the submission by the university of arizona to the sigmorphon 2023 shared task on typologically diverse morphological (re-)infection. the goal of the shared task is to model inflectional morphology. the specific task is to learn how to inflect for a language generally from a limited number of examples. in this task, we are given 10, 000 examples of inflected forms in 27 languages along with the morphological category and the generally accepted lemma form. for example, in english, we have data as in morphosyntactic information is in unimorph format @xcite . the logic is that we are given complete paradigms for n lemmas for each language where the number of lemmas we see in the training data is a function of the size of the paradigms. specifically, if paradigms are small, we see more lemmas than if paradigms are big. the goal is to build a system that learns the relationship between lemmas l, morphosyntactic descriptions m , and inflected words w . the system effectively computes a function from l × m to w . more details on the task are given in @xcite . the organizers provided two baseline systems, a neural and a non-neural one. we decided to focus our efforts on a non-neural solution and so we began our work by attempting to understand the non-neural baseline more clearly. for comparison purposes, we ultimately submitted four sets of results: i) our implementation of the non-neural baseline; ii) a version of the non-neural baseline with adjustments for prefix frequency and length; iii) an approach using weighted finite-state transducers; and iv) an ensemble approach using both prefix frequency/length and weighted transducers. in the following sections, we first review the structure of the baseline non-neural system. we then outline our approaches and present our results. we conclude with a discussion of shortcomings and next steps. foot_0 ## non-neural baseline the non-neural baseline system @xcite was inspired by @xcite . it prefix stem suffix ∅ happ y un happ iness for example, if the system were presented happy and unhappiness, it would hypothesize the morphological analysis in our first submission is essentially as described above. ## non-neural baseline improvements for our second submission, we made two revisions to the non-neural baseline system. first, we replaced the input for extracting prefix rules, which was originally specified as the concatenation of lemma's prefix and surface form's root, with the concatenation of lemma's prefix and lemma's root. given the alignment algorithm described above, this shouldn't have an effect in most cases, but it actually produced a small improvement. presumably, this is because of cases where the lemma and word form do not share an obvious root. second, we changed the criteria for choosing the best prefix rule. the criteria for choosing the best rule had been set up asymmetrically for prefix rules and suffix rules. for suffix rules, the longestmatching rule(s) given an input and the morphosyntactic description was chosen as the best rule. if there are ties, the most frequent rule was chosen. for prefix rules, frequency had been the only criterion and the length of the match had not been considered. we revised the system so that the same criteria apply to both prefix rules and the suffix rules. we were able to get a modest improvement in performance as a result of these revisions (non-neural baseline: 69.60%, revised system: 71.71%). foot_2 ## weighted finite-state transducers we also built a system, inspired by the non-neural baseline described above, but which uses weighted finite-state transducers instead. similar techniques have been tried before, for example, @xcite and @xcite . in fact, a number of them showed up in the 2016 version of this task, e.g. @xcite , @xcite , liu and mao (2016), and king (2016). 4 durrett and denero (2013) learns a set of transformations: separate ones for prefixes, stems, and suffixes. they use a conditional random field (crf) to combine and apply them. forsberg and hulden (2016) generate probabilistic and non-probabilistic morphological analyzers in an automatic way by converting morphological inflection tables into unweighted and weighted fsts. alegria and etxeberria (2016) uses phonetisaurus, a wfst-based system @xcite . king (2016) uses conditional random fields as well. separate edit rules are induced from edit distance comparisons and combined at inference. other features like position in the string were also incorporated. in our model, we use edit distance to calculate the precise overlap between a lemma and a surface form and then build a weighted finite-state transducer (wfst) from that that specifies changes with interleaving variables. the weights penalize degrees of mismatch with the variables. for example, take a lemma-word pair like break and broken. first, we use edit distance to calculate an optimal alignment. we then replace all identical spans with variables that penalize mismatches. in this example, br would be a variable and k would be a variable. our transducers are implemented in pyfoma foot_4 . using the formalism of that system, the resulting transducer would be specified as below: here there is a penalty associated with not matching the spans where the two forms align. in the formalism above, we've specified these as n to indicate that we experimented with different weighting options. there is a penalty associated with the rule as a whole, indicated above as m. this was used to incorporate different possible costs for the length of the rule. again, we tried different options here, but the general strategy was to penalize shorter less frequent rules. in training, we built transducers in this way for all training items, separated by morphosyntactic descriptions. for inference, we generated all possible outputs for a lemma with the wfsts for that morphosyntactic description and chose the one that had the lowest cost. we expected such a system would be better able to capture nonconcatenative morphological systems, systems where morphological categories might be marked by stem-internal changes as opposed to prefixes or suffixes. in fact, as we discuss below, this was not the case. based on development split performance, we saw that the frequency of forms played a role: as with the baseline system, more frequent output forms were preferred. to handle this, we adjusted our weighting scheme so that if multiple wfsts produced the same output, those got lowered scores. our approach differs from previous wfst-based approaches in three main respects. first, our alignment and overall system is extremely simple, as described above. second, our weights are naive, not trained, and assigned on the basis of a general theory of what should matter, as described above. finally, our system employs only transducers. one strength of our system is that it's very straightforward and easy to manipulate the weights. it can be used to test the effect each factor (e.g., form frequency, length of rules, etc.) has over the system's performance. ## ensemble system we found that our system generally did not perform as well as the non-neural baseline or our revision of it, but we saw improved performance for some languages with development data, specifically japanese, armenian, and italian. therefore we also submitted a ensemble system. where we generated test outputs using our improved baseline and our wfst system and selected the test results based on development data performance. ## results results for our four submissions are given in submission 1 is our execution of the non-neural baseline. it is here simply for comparison purposes. 6 submission 2 is our simple adaptation of the non-neural baseline to make prefixation and suffixation sensitive to the same variables of length and frequency of surface forms. the adapted system performed better than the non-neural baseline (67.1% vs. 71.7%). submission 3 is the wfst-based system. it does not perform very well in general (56.1%), but, as noted above, it does better than the systems 1 and 2 in a couple of cases: armenian, italian, and japanese. finally, submission 4 is the ensemble system, where we draw on systems 2 and 3 depending on which performed better with development data. ## discussion we focused our efforts on a non-neural approach and thus did not expect competitive results. that said, we did manage to improve over the non-neural baseline. our intention was to understand more deeply how morphological systems could be modeled in the simplest finite-state terms. to this end, we conducted several experiments with our wfst system. one of the experiments we did is to create the wfst with individual characters, instead of spans, as variables. in our submitted system, spans that are identical in a lemma-word pair are replaced with variables. we revised the system to replace individual matching characters with variables. for example, take the lemma-word pair break and broken once again. in our submitted system, identical spans br and k are replaced with variables that penalize mismatches. in the revised system, individual characters b, r, and k are replaced with variables. thus the first variable in the formula below is replaced as shown. the motivation for this experiment was to see if penalizing each unmatched character, rather than the whole span, would enhance the system's performance. our hypothesis was that penalizing individual characters would improve the system, as it would give a more specific penalty to an unmatched span. this was not the case. at least for the various weightings we tried, the individual character variable versions did not perform as well as system 3 above. in addition, the individual variable versions entailed much larger transducers and much longer run times. for the systems we submitted, running the languages in parallel meant a complete run always took less than an hour. for the individual variable versions, running the languages in parallel took over 15 hours on our campus supercomputer. our expectation is that with a compiled transducer system like foma or openfst and with more aggressive parallelization, we could reduce this runtime significantly. another experiment we did is to adjust weights based on the frequency of the form produced by the candidate wfsts. during error analysis, we found out that there are many wfst candidates producing the same form. in many cases these frequent forms were the correct ones, but they were not selected as the optimal forms due to high weights. in order to mitigate this issue, we tried adjusting the weights of the wfsts based on the frequency of the form the transducer produced. as a result of this adjustment, we were able to obtain a boost of approximately 5% in system performance on development data (from 51% to 56%). ## conclusion in conclusion, we developed three non-neural models. the first combined frequency and length in the selection of prefixes. the second used wf-sts built from edit distance alignments. the third model combined the results of the first two models. the direct baseline changes resulted in overall improvements, but the wfst system did not. however, there were specific language improvements from the wfst solution and we were able to incorporate these in our ensemble system.