式4

現(xiàn)在，我們使用Kernighan et al. (1990）的語料庫來進(jìn)行計(jì)算，這是AP新聞?wù)Z料庫（1988），規(guī)模為4400萬詞。所以，N為4400萬。在這個(gè)語料庫中，單詞actress出現(xiàn)了1343次，單詞acres出現(xiàn)了2879次，等等。我們計(jì)算得到如下的先驗(yàn)概率：

式5

其中，c表示候選更正單詞，freq(c)表示c的出現(xiàn)次數(shù)（頻度），p(c)表示c的概率。

似然度（p（t l c））的精確計(jì)算至今還是一個(gè)沒有解決的（或不可解決的）研究題目；一個(gè)單詞被錯(cuò)誤拼寫的精確概率與打字者是誰、打字者是否熟悉他所用的鍵盤、打字者的一只手是否比另一只手更疲倦等因素都有關(guān)系。幸運(yùn)的是，盡管我們不能精確地計(jì)算p(t | c)，但是可以相當(dāng)好地來估算它，因?yàn)轭A(yù)示插入、脫落、換位等錯(cuò)拼的大多數(shù)重要因素都是一些局部性的因素，諸如正確字母本身是否等同，字母如何被錯(cuò)拼以及錯(cuò)拼時(shí)周圍的上下文等。例如，字母m和n經(jīng)常彼此替代而發(fā)生錯(cuò)拼，其部分原因是由于這兩個(gè)字母的等同性（這兩個(gè)字母發(fā)音相近，在鍵盤的位置彼此相鄰），部分原因是由于上下文（這兩個(gè)字母不僅發(fā)音相近，而且它們往往出現(xiàn)在相似的上下文中）。

Kerninghan et al. (1990) 使用了一種估算這種概率的簡單方法，不考慮大多數(shù)可能因素對(duì)錯(cuò)誤概率的影響，而只是進(jìn)行估算。例如，考慮在某個(gè)有錯(cuò)誤的大語料庫中e替代o的次數(shù)來估算p (acress l across)。這可以用含混矩陣（confusion matrix）來表示，含混矩陣是26x26的方框表，表示一個(gè)字母被另一個(gè)字母錯(cuò)誤替代的次數(shù)。例如，在替代含混矩陣中，標(biāo)記為[o, e]的單元將給出e替代o的次數(shù)；在插入含混矩陣中，標(biāo)記為[t, s]的單元將給出t插入到s后面的次數(shù)。計(jì)算含混矩陣時(shí)，需要手工收集拼寫錯(cuò)誤及其相應(yīng)的正確拼寫，然后計(jì)算不同錯(cuò)誤發(fā)生的次數(shù)，Grudin

(1983) 就是這樣做的。Kernighan et al. (1990）使用了四個(gè)含混矩陣，每個(gè)含混矩陣代表一類單獨(dú)錯(cuò)誤。

del [x, y] 訓(xùn)練集中的字符xy在正確單詞中應(yīng)打字為x的次數(shù)。

ins [x，y] 訓(xùn)練集中的字符x在正確單詞中應(yīng)打字為xy的次數(shù)。

sub [x, y] x被打字為y的次數(shù)。

trans [x, y] xy被打字為yx的次數(shù)。

注意，在這里選擇插入和脫落的條件是前面一個(gè)字符，也可以選擇后面一個(gè)字符為條件。使用這些含混矩陣，估算p（t l c）如下（其中，Cp，表示單詞c中的第p個(gè)字符）：

式6

圖6 給出了每個(gè)潛在可能的更正的最后概率；根據(jù)式4 計(jì)算先驗(yàn)概率，使用式6和含混矩陣計(jì)算似然度，并把先驗(yàn)概率與似然度相乘。最后一欄給出了“歸一化后的百分比”。

圖6 

圖6 每個(gè)候選更正等級(jí)的計(jì)算。注意，等級(jí)最高的單詞不是actress而是acres（在表中最底部的兩行），因?yàn)閍cres可以通過兩個(gè)途徑生成。在Kerninghan et al.(1990)中給出了del[ ]，ins[ ], sub[ ]和trans[ ]的全部含混矩陣

我們使用貝葉斯算法預(yù)見到acres是正確單詞（這個(gè)單詞的歸一化百分比共計(jì)為45%），而actress 則是第二位的最可能的正確單詞。遺憾的是，這個(gè)算法在這里算錯(cuò)了。文章作者的意圖可以從如下的上下文中看得很清楚….was called a“stellar and versatile acress whose combination of sass and glamour has defined her .….”。從acress周圍的詞來看，它的正確單詞顯然應(yīng)該是actress（女演員）而不是acres（英畝）。

我們所描述的算法要求手工標(biāo)注數(shù)據(jù)來訓(xùn)練含混矩陣。Kernighan(1990）等的另一種不同方法是迭代地使用錯(cuò)拼更正算法本身來計(jì)算含混矩陣。選代算法首先用相等的值啟動(dòng)一個(gè)矩陣，這時(shí)任何字符都是相等的，無論它是脫落還是被另一個(gè)字符替代等。然后，在一個(gè)拼寫錯(cuò)誤詞的集合上運(yùn)行錯(cuò)拼更正算法。給出拼寫錯(cuò)誤類型及其相對(duì)應(yīng)的更正，這時(shí)再計(jì)算含混矩陣，再運(yùn)行拼寫算法，這樣地不斷進(jìn)行，便可以循序漸進(jìn)地得到越來越好的含混矩陣。這個(gè)聰明的方法是重要的EM算法的一個(gè)實(shí)例 (Dempster et al.,1977)。Kernighan et al.（1990）的算法的評(píng)測(cè)是取一些具有兩種潛在更正的拼寫錯(cuò)誤，請(qǐng)三個(gè)評(píng)判人從中挑一個(gè)最好的更正來投票。程序與大多數(shù)評(píng)判人的投票是一致的，占了87%。

責(zé)任編輯：admin