數學之美 系列一 -- 統計語言模型
從本周開始，我們将定期刊登 Google 科學家吳軍寫的《數學之美》系列文章，介紹數學在資訊檢索和自然語言進行中的主導作用和奇妙應用。
發表者: 吳軍, Google 研究員
前言
也許大家不相信，數學是解決資訊檢索和自然語言處理的最好工具。它能非常清晰地描述這些領域的實際問題并且給出漂亮的解決辦法。每當人們應用數學工具解決一個語言問題時，總會感歎數學之美。我們希望利用 Google 中文黑闆報這塊園地，介紹一些數學工具，以及我們是如何利用這些工具來開發 Google 産品的。
系列一： 統計語言模型 (Statistical Language Models)
Google 的使命是整合全球的資訊，是以我們一直緻力于研究如何讓機器對資訊、語言做最好的了解和處理。長期以來，人類一直夢想着能讓機器代替人來翻譯語言、識别語音、認識文字（不論是印刷體或手寫體）和進行海量文獻的自動檢索，這就需要讓機器了解語言。但是人類的語言可以說是資訊裡最複雜最動态的一部分。為了解決這個問題，人們容易想到的辦法就是讓機器模拟人類進行學習 - 學習人類的文法、分析語句等等。尤其是在喬姆斯基（Noam Chomsky 有史以來最偉大的語言學家）提出 “形式語言” 以後，人們更堅定了利用文法規則的辦法進行文字處理的信念。遺憾的是，幾十年過去了，在計算機處理語言領域，基于這個文法規則的方法幾乎毫無突破。
其實早在幾十年前，數學家兼資訊論的祖師爺 香農 (Claude Shannon)就提出了用數學的辦法處理自然語言的想法。遺憾的是當時的計算機條件根本無法滿足大量資訊處理的需要，是以他這個想法當時并沒有被人們重視。七十年代初，有了大規模內建電路的快速計算機後，香農的夢想才得以實作。
首先成功利用數學方法解決自然語言處理問題的是語音和語言處理大師賈裡尼克 (Fred Jelinek)。當時賈裡尼克在 IBM 公司做學術休假 (Sabbatical Leave)，上司了一批傑出的科學家利用大型計算機來處理人類語言問題。統計語言模型就是在那個時候提出的。
給大家舉個例子：在很多涉及到自然語言處理的領域，如機器翻譯、語音識别、印刷體或手寫體識别、拼寫糾錯、漢字輸入和文獻查詢中，我們都需要知道一個文字序列是否能構成一個大家能了解的句子，顯示給使用者。對這個問題，我們可以用一個簡單的統計模型來解決這個問題。
如果 S 表示一連串特定順序排列的詞 w1， w2，…， wn ，換句話說，S 可以表示某一個由一連串特定順序排練的詞而組成的一個有意義的句子。現在，機器對語言的識别從某種角度來說，就是想知道S在文本中出現的可能性，也就是數學上所說的S 的機率用 P(S) 來表示。利用條件機率的公式，S 這個序列出現的機率等于每一個詞出現的機率相乘，于是P(S) 可展開為：
P(S) = P(w1)P(w2|w1)P(w3| w1 w2)…P(wn|w1 w2…wn-1)
其中 P (w1) 表示第一個詞w1 出現的機率；P (w2|w1) 是在已知第一個詞的前提下，第二個詞出現的機率；以次類推。不難看出，到了詞wn，它的出現機率取決于它前面所有詞。從計算上來看，各種可能性太多，無法實作。是以我們假定任意一個詞wi的出現機率隻同它前面的詞 wi-1 有關(即馬爾可夫假設），于是問題就變得很簡單了。現在，S 出現的機率就變為：
P(S) = P(w1)P(w2|w1)P(w3|w2)…P(wi|wi-1)…
(當然，也可以假設一個詞又前面N-1個詞決定，模型稍微複雜些。）
接下來的問題就是如何估計 P (wi|wi-1)。現在有了大量機讀文本後，這個問題變得很簡單，隻要數一數這對詞（wi-1,wi) 在統計的文本中出現了多少次，以及 wi-1 本身在同樣的文本中前後相鄰出現了多少次，然後用兩個數一除就可以了,P(wi|wi-1) = P(wi-1,wi)/ P (wi-1)。
也許很多人不相信用這麼簡單的數學模型能解決複雜的語音識别、機器翻譯等問題。其實不光是常人，就連很多語言學家都曾質疑過這種方法的有效性，但事實證明，統計語言模型比任何已知的借助某種規則的解決方法都有效。比如在 Google 的中英文自動翻譯中，用的最重要的就是這個統計語言模型。去年美國标準局(NIST) 對所有的機器翻譯系統進行了評測，Google 的系統是不僅是全世界最好的，而且高出所有基于規則的系統很多。
現在，讀者也許已經能感受到數學的美妙之處了，它把一些複雜的問題變得如此的簡單。當然，真正實作一個好的統計語言模型還有許多細節問題需要解決。賈裡尼克和他的同僚的貢獻在于提出了統計語言模型，而且很漂亮地解決了所有的細節問題。十幾年後，李開複用統計語言模型把 997 詞語音識别的問題簡化成了一個 20 詞的識别問題，實作了有史以來第一次大詞彙量非特定人連續語音的識别。
我是一名科學研究人員 ，我在工作中經常驚歎于數學語言應用于解決實際問題上時的神奇。我也希望把這種神奇講解給大家聽。當然，歸根結底，不管什莫樣的科學方法、無論多莫奇妙的解決手段都是為人服務的。我希望 Google 多努力一分，使用者就多一分搜尋的喜悅。
數學之美 系列二 -- 談談中文分詞
----- 統計語言模型在中文進行中的一個應用
上回我們談到利用統計語言模型進行語言處理，由于模型是建立在詞的基礎上的，對于中日韓等語言，首先需要進行分詞。例如把句子 “中國航天官員應邀到美國與太空總署官員開會。”
分成一串詞：
中國 / 航天 / 官員 / 應邀 / 到 / 美國 / 與 / 太空 / 總署 / 官員 / 開會。
最容易想到的，也是最簡單的分詞辦法就是查字典。這種方法最早是由北京航天航空大學的梁南元教授提出的。
用 “查字典” 法，其實就是我們把一個句子從左向右掃描一遍，遇到字典裡有的詞就辨別出來，遇到複合詞（比如 “上海大學”）就找最長的詞比對，遇到不認識的字串就分割成單字詞，于是簡單的分詞就完成了。這種簡單的分詞方法完全能處理上面例子中的句子。八十年代，哈工大的王曉龍博士把它理論化，發展成最少詞數的分詞理論，即一句話應該分成數量最少的詞串。這種方法一個明顯的不足是當遇到有二義性 （有雙重了解意思）的分割時就無能為力了。比如，對短語 “開發中國家” 正确的分割是“發展-中-國家”，而從左向右查字典的辦法會将它分割成“發展-中國-家”，顯然是錯了。另外，并非所有的最長比對都一定是正确的。比如“上海大學城書店”的正确分詞應該是 “上海-大學城-書店，” 而不是 “上海大學-城-書店”。
九十年代以前，海内外不少學者試圖用一些文法規則來解決分詞的二義性問題，都不是很成功。90年前後，清華大學的郭進博士用統計語言模型成功解決分詞二義性問題，将漢語分詞的錯誤率降低了一個數量級。
利用統計語言模型分詞的方法，可以用幾個數學公式簡單概括如下：
我們假定一個句子S可以有幾種分詞方法，為了簡單起見我們假定有以下三種：
A1, A2, A3, ..., Ak,
B1, B2, B3, ..., Bm
C1, C2, C3, ..., Cn
其中，A1, A2, B1, B2, C1, C2 等等都是漢語的詞。那麼最好的一種分詞方法應該保證分完詞後這個句子出現的機率最大。也就是說如果 A1,A2,..., Ak 是最好的分法，那麼 （P 表示機率）：
P (A1, A2, A3, ..., Ak） 〉 P (B1, B2, B3, ..., Bm), 并且
P (A1, A2, A3, ..., Ak） 〉 P(C1, C2, C3, ..., Cn)
是以，隻要我們利用上回提到的統計語言模型計算出每種分詞後句子出現的機率，并找出其中機率最大的，我們就能夠找到最好的分詞方法。
當然，這裡面有一個實作的技巧。如果我們窮舉所有可能的分詞方法并計算出每種可能性下句子的機率，那麼計算量是相當大的。是以，我們可以把它看成是一個動态規劃（Dynamic Programming) 的問題，并利用 “維特比”（Viterbi） 算法快速地找到最佳分詞。
在清華大學的郭進博士以後，海内外不少學者利用統計的方法，進一步完善中文分詞。其中值得一提的是清華大學孫茂松教授和香港科技大學吳德凱教授的工作。
需要指出的是，語言學家對詞語的定義不完全相同。比如說 “北京大學”，有人認為是一個詞，而有人認為該分成兩個詞。一個折中的解決辦法是在分詞的同時，找到複合詞的嵌套結構。在上面的例子中，如果一句話包含“北京大學”四個字，那麼先把它當成一個四字詞，然後再進一步找出細分詞 “北京” 和 “大學”。這種方法是最早是郭進在 “Computational Linguistics” （《計算機語言學》）雜志上發表的，以後不少系統采用這種方法。
一般來講，根據不同應用，漢語分詞的顆粒度大小應該不同。比如，在機器翻譯中，顆粒度應該大一些，“北京大學”就不能被分成兩個詞。而在語音識别中，“北京大學”一般是被分成兩個詞。是以，不同的應用，應該有不同的分詞系統。Google 的葛顯平博士和朱安博士，專門為搜尋設計和實作了自己的分詞系統。
也許你想不到，中文分詞的方法也被應用到英語處理，主要是手寫體識别中。因為在識别手寫體時，單詞之間的空格就不很清楚了。中文分詞方法可以幫助判别英語單詞的邊界。其實，語言處理的許多數學方法通用的和具體的語言無關。在 Google 内，我們在設計語言處理的算法時，都會考慮它是否能很容易地适用于各種自然語言。這樣，我們才能有效地支援上百種語言的搜尋。
數學之美 系列三 -- 隐含馬爾可夫模型在語言進行中的應用
前言：隐含馬爾可夫模型是一個數學模型，到目前為之，它一直被認為是實作快速精确的語音識别系統的最成功的方法。複雜的語音識别問題通過隐含馬爾可夫模型能非常簡單地被表述、解決，讓我不由由衷地感歎數學模型之妙。
自然語言是人類交流資訊的工具。很多自然語言處理問題都可以等同于通信系統中的解碼問題 -- 一個人根據接收到的資訊，去猜測發話人要表達的意思。這其實就象通信中，我們根據接收端收到的信号去分析、了解、還原發送端傳送過來的資訊。以下該圖就表示了一個典型的通信系統：
其中 s1，s2，s3...表示資訊源發出的信号。o1, o2, o3 ... 是接受器接收到的信号。通信中的解碼就是根據接收到的信号 o1, o2, o3 ...還原出發送的信号 s1，s2，s3...。
其實我們平時在說話時，腦子就是一個資訊源。我們的喉嚨（聲帶），空氣，就是如電線和光纜般的信道。聽衆耳朵的就是接收端，而聽到的聲音就是傳送過來的信号。根據聲學信号來推測說話者的意思，就是語音識别。這樣說來，如果接收端是一台計算機而不是人的話，那麼計算機要做的就是語音的自動識别。同樣，在計算機中，如果我們要根據接收到的英語資訊，推測說話者的漢語意思，就是機器翻譯； 如果我們要根據帶有拼寫錯誤的語句推測說話者想表達的正确意思，那就是自動糾錯。
那麼怎麼根據接收到的資訊來推測說話者想表達的意思呢？我們可以利用叫做“隐含馬爾可夫模型”（Hidden Markov Model）來解決這些問題。以語音識别為例，當我們觀測到語音信号 o1,o2,o3 時，我們要根據這組信号推測出發送的句子 s1,s2,s3。顯然，我們應該在所有可能的句子中找最有可能性的一個。用數學語言來描述，就是在已知 o1,o2,o3,...的情況下，求使得條件機率
P (s1,s2,s3,...|o1,o2,o3....) 達到最大值的那個句子 s1,s2,s3,...
當然，上面的機率不容易直接求出，于是我們可以間接地計算它。利用貝葉斯公式并且省掉一個常數項，可以把上述公式等價變換成
P(o1,o2,o3,...|s1,s2,s3....) * P(s1,s2,s3,...)
其中
P(o1,o2,o3,...|s1,s2,s3....) 表示某句話 s1,s2,s3...被讀成 o1,o2,o3,...的可能性, 而
P(s1,s2,s3,...) 表示字串 s1,s2,s3,...本身能夠成為一個合乎情理的句子的可能性，是以這個公式的意義是用發送信号為 s1,s2,s3...這個數列的可能性乘以 s1,s2,s3...本身可以一個句子的可能性，得出機率。
（讀者讀到這裡也許會問，你現在是不是把問題變得更複雜了，因為公式越寫越長了。别着急，我們現在就來簡化這個問題。）我們在這裡做兩個假設：
第一，s1,s2,s3,... 是一個馬爾可夫鍊，也就是說，si 隻由 si-1 決定 (詳見系列一)；
第二， 第 i 時刻的接收信号 oi 隻由發送信号 si 決定（又稱為獨立輸出假設, 即 P(o1,o2,o3,...|s1,s2,s3....) = P(o1|s1) * P(o2|s2)*P(o3|s3)...。
那麼我們就可以很容易利用算法 Viterbi 找出上面式子的最大值，進而找出要識别的句子 s1,s2,s3,...。
滿足上述兩個假設的模型就叫隐含馬爾可夫模型。我們之是以用“隐含”這個詞，是因為狀态 s1,s2,s3,...是無法直接觀測到的。
隐含馬爾可夫模型的應用遠不隻在語音識别中。在上面的公式中，如果我們把 s1,s2,s3,...當成中文，把 o1,o2,o3,...當成對應的英文，那麼我們就能利用這個模型解決機器翻譯問題； 如果我們把 o1,o2,o3,...當成掃描文字得到的圖像特征，就能利用這個模型解決印刷體和手寫體的識别。
P (o1,o2,o3,...|s1,s2,s3....) 根據應用的不同而又不同的名稱，在語音識别中它被稱為“聲學模型” (Acoustic Model)， 在機器翻譯中是“翻譯模型” (Translation Model) 而在拼寫校正中是“糾錯模型” (Correction Model)。 而P (s1,s2,s3,...) 就是我們在系列一中提到的語言模型。
在利用隐含馬爾可夫模型解決語言處理問題前，先要進行模型的訓練。 常用的訓練方法由伯姆（Baum）在60年代提出的，并以他的名字命名。隐含馬爾可夫模型在處理語言問題早期的成功應用是語音識别。七十年代，當時 IBM 的 Fred Jelinek (賈裡尼克) 和卡内基·梅隆大學的 Jim and Janet Baker (貝克夫婦，李開複的師兄師姐) 分别獨立地提出用隐含馬爾可夫模型來識别語音，語音識别的錯誤率相比人工智能和模式比對等方法降低了三倍 (從 30% 到 10%)。 八十年代李開複博士堅持采用隐含馬爾可夫模型的架構， 成功地開發了世界上第一個大詞彙量連續語音識别系統 Sphinx。
我最早接觸到隐含馬爾可夫模型是幾乎二十年前的事。那時在《随機過程》（清華“著名”的一門課）裡學到這個模型，但當時實在想不出它有什麼實際用途。幾年後，我在清華跟随王作英教授學習、研究語音識别時，他給了我幾十篇文獻。 我印象最深的就是賈裡尼克和李開複的文章，它們的核心思想就是隐含馬爾可夫模型。複雜的語音識别問題居然能如此簡單地被表述、解決，我由衷地感歎數學模型之妙。
數學之美系列 4 -- 怎樣度量資訊?
前言: Google 一直以 “整合全球資訊，讓人人能擷取，使人人能受益” 為使命。那麼究竟每一條資訊應該怎樣度量呢？
資訊是個很抽象的概念。我們常常說資訊很多，或者資訊較少，但卻很難說清楚資訊到底有多少。比如一本五十萬字的中文書到底有多少資訊量。直到 1948 年，香農提出了“資訊熵”(shāng) 的概念，才解決了對資訊的量化度量問題。
一條資訊的資訊量大小和它的不确定性有直接的關系。比如說，我們要搞清楚一件非常非常不确定的事，或是我們一無所知的事情，就需要了解大量的資訊。相反，如果我們對某件事已經有了較多的了解，我們不需要太多的資訊就能把它搞清楚。是以，從這個角度，我們可以認為，資訊量的度量就等于不确定性的多少。
那麼我們如何量化的度量資訊量呢？我們來看一個例子，馬上要舉行世界杯賽了。大家都很關心誰會是冠軍。假如我錯過了看世界杯，賽後我問一個知道比賽結果的觀衆“哪支球隊是冠軍”？ 他不願意直接告訴我， 而要讓我猜，并且我每猜一次，他要收一進制錢才肯告訴我是否猜對了，那麼我需要付給他多少錢才能知道誰是冠軍呢? 我可以把球隊編上号，從 1 到 32， 然後提問： “冠軍的球隊在 1-16 号中嗎?” 假如他告訴我猜對了， 我會接着問： “冠軍在 1-8 号中嗎?” 假如他告訴我猜錯了， 我自然知道冠軍隊在 9-16 中。 這樣隻需要五次， 我就能知道哪支球隊是冠軍。是以，誰是世界杯冠軍這條消息的資訊量隻值五塊錢。
當然，香農不是用錢，而是用 “比特”（bit）這個概念來度量資訊量。 一個比特是一位二進制數，計算機中的一個位元組是八個比特。在上面的例子中，這條消息的資訊量是五比特。（如果有朝一日有六十四個隊進入決賽階段的比賽，那麼“誰世界杯冠軍”的資訊量就是六比特，因為我們要多猜一次。） 讀者可能已經發現, 資訊量的比特數和所有可能情況的對數函數 log 有關。 (log32=5, log64=6。）
有些讀者此時可能會發現我們實際上可能不需要猜五次就能猜出誰是冠軍，因為象巴西、德國、意大利這樣的球隊得冠軍的可能性比日本、美國、南韓等隊大的多。是以，我們第一次猜測時不需要把 32 個球隊等分成兩個組，而可以把少數幾個最可能的球隊分成一組，把其它隊分成另一組。然後我們猜冠軍球隊是否在那幾隻熱門隊中。我們重複這樣的過程，根據奪冠機率對剩下的候選球隊分組，直到找到冠軍隊。這樣，我們也許三次或四次就猜出結果。是以，當每個球隊奪冠的可能性（機率）不等時，“誰世界杯冠軍”的資訊量的資訊量比五比特少。香農指出，它的準确資訊量應該是
= -（p1*log p1 + p2 * log p2 + ．．． ＋p32 *log p32)，
其中，p1，p2 ， ．．．，p32 分别是這 32 個球隊奪冠的機率。香農把它稱為“資訊熵” (Entropy)，一般用符号 H 表示，機關是比特。有興趣的讀者可以推算一下當 32 個球隊奪冠機率相同時，對應的資訊熵等于五比特。有數學基礎的讀者還可以證明上面公式的值不可能大于五。對于任意一個随機變量 X（比如得冠軍的球隊），它的熵定義如下：
變量的不确定性越大，熵也就越大，把它搞清楚所需要的資訊量也就越大。
有了“熵”這個概念，我們就可以回答本文開始提出的問題，即一本五十萬字的中文書平均有多少資訊量。我們知道常用的漢字（一級二級國标）大約有 7000 字。假如每個字等機率，那麼我們大約需要 13 個比特（即 13 位二進制數）表示一個漢字。但漢字的使用是不平衡的。實際上，前 10% 的漢字占文本的 95% 以上。是以，即使不考慮上下文的相關性，而隻考慮每個漢字的獨立的機率，那麼，每個漢字的資訊熵大約也隻有 8-9 個比特。如果我們再考慮上下文相關性，每個漢字的資訊熵隻有5比特左右。是以，一本五十萬字的中文書，資訊量大約是 250 萬比特。如果用一個好的算法壓縮一下，整本書可以存成一個 320KB 的檔案。如果我們直接用兩位元組的國标編碼存儲這本書，大約需要 1MB 大小，是壓縮檔案的三倍。這兩個數量的差距，在資訊論中稱作“備援度”（redundancy)。 需要指出的是我們這裡講的 250 萬比特是個平均數，同樣長度的書，所含的資訊量可以差很多。如果一本書重複的内容很多，它的資訊量就小，備援度就大。
不同語言的備援度差别很大，而漢語在所有語言中備援度是相對小的。這和人們普遍的認識“漢語是最簡潔的語言”是一緻的。
在下一集中， 我們将介紹資訊熵在資訊進行中的應用以及兩個相關的概念互資訊和相對熵。
對中文資訊熵有興趣的讀者可以讀我和王作英教授在電子學報上合寫的一篇文章
《語資訊熵和語言模型的複雜度》
數學之美系列五 -- 簡單之美：布爾代數和搜尋引擎的索引
[建立一個搜尋引擎大緻需要做這樣幾件事：自動下載下傳盡可能多的網頁；建立快速有效的索引；根據相關性對網頁進行公平準确的排序。我們在介紹 Google Page Rank (網頁排名) 時已經談到了一些排序的問題，這裡我們談談索引問題，以後我們還會談如何度量網頁的相關性，和進行網頁自動下載下傳。］
世界上不可能有比二進制更簡單的計數方法了，也不可能有比布爾運算更簡單的運算了。盡管今天每個搜尋引擎都宣稱自己如何聰明、多麼智能化，其實從根本上講都沒有逃出布爾運算的框框。
布爾（George Boole) 是十九世紀英國一位國小數學老師。他生前沒有人認為他是數學家。布爾在工作之餘，喜歡閱讀數學論著、思考數學問題。1854 年“思維規律”（An Investigation of the Laws of Thought, on which are founded the Mathematical Theories of Logic and Probabilities）一書，第一次向人們展示了如何用數學的方法解決邏輯問題。
布爾代數簡單得不能再簡單了。運算的元素隻有兩個1 （TRUE， 真) 和 0
（FALSE，假)。基本的運算隻有“與”（AND)、“或” (OR) 和“非”（NOT) 三種（後來發現，這三種運算都可以轉換成“與”“非” ＡＮＤ－ＮＯＴ一種運算）。全部運算隻用下列幾張真值表就能完全地描述清楚。
AND | 1 0
-----------------------
1 | 1 0
0 | 0 0
這張表說明如果 AND 運算的兩個元素有一個是 0，則運算結果總是 0。如果兩個元素都是 1，運算結果是 1。例如，“太陽從西邊升起”這個判斷是假的(0),“水可以流動”這個判斷是真的（1），那麼，“太陽從西邊升起并且水可以流動”就是假的（0）。
OR | 1 0
-----------------------
1 | 1 1
0 | 1 0
這張表說明如果OR運算的兩個元素有一個是 1，則運算結果總是 1。如果兩個元素都是 0，運算結果是 0。比如說，“張三是比賽第一名”這個結論是假的（0），“李四是比賽第一名”是真的（1），那麼“張三或者李四是第一名”就是真的（1）。
NOT |
--------------
1 | 0
0 | 1
這張表說明 NOT 運算把 1 變成 0，把 0 變成 1。比如，如果“象牙是白的”是真的（1），那麼“象牙不是白的”必定是假的（0）。
讀者也許會問這麼簡單的理論能解決什麼實際問題。布爾同時代的數學家們也有同樣的問題。事實上在布爾代數提出後80 多年裡，它确實沒有什麼像樣的應用，直到 1938 年香農在他的碩士論文中指出用布爾代數來實作開關電路，才使得布爾代數成為數字電路的基礎。所有的數學和邏輯運算，加、減、乘、除、乘方、開方等等，全部能轉換成二值的布爾運算。
現在我們看看文獻檢索和布爾運算的關系。對于一個使用者輸入的關鍵詞，搜尋引擎要判斷每篇文獻是否含有這個關鍵詞，如果一篇文獻含有它，我們相應地給這篇文獻一個邏輯值 -- 真（TRUE,或 1），否則，給一個邏輯值 -- 假（FALSE, 或0）。比如我們要找有關原子能應用的文獻，但并不想知道如何造原子彈。我們可以這樣寫一個查詢語句“原子能 AND 應用 AND (NOT 原子彈)”，表示符合要求的文獻必須同時滿足三個條件：
- 包含原子能
- 包含應用
- 不包含原子彈
一篇文獻對于上面每一個條件，都有一個 True 或者 False 的答案，根據上述真值表就能算出每篇文獻是否是要找的。
早期的文獻檢索查詢系統大多基于資料庫，嚴格要求查詢語句符合布爾運算。今天的搜尋引擎相比之下要聰明的多，它自動把使用者的查詢語句轉換成布爾運算的算式。當然在查詢時，不能将每篇文獻掃描一遍，來看看它是否滿足上面三個條件，是以需要建立一個索引。
最簡單索引的結構是用一個很長的二進制數表示一個關鍵字是否出現在每篇文獻中。有多少篇文獻，就有多少位數，每一位對應一篇文獻，1 代表相應的文獻有這個關鍵字，0 代表沒有。比如關鍵字“原子能”對應的二進制數是0100100001100001...，表示第二、第五、第九、第十、第十六篇文獻包含着個關鍵字。注意，這個二進制數非常之長。同樣，我們假定“應用”對應的二進制數是 0010100110000001...。那麼要找到同時包含“原子能”和“應用”的文獻時，隻要将這兩個二進制數進行布爾運算 AND。根據上面的真值表，我們知道運算結果是0000100000000001...。表示第五篇，第十六篇文獻滿足要求。
注意，計算機作布爾運算是非常非常快的。現在最便宜的微機都可以一次進行三十二位布爾運算，一秒鐘進行十億次以上。當然，由于這些二進制數中絕大部分位數都是零，我們隻需要記錄那些等于1的位數即可。于是，搜尋引擎的索引就變成了一張大表：表的每一行對應一個關鍵詞，而每一個關鍵詞後面跟着一組數字，是包含該關鍵詞的文獻序号。
對于網際網路的搜尋引擎來講，每一個網頁就是一個文獻。網際網路的網頁數量是巨大的，網絡中所用的詞也非常非常多。是以這個索引是巨大的，在萬億位元組這個量級。早期的搜尋引擎（比如 Alta Vista 以前的所有搜尋引擎），由于受計算機速度和容量的限制，隻能對重要的關鍵的主題詞建立索引。至今很多學術雜志還要求作者提供 3-5 個關鍵詞。這樣所有不常見的詞和太常見的虛詞就找不到了。現在，為了保證對任何搜尋都能提供相關的網頁，所有的搜尋引擎都是對所有的詞進行索引。為了網頁排名友善，索引中還需存有大量附加資訊，諸如每個詞出現的位置、次數等等。是以，整個索引就變得非常之大，以至于不可能用一台計算機存下。大家普遍的做法就是根據網頁的序号将索引分成很多份（Shards)，分别存儲在不同的伺服器中。每當接受一個查詢時，這個查詢就被分送到許許多多伺服器中，這些伺服器同時并行處理使用者請求，并把結果送到主伺服器進行合并處理，最後将結果傳回給使用者。
不管索引如何複雜，查找的基本操作仍然是布爾運算。布爾運算把邏輯和數學聯系起來了。它的最大好處是容易實作，速度快，這對于海量的資訊查找是至關重要的。它的不足是隻能給出是與否的判斷，而不能給出量化的度量。是以，所有搜尋引擎在内部檢索完畢後，都要對符合要求的網頁根據相關性排序，然後才傳回給使用者。
數學之美系列六 -- 圖論和網絡爬蟲 (Web Crawlers)
[離散數學是當代數學的一個重要分支，也是計算機科學的數學基礎。它包括數理邏輯、集合論、圖論和近世代數四個分支。數理邏輯基于布爾運算，我們已經介紹過了。這裡我們介紹圖論和網際網路自動下載下傳工具網絡爬蟲 (Web Crawlers) 之間的關系。順便提一句，我們用 Google Trends 來搜尋一下“離散數學”這個詞，可以發現不少有趣的現象。比如，武漢、哈爾濱、合肥和長沙市對這一數學題目最有興趣的城市。]
我們上回談到了如何建立搜尋引擎的索引，那麼如何自動下載下傳網際網路所有的網頁呢，它要用到圖論中的周遊（Traverse) 算法。
圖論的起源可追溯到大數學家歐拉（Leonhard Euler）。1736 年歐拉來到德國的哥尼斯堡（Konigsberg，大哲學家康德的故鄉，現在是俄羅斯的加裡甯格勒），發現當地市民們有一項消遣活動，就是試圖将下圖中的每座橋恰好走過一遍并回到原出發點，從來沒有人成功過。歐拉證明了這件事是不可能的，并寫了一篇論文，一般認為這是圖論的開始。
圖論中所讨論的的圖由一些節點和連接配接這些節點的弧組成。如果我們把中國的城市當成節點，連接配接城市的國道當成弧，那麼全國的公路幹線網就是圖論中所說的圖。關于圖的算法有很多，但最重要的是圖的周遊算法，也就是如何通過弧通路圖的各個節點。以中國公路網為例，我們從北京出發，看一看北京和哪些城市直接相連，比如說和天津、濟南、石家莊、南京、沈陽、大同直接相連。我們可以依次通路這些城市，然後我們看看都有哪些城市和這些已經通路過的城市相連，比如說北戴河、秦皇島與天津相連，青島、煙台和濟南相連，太原、鄭州和石家莊相連等等，我們再一次通路北戴河這些城市，直到中國所有的城市都通路過一遍為止。這種圖的周遊算法稱為“廣度優先算法”（BFS)，因為它先要盡可能廣地通路每個節點所直接連接配接的其他節點。另外還有一種政策是從北京出發，随便找到下一個要通路的城市，比如是濟南，然後從濟南出發到下一個城市，比如說南京，再通路從南京出發的城市，一直走到頭。然後再往回找，看看中間是否有尚未通路的城市。這種方法叫“深度優先算法”（DFS)，因為它是一條路走到黑。這兩種方法都可以保證通路到全部的城市。當然，不論采用哪種方法，我們都應該用一個小本本，記錄已經通路過的城市，以防同一個城市通路多次或者漏掉哪個城市。
現在我們看看圖論的周遊算法和搜尋引擎的關系。網際網路其實就是一張大圖，我們可以把每一個網頁當作一個節點，把那些超連結（Hyperlinks)當作連接配接網頁的弧。很多讀者可能已經注意到，網頁中那些藍色的、帶有下劃線的文字背後其實藏着對應的網址，當你點下去的的時候，浏覽器是通過這些隐含的網址轉到相應的網頁中的。這些隐含在文字背後的網址稱為“超連結”。有了超連結，我們可以從任何一個網頁出發，用圖的周遊算法，自動地通路到每一個網頁并把它們存起來。完成這個功能的程式叫做網絡爬蟲，或者在一些文獻中稱為"機器人"（Robot)。世界上第一個網絡爬蟲是由麻省理工學院 (MIT)的學生馬休.格雷（Matthew Gray)在 1993 年寫成的。他給他的程式起了個名字叫“網際網路漫遊者”("www wanderer")。以後的網絡爬蟲越寫越複雜，但原理是一樣的。
我們來看看網絡爬蟲如何下載下傳整個網際網路。假定我們從一家門戶網站的首頁出發，先下載下傳這個網頁，然後通過分析這個網頁，可以找到藏在它裡面的所有超連結，也就等于知道了這家門戶網站首頁所直接連接配接的全部網頁，諸如雅虎郵件、雅虎财經、雅虎新聞等等。我們接下來通路、下載下傳并分析這家門戶網站的郵件等網頁，又能找到其他相連的網頁。我們讓計算機不停地做下去，就能下載下傳整個的網際網路。當然，我們也要記載哪個網頁下載下傳過了，以免重複。在網絡爬蟲中，我們使用一個稱為“哈希表”(Hash Table)的清單而不是一個記事本紀錄網頁是否下載下傳過的資訊。
現在的網際網路非常巨大，不可能通過一台或幾台計算機伺服器就能完成下載下傳任務。比如雅虎公司（Google 沒有公開公布我們的數目，是以我這裡舉了雅虎的索引大小為例）宣稱他們索引了 200 億個網頁，假如下載下傳一個網頁需要一秒鐘，下載下傳這 200 億個網頁則需要 634 年。是以，一個商業的網絡爬蟲需要有成千上萬個伺服器，并且由快速網絡連接配接起來。如何建立這樣複雜的網絡系統，如何協調這些伺服器的任務，就是網絡設計和程式設計的藝術了。
數學之美 系列七 -- 資訊論在資訊進行中的應用
我們已經介紹了資訊熵，它是資訊論的基礎，我們這次談談資訊論在自然語言進行中的應用。
先看看資訊熵和語言模型的關系。我們在系列一中談到語言模型時，沒有講如何定量地衡量一個語言模型的好壞，當然，讀者會很自然地想到，既然語言模型能減少語音識别和機器翻譯的錯誤，那麼就拿一個語音識别系統或者機器翻譯軟體來試試，好的語言模型必然導緻錯誤率較低。這種想法是對的，而且今天的語音識别和機器翻譯也是這麼做的。但這種測試方法對于研發語言模型的人來講，既不直接、又不友善，而且很難從錯誤率反過來定量度量語言模型。事實上，在賈裡尼克(Fred Jelinek)的人研究語言模型時，世界上既沒有像樣的語音識别系統，更沒有機器翻譯。我們知道，語言模型是為了用上下文預測目前的文字，模型越好，預測得越準，那麼目前文字的不确定性就越小。
資訊熵正是對不确定性的衡量，是以資訊熵可以直接用于衡量統計語言模型的好壞。賈裡尼克從資訊熵出發，定義了一個稱為語言模型複雜度(Perplexity)的概念，直接衡量語言模型的好壞。一個模型的複雜度越小，模型越好。李開複博士在介紹他發明的 Sphinx 語音識别系統時談到，如果不用任何語言模型（即零元語言模型）時，複雜度為997，也就是說句子中每個位置有 997 個可能的單詞可以填入。如果（二進制）語言模型隻考慮前後詞的搭配不考慮搭配的機率時，複雜度為 60。雖然它比不用語言模型好很多，但是和考慮了搭配機率的二進制語言模型相比要差很多，因為後者的複雜度隻有 20。
資訊論中僅次于熵的另外兩個重要的概念是“互資訊”（Mutual Information) 和“相對熵”（Kullback-Leibler Divergence)。
“互資訊”是資訊熵的引申概念，它是對兩個随機事件相關性的度量。比如說今天随機事件北京下雨和随機變量空氣濕度的相關性就很大，但是和姚明所在的休斯敦火箭隊是否能赢公牛隊幾乎無關。互資訊就是用來量化度量這種相關性的。在自然語言進行中，經常要度量一些語言現象的相關性。比如在機器翻譯中，最難的問題是詞義的二義性（歧義性）問題。比如 Bush 一詞可以是美國總統的名字，也可以是灌木叢。（有一個笑話，美國上屆總統候選人凱裡 Kerry 的名字被一些機器翻譯系統翻譯成了"愛爾蘭的小母牛"，Kerry 在英語中另外一個意思。）那麼如何正确地翻譯這個詞呢？人們很容易想到要用文法、要分析語句等等。其實，至今為止，沒有一種文法能很好解決這個問題，真正實用的方法是使用互資訊。具體的解決辦法大緻如下：首先從大量文本中找出和總統布什一起出現的互資訊最大的一些詞，比如總統、美國、國會、華盛頓等等，當然，再用同樣的方法找出和灌木叢一起出現的互資訊最大的詞，比如土壤、植物、野生等等。有了這兩組詞，在翻譯 Bush 時，看看上下文中哪類相關的詞多就可以了。這種方法最初是由吉爾(Gale)，丘奇(Church)和雅讓斯基(Yarowsky)提出的。
當時雅讓斯基在賓西法尼亞大學是自然語言處理大師馬庫斯 (Mitch Marcus) 教授的博士生，他很多時間泡在貝爾實驗室丘奇等人的研究室裡。也許是急于畢業，他在吉爾等人的幫助下想出了一個最快也是最好地解決翻譯中的二義性，就是上述的方法，這個看上去簡單的方法效果好得讓同行們大吃一驚。雅讓斯基因而隻花了三年就從馬庫斯那裡拿到了博士，而他的師兄弟們平均要花六年時間。
資訊論中另外一個重要的概念是“相對熵”，在有些文獻中它被稱為成“交叉熵”。在英語中是 Kullback-Leibler Divergence，是以它的兩個提出者庫爾貝克和萊伯勒的名字命名的。相對熵用來衡量兩個正函數是否相似，對于兩個完全相同的函數，它們的相對熵等于零。在自然語言進行中可以用相對熵來衡量兩個常用詞（在文法上和語義上）是否同義，或者兩篇文章的内容是否相近等等。利用相對熵，我們可以到處資訊檢索中最重要的一個概念：詞頻率-逆向文檔頻率（TF/IDF)。我們下回會介紹如何根據相關性對搜尋出的網頁進行排序，就要用的餐TF/IDF 的概念。另外，在新聞的分類中也要用到相對熵和 TF/IDF。
對資訊論有興趣又有一定數學基礎的讀者，可以閱讀斯坦福大學托馬斯.科弗 (Thomas Cover) 教授的專著 "資訊論基礎"(Elements of Information Theory)：
數學之美 系列八-- 賈裡尼克的故事和現代語言處理
讀者也許注意到了，我們在前面的系列中多次提到了賈裡尼克這個名字。事實上，現代語音識别和自然語言處理确實是和它的名字是緊密聯系在一起的。我想在這回的系列裡，介紹賈裡尼克本人。在這裡我不想列舉他的貢獻，而想講一講他作為一個普普通通的人的故事。這些事要麼是我親身經曆的，要麼是他親口對我講的。
弗萊德裡克.賈裡尼克(Fred Jelinek)出生于捷克一個富有的猶太家庭。他的父母原本打算送他去英國的公學（私立學校）讀書。為了教他德語，還專門請的一位德國的家庭女教師，但是第二次世界大戰完全打碎了他們的夢想。他們先是被從家中趕了出去，流浪到布拉格。他的父親死在了集中營，弗萊德自己成天在街上玩耍，完全荒廢了學業。二戰後，當他再度回到學校時，他的成績一塌糊塗， 全部是 D，但是很快他就趕上了班上的同學。不過，他在國小時從來沒有得過 A。1949年，他的母親帶領全家移民美國。在美國，賈裡尼克一家生活非常貧困，全家基本是靠母親做點心賣錢為生，弗萊德自己十四五歲就進工廠打工補助全家。
賈裡尼克最初想成為一個律師，為他父親那樣的冤屈者辯護，但他很快意識到他那濃厚的外國口音将使他在法庭上的辯護很吃力。賈裡尼克的第二個理想是成為醫生，他想進哈佛大學醫學院，但經濟上他無法承擔醫學院 8 年高昂的學費。與此同時麻省理工學院給于了他一份（為東歐移民設的）全額獎學金。賈裡尼克決定到麻省理工學電機工程。在那裡，他遇到了資訊論的鼻祖香農博士，和語言學大師賈格布森 Roman Jakobson (他提出了著名的通信六功能）[注釋一]，後來賈裡尼克又陪着太太聽最偉大的語言學家喬姆斯基(Noam Chomsky)的課。這三位大師對賈裡尼克今後的研究方向--利用資訊論解決語言問題産生的重要影響。
賈裡尼克從麻省理工獲得博士學位後，在哈佛大學教了一年書，然後到康乃爾大學任教。他之是以選擇康乃爾大學，是因為找工作時和那裡的一位語言學家談得頗為投機。當時那位教授表示願意和賈裡尼克在利用資訊論解決語言問題上合作。但是，等賈裡尼克到康乃爾以後，那位教授表示對語言學在沒有興趣而轉向寫歌劇了。賈裡尼克對語言學家的壞印象從此開始。加上後來他在 IBM 時發現語言學家們嘴上頭頭是道，幹起活來高不成低不就，對語言學家從此深惡痛絕。他甚至說："我每開除一名語言學家，我的語音識别系統錯誤率就降低一個百分點。" 這句話後來在業界廣為流傳，為每一個搞語音識别和語言處理的人所熟知。
賈裡尼克在康乃爾十年磨一劍，潛心研究資訊論，終于悟出了自然語言處理的真谛。１９７２年，賈裡尼克到ＩＢＭ 華生實驗室（ＩＢＭ Ｔ．Ｇ．Ｗａｔｓｏｎ Ｌａｂｓ）做學術休假，無意中上司了語音識别實驗室，兩年後他在康乃爾和ＩＢＭ 之間選擇了留在ＩＢＭ。在那裡，賈裡尼克組建了陣容空前絕後強大的研究隊伍，其中包括他的著名搭檔波爾（Bahl），著名的語音識别 Dragon 公司的創始人貝克夫婦，解決最大熵疊代算法的達拉皮垂(Della Pietra)孿生兄弟，BCJR 算法的另外兩個共同提出者庫克(Cocke)和拉維夫(Raviv)，以及第一個提出機器翻譯統計模型的布朗。
七十年代的 IBM 有點像九十年代的微軟和今天的 Google, 給于傑出科學家作任何有興趣研究的自由。在那種寬松的環境裡，賈裡尼克等人提出了統計語音識别的架構結構。 在賈裡尼克以前，科學家們把語音識别問題當作人工智能問題和模式比對問題。而賈裡尼克把它當成通信問題，并用兩個隐含馬爾可夫模型（聲學模型和語言模型）把語音識别概括得清清楚楚。這個架構結構對至今的語音和語言處理有着深遠的影響，它從根本上使得語音識别有實用的可能。 賈裡尼克本人後來也是以當選美國工程院院士。
賈裡尼克和波爾，庫克以及拉維夫對人類的另一大貢獻是 BCJR 算法，這是今天數字通信中應用的最廣的兩個算法之一（另一個是維特比算法）。有趣的是，這個算法發明了二十年後，才得以廣泛應用。IBM 于是把它列為了 IBM 有史以來對人類最大貢獻之一，并貼在加州 Amaden 實作室牆上。遺憾的是 BCJR 四個人已經全部離開 IBM，有一次IBM 的通信部門需要用這個算法，還得從斯坦福大學請一位專家去講解，這位專家看到 IBM 櫥窗裡的成就榜，感慨萬分。
賈裡尼克和 IBM 一批最傑出的科學家在九十年代初離開了 IBM，他們大多數在華爾街取得了巨大的成功。賈裡尼克的書生氣很濃，于是去約翰霍普金斯大學建立了世界著名的 CLSP 實驗室。每年夏天，賈裡尼克邀請世界上 20-30 名頂級的科學家和學生到 CLSP 一起工作，使得 CLSP 成為世界上語音和語言處理的中心之一。
賈裡尼克治學極為嚴謹，對學生要求也極嚴。他淘汰學生的比例極高，即使留下來的，畢業時間也極長。但是，另一方面，賈裡尼克也千方百計利用自己的影響力為學生的學習和事業創造友善。賈裡尼克為組裡的每一位學生提供從進組第一天到離開組最後一天全部的學費和生活費。他還為每一位學生聯系實習機會，并保證每位學生在博士生階段至少在大公司實習一次。從他那裡拿到博士學位的學生，全部任職于著名實驗室，比如IBM, 微軟，AT&T 和 Google 的實驗室。為了提高外國人的英語水準，賈裡尼克用自己的經費為他們請私人英語教師。
賈裡尼克生活儉樸，一輛老式豐田車開了二十多年，比組裡學生的車都破。他每年都邀請組裡的學生和教授到家裡做客，很多畢業了的學生也專程趕來聚會。在那裡，他不再談論學術問題，而會談些鞏俐的電影（他太太是哥倫比亞大學電影專業的教授），或是某著名教授被拉斯韋加斯的賭館定為不受歡迎的人等等。但是他聚會的食物實在難吃，無非是些生胡蘿蔔和芹菜。後來賈裡尼克掏錢讓系裡另一個教授承辦聚會，那個教授每次請專業大廚在家作出極豐盛的晚宴，并準備許多美酒，從此這種聚會就轉移到那個教授家了。
除了鞏俐的電影，賈裡尼克對中國的了解就是清華大學和青島啤酒了。他有時會把兩個名字搞混，有兩次被香港科技大學的 Pascale 馮教授抓住。
賈裡尼克說話心直口快，不留餘地。在他面前談論學術一定要十分嚴謹，否則很容易被他抓住辮子。除了剛才提到的對語言學家略有偏見的評論，他對許多世界級的大師都有過很多“刻薄”但又實事求是的評論，這些評論在業界廣為流傳。賈裡尼克在四十多年的學術生涯中居然沒有得罪太多的人 ，可以說是一個奇迹。
數學之美 系列九 -- 如何确定網頁和查詢的相關性
[我們已經談過了如何自動下載下傳網頁、如何建立索引、如何衡量網頁的品質(Page Rank)。我們今天談談如何确定一個網頁和某個查詢的相關性。了解了這四個方面，一個有一定程式設計基礎的讀者應該可以寫一個簡單的搜尋引擎了，比如為您所在的學校或院系建立一個小的搜尋引擎。]
我們還是看上回的例子，查找關于“原子能的應用”的網頁。我們第一步是在索引中找到包含這三個詞的網頁（詳見關于布爾運算的系列）。現在任何一個搜尋引擎都包含幾十萬甚至是上百萬個多少有點關系的網頁。那麼哪個應該排在前面呢？顯然我們應該根據網頁和查詢“原子能的應用”的相關性對這些網頁進行排序。是以，這裡的關鍵問題是如何度量網頁和查詢的相關性。
我們知道，短語“原子能的應用”可以分成三個關鍵詞：原子能、的、應用。根據我們的直覺，我們知道，包含這三個詞多的網頁應該比包含它們少的網頁相關。當然，這個辦法有一個明顯的漏洞，就是長的網頁比短的網頁占便宜，因為長的網頁總的來講包含的關鍵詞要多些。是以我們需要根據網頁的長度，對關鍵詞的次數進行歸一化，也就是用關鍵詞的次數除以網頁的總字數。我們把這個商稱為“關鍵詞的頻率”，或者“單文本詞彙頻率”（Term Frequency)，比如，在某個一共有一千詞的網頁中“原子能”、“的”和“應用”分别出現了 2 次、35 次 和 5 次，那麼它們的詞頻就分别是 0.002、0.035 和 0.005。 我們将這三個數相加，其和 0.042 就是相應網頁和查詢“原子能的應用”
相關性的一個簡單的度量。概括地講，如果一個查詢包含關鍵詞 w1,w2,...,wN, 它們在一篇特定網頁中的詞頻分别是: TF1, TF2, ..., TFN。 （TF: term frequency)。 那麼，這個查詢和該網頁的相關性就是:
TF1 + TF2 + ... + TFN。
讀者可能已經發現了又一個漏洞。在上面的例子中，詞“的”站了總詞頻的 80% 以上，而它對确定網頁的主題幾乎沒有用。我們稱這種詞叫“應删除詞”（Stopwords)，也就是說在度量相關性是不應考慮它們的頻率。在漢語中，應删除詞還有“是”、“和”、“中”、“地”、“得”等等幾十個。忽略這些應删除詞後，上述網頁的相似度就變成了0.007，其中“原子能”貢獻了0.002，“應用”貢獻了 0.005。
細心的讀者可能還會發現另一個小的漏洞。在漢語中，“應用”是個很通用的詞，而“原子能”是個很專業的詞，後者在相關性排名中比前者重要。是以我們需要給漢語中的每一個詞給一個權重，這個權重的設定必須滿足下面兩個條件：
1. 一個詞預測主題能力越強，權重就越大，反之，權重就越小。我們在網頁中看到“原子能”這個詞，或多或少地能了解網頁的主題。我們看到“應用”一次，對主題基本上還是一無所知。是以，“原子能“的權重就應該比應用大。
2. 應删除詞的權重應該是零。
我們很容易發現，如果一個關鍵詞隻在很少的網頁中出現，我們通過它就容易鎖定搜尋目标，它的權重也就應該大。反之如果一個詞在大量網頁中出現，我們看到它仍然不很清楚要找什麼内容，是以它應該小。概括地講，假定一個關鍵詞 ｗ 在 Ｄｗ 個網頁中出現過，那麼 Ｄｗ 越大，ｗ 的權重越小，反之亦然。在資訊檢索中，使用最多的權重是“逆文本頻率指數” （Inverse document frequency 縮寫為ＩＤＦ），它的公式為ｌｏｇ（Ｄ／Ｄｗ）其中Ｄ是全部網頁數。比如，我們假定中文網頁數是Ｄ＝１０億，應删除詞“的”在所有的網頁中都出現，即Ｄｗ＝１０億，那麼它的ＩＤＦ＝log(10億/10億）= log (1) = ０。假如專用詞“原子能”在兩百萬個網頁中出現，即Ｄｗ＝２００萬，則它的權重ＩＤＦ＝log(500) =6.2。又假定通用詞“應用”，出現在五億個網頁中，它的權重ＩＤＦ = log(2)
則隻有 0.7。也就隻說，在網頁中找到一個“原子能”的比配相當于找到九個“應用”的比對。利用 IDF，上述相關性計算個公式就由詞頻的簡單求和變成了權重求和，即 TF1*IDF1 + TF2*IDF2 ＋... + TFN*IDFN。在上面的例子中，該網頁和“原子能的應用”的相關性為 0.0161，其中“原子能”貢獻了 0.0126，而“應用”隻貢獻了0.0035。這個比例和我們的直覺比較一緻了。
ＴＦ／ＩＤＦ（term frequency/inverse document frequency) 的概念被公認為資訊檢索中最重要的發明。在搜尋、文獻分類和其他相關領域有廣泛的應用。講起 TF/IDF 的曆史蠻有意思。IDF 的概念最早是劍橋大學的斯巴克－瓊斯[注：她有兩個姓］ (Karen Sparck Jones)提出來的。斯巴克－瓊斯 １９７２ 年在一篇題為關鍵詞特殊性的統計解釋和她在文獻檢索中的應用的論文中提出ＩＤＦ。遺憾的是，她既沒有從理論上解釋為什麼權重ＩＤＦ 應該是對數函數 ｌｏｇ（Ｄ／Ｄｗ）（而不是其它的函數，比如平方根），也沒有在這個題目上作進一步深入研究，以至于在以後的很多文獻中人們提到 ＴＦ／ＩＤＦ 時沒有引用她的論文，絕大多數人甚至不知道斯巴克－瓊斯的貢獻。同年羅賓遜寫了個兩頁紙的解釋，解釋得很不好。倒是後來康乃爾大學的薩爾頓（Salton)多次寫文章、寫書讨論 TF/IDF 在資訊檢索中的用途，加上薩爾頓本人的大名（資訊檢索的世界大獎就是以薩爾頓的名字命名的）。很多人都引用薩爾頓的書，甚至以為這個資訊檢索中最重要的概念是他提出的。當然，世界并沒有忘記斯巴克－瓊斯的貢獻，2004年，在紀念文獻學學報創刊 60 周年之際，該學報重印了斯巴克-瓊斯的大作。羅賓遜在同期期刊上寫了篇文章，用香農的資訊論解釋 IDF，這回的解釋是對的，但文章寫的并不好、非常冗長（足足十八頁），把一個簡單問題搞複雜了。其實，資訊論的學者們已經發現并指出，其實 IDF 的概念就是一個特定條件下、關鍵詞的機率分布的交叉熵（Kullback-Leibler Divergence)（詳見上一系列）。這樣，資訊檢索相關性的度量，又回到了資訊論。
現在的搜尋引擎對 TF/IDF 進行了不少細微的優化，使得相關性的度量更加準确了。當然，對有興趣寫一個搜尋引擎的愛好者來講，使用 TF/IDF 就足夠了。 如果我們結合上網頁排名(Page Rank)，那麼給定一個查詢，有關網頁綜合排名大緻由相關性和網頁排名乘積決定。
數學之美 系列十 有限狀态機和位址識别
位址的識别和分析是本地搜尋必不可少的技術，盡管有許多識别和分析位址的方法，最有效的是有限狀态機。
一個有限狀态機是一個特殊的有向圖（參見有關圖論的系列），它包括一些狀态（節點）和連接配接這些狀态的有向弧。下圖是一個識别中國位址的有限狀态機的簡單的例子。
每一個有限狀态機都有一個啟始狀态和一個終止狀态和若幹中間狀态。每一條弧上帶有從一個狀态進入下一個狀态的條件。比如，在上圖中，目前的狀态是“省”，如果遇到一個詞組和（區）縣名有關，我們就進入狀态“區縣”；如果遇到的下一個詞組和城市有關，那麼我們就進入“市”的狀态，如此等等。如果一條位址能從狀态機的起始狀态經過狀态機的若幹中間狀态，走到終止狀态，那麼這條位址則有效，否則無效。比如說，“北京市雙清路83号”對于上面的有限狀态來講有效，而“上海市遼甯省馬家莊”則無效（因為無法從市走回到省）。
使用有限狀态機識别位址，關鍵要解決兩個問題，即通過一些有效的位址建立狀态機，以及給定一個有限狀态機後，位址字串的比對算法。好在這兩個問題都有現成的算法。有了關于位址的有限狀态機後，我們就可又用它分析網頁，找出網頁中的位址部分，建立本地搜尋的資料庫。同樣，我們也可以對使用者輸入的查詢進行分析，挑出其中描述位址的部分，當然，剩下的關鍵詞就是使用者要找的内容。比如，對于使用者輸入的“北京市雙清路附近的酒家”，Google 本地會自動識别出位址“北京市雙清路”和要找的對象“酒家”。
上述基于有限狀态機的位址識别方法在實用中會有一些問題：當使用者輸入的位址不太标準或者有錯别字時，有限狀态機會束手無策，因為它隻能進行嚴格比對。（其實，有限狀态機在計算機科學中早期的成功應用是在程式語言編譯器的設計中。一個能運作的程式在文法上必須是沒有錯的，是以不需要模糊比對。而自然語言則很随意，無法用簡單的文法描述。）
為了解決這個問題，我們希望有一個能進行模糊比對、并給出一個字串為正确位址的可能性。為了實作這一目的，科學家們提出了基于機率的有限狀态機。這種基于機率的有限狀态機和離散的馬爾可夫鍊（詳見前面關于馬爾可夫模型的系列）基本上等效。
在八十年代以前，盡管有不少人使用基于機率的有限狀态機，但都是為自己的應用設計專用的有限狀态機的程式。九十年代以後，随着有限狀态機在自然語言處理的廣泛應用，不少科學家緻力于編寫通用的有限狀态機程式庫。其中，最成功的是前 AT&T 實驗室的三位科學家，莫瑞（Mohri）, 皮瑞爾（Pereira） 和瑞利（Riley）。他們三人花了很多年時間，編寫成一個通用的基于機率的有限狀态機 C 語言工具庫。由于 AT&T 有對學術界免費提供各種程式設計工具的好傳統，他們三人也把自己多年的心血拿出來和同行們共享。可惜好景不長，AT&T 實驗室風光不再，這三個人都離開了 AT&T，莫瑞成了紐約大學的教授，皮瑞爾當了賓西法尼亞大學計算機系系主任，而瑞利成了 Google 的研究員，AT&T 實驗室的新東家不再免費提供有限狀态機 C 語言工具庫。雖然此前莫瑞等人公布了他們的詳細算法，但是省略了實作的細節。是以在學術界，不少科學家能夠重寫同樣功能的工具庫，但是很難達到 AT&T 工具庫的效率（即運算速度），這的确是一件令人遺憾的事。
數學之美 系列十一 - Google 阿卡 47 的制造者阿米特.辛格博士
槍迷或者看過尼古拉斯.凱奇（Nicolas Cage)主演的電影“戰争之王”（Lord of
War)的人也許還記得影片開頭的一段話：（在所有輕武器中，）最有名的是阿卡 47( AK47)沖鋒槍(也就是中國的五六式沖鋒槍的原型），因為它從不卡殼、從不損壞、可在任何環境下使用、可靠性好、殺傷力大并且操作簡單。
我認為，在計算機中一個好的算法，應該向阿卡 47 沖鋒槍那樣簡單、有效、可靠性好而且容易讀懂(或者說易操作），而不應該是故弄玄虛。Google 的傑出工程師阿米特.辛格博士 (Amit Singhal) 就是為 Google 設計阿卡 47 沖鋒槍的人，在公司内部，Google 的排序算法便是以他的名字命名的。
從加入 Google 的第一天，我就開始了和辛格長期而愉快的合作，而他一直是我的一個良師益友。辛格、Matt Cutts（中國一些使用者誤認為他是聯邦調查局特工，當然他不是）、馬丁和我四個人當時一同研究和解決網絡搜尋中的作弊問題（Spam)。我們需要建一個分類器，我以前一直在學術界工作和學習，比較傾向找一個很漂亮的解決方案。我設計了一個很完美的分類器，大約要花三個月到半年時間來實作和訓練，而辛格認為找個簡單有效的辦法就行了。我們于是盡可能簡化問題，一、兩個月就把作弊的數量減少了一半。當時我們和公司工程副總裁羅森打了個賭，如果我們能減少 40% 的作弊，他就送我們四個家庭去夏威夷度假，後來羅森真的履約了。這個分類器設計得非常小巧（隻用很小的記憶體），而且非常快速（幾台伺服器就能處理全球搜尋的分類），至今運作得很好。
後來我和辛格一起又完成了許多項目，包括對中、日、韓文排名算法的改進。每一次，辛格總是堅持找簡單有效的解決方案。這種做法在 Google 這個人才濟濟的公司常常招人反對，因為很多資深的工程師懷疑這些簡單方法的有效性。不少人試圖用精确而複雜的辦法對辛格的設計的各種“阿卡47” 進行改進，後來發現幾乎所有時候，辛格的簡單方法都接近最優化的解決方案，而且還快得多。另一條選擇簡單方案的原因是這樣設計的系統很容易查錯（debug)。
當然，辛格之是以總是能找到那些簡單有效的方法，不是靠直覺，更不是撞大運，而是靠他豐富的研究經驗。辛格早年從師于搜尋大師薩爾頓(Salton)教授，畢業後就職于 AT&T 實驗室。在那裡，他和兩個同僚半年就搭起了一個中等規模的搜尋引擎，這個引擎索引的網頁數量雖然無法和商用的引擎相比，但是準确性卻非常好。在 AT&T，他對搜尋問題的各個細節進行了仔細的研究，他的那些簡單而有效的解決方案，常常是深思熟慮去僞存真的結果。
辛格非常鼓勵年輕人不怕失敗，大膽嘗試。一次一位剛畢業不久的工程師因為把帶有錯誤的程式推出到 Google 的伺服器上而惶惶不可終日。辛格安慰她講，你知道，我在 Google 犯的最大一次錯誤是曾經将所有網頁的相關性得分全部變成了零，于是所有搜尋的結果全部是随機的了。這位工程師後來為 Google 開發了很多好的産品。
辛格在 AT&T 時确立了他在學術界的地位，但是，他不是一個滿足于做實驗寫論文的人，于是他離開了實驗室來到了當時隻有百、十人的 Google。在這裡，他得以施展才智，重寫了 Google 的排名算法，并且一直在負責改進它。辛格因為舍不得放下兩個孩子，很少參加各種會議，但是他仍然被學術界公認為是當今最權威的網絡搜尋專家。2005年，辛格作為傑出校友被請回母校康乃爾大學計算機系在 40 年系慶上作報告，獲得這一殊榮的還有大名鼎鼎的美國工程院院士，計算機獨立磁盤備援陣列（RAID)的發明人凱茨(Randy Katz) 教授。
數學之美 系列 12 - 餘弦定理和新聞的分類
餘弦定理和新聞的分類似乎是兩件八杆子打不着的事，但是它們确有緊密的聯系。具體說，新聞的分類很大程度上依靠餘弦定理。
Google 的新聞是自動分類和整理的。所謂新聞的分類無非是要把相似的新聞放到一類中。計算機其實讀不懂新聞，它隻能快速計算。這就要求我們設計一個算法來算出任意兩篇新聞的相似性。為了做到這一點，我們需要想辦法用一組數字來描述一篇新聞。
我們來看看怎樣找一組數字，或者說一個向量來描述一篇新聞。回憶一下我們在“如何度量網頁相關性”一文中介紹的TF/IDF 的概念。對于一篇新聞中的所有實詞，我們可以計算出它們的單文本詞彙頻率/逆文本頻率值（TF/IDF)。不難想象，和新聞主題有關的那些實詞頻率高，TF/IDF 值很大。我們按照這些實詞在詞彙表的位置對它們的 TF/IDF 值排序。比如，詞彙表有六萬四千個詞，分别為
單詞編号 漢字詞
------------------
1 阿
2 啊
3 阿鬥
4 阿姨
...
789 服裝
....
64000 做作
在一篇新聞中，這 64,000 個詞的 TF/IDF 值分别為
單詞編号 TF/IDF 值
==============
1 0
2 0.0034
3 0
4 0.00052
5 0
...
789 0.034
...
64000 0.075
如果單詞表中的某個次在新聞中沒有出現，對應的值為零，那麼這 64,000 個數，組成一個64,000維的向量。我們就用這個向量來代表這篇新聞，并成為新聞的特征向量。如果兩篇新聞的特征向量相近，則對應的新聞内容相似，它們應當歸在一類，反之亦然。
學過向量代數的人都知道，向量實際上是多元空間中有方向的線段。如果兩個向量的方向一緻，即夾角接近零，那麼這兩個向量就相近。而要确定兩個向量方向是否一緻，這就要用到餘弦定理計算向量的夾角了。
餘弦定理對我們每個人都不陌生，它描述了三角形中任何一個夾角和三個邊的關系，換句話說，給定三角形的三條邊，我們可以用餘弦定理求出三角形各個角的角度。假定三角形的三條邊為 a, b 和 c，對應的三個角為 A, B 和 C，那麼角 A 的餘弦 --
如果我們将三角形的兩邊 b 和 c 看成是兩個向量，那麼上述公式等價于
其中分母表示兩個向量 b 和 c 的長度，分子表示兩個向量的内積。舉一個具體的例子，假如新聞 X 和新聞 Y 對應向量分别是
x1,x2,...,x64000 和
y1,y2,...,y64000,
那麼它們夾角的餘弦等于，
當兩條新聞向量夾角的餘弦等于一時，這兩條新聞完全重複（用這個辦法可以删除重複的網頁）；當夾角的餘弦接近于一時，兩條新聞相似，進而可以歸成一類；夾角的餘弦越小，兩條新聞越不相關。
我們在中學學習餘弦定理時，恐怕很難想象它可以用來對新聞進行分類。在這裡，我們再一次看到數學工具的用途。
數學之美 系列十三 資訊指紋及其應用
任何一段資訊文字，都可以對應一個不太長的随機數，作為差別它和其它資訊的指紋（Fingerprint)。隻要算法設計的好，任何兩段資訊的指紋都很難重複，就如同人類的指紋一樣。資訊指紋在加密、資訊壓縮和進行中有着廣泛的應用。
我們在圖論和網絡爬蟲一文中提到，為了防止重複下載下傳同一個網頁，我們需要在哈希表中紀錄已經通路過的網址（URL)。但是在哈希表中以字元串的形式直接存儲網址，既費記憶體空間，又浪費查找時間。現在的網址一般都較長，比如，如果在 Google 或者百度在查找數學之美，對應的網址長度在一百個字元以上。下面是百度的連結
http://www.baidu.com/s?ie=gb2312&bs=%CA%FD%D1%A7%D6%AE%C3%C0&sr=&z=&cl=3&f=8
&wd=%CE%E2%BE%FC+%CA%FD%D1%A7%D6%AE%C3%C0&ct=0
假定網址的平均長度為一百個字元，那麼存貯 200 億個網址本身至少需要 2 TB，即兩千 GB 的容量，考慮到哈希表的存儲效率一般隻有 50%，實際需要的記憶體在 4 TB以上。即使把這些網址放到了計算機的記憶體中，由于網址長度不固定，以字元串的形式查找的效率會很低。是以，我們如果能夠找到一個函數，将這 200 億個網址随機地映射到128 二進位即 16 個位元組的整數空間，比如将上面那個很長的字元串對應成一個如下的随機數:
893249432984398432980545454543
這樣每個網址隻需要占用 16 個位元組而不是原來的一百個。這就能把存儲網址的記憶體需求量降低到原來的 1/6。這個16 個位元組的随機數，就稱做該網址的資訊指紋（Fingerprint)。可以證明，隻要産生随機數的算法足夠好，可以保證幾乎不可能有兩個字元串的指紋相同，就如同不可能有兩個人的指紋相同一樣。由于指紋是固定的 128 位整數，是以查找的計算量比字元串比較小得多。網絡爬蟲在下載下傳網頁時，它将通路過的網頁的網址都變成一個個資訊指紋，存到哈希表中，每當遇到一個新網址時，計算機就計算出它的指紋，然後比較該指紋是否已經在哈希表中，來決定是否下載下傳這個網頁。這種整數的查找比原來字元串查找,可以快幾倍到幾十倍。
産生資訊指紋的關鍵算法是僞随機數産生器算法（prng)。最早的 prng 算法是由計算機之父馮諾伊曼提出來的。他的辦法非常簡單，就是将一個數的平方掐頭去尾，取中間的幾位數。比如一個四位的二進制數 1001（相當于十進制的9），其平方為 01010001 (十進制的 81）掐頭去尾剩下中間的四位 0100。當然這種方法産生的數字并不很随機，也就是說兩個不同資訊很有可能有同一指紋。現在常用的 MersenneTwister 算法要好得多。
資訊指紋的用途遠不止網址的消重，資訊指紋的的孿生兄弟是密碼。資訊指紋的一個特征是其不可逆性, 也就是說,
無法根據資訊指紋推出原有資訊，這種性質， 正是網絡加密傳輸所需要的。比如說，一個網站可以根據使用者的Cookie 識别不同使用者，這個 cookie 就是資訊指紋。但是網站無法根據資訊指紋了解使用者的身份，這樣就可以保護使用者的隐私。在網際網路上，加密的可靠性，取決于是否很難人為地找到擁有同一指紋的資訊， 比如一個黑客是否能随意産生使用者的 cookie。從加密的角度講 MersenneTwister，算法并不好，因為它産生的随機數有相關性。
網際網路上加密要用基于加密僞随機數産生器（csprng)。常用的算法有 MD5 或者 SHA1 等标準，它們可以将不定長的資訊變成定長的 128 二進位或者 160 二進位随機數。值得一提的事，SHA1 以前被認為是沒有漏洞的，現在已經被中國的王小雲教授證明存在漏洞。但是大家不必恐慌， 因為這和黑客能真正攻破你的注冊資訊是還兩回事。
資訊指紋的雖然曆史很悠久，但真正的廣泛應用是在有了網際網路以後，這幾年才漸漸熱門起來。
數學之美 十四 談談數學模型的重要性
[注：一直關注數學之美系列的讀者可能已經發現，我們對任何問題總是在找相應的準确的數學模型。為了說明模型的重要性，今年七月份我在 Google 中國内部講課時用了整整一堂課來講這個問題，下面的内容是我講座的摘要。］
在包括哥白尼、伽利略和牛頓在内的所有天文學家中，我最佩服的是地心說的提出者托勒密。雖然天文學起源于古埃及，并且在古巴比倫時，人們就觀測到了五大行星（金、木、水、火、土）運作的軌迹，以及行星在近日點運動比遠日點快。（下圖是在地球上看到的金星的軌迹，看過達芬奇密碼的讀者知道金星大約每四年在天上畫一個五角星。）
但是真正創立了天文學，并且計算出諸多天體運作軌迹的是兩千年前古羅馬時代的托勒密。雖然今天我們可能會嘲笑托勒密犯的簡單的錯誤，但是真正了解托勒密貢獻的人都會對他肅然起敬。托勒密發明了球坐标，定義了包括赤道和零度經線在内的經緯線，他提出了黃道，還發明了弧度制。
當然，他最大也是最有争議的發明是地心說。雖然我們知道地球是圍繞太陽運動的，但是在當時，從人們的觀測出發，很容易得到地球是宇宙中心的結論。從地球上看，行星的運動軌迹是不規則的，托勒密的偉大之處是用四十個小圓套大圓的方法，精确地計算出了所有行星運動的軌迹。（托勒密繼承了畢達格拉斯的一些思想，他也認為圓是最完美的幾何圖形。）托勒密模型的精度之高，讓以後所有的科學家驚歎不已。即使今天，我們在計算機的幫助下，也很難解出四十個套在一起的圓的方程。每每想到這裡，我都由衷地佩服托勒密。一千五百年來，人們根據他的計算決定農時。但是，經過了一千五百年，托勒密對太陽運動的累積誤差，還是差出了一星期。
地心說的示意圖，我國天文學家張衡的渾天地動說其實就是地心說。
糾正地心說錯誤不是靠在托勒密四十個圓的模型上再多套上幾個圓，而是進一步探索真理。哥白尼發現，如果以太陽為中心來描述星體的運作，隻需要 8-10 個圓，就能計算出一個行星的運動軌迹，他提出了日心說。很遺憾的事，哥白尼正确的假設并沒有得到比托勒密更好的結果，哥白尼的模型的誤差比托勒密地要大不少。這是教會和當時人們認為哥白尼的學說是邪說的一個原因，是以日心說要想讓人心服口服地接受，就得更準确地描述行星運動。
完成這一使命的是開普勒。開普勒在所有一流的天文學家中，資質較差，一生中犯了無數低級的錯誤。但是他有兩條别人沒有的東西，從他的老師第谷手中繼承的大量的、在當時最精确的觀測資料，以及運氣。開普勒很幸運地發現了行星圍繞太陽運轉的軌道實際是橢圓形的，這樣不需要用多個小圓套大圓，而隻要用一個橢圓就能将星體運動規律描述清楚了。隻是開普勒的知識和水準不足以解釋為什麼行星的軌道是橢圓形的。最後是偉大的科學家牛頓用萬有引力解釋了這個問題。
故事到這裡似乎可以結束了。但是，許多年後，又有了個小的波瀾。天文學家們發現，天王星的實際軌迹和用橢圓模型算出來的不太符合。當然，偷懶的辦法是接着用小圓套大圓的方法修正，但是一些嚴肅的科學家在努力尋找真正的原因。英國的亞當斯和法國的維内爾（Verrier）獨立地發現了吸引天王星偏離軌道的海王星。
講座結束前，我和 Google 中國的工程師們一同總結了這麼幾個結論：
１. 一個正确的數學模型應當在形式上是簡單的。（托勒密的模型顯然太複雜。）
２. 一個正确的模型在它開始的時候可能還不如一個精雕細琢過的錯誤的模型來的準确，但是，如果我們認定大方向是對的，就應該堅持下去。（日心說開始并沒有地心說準确。）
３. 大量準确的資料對研發很重要。
４. 正确的模型也可能受噪音幹擾，而顯得不準确；這時我們不應該用一種湊合的修正方法來彌補它，而是要找到噪音的根源，這也許能通往重大發現。
在網絡搜尋的研發中，我們在前面提到的單文本詞頻/逆文本頻率指數（TF/IDF) 和網頁排名（page rank)都相當于是網絡搜尋中的“橢圓模型”，它們都很簡單易懂。
數學之美 系列十五 繁與簡 自然語言處理的幾位精英
我在數學之美系列中一直強調的一個好方法就是簡單。但是，事實上，自然語言進行中也有一些特例，比如有些學者将一個問題研究到極緻，執著追求完善甚至可以說完美的程度。他們的工作對同行有很大的參考價值，是以我們在科研中很需要這樣的學者。在自然語言處理方面新一代的頂級人物麥克爾 · 柯林斯 (Michael Collins) 就是這樣的人。
柯林斯：追求完美
柯林斯從師于自然語言處理大師馬庫斯 (Mitch Marcus)（我們以後還會多次提到馬庫斯），從賓夕法利亞大學獲得博士學位，現任麻省理工學院 (MIT) 副教授（别看他是副教授，他的水準在當今自然語言處理領域是數一數二的），在作博士期間，柯林斯寫了一個後來以他名字命名的自然語言文法分析器 (sentence parser)，可以将書面語的每一句話準确地進行文法分析。文法分析是很多自然語言應用的基礎。雖然柯林斯的師兄布萊爾 (Eric Brill) 和 Ratnaparkhi 以及師弟 Eisnar 都完成了相當不錯的語言文法分析器，但是柯林斯卻将它做到了極緻，使它在相當長一段時間内成為世界上最好的文法分析器。柯林斯成功的關鍵在于将文法分析的每一個細節都研究得很仔細。柯林斯用的數學模型也很漂亮，整個工作可以用完美來形容。我曾因為研究的需要，找柯林斯要過他文法分析器的源程式，他很爽快地給了我。我試圖将他的程式修改一下來滿足我特定應用的要求，但後來發現，他的程式細節太多以至于很難進一步優化。柯林斯的博士論文堪稱是自然語言處理領域的範文。它像一本優秀的小說，把所有事情的來龍去脈介紹的清清楚楚，對于任何有一點計算機和自然語言處理知識的人，都可以輕而易舉地讀懂他複雜的方法。
柯林斯畢業後，在 AT&T 實驗室度過了三年快樂的時光。在那裡柯林斯完成了許多世界一流的研究工作諸如隐含馬爾科夫模型的差別性訓練方法，卷積核在自然語言進行中的應用等等。三年後，AT&T 停止了自然語言處理方面的研究，柯林斯幸運地在 MIT 找到了教職。在 MIT 的短短幾年間，柯林斯多次在國際會議上獲得最佳論文獎。相比其他同行，這種成就是獨一無二的。柯林斯的特點就是把事情做到極緻。如果說有人喜歡“繁瑣哲學”，柯林斯就是一個。
布萊爾：簡單才美
在研究方法上，站在柯林斯對立面的典型是他的師兄艾裡克 · 布萊爾 (Eric Brill) 和雅讓斯基，後者我們已經介紹過了，這裡就不再重複。與柯林斯從工業界到學術界相反，布萊爾職業路徑是從學術界走到工業界。與柯裡斯的研究方法相反，布萊爾總是試圖尋找簡單得不能再簡單的方法。布萊爾的成名作是基于變換規則的機器學習方法 (transformation rule based machine learning)。這個方法名稱雖然很複雜，其實非常簡單。我們以拼音轉換字為例來說明它：
第一步，我們把每個拼音對應的漢字中最常見的找出來作為第一遍變換的結果，當然結果有不少錯誤。比如，“常識”可能被轉換成“長識”；
第二步，可以說是“去僞存真”，我們用計算機根據上下文，列舉所有的同音字替換的規則，比如，如果 chang 被辨別成“長”，但是後面的漢字是“識”，則将“長”改成“常”；
第三步，應該就是“去粗取精”，将所有的規則用到事先辨別好的語料中，挑出有用的，删掉無用的。然後重複二三步，直到找不到有用的為止。
布萊爾就靠這麼簡單的方法，在很多自然語言研究領域，得到了幾乎最好的結果。由于他的方法再簡單不過了，許許多多的人都跟着學。布萊爾可以算是我在美國的第一個業師，我們倆就用這麼簡單的方法作詞性标注 (part of speech tagging)，也就是把句子中的詞标成名詞動詞，很多年内無人能超越。（最後超越我們的是後來加入 Google 的一名荷蘭工程師，用的是同樣的方法，但是做得細緻很多）布萊爾離開學術界後去了微軟研究院。在那裡的第一年，他一人一年完成的工作比組裡其他所有人許多年做的工作的總和還多。後來，布萊爾又加入了一個新的組，依然是高産科學家。據說，他的工作真正被微軟重視要感謝 Google，因為有了 Google，微軟才對他從人力物力上給于了巨大的支援，使得布萊爾成為微軟搜尋研究的領軍人物之一。在研究方面，布萊爾有時不一定能馬上找到應該怎麼做，但是能馬上否定掉一種不可能的方案。這和他追求簡單的研究方法有關，他能在短時間内大緻摸清每種方法的好壞。
由于布萊爾總是找簡單有效的方法，而又從不隐瞞自己的方法，是以他總是很容易被包括作者我自己在内的很多人趕上和超過。好在布萊爾很喜歡别人追趕他，因為，當人們在一個研究方向超過他時，他已經調轉船頭駛向它方了。一次，艾裡克對我說，有一件事我永遠追不上他，那就是他比我先有了第二個孩子 ：）
在接下來了系列裡，我們還會介紹一個繁與簡結合的例子。
數學之美 系列十六 （下）－ 不要把所有的雞蛋放在一個籃子裡 最大熵模型
我們上次談到用最大熵模型可以将各種資訊綜合在一起。我們留下一個問題沒有回答，就是如何構造最大熵模型。我們已經所有的最大熵模型都是指數函數的形式，現在隻需要确定指數函數的參數就可以了，這個過程稱為模型的訓練。
最原始的最大熵模型的訓練方法是一種稱為通用疊代算法 GIS(generalized iterative scaling) 的疊代 算法。GIS 的原理并不複雜，大緻可以概括為以下幾個步驟：
1. 假定第零次疊代的初始模型為等機率的均勻分布。
2. 用第 N 次疊代的模型來估算每種資訊特征在訓練資料中的分布，如果超過了實際的，就把相應的模型參數變小；否則，将它們便大。
3. 重複步驟 2 直到收斂。
GIS 最早是由 Darroch 和 Ratcliff 在七十年代提出的。但是，這兩人沒有能對這種算法的實體含義進行很好地解釋。後來是由數學家希薩（Csiszar)解釋清楚的，是以，人們在談到這個算法時，總是同時引用 Darroch 和Ratcliff 以及希薩的兩篇論文。GIS 算法每次疊代的時間都很長，需要疊代很多次才能收斂，而且不太穩定，即使在 64 位計算機上都會出現溢出。是以，在實際應用中很少有人真正使用 GIS。大家隻是通過它來了解最大熵模型的算法。
八十年代，很有天才的孿生兄弟的達拉皮垂(Della Pietra)在 IBM 對 GIS 算法進行了兩方面的改進，提出了改進疊代算法 IIS（improved iterative scaling）。這使得最大熵模型的訓練時間縮短了一到兩個數量級。這樣最大熵模型才有可能變得實用。即使如此，在當時也隻有 IBM 有條件是用最大熵模型。
由于最大熵模型在數學上十分完美，對科學家們有很大的誘惑力，是以不少研究者試圖把自己的問題用一個類似最大熵的近似模型去套。誰知這一近似，最大熵模型就變得不完美了，結果可想而知，比打更新檔的湊合的方法也好不了多少。于是，不少熱心人又放棄了這種方法。第一個在實際資訊處理應用中驗證了最大熵模型的優勢的，是賓夕法尼亞大學馬庫斯的另一個高徒原 IBM 現微軟的研究員拉納帕提(Adwait Ratnaparkhi)。拉納帕提的聰明之處在于他沒有對最大熵模型進行近似，而是找到了幾個最适合用最大熵模型、而計算量相對不太大的自然語言處理問題，比如詞性标注和句法分析。拉納帕提成功地将上下文資訊、詞性（名詞、動詞和形容詞等）、句子成分（主謂賓）通過最大熵模型結合起來，做出了當時世界上最好的詞性辨別系統和句法分析器。拉納帕提的論文發表後讓人們耳目一新。拉納帕提的詞性标注系統，至今仍然是使用單一方法最好的系統。科學家們從拉納帕提的成就中，又看到了用最大熵模型解決複雜的文字資訊處理的希望。
但是，最大熵模型的計算量仍然是個攔路虎。我在學校時花了很長時間考慮如何簡化最大熵模型的計算量。終于有一天，我對我的導師說，我發現一種數學變換，可以将大部分最大熵模型的訓練時間在 IIS 的基礎上減少兩個數量級。我在黑闆上推導了一個多小時，他沒有找出我的推導中的任何破綻，接着他又回去想了兩天，然後告訴我我的算法是對的。從此，我們就建造了一些很大的最大熵模型。這些模型比修修補補的湊合的方法好不少。即使在我找到了快速訓練算法以後，為了訓練一個包含上下文資訊，主題資訊和文法資訊的文法模型(language model)，我并行使用了 20 台當時最快的 SUN 工作站，仍然計算了三個月。由此可見最大熵模型的複雜的一面。最大熵模型快速算法的實作很複雜，到今天為止，世界上能有效實作這些算法的人也不到一百人。有興趣實作一個最大熵模型的讀者可以閱讀我的論文。
最大熵模型，可以說是集簡與繁于一體，形式簡單，實作複雜。值得一提的是，在Google的很多産品中，比如機器翻譯，都直接或間接地用到了最大熵模型。
講到這裡，讀者也許會問，當年最早改進最大熵模型算法的達拉皮垂兄弟這些年難道沒有做任何事嗎？他們在九十年代初賈裡尼克離開 IBM 後，也退出了學術界，而到在金融界大顯身手。他們兩人和很多 IBM 語音識别的同僚一同到了一家當時還不大，但現在是世界上最成功對沖基金(hedge fund)公司----文藝複興技術公司 (Renaissance Technologies)。我們知道，決定股票漲落的因素可能有幾十甚至上百種，而最大熵方法恰恰能找到一個同時滿足成千上萬種不同條件的模型。達拉皮垂兄弟等科學家在那裡，用于最大熵模型和其他一些先進的數學工具對股票預測，獲得了巨大的成功。從該基金 1988 年創立至今，它的淨回報率高達平均每年 34%。也就是說，如果 1988 年你在該基金投入一塊錢，今天你能得到 200 塊錢。這個業績，遠遠超過股神巴菲特的旗艦公司伯克夏哈撒韋（Berkshire Hathaway)。同期，伯克夏哈撒韋的總回報是 16 倍。
值得一提的是，資訊處理的很多數學手段，包括隐含馬爾可夫模型、子波變換、貝葉斯網絡等等，在華爾街多有直接的應用。由此可見，數學模型的作用。
數學之美 系列十七 閃光的不一定是金子 談談搜尋引擎作弊問題(Search Engine Anti-SPAM)
自從有了搜尋引擎，就有了針對搜尋引擎網頁排名的作弊(SPAM)。以至于使用者發現在搜尋引擎中排名靠前的網頁不一定就是高品質的，用句俗話說，閃光的不一定是金子。
搜尋引擎的作弊，雖然方法很多，目的隻有一個，就是采用不正當手段提高自己網頁的排名。早期最常見的作弊方法是重複關鍵詞。比如一個賣數位相機的網站，重複地羅列各種數位相機的品牌，如尼康、佳能和柯達等等。為了不讓讀者看到衆多讨厭的關鍵詞，聰明一點的作弊者常用很小的字型和與背景相同的顔色來掩蓋這些關鍵詞。其實，這種做法很容易被搜尋引擎發現并糾正。
在有了網頁排名(page rank)以後，作弊者發現一個網頁被引用的連接配接越多，排名就可能越靠前，于是就有了專門賣連結和買連結的生意。比如，有人自己建立成百上千個網站，這些網站上沒有實質的内容，隻有到他們的客戶網站的連接配接。這種做法比重複關鍵詞要高明得多，但是還是不太難被發現。因為那些所謂幫别人提高排名的網站，為了維持生意需要大量地賣連結，是以很容易露馬腳。（這就如同造假鈔票，當某一種假鈔票的流通量相當大以後，就容易找到根源了。）再以後，又有了形形色色的作弊方式，我們就不在這裡一一贅述了。
幾年前，我加入Google做的第一件事就是消除網絡作弊。在Google最早發現搜尋引擎作弊的是Matt Cutts，他在我加入Google前幾個月開始研究這個問題，後來，辛格，馬丁和我先後加入進來。我們經過幾個月的努力，清除了一半的作弊者。(當然，以後抓作弊的效率就不會有這麼高了。）其中一部分網站從此"痛改前非"，但是還是有很多網站換一種作弊方法繼續作弊，是以，抓作弊成了一種長期的貓捉老鼠的遊戲。雖然至今還沒有一個一勞永逸地解決作弊問題的方法，但是，Google基本做到了對于任何已知的作弊方法，在一定時間内發現并清除它，進而總是将作弊的網站的數量控制在一個很小的比例範圍。
抓作弊的方法很像信号進行中的去噪音的辦法。學過資訊論和有信号處理經驗的讀者可能知道這麼一個事實，我們如果在發動機很吵的汽車裡用手機打電話，對方可能聽不清；但是如果我們知道了汽車發動機的頻率，我們可以加上一個和發動機噪音相反的信号，很容易地消除發動機的噪音，這樣，收話人可以完全聽不到汽車的噪音。事實上，現在一些高端的手機已經有了這種檢測和消除噪音的功能。消除噪音的流程可以概括如下：
在圖中，原始的信号混入了噪音，在數學上相當于兩個信号做卷積。噪音消除的過程是一個解卷積的過程。這在信号進行中并不是什麼難題。因為第一，汽車發動機的頻率是固定的，第二，這個頻率的噪音重複出現，隻要采集幾秒鐘的信号進行處理就能做到。從廣義上講，隻要噪音不是完全随機的、并且前後有相關性，就可以檢測到并且消除。（事實上，完全随機不相關的高斯白噪音是很難消除的。）
搜尋引擎的作弊者所作的事，就如同在手機信号中加入了噪音，使得搜尋結果的排名完全亂了。但是，這種人為加入的噪音并不難消除，因為作弊者的方法不可能是随機的（否則就無法提高排名了）。而且，作弊者也不可能是一天換一種方法，即作弊方法是時間相關的。是以，搞搜尋引擎排名算法的人，可以在搜集一段時間的作弊資訊後，将作弊者抓出來，還原原有的排名。當然這個過程需要時間，就如同采集汽車發動機噪音需要時間一樣，在這段時間内，作弊者可能會嘗到些甜頭。是以，有些人看到自己的網站經過所謂的優化（其實是作弊），排名在短期内靠前了，以為這種所謂的優化是有效的。但是，不久就會發現排名掉下去了很多。這倒不是搜尋引擎以前寬容，現在嚴厲了，而是說明抓作弊需要一定的時間，以前隻是還沒有檢測到這些作弊的網站而已。
還要強調一點，Google抓作弊和恢複網站原有排名的過程完全是自動的(并沒有個人的好惡），就如同手機消除噪音是自動的一樣。一個網站要想長期排名靠前，就需要把内容做好，同時要和那些作弊網站劃清界限。
數學之美 系列十八 － 矩陣運算和文本進行中的分類問題
我在大學學習線性代數時，實在想不出它除了告訴我們如何解線性方程外，還能有什麼别的用途。關于矩陣的許多概念，比如特征值等等，更是脫離日常生活。後來在數值分析中又學了很多矩陣的近似算法，還是看不到可以應用的地方。當時選這些課，完全是為了混學分的學位。我想，很多同學都多多少少有過類似的經曆。直到後來長期做自然語言處理的研究，我才發現數學家們提出那些矩陣的概念和算法，是有實際應用的意義的。
在自然語言進行中，最常見的兩類的分類問題分别是，将文本按主題歸類（比如将所有介紹亞運會的新聞歸到體育類）和将詞彙表中的字詞按意思歸類（比如将各種體育運動的名稱個歸成一類）。這兩種分類問題都可用通過矩陣運算來圓滿地、同時解決。為了說明如何用矩陣這個工具類解決這兩個問題的，讓我們先來來回顧一下我們在餘弦定理和新聞分類中介紹的方法。
分類的關鍵是計算相關性。我們首先對兩個文本計算出它們的内容詞，或者說實詞的向量，然後求這兩個向量的夾角。當這兩個向量夾角為零時，新聞就相關；當它們垂直或者說正交時，新聞則無關。當然，夾角的餘弦等同于向量的内積。從理論上講，這種算法非常好。但是計算時間特别長。通常，我們要處理的文章的數量都很大，至少在百萬篇以上，二次回标有非常長，比如說有五十萬個詞（包括人名地名産品名稱等等）。如果想通過對一百萬篇文章兩篇兩篇地成對比較，來找出所有共同主題的文章，就要比較五千億對文章。現在的計算機一秒鐘最多可以比較一千對文章，完成這一百萬篇文章相關性比較就需要十五年時間。注意，要真正完成文章的分類還要反複重複上述計算。
在文本分類中，另一種辦法是利用矩陣運算中的奇異值分解（Singular Value Decomposition，簡稱 SVD)。現在讓我們來看看奇異值分解是怎麼回事。首先，我們可以用一個大矩陣A來描述這一百萬篇文章和五十萬詞的關聯性。這個矩陣中，每一行對應一篇文章，每一列對應一個詞。
在上面的圖中，M=1,000,000，N=500,000。第 i 行，第 j 列的元素，是字典中第 j 個詞在第 i 篇文章中出現的權重詞頻（比如，TF/IDF)。讀者可能已經注意到了，這個矩陣非常大，有一百萬乘以五十萬，即五千億個元素。
奇異值分解就是把上面這樣一個大矩陣，分解成三個小矩陣相乘，如下圖所示。比如把上面的例子中的矩陣分解成一個一百萬乘以一百的矩陣X，一個一百乘以一百的矩陣B，和一個一百乘以五十萬的矩陣Y。這三個矩陣的元素總數加起來也不過1.5億，僅僅是原來的三千分之一。相應的存儲量和計算量都會小三個數量級以上。
三個矩陣有非常清楚的實體含義。第一個矩陣X中的每一行表示意思相關的一類詞，其中的每個非零元素表示這類詞中每個詞的重要性（或者說相關性），數值越大越相關。最後一個矩陣Y中的每一清單示同一主題一類文章，其中每個元素表示這類文章中每篇文章的相關性。中間的矩陣則表示類詞和文章雷之間的相關性。是以，我們隻要對關聯矩陣A進行一次奇異值分解，w 我們就可以同時完成了近義詞分類和文章的分類。（同時得到每類文章和每類詞的相關性）。
現在剩下的唯一問題，就是如何用計算機進行奇異值分解。這時，線性代數中的許多概念，比如矩陣的特征值等等，以及數值分析的各種算法就統統用上了。在很長時間内，奇異值分解都無法并行處理。（雖然 Google 早就有了MapReduce 等并行計算的工具，但是由于奇異值分解很難拆成不相關子運算，即使在 Google 内部以前也無法利用并行計算的優勢來分解矩陣。）最近，Google 中國的張智威博士和幾個中國的工程師及實習生已經實作了奇異值分解的并行算法，我認為這是 Google 中國對世界的一個貢獻。
數學之美 系列十九 － 馬爾可夫鍊的擴充 貝葉斯網絡 (Bayesian Networks)
我們在前面的系列中多次提到馬爾可夫鍊 (Markov
Chain)，它描述了一種狀态序列，其每個狀态值取決于前面有限個狀态。這種模型，對很多實際問題來講是一種很粗略的簡化。在現實生活中，很多事物互相的關系并不能用一條鍊來串起來。它們之間的關系可能是交叉的、錯綜複雜的。比如在下圖中可以看到，心血管疾病和它的成因之間的關系是錯綜複雜的。顯然無法用一個鍊來表示。
我們可以把上述的有向圖看成一個網絡，它就是貝葉斯網絡。其中每個圓圈表示一個狀态。狀态之間的連線表示它們的因果關系。比如從心血管疾病出發到吸煙的弧線表示心血管疾病可能和吸煙有關。當然，這些關系可以有一個量化的可信度 (belief)，用一個機率描述。我們可以通過這樣一張網絡估計出一個人的心血管疾病的可能性。在網絡中每個節點機率的計算，可以用貝葉斯公式來進行，貝葉斯網絡是以而得名。由于網絡的每個弧有一個可信度，貝葉斯網絡也被稱作信念網絡 (belief networks)。
和馬爾可夫鍊類似，貝葉斯網絡中的每個狀态值取決于前面有限個狀态。不同的是，貝葉斯網絡比馬爾可夫鍊靈活，它不受馬爾可夫鍊的鍊狀結構的限制，是以可以更準确地描述事件之間的相關性。可以講，馬爾可夫鍊是貝葉斯網絡的特例，而貝葉斯網絡是馬爾可夫鍊的推廣。
使用貝葉斯網絡必須知道各個狀态之間相關的機率。得到這些參數的過程叫做訓練。和訓練馬爾可夫模型一樣，訓練貝葉斯網絡要用一些已知的資料。比如在訓練上面的網絡，需要知道一些心血管疾病和吸煙、家族病史等有關的情況。相比馬爾可夫鍊，貝葉斯網絡的訓練比較複雜，從理論上講，它是一個 NP-complete 問題，也就是說，對于現在的計算機是不可計算的。但是，對于某些應用，這個訓練過程可以簡化，并在計算上實作。
值得一提的是 IBM Watson 研究所的茨威格博士 (Geoffrey Zweig) 和西雅圖華盛頓大學的比爾默 (Jeff Bilmes) 教授完成了一個通用的貝葉斯網絡的工具包，提供給對貝葉斯網絡有興趣的研究者。
貝葉斯網絡在圖像處理、文字處理、支援決策等方面有很多應用。在文字處理方面，語義相近的詞之間的關系可以用一個貝葉斯網絡來描述。我們利用貝葉斯網絡，可以找出近義詞和相關的詞，在 Google 搜尋和 Google 廣告中都有直接的應用。
數學之美 系列二十 －自然語言處理的教父 馬庫斯
我們在前面的系列中介紹和提到了一些年輕有為的科學家，邁克爾·柯林斯，艾裡克·布萊爾，大衛·雅讓斯基，拉納帕提等等，他們都出自賓夕法尼亞計算機系米奇·馬庫斯(Mitch Marcus)名下。就像許多武俠小說中描寫的，弟子都成了各派的掌門，師傅一定了不得。的确，馬庫斯雖然作為第一作者發表的論文并不多，但是從很多角度上講，他可以說是自然語言處理領域的教父。
馬庫斯教授長期當任賓夕法尼亞大學計算機系主任，直到他在幾年前從 AT&T 找到皮耶爾替代他為止。作為一個管理者，馬庫斯顯示出在自然處理和計算機科學方面的卓識的遠見。在指導博士生時，馬庫斯發現語料庫在自然語言進行中的重要性。馬庫斯嘔心瀝血，花了十幾年工夫建立了一系列标準的語料庫，提供給全世界的學者使用。這套被稱為 LDC 的語料庫，是當今全世界自然語言處理的所有學者都使用的工具。我們在以前的系列中講到，當今的自然語言處理幾乎都是使用給予統計的方法。要做統計，就需要大量有代表性的資料。利用這些資料開發一個自然語言處理系統的過程，可以統稱為訓練。比如，我們要訓練一個漢語分詞系統，我們需要一些已經分好詞的中文句子。當然這些句子需要有代表性。如果想知道一個分詞系統的準确性，我們也需要一些人工分好詞的句子進行測試。這些人工處理好的文字資料庫，成為語料庫(corpus)。如果每個研究室都人工建立幾個語料庫，不僅浪費時間精力，而且發表文章時，資料沒有可比性。是以，馬庫斯想到了建立一系列标準的語料庫為全世界的學者用。他利用自己的影響力讓美國自然科學基金會和 DARPA 出錢立項，聯絡的多所大學和研究機構，建立的數百個标準的語料庫。其中最著名的是 PennTree
Bank 的語料庫。PennTree Bank 覆寫多種語言（包括中文）。每一種語言，它有幾十萬到幾百萬字的有代表性的句子，每個句子都有的詞性标注，文法分析樹等等。LDC 語料庫如今已成為全世界自然語言處理科學家共用的資料庫。如今，在自然語言處理方面發表論文，幾乎都要提供基于 LDC 語料庫的測試結果。
馬庫斯給予他的博士生研究自己感興趣的課題的自由，這是他之是以桃李滿天下的原因。馬庫斯對幾乎所有的自然語言處理領域有獨到的見解。和許多教授讓博士生去做他拿到基金的項目，馬庫斯讓博士生提出自己有興趣的課題，或者用他已有的經費支援學生，或者為他們的項目區申請經費。馬庫斯高屋建瓴，能夠很快的判斷一個研究方向是否正确，省去了博士生很多 try-and-error 的時間。是以他的學生有些很快地拿到的博士學位。
作為系主任，馬庫斯在專業設定方面顯示出卓識的遠見。我有幸和他在同一個校務顧問委員會任職，一起讨論計算機系的研究方向。馬庫斯在幾年前網際網路很熱門、很多大學開始網際網路研究時，看到 bioinformatics (生物資訊學）的重要性，在賓夕法利亞大學設定這個專業，并且在其他大學還沒有意識到時，開始招聘這方面的教授。馬庫斯還建議一些相關領域的教授，包括後來的系主任皮耶爾把一部分精力轉到生物資訊學方面。馬庫斯同時向他擔任顧問的其他一些大學提出同樣的建議。等到網絡泡沫破裂以後，很多大學的計算機系開始向生物資訊學轉向，但是發現已經很難找到這些方面好的教授了。我覺得，當今中國的大學，最需要的就是馬庫斯這樣卓有遠見的管理者。
過幾天我又要和馬庫斯一起開顧問委員會的會議了，不知道這次他對計算機科學的發展有什麼見解。
數學之美系列二十一 － 布隆過濾器（Bloom Filter）
在日常生活中，包括在設計計算機軟體時，我們經常要判斷一個元素是否在一個集合中。比如在字處理軟體中，需要檢查一個英語單詞是否拼寫正确（也就是要判斷它是否在已知的字典中）；在 FBI，一個嫌疑人的名字是否已經在嫌疑名單上；在網絡爬蟲裡，一個網址是否被通路過等等。最直接的方法就是将集合中全部的元素存在計算機中，遇到一個新元素時，将它和集合中的元素直接比較即可。一般來講，計算機中的集合是用哈希表（hash table）來存儲的。它的好處是快速準确，缺點是費存儲空間。當集合比較小時，這個問題不顯著，但是當集合巨大時，哈希表存儲效率低的問題就顯現出來了。比如說，一個象 Yahoo,Hotmail 和 Gmai 那樣的公衆電子郵件（email）提供商，總是需要過濾來自發送垃圾郵件的人（spamer）的垃圾郵件。一個辦法就是記錄下那些發垃圾郵件的 email 位址。由于那些發送者不停地在注冊新的位址，全世界少說也有幾十億個發垃圾郵件的位址，将他們都存起來則需要大量的網絡伺服器。如果用哈希表，每存儲一億個 email 位址， 就需要 1.6GB 的記憶體（用哈希表實作的具體辦法是将每一個 email 位址對應成一個八位元組的資訊指紋 googlechinablog.com/2006/08/blog-post.html，然後将這些資訊指紋存入哈希表，由于哈希表的存儲效率一般隻有 50%，是以一個 email 位址需要占用十六個位元組。一億個位址大約要 1.6GB， 即十六億位元組的記憶體）。是以存貯幾十億個郵件位址可能需要上百 GB 的記憶體。除非是超級計算機，一般伺服器是無法存儲的。
今天，我們介紹一種稱作布隆過濾器的數學工具，它隻需要哈希表 1/8 到 1/4 的大小就能解決同樣的問題。
布隆過濾器是由巴頓.布隆于一九七零年提出的。它實際上是一個很長的二進制向量和一系列随機映射函數。我們通過上面的例子來說明起工作原理。
假定我們存儲一億個電子郵件位址，我們先建立一個十六億二進制（比特），即兩億位元組的向量，然後将這十六億個二進制全部設定為零。對于每一個電子郵件位址 X，我們用八個不同的随機數産生器（F1,F2, ...,F8） 産生八個資訊指紋（f1, f2, ..., f8）。再用一個随機數産生器 G 把這八個資訊指紋映射到 1 到十六億中的八個自然數 g1, g2, ...,g8。現在我們把這八個位置的二進制全部設定為一。當我們對這一億個 email 位址都進行這樣的處理後。一個針對這些 email 位址的布隆過濾器就建成了。（見下圖）
現在，讓我們看看如何用布隆過濾器來檢測一個可疑的電子郵件位址 Y 是否在黑名單中。我們用相同的八個随機數産生器（F1, F2, ..., F8）對這個位址産生八個資訊指紋 s1,s2,...,s8，然後将這八個指紋對應到布隆過濾器的八個二進制位，分别是 t1,t2,...,t8。如果 Y 在黑名單中，顯然，t1,t2,..,t8 對應的八個二進制一定是一。這樣在遇到任何在黑名單中的電子郵件位址，我們都能準确地發現。
布隆過濾器決不會漏掉任何一個在黑名單中的可疑位址。但是，它有一條不足之處。也就是它有極小的可能将一個不在黑名單中的電子郵件位址判定為在黑名單中，因為有可能某個好的郵件位址正巧對應個八個都被設定成一的二進制位。好在這種可能性很小。我們把它稱為誤識機率。在上面的例子中，誤識機率在萬分之一以下。
布隆過濾器的好處在于快速，省空間。但是有一定的誤識别率。常見的補救辦法是在建立一個小的白名單，存儲那些可能别誤判的郵件位址。