2801# 數(shù)學(xué)之美-Statistical Language Models
Google 的使命是 "整合全球信息，讓人人能獲取，使人人能受益"，研究如何讓機器對信息、語言做最好的處理和理解。喬姆斯基提出 “形式語言” 以后，人們更堅定了利用語法規(guī)則的辦法進行文字處理的信念。
此前，數(shù)學(xué)家兼信息論的祖師爺就提出了用數(shù)學(xué)的辦法處理自然語言的想法（浪潮之巔里對此人印象極為深刻），當(dāng)時的計算機條件根本無法滿足大量信息處理的需要。
還有一位首先成功利用數(shù)學(xué)方法解決自然語言處理問題的是語音和語言處理大師Fred Jelinek，當(dāng)時賈里尼克在 IBM 公司做學(xué)術(shù)休假，領(lǐng)導(dǎo)了一批杰出的科學(xué)家利用大型計算機來處理人類語言問題。統(tǒng)計語言模型就是在那個時候提出的。
自然語言處理（NLP：Natural Language Process）的領(lǐng)域機器翻譯可以包括：語音識別、印刷體、手寫體識別、拼寫糾錯、漢字輸入、文獻查詢。文中沒有提及的有情感分析（Sentiment Analysis）和機器翻譯（美國標(biāo)準(zhǔn)局NIST對所有的機器翻譯系統(tǒng)進行了評測，Google 的系統(tǒng)是不僅是全世界最好的，而且高出所有基于規(guī)則的系統(tǒng)很多。
）。
我們都需要知道一個文字序列是否能構(gòu)成一個大家能理解的句子，顯示給使用者。對這個問題，我們可以用一個簡單的統(tǒng)計模型來解決這個問題。此處作者用條件概率公式解釋了及其對于語言識別的模式（馬爾可夫假設(shè)）。
數(shù)學(xué)的精妙就在于把一些復(fù)雜的問題變得如此的簡單，也是本書的主題。
2802#數(shù)學(xué)之美-NLP中文分詞
中文分詞是統(tǒng)計語言模型在中文處理中的一個應(yīng)用，含有分詞的語言包括中日韓等在自然書寫時沒有分割的語言，在計算機處理時首先應(yīng)進行分詞處理。
一般分詞辦法就是查字典，這種方法最早是由北京航天航空大學(xué)梁南元教授提出。 “查字典” 法把一個句子從左向右掃描一遍，遇到字典里有的詞便進行標(biāo)識，遇到復(fù)合詞（比如 “上海大學(xué)”）就找最長的詞匹配，遇到不認識的字串就分割成單字詞，于是簡單的分詞就完成了。
90年前后，清華大學(xué)郭進博士用統(tǒng)計語言模型成功解決分詞二義性問題，將漢語分詞錯誤率降低了一個數(shù)量級。因此只要利用統(tǒng)計語言模型計算出每種分詞后句子出現(xiàn)的概率，并找出其中概率最大的，就能夠找到最好的分詞方法。
實現(xiàn)的技巧，窮舉所有可能的分詞方法并計算出每種可能性下句子的概率，計算量是相當(dāng)大的。因此，可以把它看成是一個動態(tài)規(guī)劃（Dynamic Programming) 的問題，并利用 “維特比” 算法快速地找到最佳分詞。
Ref. Computational Linguistics” （《計算機語言學(xué)》）
2803#數(shù)學(xué)之美-信息論
一些關(guān)鍵詞：隱含馬爾可夫模型 條件概率 貝葉斯公式 馬爾可夫鏈 信息熵 冗余度 互信息
七十年代，當(dāng)時 IBM 的 Fred Jelinek（關(guān)于賈的更多故事可以看《浪潮之巔》） 和卡內(nèi)基·梅隆大學(xué)的 Jim and Janet Baker 分別獨立地提出用隱含馬爾可夫模型來識別語音，語音識別的錯誤率相比人工智能和模式匹配等方法降低了三倍。
八十年代李開復(fù)堅持采用隱含馬爾可夫模型的框架， 成功地開發(fā)了世界上第一個大詞匯量連續(xù)語音識別系統(tǒng) Sphinx。
1948 年，Shannon提出了“信息熵”（Entropy）（一般用符號 H 表示，單位比特，從而解決了對信息的量化度量問題，信息熵很有意思，詳見Wikipedia）用來度量信息的大小。
原理則是假設(shè)一條信息的信息量大小和它的不確定性有直接的關(guān)系?？梢哉J為，信息量的度量就等于不確定性的多少。信息量的比特數(shù)和所有可能情況的對數(shù)函數(shù) log 有關(guān)，一個比特是一位二進制數(shù)，計算機中的一個字節(jié)是八個比特。
e.g. 一本五十萬字的中文書，信息量大約是 250 萬比特，如果用一個好的算法壓縮一下，整本書可以存成一個 320KB 的文件。
冗余度：如果用兩字節(jié)的國標(biāo)編碼存儲這本書，大約需要 1MB 大小，是壓縮文件的三倍。這兩個數(shù)量的差距，在信息論中稱作"冗余度"（Redundancy)。
如果一本書重復(fù)的內(nèi)容很多，它的信息量就小，冗余度就大。不同語言的冗余度差別很大，而漢語在所有語言中冗余度是相對小的。這和人們普遍的認識”漢語是最簡潔的語言"是一致的。
信息熵正是對不確定性的衡量，因此信息熵可以直接用于衡量統(tǒng)計語言模型的好壞。
信息論中僅次于熵的另外兩個重要的概念是“互信息”（Mutual Information) 和“相對熵”（Kullback-Leibler Divergence)。 互信息是信息熵的引申概念，它是對兩個隨機事件相關(guān)性的度量。
2804#數(shù)學(xué)之美-檢索原理——布爾運算
George Boole是十九世紀(jì)英國一位小學(xué)數(shù)學(xué)老師（他生前沒有人認為他是數(shù)學(xué)家，原因就是布爾運算本身= =）。
布爾在工作之余，喜歡閱讀數(shù)學(xué)論著、思考數(shù)學(xué)問題。1854 年“思維規(guī)律”（An Investigation of the Laws of Thought, on which are founded the Mathematical Theories of Logic and Probabilities）一書，第一次向人們展示了如何用數(shù)學(xué)的方法解決邏輯問題。
布爾運算所包含的元素運算的元素只有兩個1 （TRUE， 真) 和 0。直到 1938 年Shanon在他的碩士論文中指出用布爾代數(shù)來實現(xiàn)開關(guān)電路，才使得布爾代數(shù)成為數(shù)字電路的基礎(chǔ)。所有的數(shù)學(xué)和邏輯運算，加、減、乘、除、乘方、開方等等，全部能轉(zhuǎn)換成二值的布爾運算。
早期的文獻檢索查詢系統(tǒng)大多基于數(shù)據(jù)庫，嚴格要求查詢語句符合布爾運算。今天的搜索引擎相比之下要聰明的多，它自動把用戶的查詢語句轉(zhuǎn)換成布爾運算的算式。當(dāng)然在查詢時，不能將每篇文獻掃描一遍，來看看它是否滿足上面三個條件，因此需要建立一個索引。
因此，整個索引就變得非常之大，以至于不可能用一臺計算機存下。大家普遍的做法是根據(jù)網(wǎng)頁的序號將索引分成很多份（Shards)，分別存儲在不同的服務(wù)器中。每當(dāng)接受一個查詢時，這個查詢就被分送到許許多多服務(wù)器中，這些服務(wù)器 同時并行處理用戶請求，并把結(jié)果送到主服務(wù)器進行合并處理，最后將結(jié)果返回給用戶。不管索引如何復(fù)雜，查找的基本操作仍然是布爾運算。
布爾運算把邏輯和數(shù)學(xué)聯(lián)系起來了。它的最大好處是容易實現(xiàn)和速度快，這對于海量信息查找非常關(guān)鍵。
不足是只能給出是與否的判斷，而不能給出量化的度量。因此所有搜索引擎在內(nèi)部檢索完畢后，都要對符合要求的網(wǎng)頁根據(jù)相關(guān)性排序，然后才返回給用戶。
2805#數(shù)學(xué)之美-圖論
離散數(shù)學(xué)是當(dāng)代數(shù)學(xué)的一個重要分支，也是計算機科學(xué)的數(shù)學(xué)基礎(chǔ)。它包括數(shù)理邏輯、集合論、圖論和近世代數(shù)四個分支，數(shù)理邏輯便基于布爾運算。簡歷搜索引擎的引索主要依靠圖論中的遍歷算法（Traverse），圖論的起源可追溯到數(shù)學(xué)家歐拉。
關(guān)于圖的算法有很多，但最重要的是圖的遍歷算法，也就是如何通過弧訪問圖的各個節(jié)點。
此處介紹了兩種圖的算法，以地圖繪制為例，為了達到通過弧訪問圖的每個節(jié)點，可以分為：“廣度優(yōu)先算法”（BFS)，盡可能廣地訪問每個節(jié)點所直接連接的其他節(jié)點；
”深度優(yōu)先算法”（DFS)，因為它是一條路走到黑。
圖論的遍歷算法可以理解為，互聯(lián)網(wǎng)是一張大地圖，每個網(wǎng)頁是一個節(jié)點，超鏈接是連接他們的弧。瀏覽器是通過這些隱含的網(wǎng)址轉(zhuǎn)到相應(yīng)的網(wǎng)頁中的。這些隱含在文字背后的網(wǎng)址稱為”超鏈接"。有了超鏈接，我們可以從任何一個網(wǎng)頁出發(fā)，用圖的遍歷算法，自動地訪問到每一個網(wǎng)頁并把它們存起來。完成這個功能的程序叫做網(wǎng)絡(luò)爬蟲，或者在一些文獻中稱為"機器人" （Robot)。
在網(wǎng)絡(luò)爬蟲中，我們使用一個稱為"哈希表"(Hash Table)的列表而不是一個記事本紀(jì)錄網(wǎng)頁是否下載過的信息。因此，一個商業(yè)的網(wǎng)絡(luò)爬蟲需要有成千上萬個服務(wù)器，并且由快速網(wǎng)絡(luò)連接起來。如何建立這樣復(fù)雜的網(wǎng)絡(luò)系統(tǒng)，如何協(xié)調(diào)這些服務(wù)器的任務(wù)，就是網(wǎng)絡(luò)設(shè)計和程序設(shè)計的藝術(shù)了。
在計算機中一個好的算法，應(yīng)該向阿卡 47 沖鋒槍那樣簡單、有效、可靠性好而且容易讀懂(或者說易操作），而不應(yīng)該是故弄玄虛。Google 工程師Amit Singhal就是為 Google 設(shè)計阿卡 47 沖鋒槍的人，在公司內(nèi)部，Google 的排序算法便是以他的名字命名的。Singhal早年是從搜索大師Salton，畢業(yè)后就職于AT&T 實驗室，并在這里確立了他在學(xué)術(shù)界的地位。
2806#數(shù)學(xué)之美-余弦定理與新聞分類
余弦定理和新聞的分類似乎是兩件八桿子打不著的事。但是它們確有緊密的聯(lián)系。具體說，新聞的分類很大程度上依靠余弦定理。Google 的新聞是自動分類和整理的。所謂新聞的分類無非是要把相似的新聞放到一類中。計算機其實讀不懂新聞，它只能快速計算。這就要求我們設(shè)計一個算法來算出任意兩篇新聞的相似性。為了做到這一點，我們需要想辦法用一組數(shù)字來描述一篇新聞。
向量代數(shù)中，向量實際上是多維空間中有方向的線段，如果兩個向量的方向一致（夾角為0）那么這兩個向量就相近。確定兩向量是否一致，就用到余弦定理計算向量夾角了。
任何一段信息文字，都可以對應(yīng)一個不太長的隨機數(shù)，作為區(qū)別它和其它信息的指紋（Fingerprint)。只要算法設(shè)計的好，任何兩短信息的指紋都很難重復(fù)，如同人類指紋。新信息指紋在加密、信息壓縮和處理中有著廣泛的應(yīng)用。
產(chǎn)生信息指紋的關(guān)鍵算法是偽隨機數(shù)產(chǎn)生器算法prng，最早的prng算法是由馮諾伊曼提出來的。他的辦法很簡單，即將一個數(shù)的平方掐頭去尾，取中間的幾位數(shù)。e.g. 一個四位的二進制數(shù) 1001（相當(dāng)于十進制的9），其平方為 01010001 (十進制的 81）掐頭去尾剩下中間的四位 0100。當(dāng)然這種方法產(chǎn)生的數(shù)字并不很隨機，也就是說兩個不同信息很有可能有同一指紋。
信息指紋的用途遠不止網(wǎng)址的消重，信息指紋的的孿生兄弟是密碼。信息指紋的一個特征是其不可逆性, 也就是說,無法根據(jù)信息指紋推出原有信息，這種性質(zhì)正是網(wǎng)絡(luò)加密傳輸所需要的。值得一提的事，SHA1以前被認為是沒有漏洞的，現(xiàn)在已經(jīng)被中國的王小云教授證明存在漏洞。
