PaperlayerView exact revision on arXiv

Source-linked AI summary

Unbalanced Optimal Transport for Unbalanced Word Alignment

Yuki Arase, Han Bao, Sho Yokoi

arXiv:2306.04116v1cs.CLcs.LG

TL;DR

Monolingual word alignment must capture both semantic correspondences and pervasive null alignments in divergent sentences. This paper evaluates balanced, partial, and unbalanced OT as generic alignment methods, finding competitive performance across unsupervised and supervised settings, especially when null alignment is frequent. The study also identifies how OT formulations behave under different null-alignment conditions.

  • Problem

    Monolingual word alignment must identify both corresponding words and null alignments, which indicate semantic gaps in divergent sentences.

    Source: §1 · p. 1

  • Method

    The study applies balanced, partial, and unbalanced optimal transport to unbalanced word alignment without tailor-made techniques.

    Source: §1 · p. 2

  • Results

    Generic OT-based alignment methods are competitive with specially designed state-of-the-art models, particularly on datasets with high null-alignment frequencies.

    Source: §1 · p. 2, §7.2 · p. 7, §8.2 · p. 8

  • Takeaways & Limitations

    The suitable OT formulation depends on null-alignment frequency, while OT provides a natural framework for identifying both aligned and null words.

    Source: §1 · p. 2

    Using standard basic word embeddings limits phrasal alignment capability, motivating span-enhanced representations and structure- or order-aware OT.

    Source: Limitations · pp. 9–10

Abstract

from arXiv · show

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.

1 Introduction

Monolingual word alignment must identify both semantic correspondences and null alignments, especially in divergent sentences. The study proposes balanced, partial, and unbalanced OT as generic solutions and finds them competitive without tailor-made techniques.

1 Introduction

  • Null alignment is prevalent in divergent sentences, reaching 63.8% in the entailment pairs evaluated, and must be identified alongside word correspondences.It signals semantic gaps and creates asymmetric alignment, while alignment can also exceed one-to-one mappings.Source: §1 · p. 1
  • Balanced OT handles many-to-many alignment, whereas partial and unbalanced OT additionally accommodate null alignment and asymmetricity.The paper explicitly distinguishes balanced OT from partial and unbalanced OT for these differing alignment conditions.Source: §1 · pp. 1–2
  • Across extensive unsupervised and supervised experiments, OT-based alignment methods are competitive with state-of-the-art word-alignment models despite using generic mechanisms.The study examines OT formalisation, regularisation, and alignment sparsification.Source: §1 · p. 2
  • In unsupervised alignment, the best OT formulation depends on the null-alignment ratio, while thresholding regularised balanced OT can produce unbalanced alignment.In supervised alignment, simple OT-based methods remain competitive with specially designed models.Source: §1 · p. 2
  • The resulting OT-based alignment methods are publicly available as OTAlign.The paper presents the tool as supporting application development and scientific reproducibility.Source: §1 · p. 2

2 Related Work

Prior work largely treats alignment as a component of crosslingual or task-specific systems. This study instead focuses on exhaustive monolingual identification of both aligned and null words, where the suitable OT formulation remains systematically underexplored.

2 Related Work

  • Crosslingual alignment commonly exploits large parallel corpora, whereas monolingual alignment lacks such resources and faces stronger asymmetricity in divergent sentences.These differences motivate treating the monolingual setting separately from machine-translation alignment.Source: §2.1 · p. 2
  • Existing monolingual methods commonly use supervised learning, including conditional random fields and neural models that define the state of the art.Lan et al. (2021) and Nagata et al. (2020) are identified as representative neural approaches.Source: §2.1 · p. 2
  • Earlier OT applications often use alignment implicitly for similarity or generation, while other tasks prioritize precision where alignment exists.These objectives differ from exhaustive unbalanced alignment, which also identifies null alignment.Source: §2.2 · pp. 2–3
  • No systematic comparison had established which OT formulation suits problems with different null-alignment frequencies.The paper addresses this gap by comparing OT-based alignment methods directly.Source: §2.2 · p. 3

3 Problem Definition

The problem is to identify semantic word correspondences between two sentences while representing words that align to nothing. Evaluation therefore treats ordinary and null alignments as equally important.

3 Problem Definition

  • Given source and target sentence embeddings, monolingual word alignment identifies a matrix P whose entries indicate correspondence likelihoods or binary alignment decisions.The matrix has dimensions n×m for n source and m target words.Source: §3 · p. 3
  • The evaluation uses macro-averaged precision, recall, and F1 over alignment pairs while explicitly incorporating null-alignment pairs.This extends metrics that previously considered only word-by-word alignments.Source: §3 · p. 3
  • Null alignment represents a word paired with a null word w_∅, and the ground-truth null set size equals the number of null-alignment words.Both predicted and ground-truth null-alignment sets contribute to evaluation.Source: §3 · p. 3

4 Background: Optimal Transport

Optimal transport formulates word alignment by minimizing correspondence costs under constraints on word masses, with BOT enforcing complete alignment and POT/UOT permitting null alignment.

Optimal Transport Formulation

  • OT identifies an alignment matrix that minimizes total word-pair dissimilarity under constraints determined by source and target word masses.The cost matrix records pairwise distances, while measures represent word fertility.Source: §4 · p. 3

Balanced Optimal Transport

  • BOT constrains source and target measures to probability distributions, producing a linear-programming problem that aligns all words.Its nondifferentiability makes integration into neural models challenging.Source: §4.1 · pp. 3–4
  • Entropy regularization makes BOT differentiable and efficiently solvable with Sinkhorn, while sufficiently small ε approximates exact BOT.The entropy term controls the regularized objective.Source: §4.1 · p. 4

Relaxation of BOT Constraint

  • POT and UOT relax BOT’s hard mass constraints so some words can remain unaligned when null alignment is prevalent.POT fixes the aligned fraction, whereas UOT penalizes marginal deviations through soft constraints.Source: §4.2 · p. 4
  • UOT uses divergence penalties whose strengths control marginal deviations, and this study adopts Kullback–Leibler divergence for computational simplicity.Source: §4.2 · p. 4

5 Proposal: Unbalanced Word Alignment as Optimal Transport Problem

The proposal treats high-null-frequency monolingual word alignment as an optimal transport problem using generic costs and fertility measures, then sparsifies dense solutions for interpretable links.

Proposal

  • The method applies generic OT cost matrices and measures to compare BOT, POT, and UOT without engineering them to obscure their differences.This directly targets monolingual alignment with high null frequencies.Source: §5 · p. 4

Embedding and Cost Construction

  • Contextualized word embeddings are obtained by mean-pooling subword outputs from a pretrained language model after concatenating source and target sentences.Source: §5.1 · p. 4
  • Cosine and Euclidean distances define semantic costs, while an IBM Model 2 distortion discourages links between words in distant positions.The distortion is scaled by κ and depends on normalized source and target positions.Source: §5.1 · p. 4

Sparse Alignment

  • Because Sinkhorn produces dense alignment matrices, the method thresholds matrix masses to obtain sparse alignments without imposing an arbitrary fertility assumption.The thresholded matrix can yield unbalanced alignment rather than merely sparsity.Source: §5.2 · p. 5

Unsupervised and Supervised Settings

  • Unsupervised alignment uses corpus-mean-centred embeddings, while supervised alignment learns a generalized distance matrix jointly with the model.Source: §5.3 · p. 5, §5.4 · p. 5

6 Experiment Settings

The experiments evaluate OTAlign across multiple human-annotated monolingual alignment datasets, settings, and OT design choices using repeated runs and common pretrained representations.

Experimental Design

  • Experiments investigate BOT, POT, and UOT in both unsupervised and supervised alignment settings, reporting means over five random seeds.Source: §6 · p. 5

Datasets

  • The evaluation uses MSR-RTE, Edinburgh++, and MultiMWA, whose subsets include MTRef, Newsela, ArXiv, and Wiki sentence pairs.Newsela and ArXiv support transfer-learning evaluation from models trained on MTRef.Source: §6 · p. 5

Evaluation Protocol

  • Evaluation distinguishes Sure and Possible from Sure Only alignment links, reflecting different annotation-confidence settings.Source: §6 · p. 6

Model Controls

  • All compared methods use BERT-base-uncased to isolate differences in alignment mechanisms from differences in pretrained language models.Unsupervised alignment uses the 10th BERT layer.Source: §6 · p. 6

OTAlign Configurations

  • OTAlign experiments vary cosine versus Euclidean costs and uniform versus embedding-norm fertility, while the main paper reports consistently strong validation choices.The complete combination analysis appears in the appendix.Source: §6 · p. 6

7 Unsupervised Word Alignment

Unsupervised alignment performance varies with null-alignment frequency, while regularisation and thresholding make OT methods better suited to unbalanced alignments.

Setup

  • The unsupervised experiments compare OTAlign with fast-align and SimAlign using test-set F1, with validation data used for hyper-parameter tuning.Table 2 reports F1 under ‘Sure and Possible’ and ‘Sure Only’ settings; Sinkhorn is the reported regulariser abbreviation.Source: §7.1 · p. 6, §7 · p. 6, Table 2 · p. 7

Primary observations

  • Regularised POT performed best on datasets with significantly high null alignment ratios, while BOT, POT, and UOT performed similarly when null alignment was low.On higher-null datasets, regularised OT methods largely outperformed SimAlign; on lower-null datasets, SimAlign also performed strongly.Source: §7.2 · pp. 6–7
  • Thresholding substantially improved unregularised BOT and POT, helping produce sparse and unbalanced alignment matrices.Unregularised BOT performed worst because its constraints force every word to align and prohibit null alignment.Source: §7.2 · p. 7
  • Most methods exhibit a v-shaped F1 curve because high-null-ratio samples disproportionately come from MSR-RTE entailment pairs.These pairs often have substantially different sentence lengths, leaving some words unaligned.Source: §7.2 · pp. 7–8
  • Figure 2 shows that alignment F1 generally decreases as null-alignment rates increase after accounting for the MSR-RTE anomaly.The overall trend becomes approximately inversely proportional to null-alignment rate when MSR-RTE is removed.Source: Figure 2 · p. 7, §7.2 · p. 8

8 Supervised Word Alignment

Supervised OT-based alignment is competitive with specialized state-of-the-art methods, especially as null alignment increases, while UOT captures longer phrase alignments that constrain competing approaches.

8.2 Results

  • UOT achieves competitive supervised alignment against state-of-the-art methods on datasets with higher null alignment ratios.It performs on par with Lan et al. (2021) despite using a simple, generic alignment mechanism.Source: §8.2 · p. 8
  • UOT consistently achieves higher alignment F1 than regularised BOT and POT in supervised evaluation.These results support UOT as a good fit for unbalanced word alignment.Source: §8.2 · p. 8
  • Above 15% null alignment, OT-based alignment outperforms Nagata et al. (2020), while regularised BOT is stronger below roughly 20% and UOT above it.Regularised BOT is 0.7% higher on average below the crossover, whereas UOT is 1.0% higher above it.Source: §8.2 · pp. 8–9
  • Across supervised datasets, alignment performance follows a V-shaped trend as null alignment ratios vary, with an inverse relationship when MSR-RTE is excluded.Figure 3 reports supervised alignment F1 (%) by null ratio.Source: §8.2 · p. 9, Figure 3 · p. 9
  • UOT aligns longer phrase pairs that Lan et al. (2021) and Nagata et al. (2020) miss because of chunk-size and one-to-many alignment constraints.The comparison is based on visualized alignment matrices for the same sentence pair.Source: §8.2 · p. 9, Figure 4 · p. 9

9 Summary and Future Work

The study finds that BOT, POT, and UOT can support unbalanced word alignment without tailor-made designs, and releases these methods as OTAlign.

9 Summary and Future Work

  • BOT, POT, and UOT perform sufficiently well for unbalanced word alignment without tailor-made designs.The paper proposes future extensions to improve phrase alignment and apply OT-based alignment to crosslingual alignment and text matching.Source: §9 · p. 9

Limitations

Using standard basic word embeddings limits phrasal alignment, whose F1 decreases as phrase alignment becomes more prevalent; richer span and structure-aware representations are proposed as future directions.

Limitations

  • Standard and basic word embeddings limit the capability of phrasal alignment.The limitation is part of the experimental design used to highlight differences among OT problems.Source: Limitations · p. 9
  • F1 decreases as the proportion of one-to-many, many-to-one, and many-to-many phrase alignments increases.Figure 5 evaluates supervised OT-based alignment after binning test samples by phrase alignment ratio.Source: Limitations · p. 10, Figure 5 · p. 10
  • Pre-trained span representations, improved phrase-composition methods, and structure- or order-aware OT are identified as routes to improve phrase alignment.These directions are presented as future work rather than evaluated solutions in this section.Source: Limitations · p. 10

B.1 Effects of Cost Function and Measures

Unsupervised alignment favors cosine distance, while measure sensitivity depends on the OT formulation; supervised UOT benefits from learned L2-based fertility modeling.

B.1 Effects of Cost Function and Measures

  • Cosine distance consistently outperforms Euclidean distance in naive unsupervised alignment baselines.The comparison uses word embeddings as naive semantic-similarity estimates.Source: §B.1 · p. 14, Table 4 · p. 15
  • Unregularised BOT and POT favor cosine distance and perform better with uniform distributions than L2-norm measures.Regularised BOT is especially sensitive to the choice of measure.Source: §B.1 · p. 14
  • UOT and regularised POT are less sensitive to measure choice because their internal mechanisms allow null alignment.This contrasts with the stronger measure sensitivity of unregularised BOT, POT, and especially regularised BOT.Source: §B.1 · p. 14
  • In supervised alignment, UOT significantly improves over the unsupervised setting and outperforms POT while preferring L2-norms for fertility modeling.The paper conjectures that BERT with linear metric learning adapts embedding norms to represent word fertility.Source: §B.1 · p. 14, Table 7 · p. 18

Related papers

Loading 2306.04116v1…