A Framework for Bidirectional Decoding: Case Study in Morphological Inflection (2023)

Abstract: Transformer-based encoder-decoder models that generate outputs in a left-to-right fashion have become standard for sequence-to-sequence tasks. In this paper, we propose a framework for decoding that produces sequences from the “outside-in”: at each step, the model chooses to generate a token on the left, on the right, or join the left and right sequences. We argue that this is more principled than prior bidirectional decoders. Our proposal supports a variety of model architectures and includes several training methods, such as a dynamic programming algorithm that marginalizes out the latent ordering variable. Our model sets state-of-the-art (SOTA) on the 2022 and 2023 shared tasks, beating the next best systems by over 4.7 and 2.7 points in average accuracy respectively. The model performs particularly well on long sequences, can implicitly learn the split point of words composed of stem and affix, and performs better relative to the baseline on datasets that have fewer unique lemmas.

## introduction transformer-based encoder-decoder architectures @xcite that decode sequences from left to right have become dominant for sequence-to-sequence tasks. while this approach is quite straightforward and intuitive, some research has shown that models suffer from this arbitrary constraint. for example, models that decode left-to-right are often more likely to miss tokens near the end of the sequence, while rightto-left models are more prone to making mistakes near the beginning @xcite . this is a result of the "snowballing" effect, whereby the model's use of its own incorrect predictions can lead future predictions to be incorrect @xcite . we explore this issue for the task of morphological inflection, where the goal is to learn a mapping from a word's lexeme (e.g. the lemma walk) to a particular form (e.g. walked) specified by a set of morphosyntactic tags (e.g. v;v.ptcp;pst). this has been the focus of recent shared tasks @xcite @xcite @xcite @xcite . most approaches use neural encoder-decoder architectures, e.g recurrent neural networks (rnns) @xcite or transformers @xcite . 2 to our knowledge, @xcite is the only model that uses bidirectional decoding for inflection; it decodes the sequence in both directions simultaneously and returns the one with higher probability. in this paper, we propose a novel framework for bidirectional decoding that supports a variety of model architectures. unlike previous work ( §2), at each step the model chooses to generate a token on the left, generate a token on the right, or join the left and right sequences. this proposal is appealing for several reasons. as a general framework, this approach supports a wide variety of model architectures that may be task-specific. further, it generalizes l2r and r2l decoders, as the model can choose to generate sequences in a purely unidirectional fashion. finally, the model is able to decide which generation order is best for each sequence, and can even produce parts of a sequence from each direction. this is particularly appropriate for a task like inflection, where many words are naturally split into stem and affix. for example, when producing the form walked, the model may chose to generate the stem walk from the left and the suffix ed from the right. we explore several methods for training models under this framework, and find that they are highly effective on the 2023 sigmorphon shared task on inflection @xcite . our method improves by over 4 points in average accuracy over a typical l2r model, and one of our loss functions is particularly adept at learning split points for words with a clear affix. we also set sota on both the 2022 and 2023 shared tasks @xcite , which have very different data distributions. ## prior bidirectional decoders various bidirectional decoding approaches have been proposed for tasks such as machine translation and abstractive summarization, including ones that use some form of regularization to encourage the outputs from both directions to agree @xcite @xcite , or algorithms where the model first decodes the entire sequence in the r2l direction and then conditions on that sequence when decoding in the l2r direction @xcite . still more methods utilize synchronous decoding, where the model decodes both directions at the same time and either meet in the center @xcite or proceed until each direction's hypothesis is complete @xcite . @xcite allows the model to look into the future by filling placeholder tokens at each timestep. ## a bidirectional decoding framework the following sections present a general framework for training and decoding models with bidirectional decoding that is irrespective of model architecture, subject to the constraints discussed in §3.3. ## model architecture our architecture (figure 1 ) is based on the character-level transformer @xcite , which has proven useful for morphological inflection. first, the input sequence x is encoded with a typical transformer encoder; for the inflection task, this consists of the lemma (tokenized by character) concatenated with a separator token and set of tags. given a prefix -→ @xmath0, the decoder must produce each direction's token probabilities, the join probability, and the order probability. we construct the input to the decoder by concatenating the prefix and suffix tokens with some special classification tokens: the tokens c j , c o , c l2r , and c r2l are special classification tokens that serve a purpose similar to the cls embedding in bert @xcite . we feed this input to a transformer decoder as follows: these vectors are fed through their own linear layers and softmax, giving the desired probabilities: since this architecture does have cross-attention between the prefix and suffix, the decoder hidden states for each prefix-suffix pair must be recomputed at each timestep to allow for dp (see §3.3). ## experimental setup datasets. we experiment with inflection datasets for all 27 languages (spanning 9 families) from the sigmorphon 2023 shared task @xcite . each language has 10,000 training and 1,000 validation and test examples, and no lemma occurs in more than one of these partitions. we also show results on the 20 "large" languages from the sigmorphon 2022 shared task @xcite , which has a very different sampling of examples in the train and test sets. a list of all languages can be found in appendix a. tokenization. both the lemma and output form are split by character; the tags are split by semicolon. for the 2023 shared task, where the tags are "layered" @xcite , we also treat each open and closed parenthesis as a token. appendix b describes the treatment of unknown characters. model hyperparameters. our models are implemented in fairseq @xcite . we experiment with small, medium, and large model sizes (ranging from ∼240k to ∼7.3m parameters). for each language, we select a model size based on the l2r and r2l unidirectional accuracies; this procedure is detailed in appendix a. the only additional parameters in our bidirectional model come from the embeddings for the 4 classification tokens (described in §4); hence, our unidirectional and bidirectional models have roughly the same number of parameters. training. we use a batch size of 800, an adam optimizer (β 1 = 0.9, β 2 = 0.98), dropout of 0.3, and an inverse square root scheduler with initial learning rate 1e-07. training is halted if validation accuracy does not improve for 7,500 steps. all validation accuracies are reported in appepndix a. inference. decoding maximizes joint probability p (y, o|x) using the beam search algorithm of §3.5 with width 5. in some experiments, we rerank the 5 best candidates according to their marginal probability p (y|x), which can be calculated with dynamic programming ( §3.2). ## conclusion we have proposed a novel framework for bidirectional decoding that allows a model to choose the generation order for each sequence, a major difference from previous work. further, our method enables an efficient dynamic programming algorithm for training, which arises due to an independence assumption that can be built into our transformer-based architecture. we also present a simple beam-search algorithm for decoding, the outputs of which can optionally be reranked using the likelihood calculation. our model beats sota on both the 2022 and 2023 shared tasks without resorting to data augmentation. further investigations show that our model is especially effective on longer output words and can implicitly learn the morpheme boundaries of output sequences. there are several avenues for future research. one open question is the extent to which data augmentation can improve accuracy. we also leave open the opportunity to explore our bidirectional framework on other sequence tasks, such as machine translation, grapheme-to-phoneme conversion, and named-entity transliteration. various other architectures could also be investigated, such as the bidirectional attention mechanism of @xcite or non-transformer based approaches. finally, given the effectiveness of mml reranking, it could be worthwhile to explore efficient approaches to decode using marginal probability.