Python의 고정밀 워드 정렬 알고리즘

Python의 고정밀 워드 정렬 알고리즘

저는 번역 품질을 측정하기 위해 문장과 다른 언어의 번역 사이에 고정밀 단어 정렬을 구축하는 프로젝트를 진행하고 있습니다. 나는 Giza++와 통계 기계 번역 파이프라인의 일부로 사용되는 다른 단어 정렬 도구에 대해 알고 있지만, 이것은 내가 찾고 있는 것이 아니다. 나는 다음과 같은 제한 사항을 고려하여 소스 문장의 단어를 대상 문장의 해당 단어에 투명하고 정확하게 매핑할 수 있는 알고리즘을 찾고 있다:

• 두 언어는 같은 어순을 가지고 있지 않고, 그 어순은 계속 바뀐다
• 원본 문장의 일부 단어는 대상 문장에 해당하는 단어를 포함하지 않으며, 반대의 경우도 마찬가지입니다
• 때때로 소스의 단어는 대상의 여러 단어에 해당하고, 그 반대도 마찬가지이며, 다대다 매핑이 있을 수 있습니다
• 같은 단어가 문장에서 여러 번 사용되는 문장이 있을 수 있으므로 단어뿐만 아니라 단어와 색인으로 정렬해야 합니다

제가 한 일은 다음과 같습니다:

• 영어-독일어와 같이 문장 쌍의 목록으로 시작하고, 각 문장은 단어로 토큰화된다
• 각 문장의 모든 단어를 색인화하고 각 단어(예: 5, 16, 19, 26 등의 문장에서 발생한 단어 "world")에 대해 역색인을 만듭니다
• 이제 이 역색인은 소스 단어와 대상 단어 사이의 상관관계를 예측할 수 있습니다. 두 단어 사이의 교차점을 결합으로 나눈 값입니다. 예를 들어, 태그어 "Welt"가 문장 5, 16, 26, 32에서 발생하는 경우, (월드, Welt) 사이의 상관관계는 교차로(3)의 인덱스 수를 유니언(5)의 인덱스 수로 나눈 값이므로 상관관계는 0.6이다. 유니언을 사용하면 "the"와 같은 높은 빈도의 단어와 다른 언어의 해당 단어와의 상관관계가 낮아집니다
• 모든 문장 쌍에 대해 다시 반복하고, 주어진 문장 쌍에 대한 소스 및 대상 단어에 대한 인덱스를 사용하여 상관 행렬을 만듭니다

여기에 영어와 독일어 문장 사이의 상관 행렬의 예가 있다. 우리는 위에서 논의된 과제를 볼 수 있다.

이미지에는 영어와 독일어 문장 간의 정렬 예가 있어 단어 간의 상관관계를 보여주며, 녹색 셀은 단어 정렬 알고리즘으로 식별해야 하는 올바른 정렬 지점이다.

다음은 제가 시도한 것 중 일부입니다:

• 어떤 경우에는 의도된 정렬이 단순히 각 열과 행에서 가장 높은 상관 관계를 가진 단어 쌍일 수 있지만, 많은 경우에는 그렇지 않습니다.
• 정렬점을 연결하는 경로를 그리기 위해 데이크스트라 알고리즘과 같은 것을 시도해봤지만, 어순 때문에 문장에서 앞의 단어로 앞뒤로 점프할 수 있는 것 같고, 정렬이 되지 않은 단어를 건너뛸 수 있는 합리적인 방법이 없기 때문에 이런 식으로 작동하지 않는 것 같다.
• 최적의 솔루션은 가장 가능성이 높은 대응에서 시작하여 다대다 대응으로 확장하고 정렬되지 않은 단어를 건너뛰는 직사각형을 확장하는 것과 같은 것을 포함할 것이라고 생각하지만, 이것을 구현하는 좋은 방법이 무엇인지 정확히 확신할 수 없습니다

사용 중인 코드는 다음과 같습니다:

import random
src_words=["I","know","this"]
trg_words=["Ich","kenne","das"]
def match_indexes(word1,word2):
    return random.random() #adjust this to get the actual correlation value

all_pairs_vals=[] #list for all the source (src) and taget (trg) indexes and the corresponding correlation values
for i in range(len(src_words)): #iterate over src  indexes
    src_word=src_words[i] #identify the correponding src word
    for j in range(len(trg_words)): #iterate over trg indexes
        trg_word=trg_words[j] #identify the correponding trg word
        val=match_indexes(src_word,trg_word) #get the matching value from the inverted indexes of     each word (or from the data provided in the speadsheet)
        all_pairs_vals.append((i,j,val)) #add the sentence indexes for scr and trg, and the corresponding val

all_pairs_vals.sort(key=lambda x:-x[-1])  #sort the list in descending order, to get the pairs with the highest correlation first
selected_alignments=[]
used_i,used_j=[],[] #exclude the used rows and column indexes
for i0,j0,val0 in all_pairs_vals:
    if i0 in used_i: continue #if the current column index i0 has been used before, exclude current pair-value
    if j0 in used_j: continue #same if the current row was used before
    selected_alignments.append((i0,j0)) #otherwise, add the current pair to the final alignment point selection
    used_i.append(i0) #and include it in the used row and column indexes so that it will not be used again
    used_j.append(j0)

for a in all_pairs_vals: #list all pairs and indicate which ones were selected
    i0,j0,val0=a
    if (i0,j0) in selected_alignments: print(a, "<<<<")
    else: print(a)

다대다 또는 1대다 정렬을 수용하지 않으며, 이후 선택에서 행과 열을 제외하고 상관 관계가 가장 높은 잘못된 쌍을 선택하여 초기에 쉽게 오류가 발생할 수 있기 때문에 문제가 됩니다. 좋은 알고리즘은 특정 쌍이 각 행/열에서 가장 높은 상관관계를 갖는다는 점을 고려하지만, 높은 상관관계를 갖는 다른 쌍과의 근접성도 고려할 것이다.

다음은 Google 시트에 있는 몇 가지 데이터입니다:

---

단어 정렬은 어느 정도 열린 연구 주제로 남아 있다. Giza++ 뒤에 있는 확률론적 모델들은 꽤 사소하지 않다:

다음과 같은 기존 접근 방식을 많이 사용할 수 있습니다:

• Giza++에서 사용하는 "IBM 모델"을 직접 구현하십시오(또는 용감하다면 NLTK 구현을 시도하십시오)
• 뒤에서 (거의 훨씬 간단한) 알고리즘을 실행하다
• 어떤 형태로든 HMM 기반 정렬을 구현하다
• 딥 러닝을 사용하면 여러 가능성이 있다. 이 논문은 접근법에 대한 멋진 개요를 포함하는 것 같다(일반적으로 사람들은 이를 위해 신경 MT 모델의 주의 메커니즘을 활용하려고 한다)

이것은 매우 어려운 기계 학습 문제이며 당신의 것과 같은 간단한 접근법이 작동할 수 있는 것이 불가능하지는 않지만, 먼저 기존의 작업을 연구하는 것이 좋은 생각일 수 있다. 그렇긴 하지만, 우리는 이 분야에서 놀랍도록 간단한 기술에서 꽤 많은 돌파구를 보았기 때문에 누가 알겠는가:-

---

최근에는 단어 정렬을 위해 이중/다국어 단어/컨텍스트 임베딩을 사용하는 두 개의 논문도 있었다. 둘 다 단어가 포함 거리에 가중치를 부여하는 이분 그래프를 구성하고 그래프 알고리듬을 사용하여 정렬을 얻는다.

그래프 부분 간에 최대 일치를 수행합니다. 매칭이 대칭적이지 않기 때문에 양쪽에서 매칭을 수행하고 FastAlign과 유사한 대칭 휴리스틱을 사용합니다.

선형에 대해 설명합니다. 그래프에서 최소 가중치 에지 피복만 잠시 사용하고 선형으로 사용합니다.

둘 다 FastAlign보다 낫다고 주장합니다.

---

나는 테스트를 강력히 추천한다. 그것은 다국어 BERT(mBERT)에 의존하며 결과는 매우 유망해 보인다. 아랍어로 테스트까지 해봤는데, 아랍어는 형태학이 풍부한 언어이기 때문에 어려운 정렬 예를 훌륭하게 소화했고, 독일어와 같은 라틴어 기반 언어보다 더 어려울 것으로 생각합니다.

As you can see, one word in Arabic corresponds to multiple words in English, and yet Awesome-Align managed to handle the many-to-many mapping to a great extent. You may give it a try and I believe it will meet your needs.

There is also a Google Colab demo at https://colab.research.google.com/drive/1205ubqebM0OsZa1nRgbGJBtitgHqIVv6?usp=sharing#scrollTo=smW6s5JJflCN

Good luck!

---

As the question is specifically addressing Python implementations, and Giza++ and FastAlign still seem to represent SOTA, one might look into

• https://pypi.org/project/systran-align/: replicates FastAlign. Seems to be relatively mature. Also note that the original FastAlign code contains a Python wrapper (https://github.com/clab/fast_align/blob/master/src/force_align.py).

• https://www.nltk.org/api/nltk.align.html: replicates most GIZA models (a good compromise between performance and quality is IBM4). However, it is rather unclear how thoroughly tested and how well maintained that is, as people generally prefer to work with GIZA++ directly.

Most research code on the topic will nowadays come in Python and be based on embeddings, e.g., https://github.com/cisnlp/simalign, https://github.com/neulab/awesome-align, etc. However, the jury is still out on whether they outperform the older models and if so, for which applications. In the end, you need to go for a compromise between context awareness (reordering!), precision, recall and runtime. Neural models have great potential on being more context aware, statistical models have more predictable behavior.

---

You can also try simalign

The best result I have obtained so far is by consolidating the alignments of the different methods provided in simalign.

This is the only way I got perfect results on the example below. Both awsome-align and individual methods of simalign failed. Obviously one example is not enough to conclude, but I thought I'd share the idea.

def readable(alignments, src_sentence, trg_sentence):
    readable_alignments = []
    for method in alignments:
        readable_alignment = []
        for src_idx, trg_idx in alignments[method]:
            readable_alignment.append((src_sentence[src_idx], trg_sentence[trg_idx]))
        readable_alignments.append(readable_alignment)
    return readable_alignments


from collections import defaultdict

def consolidate(lists): # This code was generated by GPT4
    # Step 1: Initialize the dictionary
    pair_freq_confidence = defaultdict(lambda: {'freq': 0, 'confidence': 0})

    # Step 2: Iterate through lists and update the frequency and confidence score
    for idx, pairs in enumerate(lists):
        for src, tgt in pairs:
            pair_freq_confidence[(src, tgt)]['freq'] += 1
            pair_freq_confidence[(src, tgt)]['confidence'] += 1 / (idx + 1)  # Assume confidence decreases with list index

    # Step 3: Normalize the confidence scores
    total_confidence = defaultdict(float)
    for (src, tgt), data in pair_freq_confidence.items():
        if total_confidence[src] != 0:
            data['confidence'] /= total_confidence[src]

    # Step 4: Choose the target word with the highest normalized confidence score for each source word
    selected_pairs = {}
    for (src, tgt), data in pair_freq_confidence.items():
        if src not in selected_pairs or data['confidence'] > selected_pairs[src]['confidence']:
            selected_pairs[src] = {'tgt': tgt, 'confidence': data['confidence']}

    # Step 5: Resolve conflicts where different source words are paired with the same target word
    unique_pairs = {}
    used_tgt_words = set()
    for src, data in selected_pairs.items():
        tgt = data['tgt']
        if tgt in used_tgt_words:
            conflicting_src = [e for e, d in unique_pairs.items() if d['tgt'] == tgt][0]
            if data['confidence'] > unique_pairs[conflicting_src]['confidence']:
                del unique_pairs[conflicting_src]
                used_tgt_words.remove(tgt)
                unique_pairs[src] = data
                used_tgt_words.add(tgt)
        else:
            unique_pairs[src] = data
            used_tgt_words.add(tgt)

    return [(eng, data['tgt']) for eng, data in unique_pairs.items()]


from simalign import SentenceAligner

def compute_and_display_alignments(src_text, tgt_text, model="bert", token_type="bpe", matching_methods="maifr"):
    myaligner = SentenceAligner(model=model, token_type=token_type, matching_methods=matching_methods)
    alignments = myaligner.get_word_aligns(src_text, tgt_text)
    alignment_attempts = readable(alignments, src_text, tgt_text)
    for attempt in alignment_attempts:
        print(attempt)
    print('Consolidated :')
    print(consolidate(alignment_attempts))

english_sentence = "Autonomous cars shift insurance liability toward manufacturers".split(' ')
korean_sentence = "자율주행 자동차는 보험 책임을 제조업체 쪽으로 이동시킨다".split(' ')
compute_and_display_alignments(english_sentence, korean_sentence)