Unbalanced Optimal Transport for Unbalanced Word Alignment (2023)

Abstract: Monolingual word alignment is crucial to model semantic interactions between sentences. In particular, null alignment, a phenomenon in which words have no corresponding counterparts, is pervasive and critical in handling semantically divergent sentences. Identification of null alignment is useful on its own to reason about the semantic similarity of sentences by indicating there exists information inequality. To achieve unbalanced word alignment that values both alignment and null alignment, this study shows that the family of optimal transport (OT), i.e., balanced, partial, and unbalanced OT, are natural and powerful approaches even without tailor-made techniques. Our extensive experiments covering unsupervised and supervised settings indicate that our generic OT-based alignment methods are competitive against the state-of-the-arts specially designed for word alignment, remarkably on challenging datasets with high null alignment frequencies.

## introduction monolingual word alignment, which identifies semantically corresponding words in a sentence pair, has been actively studied as a crucial technique for modelling semantic relationships between sentences, such as for paraphrase identification, textual entailment recognition, and question answering @xcite @xcite @xcite . its ability to declare redundant information in sentences is also useful for summarisation and sentence fusion @xcite . in addition, the alignment information is valuable for interpretability of model predictions @xcite and for realising interactive document exploration as well @xcite . figure 1 illustrates the challenges of monolingual word alignment. the first challenge is the null alignment, where words may not have corresponding counterparts, which causes alignment asymmetricity @xcite . null alignment is prevalent in semantically divergent sentences; indeed, the null alignment ratio reaches 63.8% in entailment sentence pairs used in our experiments (shown in the third row of this study reveals that a family of optimal transport (ot) are suitable tools for unbalanced word alignment. among the ot problems, balanced ot (bot) @xcite 1 should be the most prominent in natural language pro-cessing (nlp) @xcite , which can handle many-to-many alignment. in contrast to bot that is unable to deal with null alignment, partial ot (pot) @xcite and unbalanced ot (uot) @xcite can handle the asymmetricity as desired in unbalanced word alignment, which has also attracted applications where null alignment is unignorable @xcite @xcite @xcite . this is the first study that connects these two paradigms of unbalanced word alignment and the family of ot problems that can naturally address null alignment as well as many-to-many alignment. we empirically (1) demonstrate that the ot-based methods are natural and sufficiently powerful approaches to unbalanced word alignment without tailor-made techniques and (2) deliver a comprehensive picture that unveils the characteristics of bot, pot, and uot on unbalanced word alignment with different null alignment ratios. we conduct extensive experiments using representative datasets for understanding ot-based alignment: effects of ot formalisation, regularisation, and a heuristic to sparsify alignments. our primary findings can be summarised as follows. first, in unsupervised alignment, the best ot problem depends on null alignment ratios. second, simple thresholding on regularised bot can produce unbalanced alignment. third, in supervised alignment, simple and generic ot-based alignment shows competitive performance to the state-of-the-art models specially designed for word alignment. the adoption of well-understood methods with a solid theory like ot is highly valuable in application development and scientific reproducibility. furthermore, ot-based alignment performs superiorly or competitively to existing methods, despite being independent of tailor-made techniques. our ot-based alignment methods are publicly available as a tool called otalign. 2 2 related work ## problem definition suppose we have a source and target sentence pair @xmath0, s 2 , . . . , s n } and @xmath1, t 2 , . . . , t m } with their word embeddings {s 1 , s 2 , • • • , s n } and {t 1 , t 2 , • • • , t m }, respectively, where s i , t @xmath2. the goal of monolingual word alignment is to identify an alignment @xmath3, where p i,j indicates a likelihood or binary indicator of aligning s i and t j . ## background: optimal transport ot seeks the most efficient way to move mass from one measure to another. remarkably, the ot problem induces the ot mapping that indicates correspondences between the samples. while ot is frequently used as a distance metric between two measures, ot mapping is often the primary concern in alignment problems. formally, the inputs to the optimal transport problem are a cost function and a pair of measures. on the premise of its application to monolingual word alignment, the following explanation assumes that the source and target sentences s and t and their word embeddings are at hand (see §3). a cost means a dissimilarity between s i and t j (source and target words) computed by a distance metric c : r d × r @xmath4, such as euclidean and cosine distances. the cost matrix @xmath5, that is, c i,@xmath6, t j ). a measure means a weight each word has. the concept of measure corresponds to fertility introduced in ibm model 3 @xcite , which defines how many target (source) words a source (target) word can align. in summary, the mass of words in s and t is represented as arbitrary measures @xmath7, respectively. 3 finally, the ot problem identifies an alignment matrix p with which the sum of alignment costs is minimised under the cost matrix c: l c (a, b) := min @xmath8,b) ⟨c, p ⟩ , where ⟨c, p ⟩ := i,j c i,j p i,j . the alignment matrix p belongs to u (a, b) ⊆ r n×m + that is a set of valid alignment matrices, introduced in the following sections. with this formulation, we can seek the most plausible word alignment matrix p . ## proposal: unbalanced word alignment as optimal transport problem in this study, we aim at formulating monolingual word alignment with high null frequencies in a natural way. for this purpose, we leverage ot with different constraints and reveal their features on this problem. we adopt the basic and generic cost matrices and measures instead of engineering them to avoid obfuscating the difference between bot, pot, and uot. ## experiment settings we empirically investigate the characteristics of bot, pot, and uot on word alignment in both unsupervised and supervised settings. we refer to our ot-based alignment methods as otalign, hereafter. to alleviate performance variations due to neural model initialisation, all the experiments were conducted for 5 times with different random seeds, and the means of the scores are reported. dataset as datasets that provide humanannotated word alignment, we used microsoft research recognizing textual entailment (msr-rte) @xcite , edinburgh++ @xcite , and multi-genre monolingual word alignment (multimwa) @xcite as shown in pre-trained language model otalign as well as the recent powerful methods ( §2.1) use contextualised word embeddings obtained from pre-trained (masked) language models. as the basic and standard model, we used bert-base-uncased @xcite for all the methods compared to directly observe the capabilities of different alignment mechanisms and to exclude performance differences owing to the underlying pre-trained models. 6 for unsupervised word alignment, we used the 10th layer in bert that performs strongly in unsupervised textual similarity estimation @xcite . for supervised alignment, we used the last hidden layer following the convention. otalign our ot-based alignment methods require a cost function and fertility. as discussed in §5.1, we experiment with cosine and euclidean distances as cost functions and uniform distribution and l 2 -norm of word embeddings as the fertility. due to the space limitation, the main paper only discusses the results of a cost function and fertility that performed consistently strongly on the validation sets. appendix b draws the complete picture of different distance metrics and fertility and analyses their effects. we fixed the regularisation penalty ε to 0.1 throughout all experiments. the threshold λ to sparsify alignment matrices was searched in [0, 1] with 0.01 interval to maximise the validation f1. more details of the implementation and experiment environment are described in appendix a.2. ## unsupervised word alignment we reveal features of ot-based methods on monolingual word alignment under unsupervised learning to segregate the effects of supervision on the pre-trained language model. note that we use the validation sets for hyper-parameter tuning, which may not be strictly 'unsupervised.' we still call this scenario 'unsupervised' for convenience, believing that the preparation of small-scale annotation datasets should be feasible in most practical cases. ## summary and future work this study revealed the features of bot, pot, and uot on unbalanced word alignment and suggested that they perform sufficiently powerfully without tailor-made designs. in future, our ot-based methods can be enhanced for better phrase alignment by employing sophisticated phrase embedding models as discussed in limitations section. we will also apply ot-based alignment to problems related yet with different constraints and objectives, e.g., crosslingual word alignment and text matching.