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