【專欄】數學之美番外篇：平凡而又神奇的貝葉斯方法（2）

拼寫糾正

經典著作《人工智能：現代方法》的作者之一Peter Norvig曾經寫過一篇介紹如何寫一個拼寫檢查/糾正器的文章（原文在這里，徐宥的翻譯版在這里，這篇文章很深入淺出，強烈建議讀一讀），里面用到的就是貝葉斯方法，這里我們不打算復述他寫的文章，而是簡要地將其核心思想介紹一下。

首先，我們需要詢問的是：“問題是什么？”

問題是我們看到用戶輸入了一個不在字典中的單詞，我們需要去猜測：“這個家伙到底真正想輸入的單詞是什么呢？”用剛才我們形式化的語言來敘述就是，我們需要求：

P(我們猜測他想輸入的單詞|他實際輸入的單詞)

這個概率。并找出那個使得這個概率最大的猜測單詞。顯然，我們的猜測未必是唯一的，就像前面舉的那個自然語言的歧義性的例子一樣；這里，比如用戶輸入：thew，那么他到底是想輸入the，還是想輸入thaw？到底哪個猜測可能性更大呢？幸運的是我們可以用貝葉斯公式來直接出它們各自的概率，我們不妨將我們的多個猜測記為h1 h2……（h代表hypothesis），它們都屬于一個有限且離散的猜測空間H（單詞總共就那么多而已），將用戶實際輸入的單詞記為D（D代表Data，即觀測數據），于是：

P(我們的猜測1|他實際輸入的單詞)

可以抽象地記為：

P(h1|D)

類似地，對于我們的猜測2，則是P(h2|D)。不妨統一記為：

P(h|D)

運用一次貝葉斯公式，我們得到：

P(h|D)=P(h)*P(D|h)/P(D)

對于不同的具體猜測h1 h2 h3……，P(D)都是一樣的，所以在比較P(h1|D)和P(h2|D)的時候我們可以忽略這個常數。即我們只需要知道：

P(h|D)∝P(h)*P(D|h)（注：那個符號的意思是“正比例于”，不是無窮大，注意符號右端是有一個小缺口的。）

這個式子的抽象含義是：對于給定觀測數據，一個猜測是好是壞，取決于“這個猜測本身獨立的可能性大?。ㄏ闰灨怕?，Prior）”和“這個猜測生成我們觀測到的數據的可能性大小”（似然，Likelihood）的乘積。具體到我們的那個thew例子上，含義就是，用戶實際是想輸入the的可能性大小取決于the本身在詞匯表中被使用的可能性（頻繁程度）大?。ㄏ闰灨怕剩┖拖氪騮he卻打成thew的可能性大?。ㄋ迫唬┑某朔e。

下面的事情就很簡單了，對于我們猜測為可能的每個單詞計算一下P(h) * P(D | h)這個值，然后取最大的，得到的就是最靠譜的猜測。

一點注記：Norvig的拼寫糾正器里面只提取了編輯距離為2以內的所有已知單詞。這是為了避免去遍歷字典中每個單詞計算它們的P(h) * P(D | h)，但這種做法為了節省時間帶來了一些誤差。但話說回來難道我們人類真的回去遍歷每個可能的單詞來計算他們的后驗概率嗎？不可能。實際上，根據認知神經科學的觀點，我們首先根據錯誤的單詞做一個bottom-up的關聯提取，提取出有可能是實際單詞的那些候選單詞，這個提取過程就是所謂的基于內容的提取，可以根據錯誤單詞的一些模式片段提取出有限的一組候選，非?？斓乜s小的搜索空間（比如我輸入explaination，單詞里面就有充分的信息使得我們的大腦在常數時間內把可能性narrow down到explanation這個單詞上，至于具體是根據哪些線索——如音節——來提取，又是如何在生物神經網絡中實現這個提取機制的，目前還是一個沒有弄清的領域）。然后，我們對這有限的幾個猜測做一個top-down的預測，看看到底哪個對于觀測數據（即錯誤單詞）的預測效力最好，而如何衡量預測效率則就是用貝葉斯公式里面的那個P(h) * P(D | h)了——雖然我們很可能使用了一些啟發法來簡化計算。后面我們還會提到這樣的bottom-up的關聯提取。

（待續；此文的修訂版已收錄《暗時間》一書，由電子工業出版社2011年8月出版。作者于2009年7月獲得南京大學計算機系碩士學位，現在微軟亞洲研究院創新工程中心從事軟件研發工程師工作。）