轉(zhuǎn)自：http://book.douban.com/annotation/19461092/


       半個(gè)月前在豆瓣上看到了一本新書(shū)《數(shù)學(xué)之美》，評(píng)價(jià)很高。而因?yàn)樵诎肽昵翱戳恕妒裁词菙?shù)學(xué)》就對(duì)數(shù)學(xué)產(chǎn)生濃厚興趣，但苦于水平不足的我便立馬買(mǎi)了一本，希望能對(duì)數(shù)學(xué)多一些了解，并認(rèn)真閱讀起來(lái)。
       令我意外并欣喜的是，這本書(shū)里邊的數(shù)學(xué)內(nèi)容并不晦澀難懂，而且作者為了講述數(shù)學(xué)之美而搭配的一些工程實(shí)例都是和我學(xué)習(xí)并感興趣的模式識(shí)別，目標(biāo)分類(lèi)相關(guān)算法相關(guān)聯(lián)的。這讓我覺(jué)得撿到了意外的寶藏。
        書(shū)中每一個(gè)章節(jié)都或多或少是作者親身經(jīng)歷過(guò)的，比如世界級(jí)教授的小故事，或者Google的搜索引擎原理，又或者是Google的云計(jì)算等。作者用其行云流水般的語(yǔ)言將各個(gè)知識(shí)點(diǎn)像講故事一樣有趣的敘述出來(lái)。
        這本書(shū)著實(shí)讓我印象深刻，所以我把筆記分享出來(lái)，希望更多和我學(xué)習(xí)研究領(lǐng)域一樣的人會(huì)喜歡并親自閱讀這本書(shū)，并能支持作者。畢竟國(guó)內(nèi)這種書(shū)實(shí)在是太少了，也希望能有更多領(lǐng)域內(nèi)的大牛能再寫(xiě)出一些這種書(shū)籍來(lái)讓我們共同提高。
1.    因?yàn)樾枰獋鞑バ畔⒘康脑黾樱煌穆曇舨⒉荒芡耆磉_(dá)信息，語(yǔ)言便產(chǎn)生了。
2.    當(dāng)文字增加到?jīng)]有人能完全記住所有文字時(shí)，聚類(lèi)和歸類(lèi)就開(kāi)始了。例如日代表太陽(yáng)或者代表一天。
3.    聚類(lèi)會(huì)帶來(lái)歧義性，但上下文可以消除歧義。信息冗余是信息安全的保障。例如羅塞塔石碑上同一信息重復(fù)三次。
4.    最短編碼原理即常用信息短編碼，生僻信息長(zhǎng)編碼。
5.    因?yàn)槲淖种皇切畔⒌妮d體而非信息本身，所以翻譯是可以實(shí)現(xiàn)的。
6.    2012，其實(shí)是瑪雅文明采用二十進(jìn)制，即四百年是一個(gè)太陽(yáng)紀(jì)，而2012年恰巧是當(dāng)前太陽(yáng)紀(jì)的最后一年，2013年是新的太陽(yáng)紀(jì)的開(kāi)始，故被誤傳為世界末日。
7.    字母可以看為是一維編碼，而漢字可以看為二維編碼。
8.    基于統(tǒng)計(jì)的自然語(yǔ)言處理方法，在數(shù)學(xué)模型上和通信是相通的，甚至是相同的。
9.    讓計(jì)算機(jī)處理自然語(yǔ)言的基本問(wèn)題就是為自然語(yǔ)言這種上下文相關(guān)的特性建立數(shù)學(xué)模型，即統(tǒng)計(jì)語(yǔ)言模型（Statistical Language Modal）。
10.    根據(jù)大數(shù)定理（Law of Large Numbers），只要統(tǒng)計(jì)量足夠，相對(duì)頻度就等于概率。
11.    二元模型。對(duì)于p(w1,w2,…,wn)=p(w1)p(w2|w1)p(w3|w1,w2)…p(wn|w1,w2,…,wn-1)的展開(kāi)問(wèn)題，因?yàn)閜(w3|w1,w2)難計(jì)算，p(wn|w1,w2,…,wn-1)更難計(jì)算，馬爾科夫給出了一個(gè)偷懶但是頗為有效的方法，也就是每當(dāng)遇到這種情況時(shí)，就假設(shè)任意wi出現(xiàn)的概率只與它前面的wi-1有關(guān)，即p(s)=p(w1)p(w2|w1)p(w3|w2)…p(wi|wi-1)…p(wn|wn-1)。現(xiàn)在這個(gè)概率就變的簡(jiǎn)單了。對(duì)應(yīng)的語(yǔ)言模型為2元模型（Bigram Model）。
12.    *N元模型。wi只與前一個(gè)wi-1有關(guān)近似的過(guò)頭了，所以N-1階馬爾科夫假設(shè)為p(wi|w1,w2,…,wi-1)=p(wi|wi-N+1,wi-N+2,…,wi-1)，對(duì)應(yīng)的語(yǔ)言模型成為N元模型（N-Gram Model）。一元模型就是上下文無(wú)關(guān)模型，實(shí)際應(yīng)用中更多實(shí)用的是三元模型。Google的羅塞塔翻譯系統(tǒng)和語(yǔ)言搜索系統(tǒng)實(shí)用的是四元模型，存儲(chǔ)于500臺(tái)以上的Google服務(wù)器中。
13.    *卡茲退避法（Katz backoff），對(duì)于頻率超過(guò)一定閾值的詞，它們的概率估計(jì)就是它們?cè)谡Z(yǔ)料庫(kù)中的相對(duì)頻度，對(duì)于頻率小于這個(gè)閾值的詞，它們的概率估計(jì)就小于他們的相對(duì)頻度，出現(xiàn)次數(shù)越少，頻率下調(diào)越多。對(duì)于未看見(jiàn)的詞，也給予一個(gè)比較小的概率（即下調(diào)得到的頻率總和），這樣所有詞的概率估計(jì)都平滑了。這就是卡茲退避法（Katz backoff）。
14.    訓(xùn)練數(shù)據(jù)通常是越多越好，通過(guò)平滑過(guò)渡的方法可以解決零概率和很小概率的問(wèn)題，畢竟在數(shù)據(jù)量多的時(shí)候概率模型的參數(shù)可以估計(jì)的比較準(zhǔn)確。
15.    利用統(tǒng)計(jì)語(yǔ)言模型進(jìn)行分詞，即最好的分詞方法應(yīng)該保證分完詞后這個(gè)句子出現(xiàn)的概率最大。根據(jù)不同應(yīng)用，漢語(yǔ)分詞的顆粒度大小應(yīng)該不同。
16.    符合馬爾科夫假設(shè)（各個(gè)狀態(tài)st的概率分布只與它前一個(gè)狀態(tài)st-1有關(guān)）的隨即過(guò)程即成為馬爾科夫過(guò)程，也稱(chēng)為馬爾科夫鏈。
17.    隱含馬爾科夫模型是馬爾科夫鏈的擴(kuò)展，任意時(shí)刻t的狀態(tài)st是不可見(jiàn)的，所以觀察者沒(méi)法通過(guò)觀察到一個(gè)狀態(tài)序列s1,s2,s3,…,sT來(lái)推測(cè)轉(zhuǎn)移概率等參數(shù)。但是隱馬爾科夫模型在每個(gè)時(shí)刻t會(huì)輸出一個(gè)符號(hào)ot，而且ot和st相關(guān)且僅和ot相關(guān)。這個(gè)被稱(chēng)為獨(dú)立輸出假設(shè)。其中隱含的狀態(tài)s1,s2,s3,…是一個(gè)典型的馬爾科夫鏈。
18.    隱含馬爾科夫模型是機(jī)器學(xué)習(xí)主要工具之一，和幾乎所有機(jī)器學(xué)習(xí)的模型工具一樣，它需要一個(gè)訓(xùn)練算法（鮑姆-韋爾奇算法）和使用時(shí)的解碼算法（維特比算法）。掌握了這兩類(lèi)算法，就基本上可以使用隱含馬爾科夫模型這個(gè)工具了。
19.    鮑姆-韋爾奇算法（Baum-Welch Algorithm），首先找到一組能夠產(chǎn)生輸出序列O的模型參數(shù)，這個(gè)初始模型成為Mtheta0，需要在此基礎(chǔ)上找到一個(gè)更好的模型，假定不但可以算出這個(gè)模型產(chǎn)生O的概率P(O|Mtheta0)，而且能夠找到這個(gè)模型產(chǎn)生O的所有可能的路徑以及這些路徑的概率。并算出一組新的模型參數(shù)theta1，從Mtheta0到Mtheta1的過(guò)程稱(chēng)為一次迭代。接下來(lái)從Mtheta1出發(fā)尋找更好的模型Mtheta2，并一直找下去，直到模型的質(zhì)量沒(méi)有明顯提高為止。這樣一直估計(jì)（Expectation）新的模型參數(shù)，使得輸出的概率達(dá)到最大化（Maximization）的過(guò)程被稱(chēng)為期望值最大化（Expectation-Maximization）簡(jiǎn)稱(chēng)EM過(guò)程。EM過(guò)程能保證一定能收斂到一個(gè)局部最優(yōu)點(diǎn)，但不能保證找到全局最優(yōu)點(diǎn)。因此，在一些自然語(yǔ)言處理的應(yīng)用中，這種無(wú)監(jiān)督的鮑姆-韋爾奇算法訓(xùn)練處的模型比有監(jiān)督的訓(xùn)練得到的模型效果略差。
20.    熵，信息熵的定義為H(X)=-SumP(x)logP(x)，變量的不確定性越大，熵也越大。
21.    一個(gè)事物內(nèi)部會(huì)存在隨機(jī)性，也就是不確定性，假定為U，而從外部消除這個(gè)不確定性唯一的辦法是引入信息I，而需要引入的信息量取決于這個(gè)不確定性的大小，即I>U才行。當(dāng)I<U時(shí)，這些信息可以消除一部分不確定性，U'=U-I。反之，如果沒(méi)有信息，任何公示或者數(shù)字的游戲都無(wú)法排除不確定性。
22.    信息的作用在于消除不確定性。
23.    互信息，對(duì)兩個(gè)隨機(jī)事件相關(guān)性的量化度量，即隨機(jī)事件X的不確定性或者說(shuō)熵H(X)，在知道隨機(jī)事件Y條件下的不確定性，或者說(shuō)條件熵H(X|Y)之間的差異，即I(X;Y)=H(X)-H(X|Y)。所謂兩個(gè)事件相關(guān)性的量化度量，即在了解了其中一個(gè)Y的前提下，對(duì)消除另一個(gè)X不確定性所提供的信息量。
24.    相對(duì)熵（Kullback-Leibler Divergence）也叫交叉熵，對(duì)兩個(gè)完全相同的函數(shù)，他們的相對(duì)熵為零；相對(duì)熵越大，兩個(gè)函數(shù)差異越大，反之，相對(duì)熵越小，兩個(gè)函數(shù)差異越小；對(duì)于概率分布或者概率密度函數(shù)，如果取值均大于零，相對(duì)熵可以度量?jī)蓚€(gè)隨機(jī)分布的差異性。
25.    弗里德里克·賈里尼克（Frederek Jelinek）是自然語(yǔ)言處理真諦的先驅(qū)者。
26.    技術(shù)分為術(shù)和道兩種，具體的做事方法是術(shù)，做事的原理和原則是道。術(shù)會(huì)從獨(dú)門(mén)絕技到普及再到落伍，追求術(shù)的人會(huì)很辛苦，只有掌握了道的本質(zhì)和精髓才能永遠(yuǎn)游刃有余。
27.    真理在形式上從來(lái)是簡(jiǎn)單的，而不是復(fù)雜和含混的。
28.    搜索引擎不過(guò)是一張大表，表的每一行對(duì)應(yīng)一個(gè)關(guān)鍵字，而每一個(gè)關(guān)鍵字后面跟著一組數(shù)字，是包含該關(guān)鍵詞的文獻(xiàn)序號(hào)。但當(dāng)索引變的非常大的時(shí)候，這些索引需要通過(guò)分布式的方式存儲(chǔ)到不同的服務(wù)器上。
29.    網(wǎng)絡(luò)爬蟲(chóng)（Web Crawlers），圖論的遍歷算法和搜索引擎的關(guān)系。互聯(lián)網(wǎng)雖然復(fù)雜，但是說(shuō)穿了其實(shí)就是一張大圖……可以把每一個(gè)網(wǎng)頁(yè)當(dāng)做一個(gè)節(jié)點(diǎn)，把那些超鏈接當(dāng)做連接網(wǎng)頁(yè)的弧。有了超鏈接，可以從任何一個(gè)網(wǎng)頁(yè)出發(fā)，用圖的遍歷算法，自動(dòng)訪問(wèn)到每一個(gè)網(wǎng)頁(yè)并且把他們存儲(chǔ)起來(lái)。完成這個(gè)功能的程序叫網(wǎng)絡(luò)爬蟲(chóng)。
30.    哥尼斯堡七橋，如果一個(gè)圖能從一個(gè)頂點(diǎn)出發(fā)，每條邊不重復(fù)的遍歷一遍回到這個(gè)頂點(diǎn)，那么每一個(gè)頂點(diǎn)的度必須為偶數(shù)。
31.    構(gòu)建網(wǎng)絡(luò)爬蟲(chóng)的工程要點(diǎn)：1.用BFS（廣度優(yōu)先搜索）還是DFS（深度優(yōu)先搜索），一般是先下載完一個(gè)網(wǎng)站，再進(jìn)入下一個(gè)網(wǎng)站，即BFS的成分多一些。2.頁(yè)面的分析和URL的提取，如果有些網(wǎng)頁(yè)明明存在，但搜索引擎并沒(méi)有收錄，可能的原因之一是網(wǎng)絡(luò)爬蟲(chóng)中的解析程序沒(méi)能成功解析網(wǎng)頁(yè)中不規(guī)范的腳本程序。3.記錄哪些網(wǎng)頁(yè)已經(jīng)下載過(guò)的URL表，可以用哈希表。最終，好的方法一般都采用了這樣兩個(gè)技術(shù)：首先明確每臺(tái)下載服務(wù)器的分工，也就是在調(diào)度時(shí)，一看到某個(gè)URL就知道要交給哪臺(tái)服務(wù)器去下載，這樣就避免了很多服務(wù)器對(duì)同一個(gè)URL做出是否需要下載的判斷。然后，在明確分工的基礎(chǔ)上，判斷URL是否下載就可以批處理了，比如每次向哈希表（一組獨(dú)立的服務(wù)器）發(fā)送一大批詢(xún)問(wèn)，或者每次更新一大批哈希表的內(nèi)容，這樣通信的次數(shù)就大大減少了。
32.    PageRank衡量網(wǎng)頁(yè)質(zhì)量的核心思想，在互聯(lián)網(wǎng)上，如果一個(gè)網(wǎng)頁(yè)被很多其他網(wǎng)頁(yè)所鏈接，說(shuō)明它受到普遍的承認(rèn)和信賴(lài)，那么它的排名就高。同時(shí)，對(duì)于來(lái)自不同網(wǎng)頁(yè)的鏈接區(qū)別對(duì)待，因?yàn)榫W(wǎng)頁(yè)排名高的那些網(wǎng)頁(yè)的鏈接更可靠，于是要給這些鏈接比較大的權(quán)重。
33.    TF-IDF(Term Frequency / Inverse Document Frequency) ，關(guān)鍵詞頻率-逆文本頻率值，其中，TF為某個(gè)網(wǎng)頁(yè)上出現(xiàn)關(guān)鍵詞的頻率，IDF為假定一個(gè)關(guān)鍵詞w在Dw個(gè)網(wǎng)頁(yè)中出現(xiàn)過(guò)，那么Dw越大，w的權(quán)重越小，反之亦然，公式為log(D/Dw)。1.一個(gè)詞預(yù)測(cè)主題的能力越強(qiáng)，權(quán)重越大，反之，權(quán)重越小。2.停止詞的權(quán)重為零。
34.    動(dòng)態(tài)規(guī)劃（Dynamic Programming）的原理，將一個(gè)尋找全程最優(yōu)的問(wèn)題分解成一個(gè)個(gè)尋找局部最優(yōu)的小問(wèn)題。
35.    一個(gè)好的算法應(yīng)該像輕武器中最有名的AK-47沖鋒槍那樣：簡(jiǎn)單、有效、可靠性好而且容易讀懂（易操作）而不應(yīng)該故弄玄虛。選擇簡(jiǎn)單方案可以容易解釋每個(gè)步驟和方法背后的道理，這樣不僅便于出問(wèn)題時(shí)的查錯(cuò)，也容易找到今后改進(jìn)的目標(biāo)。
36.    在實(shí)際的分類(lèi)中，可以先進(jìn)行奇異值分解（得到分類(lèi)結(jié)果略顯粗糙但能較快得到結(jié)果），在粗分類(lèi)結(jié)果的基礎(chǔ)上，利用計(jì)算向量余弦的方法（對(duì)范圍內(nèi)的分類(lèi)做兩兩計(jì)算），在粗分類(lèi)結(jié)果的基礎(chǔ)上，進(jìn)行幾次迭代，得到比較精確的結(jié)果。
37.    奇異值分解（Singular Value Decomposition），在需要用一個(gè)大矩陣A來(lái)描述成千上萬(wàn)文章和幾十上百萬(wàn)詞的關(guān)聯(lián)性時(shí)，計(jì)算量非常大，可以將A奇異值分解為X、B和Y三個(gè)矩陣，Amn=Xmm*Bmn*Ynn，X表示詞和詞類(lèi)的相關(guān)性，Y表示文本和主題的相關(guān)性，B表示詞類(lèi)和主題的相關(guān)性，其中B對(duì)角線上的元素很多值相對(duì)其他的非常小，或者為零，可以省略。對(duì)關(guān)聯(lián)矩陣A進(jìn)行一次奇異值分解，就可以同時(shí)完成近義詞分類(lèi)和文章的分類(lèi)，同時(shí)能得到每個(gè)主題和每個(gè)詞義類(lèi)之間的相關(guān)性，這個(gè)結(jié)果非常漂亮。
38.    信息指紋。如果能夠找到一種函數(shù)，將5000億網(wǎng)址隨即地映射到128位二進(jìn)制，也就是16字節(jié)的整數(shù)空間，就稱(chēng)這16字節(jié)的隨機(jī)數(shù)做該網(wǎng)址的信息指紋。信息指紋可以理解為將一段信息映射到一個(gè)多維二進(jìn)制空間中的一個(gè)點(diǎn)，只要這個(gè)隨即函數(shù)做的好，那么不同信息對(duì)應(yīng)的點(diǎn)不會(huì)重合，因此這個(gè)二進(jìn)制的數(shù)字就變成了原來(lái)信息所具有的獨(dú)一無(wú)二的指紋。
39.    判斷兩個(gè)集合是否相同，最笨的方法是這個(gè)集合中的元素一一比較，復(fù)雜度O(squareN)，稍好的是將元素排序后順序比較，復(fù)雜度O(NlogN)，最完美的方法是計(jì)算這兩個(gè)集合的指紋，然后直接進(jìn)行比較，計(jì)算復(fù)雜度O(N)。
40.    偽隨機(jī)數(shù)產(chǎn)生器算法（Pseudo-Random Number Generator，PRNG），這是產(chǎn)生信息指紋的關(guān)鍵算法，通過(guò)他可以將任意長(zhǎng)的整數(shù)轉(zhuǎn)換成特定長(zhǎng)度的偽隨機(jī)數(shù)。最早的PRNG是將一個(gè)數(shù)的平方掐頭去尾取中間，當(dāng)然這種方法不是很隨即，現(xiàn)在常用的是梅森旋轉(zhuǎn)算法（Mersenne Twister）。
41.    在互聯(lián)網(wǎng)上加密要使用基于加密的偽隨機(jī)數(shù)產(chǎn)生器（Cryptography Secure Pseudo-Random Number Generator，CSPRNG），常用的算法有MD5或者SHA-1等標(biāo)準(zhǔn)，可以將不定長(zhǎng)的信息變成定長(zhǎng)的128位或者160位二進(jìn)制隨機(jī)數(shù)。
42.    最大熵模型（Maximum Entropy）的原理就是保留全部的不確定性，將風(fēng)險(xiǎn)降到最小。最大熵原理指出，需要對(duì)一個(gè)隨機(jī)事件的概率分布進(jìn)行預(yù)測(cè)時(shí)，我們的預(yù)測(cè)應(yīng)當(dāng)滿足全部已知的條件，而對(duì)未知的情況不要做任何主觀假設(shè)。在這種情況下，概率分布最均勻，預(yù)測(cè)的風(fēng)險(xiǎn)最小。I.Csiszar證明，對(duì)任何一組不自相矛盾的信息，這個(gè)最大熵模型不僅存在，而且是唯一的，此外，他們都有同一個(gè)非常簡(jiǎn)單的形式-指數(shù)函數(shù)。
43.    通用迭代算法（Generalized Iterative Scaling，GIS）是最原始的最大熵模型的訓(xùn)練方法。1.假定第零次迭代的初始模型為等概率的均勻分布。2.用第N次迭代的模型來(lái)估算每種信息特征在訓(xùn)練數(shù)據(jù)中的分布。如果超過(guò)了實(shí)際的，就把相應(yīng)的模型參數(shù)變小，反之變大。3.重復(fù)步驟2直至收斂。這是一種典型的期望值最大化（Expectation Maximization，EM）算法。IIS(Improved Iterative Scaling)比GIS縮短了一到兩個(gè)數(shù)量級(jí)。
44.    布隆過(guò)濾器實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射的函數(shù)。
45.    貝葉斯網(wǎng)絡(luò)從數(shù)學(xué)的層面講是一個(gè)加權(quán)的有向圖，是馬爾科夫鏈的擴(kuò)展，而從知識(shí)論的層面看，貝葉斯網(wǎng)絡(luò)克服了馬爾科夫那種機(jī)械的線性的約束，它可以把任何有關(guān)聯(lián)的事件統(tǒng)一到它的框架下面。在網(wǎng)絡(luò)中，假定馬爾科夫假設(shè)成立，即每一個(gè)狀態(tài)只與和它直接相連的狀態(tài)有關(guān)，而和他間接相連的狀態(tài)沒(méi)有直接關(guān)系，那么它就是貝葉斯網(wǎng)絡(luò)。在網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)概率的計(jì)算，都可以用貝葉斯公式來(lái)進(jìn)行，貝葉斯網(wǎng)絡(luò)也因此得名。由于網(wǎng)絡(luò)的每個(gè)弧都有一個(gè)可信度，貝葉斯網(wǎng)絡(luò)也被稱(chēng)作信念網(wǎng)絡(luò)（Belief Networks）。
46.    條件隨機(jī)場(chǎng)是計(jì)算聯(lián)合概率分布的有效模型。在一個(gè)隱含馬爾科夫模型中，以x1,x2,...,xn表示觀測(cè)值序列，以y1,y2,...,yn表示隱含的狀態(tài)序列，那么xi只取決于產(chǎn)生它們的狀態(tài)yi,和前后的狀態(tài)yi-1和yi+1都無(wú)關(guān)。顯然很多應(yīng)用里觀察值xi可能和前后的狀態(tài)都有關(guān)，如果把xi和yi-1,yi,yi+1都考慮進(jìn)來(lái)，這樣的模型就是條件隨機(jī)場(chǎng)。它是一種特殊的概率圖模型（Probablistic Graph Model），它的特殊性在于，變量之間要遵守馬爾科夫假設(shè)，即每個(gè)狀態(tài)的轉(zhuǎn)移概率只取決于相鄰的狀態(tài)，這一點(diǎn)和另一種概率圖模型貝葉斯網(wǎng)絡(luò)相同，它們的不同之處在于條件隨機(jī)場(chǎng)是無(wú)向圖，而貝葉斯網(wǎng)絡(luò)是有向圖。
47.    維特比算法（Viterbi Algoritm）是一個(gè)特殊但應(yīng)用最廣的動(dòng)態(tài)規(guī)劃算法，利用動(dòng)態(tài)規(guī)劃，可以解決任何一個(gè)圖中的最短路徑問(wèn)題。它之所以重要，是因?yàn)榉彩鞘褂秒[含馬爾科夫模型描述的問(wèn)題都可以用它來(lái)解碼。1.從點(diǎn)S出發(fā)，對(duì)于第一個(gè)狀態(tài)x1的各個(gè)節(jié)點(diǎn)，不妨假定有n1個(gè)，計(jì)算出S到他們的距離d(S,x1i)，其中x1i代表任意狀態(tài)1的節(jié)點(diǎn)。因?yàn)橹挥幸徊剑赃@些距離都是S到他們各自的最短距離。2.對(duì)于第二個(gè)狀態(tài)x2的所有節(jié)點(diǎn)，要計(jì)算出從S到他們的最短距離。d(S,x2i)=min_I=1,n1_d(S,x1j)+d(x1j,x2i)，由于j有n1種可能性，需要一一計(jì)算，然后找到最小值。這樣對(duì)于第二個(gè)狀態(tài)的每個(gè)節(jié)點(diǎn)，需要n1次乘法計(jì)算。假定這個(gè)狀態(tài)有n2個(gè)節(jié)點(diǎn)，把S這些節(jié)點(diǎn)的距離都算一遍，就有O(n1*n2)次運(yùn)算。3.按照上述方法從第二個(gè)狀態(tài)走到第三個(gè)狀態(tài)一直走到最后一個(gè)狀態(tài)，這樣就得到整個(gè)網(wǎng)絡(luò)從頭到尾的最短路徑。
48.    擴(kuò)頻傳輸（Spread-Spectrum Transmission）和固定頻率的傳輸相比，有三點(diǎn)明顯的好處：1.抗干擾能力強(qiáng)。2.信號(hào)能量非常低，很難獲取。3.擴(kuò)頻傳輸利用帶寬更充分。
49.    Google針對(duì)云計(jì)算給出的解決工具是MapReduce，其根本原理就是計(jì)算機(jī)算法上常見(jiàn)的分治算法（Divide-and-Conquer）。將一個(gè)大任務(wù)拆分成小的子任務(wù)，并完成子任務(wù)的計(jì)算，這個(gè)過(guò)程叫Map，將中間結(jié)果合并成最終結(jié)果，這個(gè)過(guò)程叫Reduce。
50.    邏輯回歸模型（Logistic Regression）是將一個(gè)事件出現(xiàn)的概率適應(yīng)到一條邏輯曲線（Logistic Curve）上。典型的邏輯回歸函數(shù)：f(z)=e`z/e`z+1=1/1+e`-z。邏輯曲線是一條S型曲線，其特點(diǎn)是開(kāi)始變化快，逐漸減慢，最后飽和。邏輯自回歸的好處是它的變量范圍從負(fù)無(wú)窮到正無(wú)窮，而值域范圍限制在0-1之間。因?yàn)橹涤虻姆秶?-1之間，這樣邏輯回歸函數(shù)就可以和一個(gè)概率分別聯(lián)系起來(lái)了。因?yàn)樽宰兞糠秶谪?fù)無(wú)窮到正無(wú)窮之間，它就可以把信號(hào)組合起來(lái)，不論組合成多大或者多小的值，最后依然能得到一個(gè)概率分布。
51.    期望最大化算法（Expectation Maximization Algorithm），根據(jù)現(xiàn)有的模型，計(jì)算各個(gè)觀測(cè)數(shù)據(jù)輸入到模型中的計(jì)算結(jié)果，這個(gè)過(guò)程稱(chēng)為期望值計(jì)算過(guò)程（Expectation），或E過(guò)程；接下來(lái)，重新計(jì)算模型參數(shù)，以最大化期望值，這個(gè)過(guò)程稱(chēng)為最大化的過(guò)程（Maximization），或M過(guò)程。這一類(lèi)算法都稱(chēng)為EM算法，比如隱含馬爾科夫模型的訓(xùn)練方法Baum-Welch算法，以及最大熵模型的訓(xùn)練方法GIS算法。