"Doubting" Augustinus

Bigram based dynamic programming algorithm for Chinese word segmentation [en]

2008-10-13T06:18:00.001-07:00

Scan all characters left-to-right, to calculate the score of current position "i" as a word boundary by accumulating the previous best choice.

Scoring function:


    For all j = i -1 to 0
        pre_best = argmax{ score(0, j) + logprob(j, i) }

The logprob(j, i) means the log probability that C[j+1…i] form a word, C stands for a character sequence, and this probability should consider bigram to match the requirement.

Initialization:


    score[0,0] = 0

"Sub-optimal" characteristic of dynamic programming:


    score(0, i) =
        score(0, pre_best) + logprob(pre_best, i)

After all calculations, just go back-tracking to pick the best choices up to form the segmented string.

Here is an example that based on SIGHAN word segmentation bakeoff corpus' word counts only. It is not the standard form of language model,
but generally it is easy to modify to use smoothed (in Good-Turing or Chen-Goodman modified KN discounting or other scheme) log probabilities.
To simulate the behavior "Katz's back-off" of real language model, this example includes a *fake* factor to boost bigram probabilities.

question: 混合型演算法 (C1, C2, C3, C4, C5, C6)

混 10
合 20
型 20
演 15
算 60
法 80

混合 35
演算 80
算法 9
混合型 6
演算法 160

演算:法 1
混合型:演算法 5

Notations:

a(x, y) stands for accumulative scores of previous segmentations.

d(x, y) stands for known word counts of current positions.


i=1:
    a(0, 0) + d(0, 1) = 0 + 10 = 10

    argmax{...}=C1
    a(0, 1) = 10

i=2:
    a(0, 1) + d(1, 2) = 10 + 20 = 30
    a(0, 0) + d(0, 2) = 0 + 35 = 35

    argmax{...}=C12
    a(0, 2) = 35

i=3:
    a(0, 2) + d(2, 3) = 35 + 20 = 55
    a(0, 0) + d(0, 3) = 0 + 6 = 6

    argmax{...}=C3
    a(0, 3) = 55

i=4:
    a(0, 3) + d(3, 4) = 55 + 15 = 70

    argmax{...}=C4
    a(0, 4) = 70

i=5:
    a(0, 4) + d(4, 5) = 70 + 60 = 130
    a(0, 3) + d(3, 5) = 70 + 80 = 150

    argmax{...}=C45
    a(0, 5) = 150

i=6:
    a(0, 5) + d(5, 6) = 150 + 80 + 1 * (factor of bigram)
                      = 230 + (fob)
    a(0, 4) + d(4, 6) = 70 + 9 = 79
    a(0, 3) + d(3, 6) = 55 + 160 + 5 * (factor of bigram)
                      = 220 + 5(fob)

    [let fob > 2]
    argmax{...}=C456
    a(0, 6) = 220 + 5(fob)

backtrack: C456 -> C3 -> C12

answer: 混合 型 演算法

Vi-Vi-Vi-Viterbi

2008-10-13T06:04:00.001-07:00

大師的姓可不能念錯。

Prof. Andrew Viterbi，猶太裔，出生於義大利。藉由這些線索，我猜發音規則應以拉丁語而非以英語為準。但，數年來，都只是猜測。

（英語發音慣例是，名詞的重音在第一個音節，動詞則在第二個音節，"record" 就是絕佳的例子；然而，拉丁語系的語言則通常一律把重音擺在第二音節之後，所以有不少該語系的人分不出 "record" 念法的差別。）

今天窮極無聊，終於在某影片中找到肯定的答案了：

Andrew & Erna Viterbi: The Journey and the Legacy

當然，把 Viterbi algorithm 融會貫通，才是更重要的事：所有和 Markov chain 及 Shannon noisy channel model 相關的 machine learning 演算法都會用到：n-gram language model, Hidden Markov Model, Maximum Entropy, Conditional Random Field, etc.

附帶一提，義大利有個城市叫 Viterbo，也可作為姓氏，同樣應該將重音擺在第二音節。

Viterbi algorithm

2008-10-13T06:02:00.000-07:00

還沒有時間詳細寫下輸入法相關的範例，就先列出我覺得最好的參考資料湊合著用。

里茲 (Leeds) 大學的 Viterbi Algorithm 教學頁

看這一頁之前，最好先看看前頭講 Forward Algorithm 的部分。若是對 Hidden Markov Model (HMM) 不熟，請先看看 HMM 不負責講座系列。

如果沒耐心看完文字敘述，可以先跳到 Forward Algorithm example 和 Viterbi Algorithm example，透過動畫步驟演示來比較箇中差異。

最容易懂也和輸入法最相關的分析，則在 Speech and Language Processing 一書中第五章的 Weighted Automata 與第七章的 The Viterbi Algorithms Revisited。

Wikipedia 上的 Viterbi Algorithm 寫得太亂，而且竟然偷懶把 Forward Algorithm 合併至該頁，恐怕只會讓人愈看愈模糊，故不推薦。

Bi-gram 中文應用範例：Language model 的授權問題（續）

2008-10-13T06:01:00.001-07:00

從中文維基百科的語料產出 language model，還有點「時間管理」問題，再等等......

既然要等，就連這個一起：All Our N-gram are Belong to You

We processed 1,011,582,453,213 words of running text and are publishing the counts for all 1,146,580,664 five-word sequences that appear at least 40 times. There are 13,653,070 unique words, after discarding words that appear less than 200 times.
Watch for an announcement at the LDC, who will be distributing it soon, and then order your set of 6 DVDs.

Well, resources at the LDC are usually NOT FREE.

Bi-gram 中文應用範例： Maximum Likelihood Estimation 演算法流程圖

2008-10-13T06:00:00.003-07:00

這流程圖就是虛擬碼的視覺化呈現，或許有助於理解。
圖中 "Permute candidate" 那段，若應用於音節或鍵碼序列轉換為字詞，就是把所有同音詞或同碼詞的排列產生出來；如果是斷詞，則不必做任何事。
以菱形表示的條件判斷式的數量，與緊接著要進行什麼處理，都會隨著 n-gram 的 n 等於多少而有所不同，也就是目前作法最缺乏彈性的地方。

Bi-gram MLE Flow Chart

Hosted on Zooomr

Bi-gram 中文應用範例：虛擬碼與程式碼更新

2008-10-13T06:00:00.001-07:00

首先，又是虛擬碼的問題：前篇勘誤提到的那行，變數應為 temp_score 而非 best_score。

再來，順著虛擬碼的脈絡仔細看，不難發現 IF left > 0 AND left != prefix 這段，沒有相應的 ELSE 區塊。這是最初偷懶沒寫，因為使用 SRILM 產生出來的 language model 時有個小小把戲：用 <s> 代表句子開頭，</s> 代表句子結尾。於是，如果斷詞或音轉字之前，先在測試句前後標上這兩個符號，就讓頭尾的字詞也有了 bi-gram。例如，本來測試句是「下雨天留客」，在句首只能有「下」這個 uni-gram；但要是把測試句改成「<s>下雨天留客</s>」，便能將「<s> 下」這樣的 bi-gram 列入考慮了。等等，「<s>」就不用管它嗎？當然，因為這是人工附加的，無論該符號會獲得什麼樣的分數，反正最後都要拿掉。

但是，偷懶是不好的，而且程式這種東西，搞不好一轉頭就忘了偷懶的事實與理由。所以，無論是虛擬碼、實際釋出的 C# 與 C++ 程式碼，我都把對應的部分補回去了。

講到 if-else，原來的段落裡還有一個地方稍微特殊了些－－ ELSE IF Length(right_gram) == 1 －－算是基於「漢字」特性而寫的特例。翻成自然語言是「抑或右邊是個不認得的漢字」之類的意思。然而，對通用的 language model 來講，應該只是「認不認識」的區別而已。所以，這段 ELSE IF 就直接一般化成 ELSE 了。

最後，為了讓虛擬碼更簡潔些，在不同情況下重覆出現的動態規劃分數更新步驟，則已抽離為 Scoring 常式了。這名字其實不太對，抽象層次上，scoring function 還應包括不同條件下分數加總的行為，而不只是這個被抽離出來的分數更新步驟。不過算了。XD

Bi-gram 中文應用範例：虛擬碼勘誤

2008-10-13T05:59:00.001-07:00

嗚啊，真是非常抱歉，〈Bi-gram 中文應用範例：虛擬碼〉裡頭有一行錯了，而且是嚴重的錯誤：

~~best_score~~ temp_score += -LogProb(Unknown) + BackOff(right_gram);

應該要加上括號再取負值：

~~best_score~~ temp_score += -(LogProb(Unknown) + BackOff(right_gram));

說起來這有點蠢，加了負號讓自己都容易疏忽；特別是在選擇 best_score 時，用「大於」總是比「小於」要直觀。事實上，C++ 版的 WordSegmenter 裡就沒加負號。改寫成 C# 版時，基於平常寫動態規劃程式的習慣，為避免某些初值在進行比較時不合理，才故意把負的 log probability 都轉成正值。然而，我後來程式根本沒那樣寫，仍然沿用了在 log probability 為負值時所需的額外條件判斷來檢查初值： if(best_score == 0 || ... ) ，如此一來，加負號的意義便喪失了。雖然之前釋出的實際程式並未犯下與虛擬碼相同的錯誤，不過 C# 版中多此一舉的狀況，還是改一改好了。

真是腦筋不清楚不行啊！

更新：上文中畫上刪除線的 best_score 應為 temp_score，但敘述中提到的 best_score 仍是正確的。詳見〈Bi-gram 中文應用範例：虛擬碼與程式碼更新〉

Bi-gram 中文應用範例：Language model 的授權問題

2008-10-13T05:58:00.001-07:00

在〈Bi-gram 中文應用範例：以 C# 實作〉中所用到的 language models，礙於語料本身的授權問題，我要晚個一兩天才能放出來。

根據 SIGHAN 2005 Second International Chinese Word Segmentation Bakeoff: Detailed Instructions 的聲明，我們無法直接使用那些語料做其他用途：

Licensing

The corpora have been made available by the providers for the purposes of this competition only. By downloading the training and testing corpora, you agree that you will not use these corpora for any other purpose than as material for this competition. Petitions to use the data for any other purpose MUST be directed to the original providers of the data. Neither SIGHAN nor the ACL will assume any liability for a participant's misuse of the data.

因此，我可能會想辦法改用 Wikipedia 來產生 language models。

Bi-gram 中文應用範例：虛擬碼

2008-10-13T05:55:00.000-07:00

這是〈Bi-gram 中文應用範例：以 C# 實作〉的音節轉詞彙程式的虛擬碼：

Bi-gram Based Chinese Syllable-to-Word Conversion Algorithm Pseudo Codes Hosted on Zooomr

我在這裡排不出好看的效果，只好用圖片了。不過這樣倒是剛好可以讓人有個粗略印象，由程式排版中得知，那些巢狀迴圈有多麼討厭。

把虛擬碼中的 Homophones() 拆掉，留下 Substring()，再把相關的 FOR EACH 拿掉，就變成斷詞了。

而在 WordSegmenter 範例中，我動了一點手腳：temp_score += scores[prefix]; 被換成了 temp_score += LogProb(right_gram) + scores[prefix]; ，多加的 LogProb(right_gram) 會使得某些高頻字更容易被斷成單字詞。這麼做的原因是，在語料涵蓋率不夠高的情況下，我利用中文「自由詞素」的特性，來確保某些不常見的單字詞序列不會被左右常見的高頻詞搶走；反應在測試上，偶爾就會看到「是的」被斷成「是　的」。當然，這只是種基於實驗結果所耍的小把戲，不算是標準的 Maximum Likelihood Estimation。

更新：原圖中虛擬碼有一處重大錯誤，已更正，並請參閱〈Bi-gram 中文應用範例：虛擬碼勘誤〉，謝謝。

又更新：請參考〈Bi-gram 中文應用範例：程式碼與虛擬碼更新〉。

再次更新：〈Bi-gram 中文應用範例：Maximum Likelihoood Estimation 演算法流程圖〉或許有助於理解。

Bi-gram 中文應用範例：以 C# 實作

2008-10-13T05:53:00.000-07:00

能用 VS.NET 2003 或 2005 編譯的程式碼與方案檔，放在 OpenFoundry: SRILMWin32 的 SVN 裡。如果不喜歡 C# 而想要看看 C++ 版，目前僅有斷詞程式可供參考，放在 OpenVanilla 的實驗區：WordSegmenter。
~~上述程式碼位置，請改以 http://taipedia.selfip.info/mediawiki/index.php/ELUTE 記載的為準。~~基於我工作上潛在的 NDA，此專案已註銷。

這些程式用到了幾項外部資源：

用 SRILM 從 SIGHAN 2005 Chinese Word Segmentation Bakeoff 的語料中提煉出的 language models。
從 MediaWiki: includes/ZhConversion.php 裡擷取出來的簡繁詞彙對照表。
新酷音輸入法詞庫專案的 tsi.src。

首先是中文斷詞。演算法在 Bigram based dynamic programming algorithm for Chinese word segmentation [en] 這篇裡提過了。只要切換不同的 language model，就能支援簡體、繁體甚至混合的斷詞。

再來是簡繁轉換。其實，只要斷詞做完，簡繁轉換「幾乎」只是到對照表裡查詢再代換之即可，幾乎，是的。由於簡繁詞彙之間的對應其實是一對多關係，轉換結果並不唯一，因此這個程式還可以寫得更複雜一點——更像輸入法。

而智慧型輸入法，就可視為音節或鍵碼序列轉換成詞彙的過程。目前本篇所提到的範例，與大多數輸入法產品類似的是，僅在斷詞過程中將同音或同碼詞於迴圈中展開，也就是仍然只考慮詞彙相鄰關係，而未考慮音節或鍵碼序列的 bi-grams，與音節或鍵碼序列轉換為某詞彙的機率或排名。這方面的說明，請參考我在 Google Groups: Chewing IM Development 上針對〈音找字 vs. 音找詞〉所作的回應。

除了上述問題應進一步加強之外，本範例在演算法實作上仍有改善空間：現在直接以巢狀迴圈實作的方式，若想要從 bi-gram 推廣到 n-gram，顯然相當麻煩。因此，如何更有彈性地使用資料結構並實作動態規劃演算法，將是下一個課題。

另外，若想要有個從詞彙反轉回音節或鍵碼序列的程式，把簡繁轉換程式裡的對照表換成音節或鍵碼序列與詞彙的對照表即可。現成的表格整理在這裡：〈OpenVanilla: ChineseInformationProcessing: 輸入法表格〉。

範例程式核心演算法的虛擬碼，以及各個 language model 檔案，明天我整理好會放出來。