User Tools


This is an old revision of the document!


Slide 1 :public:bg19.jpg

Joint Approaches for Sentence Alignment on Multiparallel Texts

Johannes Graën
2016-11-29

↓ Slide 2

Overview

  • Sentence Alignment on Multiparallel Texts
  • Approaches
    • Agreement of Bilingual Alignments
    • Sampling in Discrete Vector Space
    • Agglomerative Hierarchical Clustering
  • Outlook
    • Evaluation Metrics
    • Hierarchical Clustering for Word Alignment
→ Slide 3

Sentence Alignment on Multiparallel Texts

  • Like sentence alignment of two languages.
  • There may be alignments that only exists on a subset of languages.
    • This leads to hierarchical alignments.
↓ Slide 4

Example

de 1+3 Es geht nicht um die Großzügigkeit des Präsidenten, es geht um die Zeit, die Sie sich selbst genehmigen;
2+3 ich habe Ihnen angezeigt, wann die Minute abgelaufen war.
en 3 Mr Izquierdo Collado, it is not a question of the President’s generosity.
It is a question of the time you allow yourself, because I informed you when your minute was up.
fr 1+3 Monsieur Izquierdo, il ne s’agit pas de la générosité du président, il s’agit du temps que vous vous attribuez.
2+3 Je vous ai fait signe quand vous avez atteint la minute.
→ Slide 5

Agreement of Bilingual Alignments

  • Perform sentence alignment on all language pairs.
  • Derive correct alignments by “voting”.
    • Hypothesis: The majority of pairwise alignments is correct in most cases, i.e. anya alignment error is due to the properties of its particular language pair.
↓ Slide 6

Approach

  1. Perform pairwise alignments with hunalign.
  2. Join all these alignments in a graph.
  3. Calculate “connectedness” by counting supporting languages for each edge.
    • How many languages align with both sentences of a particular language pair?
  4. Continue deleting the least supported edge until small consistent clusters emerge.
  5. An alignment hierarchy can be obtained by reversing the deletion process.
↓ Slide 7

Two Languages

↓ Slide 8

Three Languages

↓ Slide 9

Four Languages

↓ Slide 10

Five Languages

↓ Slide 11

Hierarchical Alignments

↓ Slide 12

Problems/Limitations

  • Short sentences in 1:n pairs do not align in any language.
    • … and we are merely removing (wrong) alignments.
  • Decisions not straightforward if more than one pair disagrees.
    • hunalign's alignment score does not help taking the right decision.
  • Dictionaries for hunalign only allow binary entries.
→ Slide 13

Sampling in Discrete Vector Space

  • Discrete vector space spanned by languages as dimensions.
  • Alignments are pairs of location and direction vectors with all positive components.
    • E.g. $\left((1,2)^T,(2,1)^T\right)$ defines the alignment of the second and third sentence of the first language with the third sentence of the second language.
  • The location vector of the nth alignment equals the sum of the direction vector 1..n-1.
  • Alignment is obtained by simulated annealing.
↓ Slide 14

Visual Representation

↓ Slide 15

Approach

  1. Set initial aligment to a sequence of vectors approximating a diagonal line.
  2. Calculate local (pairwise) and global alignment scores (and keep results in memory).
  3. Find and evaluate all applicable sampling operations.
  4. Sample by selecting one of those operations – according to their respective evaluation scores.
  5. Lower temperature, i.e. probability of picking an operation that leads to a worse sample.
  6. Repeat from (3) until temperature reaches zero-point.
↓ Slide 16

Sampling Operations

  1. Changing two consecutive vectors $\vec{x}$ and $\vec{y}$ such that $\vec{x}^\prime + \vec{y}^\prime = \vec{x} + \vec{y}$.
  2. Replace two consecutive vectors $\vec{x}$ and $\vec{y}$ by vector $\vec{z}$ such that $\vec{z} = \vec{x} + \vec{y}$.
  3. Split a vector $\vec{z}$ into vectors $\vec{x}$ and $\vec{y}$ such that $\vec{x} + \vec{y} = \vec{z}$.
↓ Slide 17

Problems/Limitations

  • The sampling often does not converge.
  • For higher dimensions (more languages), sampling did not inlcude the correct (gold) alignment.
  • Finding and evaluation all applicable operations is expensive, even if scores are only calculated on language pairs.
→ Slide 18

Agglomerative Hierarchical Clustering

→ Slide 19

Evaluation Metrics

→ Slide 20

Hierarchical Clustering for Word Alignment

Slide 21 :public:bg23.jpg

CL Wiki

Institute of Computational Linguistics – University of Zurich