# CharacTER : Translation Edit Rate on Character Level 論文導讀
### 先備知識
#### 萊文斯坦距離 Levenshtein distance
**萊文斯坦距離**是一種量化兩字串間差異的演算法，代表從一個字串轉換為另一個字串最少需要多少次編輯操作，這種量化字間差異指標的演算法通稱**編輯距離(Edit distance)**。
萊文斯坦距離允許三種編輯方式：插入、刪除、置換
每一種編輯的距離都是1，因此舉例sitting跟kitten：
1. $sitting \rightarrow kitting$ 置換 $s \rightarrow k$
2. $kitting \rightarrow kitteng$ 置換 $i \rightarrow e$
3. $kitteng \rightarrow kitten$ 刪除 $g$

因此可知兩字間的編輯距離為 $3$。

Reference: [Wikipedia](https://en.wikipedia.org/wiki/Levenshtein_distance)
#### TER -- Translation Edit Rate
TER是考慮機器翻譯品質的方法，顧名思義，是計算翻譯結果Edit次數來評分翻譯品質，亦即：

$TER = \large{\#\,of\,edit \over average\,\#\,of\,reference\,words}$

- 分子是hypothesis調整至最接近的reference所需要的**編輯次數(cost)**，編輯動作包含：**插入、刪除、替代和字的平移，其中也包含標點符號以及大小寫。**
- 分母則是references的平均長度。

可以看出TER的方法是參考自萊文斯坦距離，但多考慮了字的平移操作。平移**連續**的字，不管平移幾格或總共幾個字的cost都是一樣的，在實作上需要注意的是最佳化字的平移這件事本身是**NP-complete**(Shapira and Storer, 2002)，所以TER在運算最佳化平移次數時是使用Greedy Algorithm 和 Dynamic Programming來近似。

#### TER sample python code:

CLASStorchmetrics.TranslationEditRate(normalize=False, no_punctuation=False, lowercase=True, asian_support=False, return_sentence_level_score=False, **kwargs)

preds = ['the cat is on the mat']
target = [['there is a cat on the mat', 'a cat is on the mat']]
ter = TranslationEditRate()
ter(preds, target)
#tensor(0.1538)

Reference: [A Study of Translation Edit Rate with Targeted Human Annotation](https://www.cs.umd.edu/~snover/pub/amta06/ter_amta.pdf), [TorchMetrics](https://torchmetrics.readthedocs.io/en/stable/text/translation_edit_rate.html)

### Translation Edit Rate on Character Level
廢話不多說，先上公式：
$\small CharacTER = \large{shift\,cost\,+\,edit\,distance \over \#\,characters\,in \,the\,hypothesis\,sentence}$

Translation Edit Rate on Character Level，顧名思義，CharacTER考慮的是字元(Character)層級的TER，但考慮到字母種類(alhpabet)在語言中的是非常有限的(ex:English 26)，因此若做單純的字母TER，字元比起字(words)更容易match，並在平移操作中使字污染而變成無意義的字，除此之外，words層級的TER若找到match的字，會繼續往後遍歷(traverse)直到找到最長的match字串，但字元層級的TER，因為字元彼此match的機率很高，因此會需要重複做traverse，使計算時間大幅度提升。

處理字串比對的演算法Rabin-Karp和KMP分別有average $O(n)$和worst case$O(n)$的Time Complexity，但都需要固定的pattern，因為TER的處理需要不斷更新pattern，因此不管以hash處理字串的Rabin-Karp還是以prefix和postfix處理文字的KMP都沒辦法在TER達成linear time的時間複雜度(應該需要$O(n^2)$)，所以簡單推算，若一個文章中的平均字長是$6$(採用ChrF的假設)，那需要的運算時間將會增加$6^2=36$倍(與文中作者比較TER和Character Error Rate在example sentence的運算時間相差$44$倍相近)。

因此CharacTER決定，先使用TER的**字平移規則**處理hypothesis，再將平移後的hypothesis sequence拆解成character(會考慮字間空格)並計算**萊文斯坦距離**。
這種處理方法僅會使運算時間增加10%。
#### 再來就是重頭戲了，在CharacTER中，兩個字(words)在符合這兩種情況下，會被判斷成匹配(matched)：
- **當兩個字一樣時**
- **當兩個字的編輯距離在一定的Threshold之下時**

例如，establish和established在absolute edit distance=2時會被判斷成匹配。因此，適當設定threshold可以提升CharacTER與人工ranking的correlation。

此外，因為字元level的刪除跟插入的cost增加很快，因此若採用TER對平移的***不管平移幾格或總共幾個字的cost都是一樣*** 的設定，penalty會太低，因此CharacTER採用字串中字的平均字長當作cost。
假設平移字串是: **the day before yesterday**
那平移它所需要的cost就會是 ${3+3+6+9\over4}=5.25$

CharacTER也測試了各種標準化的方法，若採用原本將reference長度作為分母的方式，會使的相同編輯距離的兩個不同長度的翻譯有一樣的TER，再經過比對後，文章發現採用hypotheses的字串長度比reference的字串長度更能反應不同翻譯的差異性和提升correlation，因此CharacTER決定採用hypotheses的字元長度作為分母。

#### 整理以上內容，總結CharacTER的評分方式：
- **使用TER的shift方式先最佳化平移句子，平移時的penalty考慮字串的平均字長**
- **拆解shift後的sequence並使用萊文斯坦距離計算編輯距離**
- **設定以編輯距離為Threshold作為判斷字異同的標準，文章實驗以WMT13/14作為資料時，Threshold設定為absolute edit distance=1有最好的correlation**
- **Normalization考慮評分需能反應不同翻譯句子長度，因此採用hypotheses的字元長度作為分母**

Reference: [Translation Edit Rate on Character Level](https://aclanthology.org/W16-2342.pdf), [CharacTER-Github](https://github.com/rwth-i6/CharacTER)