編譯環境
Dev-C++ 5.6.3
Language model implementation
實作語言處理模型，要求讀入一連串的英文語句做為基底，接著詢問一句的正確性為多少，也就是這句話是正確拼讀的機率為何，算是一個可用的句子嗎？
$$P(w_{i}) = \frac{Count(w_{i})}{\sum_{j} Count(w_{j})} \\ P(w_{i}, w_{i+1}) = \frac{Count(w_{i}, w_{i+1})}{\sum_{j} Count(w_{j}, w_{j+1})} \\ P(w_{i+1}|w_{i}) = \frac{P(w_{i}, w_{i+1})}{P(w_{i})}$$上述分別是一個單詞的機率，以及計算相鄰兩個單詞的機率，最後推估在這個單詞下，它們相鄰的機率。請查閱 貝氏定理 。
$P(s) = P(w_{0}) \times P(w_{1}|w_{0}) \times ... \times P(w_{n-1}|w_{n-2})$
- P(A)是A的先驗機率或邊緣機率。之所以稱為”先驗”是因為它不考慮任何B方面的因素。
- P(A|B)是已知B發生後A的條件機率，也由於得自B的取值而被稱作A的後驗機率。
- P(B|A)是已知A發生後B的條件機率，也由於得自A的取值而被稱作B的後驗機率。
- P(B)是B的先驗機率或邊緣機率，也作標准化常量（normalizing constant）.
上述為一個句子的機率，一個句子可以表示成一個序列單詞，利用連乘積將機率算出。當句子越常時，很容易發現機率陡降的速度相當快，就算是數個字詞，機率大約也是在$10^{-3}$ 左右。因此這麼算下去，長句子的正確性就會大幅減少，但是在邏輯上，如果句子都是短短幾個單詞也是相當奇怪的，口語上也許是，文章判讀上就難說。至於要不要取$\sqrt[n]{x}$ 值得思考。
$$\begin{cases} Count^{*}(w_{i}) = (Count(w_{i})+1) \times \frac{N_{Count(w_{i})+1}}{N_{Count(w_{i})}} & \text{ if } Count(w_{i}) < k \\ Count^{*}(w_{i}) = Count(w_{i}) & \text{ if } Count(w_{i}) \geq k \end{cases} \\ \text{unigram } N_{0} = 80000$$當我們去計算一個單詞的機率時，必須相對於其他單詞的出現機率，然而像介係詞、助詞等，出現次數是相對高出取多，必須取一個閥值，來忽略過高無用的機率，以免將其他的單詞的機率過低不均。
$$\begin{cases} Count^{*}(w_{i}, w_{i+1}) = (Count(w_{i}, w_{i+1})+1) \times \frac{N_{Count(w_{i}, w_{i+1})+1}}{N_{Count(w_{i}, w_{i+1})}} & \text{ if } Count(w_{i}, w_{i+1}) < k \\ Count^{*}(w_{i}, w_{i+1}) = Count(w_{i}, w_{i+1}) & \text{ if } Count(w_{i}, w_{i+1}) \geq k \end{cases} \\ \text{bigram } N_{0} = 80000 \times 80000$$在計算相鄰兩個單詞的出現次數時，一樣會遇到這種情況。既然在計算次數上需要做 smoothing 的調整，在機率處理上也是一樣動作。
$$\begin{cases} P(w_{i}) = \frac{N_{1}}{N} & \text{ if } Count(w_{i}) = 0 \\ P(w_{i}) = \frac{Count^{*}(w_{i})}{N} & \text{ if } Count(w_{i}) < K \\ P(w_{i}) = \frac{Count(w_{i})}{N} & \text{ if } Count(w_{i}) \geq K \end{cases}$$ $$\begin{cases} P(w_{i}, w_{i+1}) = \frac{Count^{*}(w_{i}, w_{i+1})}{N} & \text{ if } Count(w_{i}, w_{i+1}) < K \\ P(w_{i}, w_{i+1}) = \frac{Count(w_{i}, w_{i+1})}{N} & \text{ if } Count(w_{i}, w_{i+1}) \geq K \end{cases}$$在單詞出現次數很少時，就必須使用 smoothing，因為出現 1 次、2 次、3 次 … 的單詞次數，之間大小關係不保證嚴格遞增或遞減，
實作細節
- 公式都已經給定，基本上麻煩就是在於資料紀錄而已，其他就照著流程跑。
- 雖然沒有規定語言，以下代碼在 Dev-C++ 下編過，別問 VS 到底行不行。
原則上，讀檔案，建立模型可以在 1.4 秒內完成
|
|
測試輸入
|
|
測式輸出
考量長句子的機率，採用 log 平均結果，輸出應該為負值。
|
|
原始版本，直接輸出 P(s)，這裡採用科學記號表示法。
|
|
結語
有 STL library，代碼不用太長，跑得時間也不會太久。想到插手別學校的自然語言處理，玩了一下他們作業，把同學的代碼效率修得好一點，其實也不錯玩得，只是在公式計算上比較沒有，但是要求高效率的搜索結構，讀檔案進來後，依據什麼建表、該用什麼順序完成是很重要的。
切記，在寫這種程式時，發現跑的速度太久，一部分是因為使用太多的標準輸出，也就是用太多 printf()、cout << 或 System.out.println() 之類的在進行流程監控。輸出的效率必須將檔案寫到螢幕顯示的 memory buffer，因此 context-switch 什麼，消耗時間太大，盡可能不要輸出，要不然就是按比例輸出，速度可以快個數百倍。
|
|
