原文引自 豆瓣《數(shù)學(xué)之美》-筆記總結(jié)

第1章 文字和語言vs數(shù)字和信息

講述了文字、數(shù)字和語言的歷史，目的是幫助讀者感受語言和數(shù)字的內(nèi)在聯(lián)系嘶朱。

任何事物的規(guī)律性是內(nèi)在的珍促，不隨著載體的改變而改變。

通信方式：信息源編碼——信道傳播——接收者解碼

文字和數(shù)字的歷史：

簡單的聲音不能滿足溝通的需求拆座，語言由此產(chǎn)生——隨著對新鮮事物的學(xué)習(xí)，用來描述共同因素的語言被抽象成詞匯——語言和詞匯多到難以記憶，便產(chǎn)生了文字——文字多到難以記憶時酱畅，概念的概括和歸納就開始了——文字按照意思來聚類會產(chǎn)生歧義，可以利用上下文來消除——不同文明相互融合江场，于是產(chǎn)生翻譯——記錄物件數(shù)量纺酸，計數(shù)系統(tǒng)產(chǎn)生（10位以內(nèi)掰指頭，10位后使用10進(jìn)制址否，后產(chǎn)生數(shù)量級）——阿拉伯?dāng)?shù)字的產(chǎn)生標(biāo)志著數(shù)字和文字的分離餐蔬，奠定了數(shù)學(xué)未來的發(fā)展。

【事物發(fā)展到一定階段時，會變得復(fù)雜起來用含，這時會有新的事物來代替它矮慕。新的事物看起來簡單，但這種簡單也是它的復(fù)雜性之所在啄骇，因為它又需要其它事物來進(jìn)行解釋痴鳄。從這方面來說，事物之間并不存在好壞之分缸夹，放到合適的位置上便是好的痪寻。】

關(guān)于翻譯：

翻譯之所以能達(dá)成虽惭，是因為不同的文字在記錄信息上的能力是等價的橡类。即文字只是信息的載體，而非信息本身芽唇。信息冗余是信息安全的保障顾画，只要有一份內(nèi)容完好保存下來，原有信息就不會丟失匆笤。雙語或者多語的對照語料對翻譯至關(guān)重要研侣，它是機(jī)器翻譯的基礎(chǔ)。

文字和語言背后的數(shù)學(xué)：

楔形/象形文字誕生——為方便雕刻炮捧，簡化成22個字母——為方便學(xué)習(xí)庶诡，拼寫和讀音結(jié)合（將物體外表編碼為抽象概念，常用字短咆课，生僻字長）——為節(jié)省信道末誓，傳播信息前需進(jìn)行壓縮，接收后再解壓书蚪，并校驗——語法使語言表達(dá)更準(zhǔn)確喇澡、更豐富

關(guān)于語言、語法：

語言堅持從真實(shí)語句文本（即語料）出發(fā)善炫，語法堅持從規(guī)則出發(fā)撩幽，前者在自然語言處理上獲勝。

第2章 自然語言規(guī)則——從規(guī)則到統(tǒng)計

自然語言的發(fā)展：

第一階段箩艺，局限在人類學(xué)習(xí)語言的方式上（即句法分析）窜醉；第二階段，基于數(shù)學(xué)模型和統(tǒng)計的方法艺谆，并取得突破榨惰。

句法分析：

將句子分為主語、謂語静汤、句號三部分琅催，然后對每一個部分進(jìn)行分析居凶，得到語法分析樹。

不足在于：一個短短的句子需要很復(fù)雜的文法規(guī)則藤抡，這些文法規(guī)則寫到后來甚至?xí)霈F(xiàn)矛盾侠碧，為了解決這些矛盾，還需要說明各個規(guī)則特定的使用環(huán)境缠黍；自然語言中的詞很難用文法去描述弄兜，嚴(yán)重依賴于上下文，甚至是“世界知識”或者“常識”瓷式，所以很難用計算機(jī)去解析替饿。

基于統(tǒng)計方法的發(fā)展：

上世紀(jì)70年代，IBM利用統(tǒng)計方法將語音識別率從70%提到90%贸典，基于統(tǒng)計的方法核心模型是通信系統(tǒng)加隱含馬爾科夫模型（這個系統(tǒng)的輸入輸出都是一維符號系列视卢，且保持原有次序）；

80年代廊驼，IBM提出提出基于統(tǒng)計的機(jī)器翻譯方法据过，因數(shù)據(jù)、模型欠缺蔬充，解決不了語序顛倒問題蝶俱；

90年代班利，隨著計算機(jī)能力的提高和數(shù)據(jù)量的增加饥漫，統(tǒng)計方法得以實(shí)現(xiàn)

第3章 統(tǒng)計語言模型

講述如何利用統(tǒng)計語言模型處理自然語言，以及如何確保結(jié)果的準(zhǔn)確性罗标、減少不平滑庸队。

統(tǒng)計語言模型：用來處理自然語言的上下文關(guān)系，它是所有自然語言處理的基礎(chǔ)闯割。并廣泛應(yīng)用于機(jī)器翻譯彻消、語音識別、印刷體或手寫體識別宙拉、拼音糾錯宾尚、漢字輸入和文獻(xiàn)查詢。

利用概率大小來衡量一個文字序列是否能構(gòu)成大家理解而且有意義的句子：

序列S出現(xiàn)的概率W谢澈，等于序列中每一個詞出現(xiàn)的條件概率相乘煌贴，W出現(xiàn)的概率同他前面的所有詞有關(guān)，即P（S）=P（W1锥忿，W2牛郑，...，Wn）=P（W1）P（W2|W1）P(W3|W1,W2)...P(Wn|W1,W2敬鬓，...,W(n-1)）淹朋。

由于計算復(fù)雜笙各，所以就假設(shè)任意一個詞Wi出現(xiàn)的概率只同它前面的詞W（i-1）有關(guān)，即P（S）=P（W1）*P（W2|W1）...P（Wi|W(i-1)）...P(Wn|W(n-1))）

P（W(i-1)础芍，Wi）=#(W(i-1)杈抢，Wi)/# （注：#（W(i-1)，Wi）為W(i-1),Wi這對詞在統(tǒng)計的文本中前后相鄰出現(xiàn)的次數(shù)仑性，#為語料庫的大写焊小）

N-1階馬爾科夫模型：

假設(shè)文本中的每個詞Wi和前面的N-1個詞有關(guān)系，而與更前面的詞無關(guān)虏缸，則P（Wi|W1鲫懒，W2，...刽辙，W(i-1)）=P(Wi|W(i-n+1)窥岩，W(i-n+2)，...,W(i-1)）宰缤。

n=1的一元模型實(shí)際上是一個上下文無關(guān)的模型颂翼，n的值一般為2，或3慨灭。n值很少取更高值的原因朦乏，一是n越大，復(fù)雜度n方越大氧骤；二是自然語言中上下文的相關(guān)性可能跨度非常大呻疹，甚至可以從一個段落跨到另一個段落，所以即使模型階數(shù)n再高筹陵，也沒有太多意義刽锤。這是馬爾科夫假設(shè)的局限。

模型的訓(xùn)練：通過對語料的統(tǒng)計朦佩，得到模型中的參數(shù)并思。

大數(shù)定理： 在試驗不變的條件下，重復(fù)試驗多次语稠，隨機(jī)事件的頻率近似于它的概率宋彼。偶然中包含著某種必然。

我們需要足夠的語料才能得到較為可靠的概率仙畦。然而語料過多输涕，可能會導(dǎo)致大部分條件概率為0的情況，這種模型叫做“不平滑”议泵。

減少不平滑：

古德-圖靈估計占贫，對于沒有看見的事件，我們不能認(rèn)為它的發(fā)生概率就是零先口，因此我們從概率的總量中型奥，分配一個很小的概率給予這些沒有看見的事件瞳收。這樣一來，看見的時間的概率總和就要小于1了厢汹。即“越是不可信的統(tǒng)計折扣越多”螟深。

設(shè)語料庫中出現(xiàn)r次的詞有Nr個，則當(dāng)r比較小時烫葬，它的統(tǒng)計可能不可靠界弧，經(jīng)過古德-圖靈估計后的相對頻度r’=（r+1）*N(r+1)/N(r).

刪除插值法，因為一元組（Wi）出現(xiàn)的次數(shù)平均比二元組（W(i-1)搭综，Wi）出現(xiàn)的次數(shù)要高得多垢箕，根據(jù)大數(shù)定理，它的頻度更接近概率分布兑巾。所依条获，用低階語言模型和高階模型進(jìn)行線性差值來達(dá)到平滑的目的。即連續(xù)三個字出現(xiàn)的概率=T倍連續(xù)三個字出現(xiàn)的概率+t倍連續(xù)兩個字出現(xiàn)的概率+（1-T-t）倍該字單獨(dú)出現(xiàn)的概率

語料的選冉琛：

訓(xùn)練語料和模型應(yīng)用的領(lǐng)域須保持一致帅掘，以減少噪音；語料數(shù)據(jù)通常是越多越好堂油，可以利用平滑過渡方法解決小/零概率事件修档；最好能預(yù)處理能具有規(guī)律的、量比較大的噪音府框。

第4章 談?wù)勚形姆衷~

利用統(tǒng)計模型進(jìn)行自然語言處理吱窝，這些語言模型是建立在詞的基礎(chǔ)上的，因為詞是語義的最小單位寓免。在此之前癣诱，需要對句子進(jìn)行分詞。

常見分詞方法——查字典：

把一個句子從左往右掃描一遍袜香，遇到字典里有的詞就標(biāo)識出來，遇到復(fù)核詞（如“上海大學(xué)”）就找最長的詞匹配鲫惶，遇到不認(rèn)識的字串就分割成單字詞蜈首。該方法能解決七八成問題，然而對二義性的分割無能為力（如發(fā)展-中-國家欠母、發(fā)展-中國-家）欢策。

處理二義性：

最好的分詞方法應(yīng)該保證分完詞后，該句子出現(xiàn)的概率最大赏淌，但是如果窮舉所有的分詞方法并計算所有可能的概率踩寇，計算率太大。對此六水，不同的應(yīng)用，分詞的顆粒度應(yīng)采用不同的大小不瓶，即不同的應(yīng)用應(yīng)該有不同的分詞系統(tǒng)紊扬。

關(guān)于詞的顆粒度和層次：

不同的人對詞的切分方法差異甚大，其主要原因是對詞的顆粒度的認(rèn)識不一致荣茫。在不同的應(yīng)用中，詞的顆粒度可能很不一樣场靴，如在機(jī)器翻譯中啡莉，顆粒度大翻譯效果好，在網(wǎng)頁搜索中則相反旨剥。如果對不同的應(yīng)用構(gòu)造不同的分詞系統(tǒng)咧欣，會很浪費(fèi)，最好的方法是讓一個分詞器同時支持不同層次的詞的切分轨帜，然后由不同的應(yīng)用自行決定采用哪個顆粒的切分该押。

分詞器的準(zhǔn)確性：

應(yīng)避免越界型錯誤、覆蓋型錯誤阵谚、顆粒不一致蚕礼。越界型錯誤，如“北京大學(xué)生”分為“北京大學(xué)——生”梢什。覆蓋型錯誤奠蹬，如"賈里尼克”拆成了四個字。錯誤要盡可能消除嗡午。關(guān)于顆粒不一致囤躁，需要多做些數(shù)據(jù)挖掘工作，完善不同應(yīng)用的復(fù)合詞詞典荔睹。

第5章 隱含馬爾可夫模型

通信的過程本質(zhì)上就是：發(fā)送者編碼——信道傳播——接收者解碼狸演。如何根據(jù)接收端的觀測信號O1,O2,...O3...來推測信號源的發(fā)送信息S1,S2,S3,...呢？我們需要從所有的信息源中找到最可能產(chǎn)生觀測信號的那一個信息僻他。

隱含馬爾可夫模型：

假設(shè)模型在每個時刻t會輸出一個符號Ot宵距，而且Ot僅和St相關(guān)（即馬爾科夫假設(shè)），我們可以計算出某個特定狀態(tài)序列S1,S2,S3,...產(chǎn)生輸出符O1,O2,...O3...號的概率吨拗。如何讓找到概率最大值满哪，需運(yùn)用維特比算法（后面會提到）。（注：St可能會生成Ot劝篷，即生成概率哨鸭；也可能會轉(zhuǎn)化為S(t-1)，即轉(zhuǎn)移概率）

隱含馬爾科夫模型的訓(xùn)練：

首先有三個基本問題：1娇妓、給定一個模型像鸡，如何計算某個特定輸出序列的概率；2哈恰、給定一個模型和某個特定的輸出序列只估，如何找到最可能產(chǎn)生這個輸出的狀態(tài)序列志群；3、給定足夠的觀測數(shù)據(jù)仅乓，如何估算隱含馬爾可夫模型的參數(shù)赖舟。

問題1可參考賈里尼克《Statistical Methods for Speech Recognition 》，問題2使用維特比算法來解碼（后面會提到）夸楣。

關(guān)于問題3宾抓。通過大量的觀察信號推測模型參數(shù)的生成概率、轉(zhuǎn)移概率豫喧，以尋找最可能的模型石洗，主要使用的是鮑穆-韋爾奇算法。首先紧显，找到能夠產(chǎn)生O序列的模型參數(shù)讲衫；然后，計算出這個模型產(chǎn)生O的概率孵班，以及產(chǎn)生O的所有可能路徑和產(chǎn)生這些路徑的概率。最終篙程，計算出一組新的模型參數(shù)枷畏，根據(jù)新的模型參數(shù)再繼續(xù)尋找更好的模型參數(shù)。以此類推虱饿，直到目標(biāo)函數(shù)的輸出概率達(dá)到最大化拥诡。這個過程被稱為期望最大化，即EM氮发。EM能保證算法收斂到一個局部最優(yōu)點(diǎn)渴肉，卻不能保證找到全局最優(yōu)點(diǎn)。

第6章 信息的度量和作用

信息嫡：即我們弄清楚一件事所需要的信息量爽冕。信息量就等于不確定性的多少仇祭。假設(shè)一件事由n部分組成，每件事發(fā)生的概率為p(i)扇售，則該事信息嫡為H=-（p1.logp1+p2.logp2+...+pn.logpn）前塔，單位是比特〕斜可以用來衡量統(tǒng)計語言模型的好壞。

信息的作用在于消除不確定性食零，這些信息可以針對事物本身困乒，也可以是與關(guān)注對象相關(guān)的信息。

條件嫡：假定x和y是兩個隨機(jī)變量贰谣，我們知道了y隨x一起出現(xiàn)的概率娜搂，以及x的概率迁霎，那我們就可以求出y的概率。

互信息就是對兩個隨機(jī)事件“相關(guān)性”的量化度量百宇。例舉互信息在解決詞義二義性上的運(yùn)用考廉，bush一詞可以解釋為：灌木叢、布什携御，區(qū)分辦法如下：首先從大量文本中找出和總統(tǒng)布什一起出現(xiàn)的互信息最大的一些詞昌粤，比如：總統(tǒng)、美國啄刹、國會等涮坐；同理找出和灌木叢一起出現(xiàn)的互信息量大的詞，比如土壤誓军、樹木袱讹、植物等。翻譯時昵时，看看上下文中哪類相關(guān)的詞多就可以了捷雕。

相對嫡也可以用來衡量兩個取值為正數(shù)的函數(shù)相關(guān)性。相對嫡越大壹甥，兩個函數(shù)的差異越大救巷；反之差異越小。對于概率分布或者概率密度函數(shù)盹廷，如果取值均大于零征绸，相對嫡可以度量兩個隨機(jī)分布的差異性，如用來衡量兩個常用詞在不同文本中的概率分布俄占，看它們是否同義管怠，或者根據(jù)兩篇文章中不同詞的分布，看看它們的內(nèi)容是否相近缸榄。

因為有了上下文條件渤弛，所以對于高階的語言模型，應(yīng)該用條件嫡甚带；如果再考慮從訓(xùn)練語料和真實(shí)應(yīng)用的文本中得到的概率函數(shù)有偏差她肯，就需要再引入相對嫡的概念。

第7章 賈里尼克和現(xiàn)代語言處理

賈里尼克和作者花在學(xué)校里讀書的時間比99%的孩子都少鹰贵，卻比他們的建樹都高晴氨。他們都認(rèn)為，第一碉输，小學(xué)生沒和中學(xué)生其實(shí)沒必要花那么多時間讀書籽前，而他們的社會經(jīng)驗、生活能力以及在那時樹立起的志向?qū)椭麄兊囊簧５诙澹袑W(xué)階段花很多時間比同伴多讀的課程肄梨，在大學(xué)以后用非常短的時間就可以讀完，因為大學(xué)階段挠锥，人的理解力要強(qiáng)得多众羡。第三，學(xué)習(xí)是一輩子的事蓖租，興趣是最好的動力粱侣。第四，書本的內(nèi)容可以早學(xué)菜秦，也可以晚學(xué)甜害，但是錯過了成長階段確是無法彌補(bǔ)回來的。

第8章 簡單之美——布爾代數(shù)和搜索引擎的應(yīng)用

技術(shù)分為術(shù)和道兩種球昨，具體的做事方法是術(shù)尔店，做事的原理和原則是道。追求術(shù)的人一輩子工作都很辛苦主慰，只有掌握了搜索的本質(zhì)和精髓才能游刃有余嚣州。真正做好一件事沒有捷徑，作者在Google做搜索時共螺，每天至少要分析20個左右不好的搜索結(jié)果该肴。

搜索引擎的原理：自動下載盡可能多的網(wǎng)頁；建立快速有效的索引藐不；根據(jù)相關(guān)性對網(wǎng)頁進(jìn)行公平準(zhǔn)確的排序匀哄。

布爾代數(shù)：元素（真、假）雏蛮、基本運(yùn)算（與涎嚼、或、非）挑秉。文獻(xiàn)檢索時法梯，需要根據(jù)是否含關(guān)鍵字返回相應(yīng)的參數(shù)：真或假。這樣邏輯推理和計算就合二為一了犀概。

索引：是一張大表立哑，表的每一行對應(yīng)一個關(guān)鍵字，以及包含該關(guān)鍵字的文獻(xiàn)序號姻灶。為方便網(wǎng)頁排名铛绰，索引中還有一些附加信息，諸如每個詞出現(xiàn)的位置产喉、次數(shù)等等至耻，使得索引變得非常之大若皱，一臺服務(wù)器難以存儲镊叁。普遍的做法是根據(jù)網(wǎng)頁的序號將索引分成很多份尘颓，分別存儲在不同的服務(wù)器中，這些服務(wù)器同時并行處理用戶的請求晦譬，并把結(jié)果送到主服務(wù)器進(jìn)行合并處理疤苹，最終將結(jié)果返回給用戶。

需要根據(jù)網(wǎng)頁的重要性敛腌、質(zhì)量和訪問的頻率建立常用和非常用等不同級別的索引卧土。常用的索引需要訪問速度快、更新快像樊，附加信息多尤莺。

真理在形式上從來是簡單的，而不是復(fù)雜和含混的生棍。

第9章 圖論和網(wǎng)絡(luò)爬蟲

圖論中的遍歷算法：

圖論中的圖由一些節(jié)點(diǎn)和連接這些節(jié)點(diǎn)的弧組成颤霎。順著弧把所有的節(jié)點(diǎn)都走一遍，記錄訪問過的節(jié)點(diǎn)涂滴，同時避免多次訪問或漏掉某個節(jié)點(diǎn)友酱，該方法叫做遍歷。常見遍歷算法有廣度優(yōu)先（BFS-盡可能廣得訪問每一個節(jié)點(diǎn)所直接連接的其他節(jié)點(diǎn)）和深度優(yōu)先（DFS-從頭一路走到黑）柔纵。

網(wǎng)絡(luò)爬蟲：有了超鏈接缔杉，我們可以利用遍歷算法，自動地訪問每一個網(wǎng)頁搁料，并把它們存起來或详。完成該功能的程序即網(wǎng)絡(luò)爬蟲。

圖論定理：如果一個圖能夠從一個頂點(diǎn)出發(fā)郭计，每條邊不重復(fù)地遍歷一遍回到這個頂點(diǎn)霸琴，那么每個頂點(diǎn)的度必須為偶數(shù)。（若想回到頂點(diǎn)拣宏，則有多少出去的邊沈贝，就要有多少進(jìn)入的邊）

構(gòu)建網(wǎng)絡(luò)爬蟲的工程要點(diǎn)：

1、采用BFS還是DFS勋乾？即如何在有限的時間里最多地爬下最重要的網(wǎng)頁宋下。

對于某個網(wǎng)站來說，首頁最重要辑莫，其次是首頁的鏈接学歧，鏈接越深越相對不重要。所以各吨，在下載某一個互聯(lián)網(wǎng)的具體內(nèi)容時枝笨，BFS優(yōu)先于DFS。

但是，在網(wǎng)路通信的握手成本上横浑，DFS優(yōu)先于BFS剔桨。“握手”就是指下載服務(wù)器網(wǎng)站和網(wǎng)站服務(wù)器建立通信的過程徙融。如果握手的次數(shù)太多洒缀，下載的效率就降低。對于某個網(wǎng)站欺冀，一般是由特定的一臺或幾臺服務(wù)器專門下載树绩。這些服務(wù)器下載完一個網(wǎng)站，再去下載另一個網(wǎng)站隐轩，而不是先下載一部分饺饭，再來回折騰。

所以职车，同時存在DFS瘫俊、BFS。有一個調(diào)度系統(tǒng)來存儲那些已經(jīng)發(fā)現(xiàn)但尚未下載的網(wǎng)頁URL提鸟，且按優(yōu)先級排列军援。

2、頁面的分析和URL的提取

以html語言書寫的網(wǎng)頁称勋，解析起來比較簡單胸哥；以腳本js等書寫網(wǎng)頁，解析起來較為困難赡鲜，需要做瀏覽器的內(nèi)核工程師來做空厌。

3、記錄哪些網(wǎng)頁URL已經(jīng)下載過——哈希表

如果同時有上千臺服務(wù)器一起下載網(wǎng)頁银酬，維護(hù)一張統(tǒng)一的哈希表就比較麻煩嘲更。首先，哈希表會大到一臺服務(wù)器存儲不下揩瞪，其次由于每個下載服務(wù)器在開始下載前和完成下載后都需要訪問和維護(hù)這張表赋朦，以免不同的服務(wù)器重復(fù)工作，存儲這張哈希表的服務(wù)器的通信就成為了整個爬蟲系統(tǒng)的瓶頸李破。

好的方法一般采用兩個技術(shù)：首先明確每臺服務(wù)器的分工宠哄，也就是在調(diào)度時一看到某個URL就知道要交給哪臺服務(wù)器去下載，這樣就避免了很多服務(wù)器對同一個URL做出是否要下載的判斷嗤攻。然后毛嫉，在明確分工的基礎(chǔ)上，可以批量判斷URL是否下載妇菱，比如每次向哈希表發(fā)送一大批詢問承粤，或者每次更新一大批哈希表的內(nèi)容暴区，以減少通信的次數(shù)。

第10章 PageRank——Google民主表決式網(wǎng)頁排名技術(shù)

對于一個特定的查詢辛臊，搜索結(jié)果取決于網(wǎng)頁的質(zhì)量信息仙粱，和這個查詢與每個網(wǎng)頁的相關(guān)性信息。

pagerank算法核心思想：如果一個網(wǎng)頁被很多其他網(wǎng)頁所鏈接浪讳，說明它受到普遍的承認(rèn)和信賴缰盏。比如說，對于來自不同網(wǎng)頁的鏈接區(qū)別對待淹遵，因為網(wǎng)頁排名高的網(wǎng)頁鏈接更可靠，于是要給這些鏈接以較大的權(quán)重负溪。

計算結(jié)果的網(wǎng)頁排名需要用到網(wǎng)頁本身的排名透揣。布林破解了這個怪圈，把這個問題變成了一個二維矩陣相乘的問題川抡。先假設(shè)所有的網(wǎng)頁排名是相同的辐真，并根據(jù)這個初始值，算出各個網(wǎng)頁的第一次迭代排名崖堤，然后根據(jù)第一次迭代排名算出第二代的排名侍咱。

網(wǎng)頁排名的高明之處在于它把整個互聯(lián)網(wǎng)系統(tǒng)當(dāng)作一個整體對待。以前的信息檢索把每個網(wǎng)頁當(dāng)做獨(dú)立的個體對待密幔，只注意到網(wǎng)頁內(nèi)容和查詢語句的相關(guān)性楔脯，忽略了網(wǎng)頁之間的關(guān)系。

pagerank的計算方法

假定向量B=[b1;b2;...bn]為第一胯甩、第二...第n個網(wǎng)站的網(wǎng)頁排名昧廷。初始值為B0=[1/n；1/n...偎箫；1/n]

矩陣A=[a11 ...a1n...a1m木柬；...；am1...amn...amm淹办；...眉枕；am1 ...amn...amm]為網(wǎng)頁之間的鏈接數(shù)目，其中amn代表第m個網(wǎng)頁指向第n個網(wǎng)頁的鏈接數(shù)怜森。A已知速挑，B未知。

假定Bi是第i次迭代結(jié)果塔插，那么Bi=A*Bi-1梗摇。最終Bi會收斂于B，當(dāng)Bi與Bi-1的結(jié)果差異非常小時想许，就可以停止迭代運(yùn)算伶授。（注：計算訪問概率較小的網(wǎng)站時断序，需要做平滑處理）

第11章 如何確定網(wǎng)頁和查詢的相關(guān)性

搜索關(guān)鍵詞權(quán)重的科學(xué)度量TF-IDF

某關(guān)鍵詞頻率TF=關(guān)鍵詞的次數(shù)/該網(wǎng)頁的總字?jǐn)?shù)。這個查詢和該網(wǎng)頁的相關(guān)度=TF1+TF2+...+TFn糜烹。由于每個詞的重要程度不一樣违诗，所以給每個詞設(shè)置權(quán)重時，需滿足如下兩個條件：

1疮蹦、一個詞的預(yù)測主題能力越強(qiáng)诸迟，權(quán)重越大；反之愕乎，權(quán)重越小阵苇。

2、停止詞的權(quán)重為零感论。如果一個詞只在很少的網(wǎng)頁中出現(xiàn)绅项，通過它就容易鎖定目標(biāo)，它的權(quán)重也就應(yīng)該大比肄；反之快耿，類似“的、是”等詞芳绩，權(quán)重應(yīng)該小住拭。概括地將镊屎，假定一個詞w在Dw個網(wǎng)頁中出現(xiàn)過逛尚，那么Dw越大鹏倘，w的權(quán)重越小。使用最多的權(quán)重是“逆文本頻率指數(shù)”垛膝，即IDF=log（D/Dw）,其中鳍侣，D是全部網(wǎng)頁數(shù)。

所以吼拥，得到相關(guān)性的計算公式TF-IDF=TF1IDF1+TF2IDF2+...+TFn*IDFn

TF-IDF的信息論依據(jù)倚聚？？P136

第12章 地圖和本地搜索的最基本技術(shù)

智能手機(jī)的定位和導(dǎo)航功能涉及3個關(guān)鍵技術(shù)：利用導(dǎo)航儀進(jìn)行衛(wèi)星定位凿可，地址的識別惑折，根據(jù)用戶輸入的起點(diǎn)和終點(diǎn)，在地圖上規(guī)劃最短路線或者最快路線枯跑。

有限狀態(tài)機(jī)：是一個特殊的有向圖惨驶，包括一些狀態(tài)（節(jié)點(diǎn)）和連接這些狀態(tài)的有向弧。每一個有限狀態(tài)機(jī)有一個開始狀態(tài)和一個終止?fàn)顟B(tài)敛助，以及若干中間狀態(tài)粗卜。每一條弧上帶有從上一個狀態(tài)進(jìn)入下一個狀態(tài)的條件。如果輸入的符號可以從狀態(tài)機(jī)的開始狀態(tài)經(jīng)過中間狀態(tài)纳击，走到終止?fàn)顟B(tài)续扔，那么這條地址就有效攻臀，否則無效。

有限狀態(tài)機(jī)是一個五元組纱昧，輸入符號的集合刨啸、非空的有限狀態(tài)的集合S、初始狀態(tài)S0识脆、從輸入到有限狀態(tài)的映射函數(shù)设联、終止?fàn)顟B(tài)。如果輸入和輸出的可能性不同灼捂，也可以給賦予每條邊權(quán)重离例。

使用有限狀態(tài)機(jī)識別地址，關(guān)鍵要解決兩個問題纵东，即通過一些有效的地址建立狀態(tài)機(jī)粘招，以及地址字串的匹配算法。

有限狀態(tài)機(jī)只能進(jìn)行嚴(yán)格匹配偎球，當(dāng)用戶輸入存在錯誤時，則無法識別辑甜∷バ酰基于概率的有限狀態(tài)機(jī)可以解決該問題（效果等同馬爾可夫鏈，相當(dāng)于給每個有向弧加上概率）

動態(tài)規(guī)劃——解決最短路徑：

加權(quán)圖：一個抽象的圖包括節(jié)點(diǎn)和連接他們的弧磷醋，以及每條弧的權(quán)重猫牡。找到一個圖中給定兩點(diǎn)間的距離，最直接的辦法就是計算出所有的路徑權(quán)重邓线，找出最優(yōu)的淌友。不過可能路徑數(shù)量隨著節(jié)點(diǎn)數(shù)的增長而成指數(shù)增長，復(fù)雜度過高骇陈。

假設(shè)已經(jīng)找到了從北京到廣州的最短路徑震庭，且經(jīng)過鄭州，那么從北京到鄭州的這條子徑也是所有從北京到鄭州的路線中最短的你雌。反過來想器联，如果想要找到從北京到廣州的最短路線，先要找到北京到鄭州（即某個必經(jīng)的中間節(jié)點(diǎn)）的最短路線婿崭。如何找到必經(jīng)的中間節(jié)點(diǎn)拨拓？

只要在圖上橫切一刀，這一刀一定要保證將任何從北京到廣州的路線一分為二（怎么切氓栈？渣磷？）。那么從廣州到北京的最短路徑必須經(jīng)過這一條線上的某個城市授瘦。我們可以先找到從北京出發(fā)到這條線上所有城市的最短路徑醋界，最后得到的全城最短路線一定包括這些局部最短路線中的一條竟宋，這樣，就可以將一個“尋找全城最短路線”的問題物独，分解成一個個尋找局部最短路線的小問題袜硫。

第13章 Google ak-47 的設(shè)計者

從辛格身上學(xué)到的：

先幫助用戶解決80%的問題，再慢慢解決剩下20%的問題挡篓。一開始追求大而全婉陷，可能長時間不能完成，最后不了了之官研。

堅持選擇簡單方案的另一個原因是容易解釋每一個步驟和方法背后的道理秽澳，這樣不僅便于出了問題時查錯，而且容易找到今后的改進(jìn)目標(biāo)戏羽。

第14章 余弦定理和新聞分類

總結(jié)：求特征向量時担神，要先計算TF-IDF（即每篇文章中關(guān)鍵詞的詞頻 乘以 關(guān)鍵詞的權(quán)重。權(quán)重與關(guān)鍵詞在語料庫文章中的集中/分散程度始花，以及關(guān)鍵字在文章中的位置有關(guān)妄讯。）。計算余弦相似度時酷宵，要注意矩陣存儲大小及計算復(fù)雜度亥贸。

對于一篇新聞中所有的實(shí)詞，計算出它們的TF-IDF值浇垦，沒有出現(xiàn)的詞的TF-IDF為零炕置。把這些詞按照對應(yīng)的實(shí)詞在詞匯表的位置依次排列，就得到一個多維向量男韧，即該新聞的特征向量朴摊，向量中每一個維度的大小代表每個詞對這篇新聞主題的貢獻(xiàn)度。

同一類新聞一定是某些主題詞用得較多此虑，即它們的特征向量在某幾個維度上的值都比較大甚纲。如果不屬于同一類，則較大的特征向量應(yīng)該沒什么交集寡壮。由于每篇新聞的文本長度不同贩疙，所以特征向量各個維度的數(shù)值也不同。單純比較各個維度的大小沒有太大意義况既。但是向量的方向卻有很大意義这溅。如果兩個向量的方向一字，說明對應(yīng)的新聞用詞的比例也基本一致棒仍。因此可以利用余弦定理計算兩個向量的夾角來判斷對應(yīng)新聞主題的接近程度悲靴。

有兩種計算方法：

第一種假設(shè)我們已知一些新聞類別的特征向量，計算出要被分類的新聞和各類新聞特征向量的余弦相似性莫其，余弦越小癞尚，相似度越高耸三。

第二種假設(shè)我們不知道這些新聞類別的特征向量，則我們要計算出所有新聞兩兩之間的余弦相似性浇揩，把相似性大于一個閾值的新聞合并成一個小類仪壮，然后把每個小類中的所有新聞作為一個整體，并計算出小類的特征向量胳徽，再計算出所有小類之間兩兩的余弦相似性积锅，然后把小類合并成大一點(diǎn)的小類，以此類推养盗，直到小類之間的余弦相似度很小時缚陷，就可以停止迭代了。

計算向量余弦的技巧：

計算N篇新聞之間的兩兩相關(guān)性往核，一次迭代計算復(fù)雜度為N方箫爷，計算量較大。簡化方法如下：首先聂儒，分母（向量的長度）不需要重復(fù)計算虎锚，第一次計算余弦以后，長度可以存起來衩婚。其次翁都，只考慮向量中的非零元素即可，這樣一來復(fù)雜度取決于兩個向量中非零元素個數(shù)的最小值谅猾。第三，刪除虛詞鳍悠，如“因為税娜、是、的藏研、如果”等等敬矩，既提高了計算速度，又減少了干擾蠢挡。

標(biāo)題中的詞對主題的貢獻(xiàn)要大于正文中的弧岳；出現(xiàn)在文章首尾中的詞比中間部分的詞重要。所以业踏，可以對重要位置的詞進(jìn)行額外的加權(quán)禽炬，以提高文本分類的準(zhǔn)確性。

第15章 矩陣運(yùn)算和文本處理中的兩個分類問題

將文本按主題歸類與將詞匯表中的詞按意思?xì)w類勤家，需要多次迭代計算相似度腹尖，耗時較長》ゲ保可以利用矩陣運(yùn)算中的奇異值分解來一次性計算相關(guān)性热幔。

首先乐设，要用一個大矩陣A描述成千上萬篇文章和百萬個詞的關(guān)聯(lián)性。在矩陣中绎巨，每一行對應(yīng)一篇文章近尚，每一列對應(yīng)一個詞，導(dǎo)致矩陣非常大场勤。奇異值分解就是將大矩陣分解成三個小矩陣相乘戈锻。

第一個矩陣X是對詞進(jìn)行分類的一個結(jié)果，每一行代表一個詞却嗡，每一列表示一個語義相近的詞類舶沛。第三個矩陣Y是對文本分類的結(jié)果，每一列對應(yīng)一個文本窗价，每一行對應(yīng)一個主題如庭，每一列可以只保留最大值，其余的都改為零撼港，那么每一篇文本都被唯一地分到一類主題中坪它。中間的矩陣B則表示詞的類和文章的類之間的相關(guān)性，每一行代表一篇文章帝牡，每一列代表一個詞往毡。

A=X *B *Y。分解后靶溜，可以同時完成近義詞分類和文章的分類开瞭，以及每個主題和每個詞的語義類之間的相關(guān)性。

相比于利用文本特征向量余弦的距離自底向上聚類的方法罩息，奇異值分解的優(yōu)點(diǎn)是能較快速地得到結(jié)果嗤详，因為它不需要一次次迭代。但這種方法得到的分類結(jié)果略顯粗糙瓷炮。實(shí)際工作中葱色，可以先進(jìn)行奇異值分解得到粗分類結(jié)果，再利用計算向量余弦的方法娘香，在粗分類結(jié)果的基礎(chǔ)上苍狰，迭代得到更精確的結(jié)果。

P169奇異值分解的方法烘绽？淋昭？

第16章 信息指紋及其應(yīng)用

一段文字所包含的信息，就是它的信息嫡诀姚。如果對這段信息進(jìn)行無損壓縮編碼响牛，理論上編碼后的最短長度就是它的信息嫡。但是，如果僅僅要區(qū)分兩段文字或者圖片呀打，則遠(yuǎn)不需要那么長的編碼矢赁。任何一段信息，都可以對應(yīng)一個不太長的隨機(jī)數(shù)贬丛，作為區(qū)分它和其他信息的指紋撩银。

信息指紋的用途：

網(wǎng)址消重：比如一般網(wǎng)址由字符串組成，長度不固定豺憔，所以查找困難额获，占用容量較大」вΓ可以將字符串看成是一個特殊的抄邀、長度很長的整數(shù)，利用偽隨機(jī)數(shù)產(chǎn)生算法器昼榛，將其轉(zhuǎn)換成特定長度的偽隨機(jī)數(shù)境肾，即信息指紋。

密碼：cookie也是一種信息指紋胆屿，網(wǎng)站無法根據(jù)信息指紋了解用戶的身份奥喻，這樣可以起到保護(hù)隱私的作用。信息指紋具有不可逆性非迹。

網(wǎng)絡(luò)爬蟲：可以利用信息指紋判斷一個網(wǎng)址是否已經(jīng)下載過环鲤。

判定集合相同：計算兩個集合元素的信息指紋，由于加法的交換律憎兽，保證集合的指紋不因元素出現(xiàn)的次序而改變冷离，如果兩個集合元素相同，那么它們的信息指紋一定相同纯命。

判定集合基本相同：比較兩個網(wǎng)頁是否相同酒朵，只需找出每個網(wǎng)頁中IDF最大的幾個詞，計算并比較他們的信息指紋扎附。

反盜版：提取并比較視頻的關(guān)鍵幀

P151相似哈希計算方法？（能看懂结耀，原因留夜？？）

第17章 由電視劇《暗算》所想到的

加密的過程可以看做是一個函數(shù)的運(yùn)算F图甜，解密的過程是反函數(shù)運(yùn)算碍粥。明碼是自變量，密碼是函數(shù)值黑毅。好的加密函數(shù)不應(yīng)該通過幾個自變量和函數(shù)值就能推導(dǎo)出函數(shù)嚼摩。

一般來講，當(dāng)密碼之間分布均勻并且統(tǒng)計獨(dú)立時，提供的信息最少枕面。均勻使得敵人無從統(tǒng)計愿卒，而統(tǒng)計獨(dú)立能夠保證敵人即使看到一段密碼和明碼后，不能破譯另一段密碼潮秘。

設(shè)計一個密碼系統(tǒng)：

1琼开、找兩個很大的素數(shù)（質(zhì)數(shù)）P和Q，越大越好枕荞，然后計算他們的乘積：

N=P * Q柜候，M=（P-1）*（Q-1）

2、找一個和M互素的整數(shù)E躏精，找一個整數(shù)D渣刷，使得E*D mod M=1（mod為兩個表達(dá)式作除法運(yùn)算后的余數(shù)）。E是公鑰矗烛，誰都可以用來加密辅柴，D是私鑰用于解密，一定要自己保存好高诺。乘積N是公開的碌识。

3、用公式對X加密虱而，得到密碼Y= X的E次方 mod N筏餐。根據(jù)費(fèi)爾馬小定理，得到：X=Y的D次方 mod N牡拇，所以要解密魁瞪，必須知道D。

公開密鑰的好處有：簡單惠呼，只涉及一些乘法导俘；可靠，公開密鑰方法保證產(chǎn)生的密文是統(tǒng)計獨(dú)立而分布均勻的剔蹋。更重要的是N旅薄、E可以公開給任何人加密使用，但只有掌握密鑰D的人才能解密泣崩；靈活少梁，可以產(chǎn)生很多E和D的組合給不同的加密者。

該種方法破解難度較大矫付，破解的最好辦法是對大數(shù)N進(jìn)行因式分解凯沪，即通過N反過來找P、Q买优，得到M妨马、N挺举。而找到P、Q目前只有用計算機(jī)把所有的數(shù)字試一遍的笨辦法烘跺，耗時很長湘纵。這也是為什么P、Q都需要非常大的原因液荸。

第18章 閃光的不一定是金子——談?wù)勊阉饕?/h2>

搜索反作弊也存在道和術(shù)兩種境界：

術(shù)：分析作弊的例子瞻佛，分析它，然后清除它娇钱，這種方法能解決問題伤柄，且不需要太動腦筋，但工作量較大文搂，難以從個別現(xiàn)象上升級到普遍規(guī)律适刀。道：通過具體的作弊例子，找到作弊的動機(jī)和本質(zhì)煤蹭，從本質(zhì)上解決問題笔喉。

在通信中解決噪音抗干擾問題的基本思路有兩條：

從信息源出發(fā)，加強(qiáng)通信編碼自身的抗干擾能力硝皂；從傳輸上看常挚，過濾掉噪音，還原信息稽物。

賣鏈接的網(wǎng)站奄毡，都有大量的出鏈。每一個網(wǎng)站到其它網(wǎng)站的出鏈數(shù)目可以作為一個向量贝或，它是網(wǎng)站的固有特征吼过。既然是向量就可以計算出余弦距離。通常情況下咪奖，這些網(wǎng)站的出鏈向量之間的余弦距離幾乎為1盗忱。

運(yùn)用圖論。作弊網(wǎng)站一般需要互相鏈接羊赵，以提高排名趟佃。這樣就在互聯(lián)網(wǎng)這張大圖中形成了一些Clique。

第19章 談?wù)剶?shù)學(xué)模型的重要性

一個正確的模型應(yīng)當(dāng)在形式上是簡單的昧捷。

一個正確的模型可能一開始還不如一個精雕細(xì)琢過的錯誤模型來得準(zhǔn)確揖闸，但是，如果我們認(rèn)定大方向是對的料身，就應(yīng)該堅持下去。

大量的準(zhǔn)確數(shù)據(jù)對研發(fā)很重要衩茸。

正確的模型也可能受噪音干擾芹血，而顯得不準(zhǔn)確；這時不應(yīng)該用一種湊合的修正方法來彌補(bǔ)它，二是要找到噪音的根源幔烛，這樣也許能通往重大的發(fā)現(xiàn)啃擦。

第20章 不要把雞蛋放到一個籃子里

最大嫡原理指出，需要對一個隨機(jī)事件分布進(jìn)行預(yù)測時饿悬，我們的預(yù)測應(yīng)當(dāng)滿足全部已知的條件令蛉，而對未知的情況不要做任何主觀假設(shè)。在這種情況下狡恬，概率分布最均勻珠叔，預(yù)測風(fēng)險最小。因為這時弟劲，概率分布的信息嫡最大祷安，所以叫“最大嫡模型”⊥闷颍總結(jié)一句話就是：當(dāng)我們不確定時汇鞭，就要保留各種可能性。

P208最大嫡模型公式及訓(xùn)練庸追？霍骄？

通用迭代算法GIS：

假定第零次迭代的初始模型為等概率的均勻分布；用第n次迭代的模型來估算每種信息特征在訓(xùn)練數(shù)據(jù)中的分布淡溯，如果超過實(shí)際的读整，則把相應(yīng)參數(shù)變小，反之血筑，則變大绘沉；重復(fù)步驟2直至收斂。

第21章 拼音輸入法的數(shù)學(xué)原理

輸入法輸入漢字的快慢取決于對漢字編碼的平均長度豺总，即擊鍵次數(shù)乘以尋找這個鍵所需要的時間车伞。

拼音輸入法的優(yōu)點(diǎn)：第一，不需要專門學(xué)習(xí)喻喳；第二另玖，輸入自然，不會中斷思維表伦，也就是說找每個鍵的時間非常短谦去。第三，因為編碼長蹦哼，有信息冗余鳄哭，容錯性好。如果把字換成詞纲熏，每個漢字的信息嫡將會減少妆丘。如果能更多地利用上下文相關(guān)性锄俄，當(dāng)輸入一半的時候，可能已經(jīng)看到自己要找的字了勺拣。

拼音轉(zhuǎn)漢字的算法：

輸入法就是將拼音串變?yōu)闈h字串的轉(zhuǎn)換器奶赠。一個拼音可以對應(yīng)多個漢字，把一個拼音對應(yīng)的漢字從左到右連起來药有，就是一張有向圖毅戈，它被稱為網(wǎng)格圖或籬笆圖。

從第一個漢字到最后一個漢字可以對應(yīng)很多很多句子愤惰，每一個句子和圖中的一條路徑一一對應(yīng)苇经。拼音輸入法就是要根據(jù)上下文在給定拼音條件下找到一個最優(yōu)的句子（可以參考隱含馬爾可夫，前后漢字關(guān)系可以只考慮二階關(guān)系羊苟，求出概率最大的句子）塑陵。

個性化的語音模型：

每個人的輸入習(xí)慣不同，可以找到大量符合用戶經(jīng)常輸入的內(nèi)容和用語習(xí)慣的語料蜡励，訓(xùn)練出一個用戶特定的語言模型令花，步驟如下：

將訓(xùn)練語言模型的文本按照主題分成很多不同的類別，對于每個類凉倚，找出它們的特征向量兼都；

統(tǒng)計某個人輸入的文本，得到他輸入的詞的特征向量Y稽寒；

計算Y和每個分類特征向量的余弦相似度扮碧，并選擇前K個和Y距離最近的類對應(yīng)的文本，作為這個特定用戶的語言模型訓(xùn)練數(shù)據(jù)杏糙；

訓(xùn)練出用戶特定的語言模型M1慎王。大部分情況下，M1對這個用戶的輸入比通用模型M0要好宏侍。但是相對于偏僻的內(nèi)容赖淤，M1覆蓋語言較少，效果就不如M0了谅河。所以最好是綜合二者（線性關(guān)系）咱旱。

第22章 自然語言處理的教父馬庫斯

第23章 布隆過濾器

布隆過濾器實(shí)際上是一個很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。

布隆過濾器過濾垃圾郵件的工作原理：對于每一個電子郵件地址绷耍，用8個不同的隨機(jī)數(shù)產(chǎn)生器產(chǎn)生8個信息指紋（f1吐限，f2，...f8）褂始。再用一個隨機(jī)數(shù)產(chǎn)生器把這8個信息指紋映射到布隆過濾器的8個二進(jìn)制位诸典，并把這8個位置的二進(jìn)制全部設(shè)置為1。

如果郵件在黑名單中崎苗，該郵件經(jīng)過兩次映射最終得到的8個二進(jìn)制位都是1狐粱。

布隆過濾器優(yōu)點(diǎn)在于快速赘阀、省空間，但是有一定的誤識別率脑奠。常見的辦法是再建立一個小的白名單，存儲那些有可能被誤判的郵件地址幅慌。

P207布隆過濾器的誤識別問題宋欺？？

第24章 馬爾科夫鏈的擴(kuò)展——貝葉斯網(wǎng)絡(luò)

貝葉斯網(wǎng)絡(luò)：有很多節(jié)點(diǎn)（狀態(tài)）胰伍，節(jié)點(diǎn)之間通過有向弧連接齿诞，各個節(jié)點(diǎn)之間的相互轉(zhuǎn)化可能存在一定的概率。

首先確定貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)骂租。優(yōu)化結(jié)構(gòu)要保證它產(chǎn)生的序列從頭到尾的可能性最大祷杈，即后驗概率最大。尋找全局最優(yōu)的路徑渗饮，一般采用貪婪算法但汞，也就是在每一步時，沿著箭頭的方向?qū)ふ矣邢薏交フ尽Ｈ粢苊饩植孔顑?yōu)私蕾，就要用許多隨機(jī)數(shù)在貝葉斯網(wǎng)絡(luò)中試一試，看看是否有更好的方法胡桃。

然后踩叭，要通過參數(shù)訓(xùn)練確定這些節(jié)點(diǎn)之間的弧的權(quán)重（參考前面提到的EM過程）吼野。實(shí)際上酒甸，結(jié)構(gòu)的訓(xùn)練和參數(shù)的訓(xùn)練是交替進(jìn)行迈螟、不斷優(yōu)化的棕诵，直至得到收斂或者誤差較小的模型屈留。

第25章 條件隨機(jī)場和句法分析

第26章 維特比和他的維特比算法

維特比算法是一個特殊的但應(yīng)用最廣泛的動態(tài)規(guī)劃算法憋沿，維特比算法主要解決籬笆網(wǎng)絡(luò)的有向圖的最短路徑問題葵诈。它之所以重要摩桶，是因為凡是使用隱含馬爾可夫模型描述的問題都可以用它來解碼闺兢。

對于每一個給定的起始點(diǎn)茂缚、終止點(diǎn)，如果列出所有可能的路徑屋谭，從中找出最短路徑脚囊，計算復(fù)雜度呈指數(shù)增長。

P230維特比算法：假設(shè)在隱含馬爾可夫鏈中桐磁，總共有N個節(jié)點(diǎn)悔耘，節(jié)點(diǎn)最多的狀態(tài)有D個節(jié)點(diǎn)，也就是整個網(wǎng)格的寬度為D我擂，那么找出任何相鄰兩個狀態(tài)節(jié)點(diǎn)的最短路徑的復(fù)雜度不超過 D的平方衬以。由于網(wǎng)格的長度是N缓艳，所以整個維特比的復(fù)雜度不超過 N*D的平方。（確定節(jié)點(diǎn)的狀態(tài)順序看峻？阶淘？）

第27章 再談文本自動分類問題——期望最大化EM

文本的自收斂分類：

不同于TF-IDF利用余弦相似度來進(jìn)行分類，這里不需要事先設(shè)定好類別互妓，也不需要對文本兩兩比較進(jìn)行合并聚類溪窒。而是隨機(jī)挑選一些類的中心，然后來優(yōu)化這些中心冯勉，使它們和真實(shí)的聚類中心盡可能一致澈蚌。步驟如下：

假設(shè)有很多點(diǎn)隨機(jī)分布，隨機(jī)挑選k個點(diǎn)作為聚類的中心灼狰；分別計算出所有點(diǎn)到這些聚類中心的距離宛瞄，將這些點(diǎn)歸到最近的一類中；重新計算每一類的中心（分別計算每個維度的平均值）交胚；重復(fù)上述過程份汗，直到新的中心和舊的中心之間偏移非常非常小，即過程收斂承绸。

如何確保期望最大化：

首先裸影，我們的距離函數(shù)必須足夠好，能保證同一類相對距離較近军熏，不同類相對距離較遠(yuǎn)轩猩。我們希望最終的分類結(jié)果是：相近的點(diǎn)都被聚類到了一類中，即同一類中各個點(diǎn)到中心距離的平均距離d較近荡澎，而不同類中心之間的平均距離D較遠(yuǎn)均践。

EM算法——上帝的算法：

在一般性的問題中如果有很多觀測值，可以讓計算機(jī)不斷迭代來學(xué)習(xí)一個模型摩幔。首先彤委，根據(jù)現(xiàn)有的模型，計算出觀測數(shù)據(jù)輸入到模型中的結(jié)果或衡，這個過程為期望值計算過程（Expectation焦影，E過程）；接下來封断，重新計算模型參數(shù)斯辰，以最大化期望值（文本分類中是最大化D和-d），該過程為最大化過程（Maximization坡疼，M過程）彬呻。統(tǒng)稱為EM算法。

EM算法只需要有一些訓(xùn)練數(shù)據(jù)，定義一個最大化函數(shù)闸氮，剩下的事就交給計算機(jī)了剪况。經(jīng)過若干次迭代，達(dá)到收斂或誤差最小化蒲跨，模型就訓(xùn)練好了译断。是一個通用的算法。

EM算法不一定能得到全局最優(yōu)解或悲，如果目標(biāo)函數(shù)是凸函數(shù)镐作，就可以；如果是凹函數(shù)隆箩，則可能得到的是局部最優(yōu)解。

第28章 邏輯回歸和搜索廣告

廣告搜索跟很多因素相關(guān)羔杨，如以前的經(jīng)驗值捌臊、統(tǒng)計數(shù)據(jù)的大小、擺放的位置兜材、廣告費(fèi)等等理澎。

邏輯回歸模型

f（z）=e的z次方/(e的z次方+1）。

將一個事件出現(xiàn)的概率適應(yīng)到一條邏輯曲線上曙寡。邏輯曲線是一條S型曲線糠爬，其特點(diǎn)是開始變化快，逐漸減慢举庶，最后飽和执隧。其好處是自變量范圍是負(fù)無窮到正無窮，而值域范圍限制在0~1之間户侥，不論自變量如何組合镀琉，總能得到一個概率分布。

假設(shè)有n個影響廣告點(diǎn)擊率的變量x1蕊唐，x2屋摔，...xn。設(shè)自變量z=k0+k1x1+k2x2+...+knxn替梨。（ki是自回歸參數(shù)钓试，k0是一個特殊的參數(shù)，保證在沒有任何信息時副瀑，有一個穩(wěn)定的分布）

可以通過最大嫡-GIS算法來訓(xùn)練邏輯回歸函數(shù)的參數(shù)弓熏。

第29章 各個擊破算法和Google云計算的基礎(chǔ)

云計算的一個關(guān)鍵問題是，如何把一個非常大的計算問題俗扇，自動分解到許多計算能力不是很強(qiáng)大的計算機(jī)上硝烂，共同完成。其根本原理是分治算法。

分治算法：將一個復(fù)雜的問題滞谢，分成若干簡單的子問題進(jìn)行解決串稀。然后，對子問題的結(jié)果進(jìn)行合并狮杨，得到原有問題的解母截。

通過分治算法實(shí)現(xiàn)矩陣相乘C=A*B：將矩陣A、B劃分為小的矩陣橄教，分別放到不同的服務(wù)器上計算求得中間值清寇，再進(jìn)行合并。