chapter 3
漢語的詞匯量大致在200k最有老虫，訓(xùn)練一個三元模型就有200K^3 的參數(shù)，即使將整個互聯(lián)網(wǎng)的全部中文內(nèi)容用作訓(xùn)練黍衙，很可能只有10^13冕象。如果只用比例來計算概率，大部分的條件概率仍然為0龟梦，這樣的模型被我們稱之為 不平滑 的模型隐锭。
使用古德-圖靈（Good-Turing Estimate）去估算，即從概率的總量中分配一個很小的比例給那些沒有看見的事件计贰。即使得看見的事件的概率總量之和小于1钦睡。然而需求調(diào)多少的比例，就要根據(jù)古德-圖靈公式去估算躁倒。
定義語料庫中出現(xiàn)了r次的詞為Nr個荞怒，總量很自然的用r*Nr的總和洒琢，但是這時為了使平滑，所以r不用r褐桌，定義一個新的dr來代替r
由于Zipf定律衰抑，即r越大，詞的數(shù)量Nr越小荧嵌，即可以保證d0>0停士。
在二元模型中，則是用卡茨退避法(Katz backoff)來進行平滑完丽，同樣的，內(nèi)伊(Herman Nay)在此基礎(chǔ)上優(yōu)化了卡茨退避法拇舀。
chapter 4
分詞法的發(fā)展：
- 查字典的方法
- 引入了統(tǒng)計語言模型解決語義中的二義性問題 （維特比算法）
- 現(xiàn)代分詞器的顆粒度問題以及選用的語料庫的區(qū)別
chapter 5
在通信模型中引入隱馬爾科夫模型(Hidden Markov Models)
- 針對已知 觀測序列逻族，求最大可能的 隱含序列的問題。在不同的領(lǐng)域中有著不同的名字骄崩，在語音識別中被稱為 聲學(xué)模型(Acoustic Model)聘鳞，在機器翻譯中是 翻譯模型(Translation Model)，而在拼寫校正中則是 糾錯模型(Correction Model)要拂。
- 簡單描述了隱馬爾科夫模型中基本的 三個問題
- 主要描述了HMM的訓(xùn)練過程抠璃，其中分為有監(jiān)督的訓(xùn)練方法和無監(jiān)督的訓(xùn)練方法(Baum-Welch Algorithm)。是一個EM(Expectation-Maximization)算法的過程脱惰。
chapter 6
信息論的基本概念
包括信息熵的基礎(chǔ)搏嗡，公式，講解
條件熵的概念拉一，用以說明為什么相關(guān)的信息可以用來消除不確定性采盒。
即通過相關(guān)的信息來消除模型中的不確定性
互信息的概念，度量兩個隨機事件“相關(guān)性”的量化衡量
相對熵（交叉熵Kullback-Leibler Divergence）：同樣地蔚润，是用來衡量相關(guān)磅氨。但不同于互信息，是用來衡量兩個取值為正數(shù)的函數(shù)的相似性
- 對于兩個完全相同的函數(shù)嫡纠，他們的相對熵等于0
- 相對熵越大烦租，兩個函數(shù)差異越大
- 對于概率分布或者概率密度函數(shù)，如果取值均大于0除盏，相對熵可以度量兩個隨機分布的差異性
- 相對熵是不對稱的叉橱。
后有人從條件上和相對熵出發(fā)，定義了一個稱謂語言模型復(fù)雜度（Perplexity）的概念痴颊，直接衡量語言模型的好壞赏迟。即在給定上下文的條件下，句子中每個位置平均可以選擇的單詞的數(shù)量蠢棱。
信息的作用：在于消除不確定性锌杀，自然語言處理的大量問題在于尋找相關(guān)信息甩栈。
chapter 8
關(guān)于搜索
一個搜索引擎需要做的事情：
- 自動下載盡可能多的網(wǎng)頁
- 建立快速有效的索引
- 根據(jù)相關(guān)性對網(wǎng)頁進行公平準確的排序。
如何在搜索系統(tǒng)的索引中使用布爾運算糕再。對每次的搜索量没，可以在數(shù)據(jù)庫中所有的網(wǎng)頁生成一個長度為網(wǎng)頁數(shù)量的二進制字符串。通過布爾運算中的AND OR進行計算突想，從而大大減少時間殴蹄。
chapter 9
圖論中的遍歷算法
- BFS（Breadth-First Search）
- DFS（Depth-First Search）
工程上說，由于大部分網(wǎng)頁最重要的為首頁猾担，所以其實BFS比DFS在實際上更常用一點袭灯。但DFS的請求次數(shù)會比BFS的少很多。
當(dāng)然工程上的網(wǎng)絡(luò)爬蟲绑嘹，對網(wǎng)頁遍歷的次序不是簡單的BFS或者DFS稽荧，而是一個有著相對復(fù)雜下載優(yōu)先級排序的方法，而管理這個優(yōu)先級排序的子系統(tǒng)一般稱為調(diào)度系統(tǒng)（Scheduler）
chapter 10
Google 的PageRank算法（民主表決式的網(wǎng)頁排名技術(shù)）
搜索結(jié)果的排名取決于兩個信息
- 關(guān)于網(wǎng)頁的質(zhì)量信息（Quality）
- 查詢用詞與每個網(wǎng)頁的相關(guān)性信息（Relevance）
通過初始化一個排名工腋，然后每次使用這個排名及其相應(yīng)的鏈接權(quán)重去重新計算排名姨丈，不斷迭代后可以收斂到一個真實的排名。
通過稀疏矩陣相乘的方法優(yōu)化過于巨大的矩陣相乘擅腰。
影響搜索引擎質(zhì)量的因素
- 用戶的點擊數(shù)據(jù)
- 完備的索引
- 對網(wǎng)頁質(zhì)量的度量
- 用戶偏好
- 確定一個網(wǎng)頁和某個查詢相關(guān)性的方法
chapter 11
確定相關(guān)性
- 歸一化網(wǎng)頁-->避免長內(nèi)容網(wǎng)頁跟短內(nèi)容網(wǎng)頁的bias
- 計算關(guān)鍵詞出現(xiàn)次數(shù)/網(wǎng)頁的總字數(shù)
- 即查詢一個網(wǎng)頁中N個關(guān)鍵詞的出現(xiàn)頻率蟋恬，即TF（Term Frequency，即詞頻）
- 不同的查詢詞得到權(quán)重也是不一樣的趁冈，甚至于一些語氣詞的權(quán)重應(yīng)該是0
- 權(quán)重中使用最多的權(quán)重即 “逆文本頻率指數(shù)”IDF（Inverse Document Frequency）
若該關(guān)鍵詞只在很少的網(wǎng)頁中出現(xiàn)歼争，則權(quán)重大。
- 使用TF-IDF箱歧，相關(guān)性就從TF的累加矾飞，變成了TF*IDF的累加。
- 有人指出IDF其實就是一個在特定條件下關(guān)鍵詞的概率分布的交叉熵呀邢。
chapter 12
特殊的上下文識別洒沦，地址。
最有效的識別分析方法------有限狀態(tài)機
有限狀態(tài)機：一個特殊的有向圖价淌，具有一個開始和一個終止狀態(tài)申眼，點之間的鏈接具有方法，代表狀態(tài)轉(zhuǎn)移的條件(類似于樹結(jié)構(gòu))蝉衣。若能從開始狀態(tài)走到終止狀態(tài)括尸，這說明該地址有效。
為解決模糊匹配的地址的問題病毡，提出了一個基于概率的有限狀態(tài)機濒翻，類似于離散的馬爾科夫鏈。
全球?qū)Ш?動態(tài)規(guī)劃 Dynamic Programming)
在一個加權(quán)無向圖上規(guī)劃一個最短路徑
該處動態(tài)規(guī)劃的原理： 假設(shè)尋找北京到廣州的最短路徑，在北京到廣州的中點城市中遍歷有送，若為最短路徑淌喻，那么北京到中點城市的路徑必然也是最短。從而將一個全局的最短路徑問題不斷的分塊成一個局部的最短路徑問題雀摘。
有限狀態(tài)傳感器的拓展
在語音識別和自然語言理解中也有該模型的利用裸删。但未一種特殊的有限狀態(tài)機---加權(quán)的有限狀態(tài)傳感器(Weighted Finite State Transducer) WFST。
特殊之處在于每個狀態(tài)由輸入和輸出的符號來定義阵赠，其中輸入和輸出都具有多個涯塔，如：某個狀態(tài)可以為輸入為is或者are，輸出為better或者worse清蚀，并且具有對應(yīng)的權(quán)重匕荸，通過動態(tài)規(guī)劃去找到一個概率最大的路徑，從而找到一個概率最大的識別到的句子枷邪。
chapter 14
新聞的自動分類 ---> 余弦定理
建立一個特征變量每聪，從建立的字典集中計算每一個詞的TF-IDF值，從而形成一個一維向量/文章齿风。衡量兩篇文章的相似度可以用計算兩篇文章特征向量的夾角的值，夾角越小則說明其相似度越大绑洛。
這樣的方法既可以用有監(jiān)督的訓(xùn)練方法救斑，也可以用無監(jiān)督的閾值來不斷的聚類，直到不存在低于該閾值的兩個小類真屯。
算法本身的優(yōu)化：
- 刪除虛詞
- 儲存向量長度
- 刪除為0的元素脸候，只計算非零元素
- 位置的加權(quán) （標題的詞比文中的詞重要，開頭結(jié)尾的詞也更重要）
chapter 15
矩陣運算和文本處理中的兩個分類問題
同樣為前一章的問題绑蔫，如果不想兩兩計算文章之間的相似度(因為在復(fù)雜度很高)运沦，能否一次性算出所有文章的相關(guān)性。 使用奇異值分解(Singular Value Decomposition)可以做到
每一行代表一篇文章配深，每一列代表一個詞在對應(yīng)文章中的TF-IDF携添，則可以構(gòu)造出一個巨大的Matrix。
然后通過奇異值分解分成三個小矩陣相乘篓叶。
這個地方吳軍老師似乎寫錯了烈掠，我這里加以改正
- 第一個矩陣則為對文章進行分類的結(jié)果，每一行表示一篇文章缸托，每一列代表一個分類結(jié)果左敌。值是這一篇文章跟這個分類的相近程度。
- 第三個矩陣則為對詞進行的分類結(jié)果俐镐，每一列代表一個詞矫限，每一行為一個語義類，對應(yīng)的，該詞與這個語義類的相關(guān)程度叼风。
- 第二個矩陣則為語義類和文章分類的相關(guān)程度的矩陣取董。
但SVD的方法較上篇兩兩計算的方法粗糙，所以可以基于SVD的結(jié)果上去進行余弦計算的迭代咬扇。
chapter 16
信息指紋的存在
相似哈希--一類特殊的信息指紋
- 假定一個網(wǎng)頁中有若干個詞甲葬，先計算出它們的權(quán)重(例如TF-IDF的值)，再計算這些詞的信息指紋懈贺，若用8位二進制來記錄经窖。
- 擴展：將原先的8位的信息指紋擴展成8個實數(shù)，若w1的指紋第一位為1梭灿，則第一個實數(shù)+w1画侣，反之則-w1,。如此拓展堡妒，用若干個詞的權(quán)重的加減分別構(gòu)成8個實數(shù)配乱。
- 收縮：把8個實數(shù)變回一個8位的二進制數(shù)，如果大于0皮迟，就為1搬泥，否則就為0。這樣得到一個8位的二進制數(shù)字伏尼。
從而我們可以用一個簡單的相似哈希來代表一個網(wǎng)頁忿檩，然后比較兩個相似哈希就可以比較相似程度。
chapter 17
對于凱撒加密法之類的爆阶，可以通過統(tǒng)計詞頻燥透，可以輕易的破解這種加密方式。由于這些詞頻在加密前后沒有發(fā)生任何改變辨图，只是進行了轉(zhuǎn)變
RSA算法的加密
- 任意找兩個很大的質(zhì)數(shù)P班套，Q進行相乘
N = P * Q;
M = （P-1）*（Q - 1）- 找一個和M互素的整數(shù)E
- 找一個整數(shù)D，使得E * D 除以 M 余 1故河。
其中E是公鑰吱韭，D是私鑰。
加密： X^E mod N = Y 鱼的，Y即加密內(nèi)容杉女，X為待加密內(nèi)容。
解密：Y^D mod N = X
chapter 18
搜索引擎的反作弊：防止部分網(wǎng)站通過一些作弊手段提高在搜索引擎中的排名鸳吸。
搜索結(jié)果的權(quán)威性：PageRank的算法無法保證搜索結(jié)果的權(quán)威性熏挎，許多排名高的網(wǎng)站可能只是主流更關(guān)注的網(wǎng)站而非更權(quán)威的網(wǎng)站。所以需要引入提及（Mention）的概念晌砾，如果多篇文章或者網(wǎng)站在提及同一個話題時坎拐，提及的組織或個人很多，那么我們會傾向于使用這些組織或個人的搜索記錄排在前面。
計算權(quán)威度的步驟：
- 對網(wǎng)頁的內(nèi)容進行句法分析哼勇，以及對信息源的提及
- 利用互信息都伪，找到短語與信息源之間的相關(guān)性。
- 對短語進行聚類积担，
- 對信息源的網(wǎng)頁的子網(wǎng)頁和子目錄進行聚類
chapter 19
天文學(xué)上陨晶，古埃及人是根據(jù)天狼星和太陽在一起的位置來判斷一年中的時間和節(jié)氣
美索不達米亞文明興起時，古巴比倫人的歷法中產(chǎn)生了月和四季的概念帝璧，并且觀測到了五大行星不是簡單的圍繞地球轉(zhuǎn)先誉，而是波浪形的運動。所以的烁，行星（Planet）即指飄移的星球
托勒密發(fā)明了球坐標褐耳，赤道和零度經(jīng)線在內(nèi)的經(jīng)緯線，提出了黃道渴庆，發(fā)明了弧度制铃芦，用40-60個大圓套小圓的方法精確計算了所有行星運動的軌跡。襟雷。刃滓。(害怕)....制定了儒略歷（即每年365天，每4年為一個閏年耸弄，多一天）注盈。后來被教皇格里高利十三世改正。
開普勒的日心說剛開始叙赚，計算出來的行星運動軌跡反而沒有托勒密的高。
chapter 20
最大熵原理：對一個隨機事件的概率分布進行預(yù)測時僚饭，預(yù)測應(yīng)當(dāng)滿足全部已知條件震叮，對于未知的情況不要做任何的主觀假設(shè)，使用概率分布最均勻的模式鳍鸵，可以使得概率分布的信息熵最大苇瓣。
最原始的最大熵模型的訓(xùn)練方法是一種稱為通用迭代算法（Generalized Iterative Scaling）GIS的迭代算法。是一種EM算法偿乖。后來提出了改進迭代算法IIS击罪。
chapter 23
布隆過濾器
原理：在于兩個完全隨機的數(shù)字相沖突的概率很小，所以可以在很小的誤識別率的條件下贪薪，用很少的空間儲存大量信息媳禁。
優(yōu)點：只需要散列表1/8-1/4左右的大小就能解決同樣的問題
做法：若儲存1億個郵件地址，只需要準備16億個全部為0比特位(2億個字節(jié))画切，對每個點以郵件竣稽，使用8個不同的隨機數(shù)產(chǎn)生器，產(chǎn)生8個信息指紋，再用一個隨機數(shù)產(chǎn)生器把這8個信息指紋映射到1-16億的8個自然數(shù)毫别，現(xiàn)在將這8個位置全部設(shè)為1,娃弓。由此往復(fù)。
這樣給一個電子郵件Y岛宦，只需要檢查對應(yīng)8個位置是否為1台丛。即可。
缺點：存在誤分類砾肺，可能把錯誤認為該Y郵件地址已經(jīng)存在挽霉。
chapter 25
文法分析
自然語言中的句法分析一般指根據(jù)文法對一個句子進行分析，建立這個句子的語法樹债沮，即文法分析（Synatctic Parsing）炼吴。
對一個句子中各成分的語義進行分析，得到對這個句子語義的一種描述疫衩，即語義分析（Semantic Parsing）硅蹦。
傳統(tǒng)的文法分析是基于規(guī)則的方法，不斷地使用規(guī)則將樹的末端節(jié)點逐級往上合并闷煤，直到合并出根節(jié)點童芹。
后來發(fā)展出另外的方法：
- 先進行分詞
- 從左到右用括號括起來，進行分組
- 給每個括號一個句子成分鲤拿，重復(fù)括括號的過程
- 直到整個句子被一個大括號覆蓋假褪。每個括號，就是句子的一個成分近顷，括號之間的嵌套關(guān)系生音，就是不同層面的句子成分的構(gòu)成關(guān)系。
每次從左到右掃描詞或者成分時窒升，只需要判斷進行三個操作之一缀遍。
- 是否開一個新括號
- 是否繼續(xù)留在這個括號中
- 是否結(jié)束一個括號
并且在判斷哪個操作之前，建立了一個統(tǒng)計模型P（A|prefix）饱须，prefix表示了從句子開頭到目前位置所有的詞和其語法成分域醇。使用最大熵模型實現(xiàn)。
優(yōu)點：從左往右的一個掃描過程大大減少了分析的時間蓉媳，將算法的復(fù)雜度降到了句子長度的對數(shù)函數(shù)的級別譬挚，從算法的計算時間上來說已經(jīng)是一個最優(yōu)的算法
缺點：對于語義語法嚴謹?shù)膱罂木洌_率可以達到80%以上酪呻，但是如果需要分析網(wǎng)文的語義語法减宣，就會非常的差。但鑒于自然語言處理的實際應(yīng)用中玩荠，也只需要對語句進行淺層的分析蚪腋。
后來采用了一種新的數(shù)學(xué)模型工具---條件隨機場（CRF Conditional Random Field）
CRF
屬于一種 HMM（Hidden Markov Models）的拓展丰歌，所以也要符合馬爾科夫假設(shè)，同樣的也屬于一種特殊的概率圖模型（PGM）屉凯。
與HMM不同的地方在于立帖，觀察層不僅與當(dāng)前的隱含狀態(tài)有關(guān)，還可能會與前后的隱含層相關(guān)悠砚。晓勇，當(dāng)然隱含層自身還是一個馬爾科夫鏈。
使用最大熵模型的訓(xùn)練方法去求得邊緣概率灌旧，從而求得聯(lián)合概率绑咱。
chapter 26
維特比算法
略
CDMA技術(shù)
頻分多址、時分多址枢泰、碼分多址描融。
- 對頻率進行切分，每一路通信使用一個不同的頻率
- 將同一頻帶按時間分成很多份衡蚂。
- 將很多細分的頻帶合在一起窿克，很多路信息同時傳輸，應(yīng)該可以提高帶寬的利用率毛甲∧甓＃可以根據(jù)密碼去過濾無法解碼的信號，從而實現(xiàn)碼分多址
chapter 27
EM算法（Expectation Maximization Algorithm）
相比于
- 預(yù)先設(shè)定好的類別和文本中心進行聚類
- 自底向上地將文本兩兩比較進行聚類
EM算法可以隨機設(shè)定一些中心點玻募，然后進行多次迭代后即可收斂到少數(shù)的類只损。
前提是距離函數(shù)要足夠的好，保證同一類相對距離較近七咧，不同類的相對距離較遠跃惫。
若擴展到其它機器學(xué)習(xí)的問題中。
- 期望值計算過程：計算各個觀測數(shù)據(jù)輸入到模型中的計算結(jié)果
- 最大化的過程：重新計算模型參數(shù)艾栋，以最大化期望
缺點：如果優(yōu)化的目標函數(shù)是一個凸函數(shù)爆存，那么一定能保證得到全劇最優(yōu)解，但如果優(yōu)化的目標函數(shù)不能保證為凸函數(shù)裹粤，則不能保證為全局最優(yōu)解
chapter 28
Logistic Regression & 定向廣告
通過邏輯回歸模型，假設(shè)有k個影響點擊率的變量x1,x2,x3,...,xk蜂林。用線性組合的方法組合起來遥诉，這個和的結(jié)果作為邏輯回歸模型的自變量。將其代入邏輯回歸模型后即可得到一個概率噪叙。（由于一個邏輯回歸模型定義域為所有實數(shù)矮锈，值域只在0-1間。）
將k個變量與其系數(shù)作為每一個用戶得到定制標準睁蕾，并且根據(jù)數(shù)據(jù)挖掘?qū)＜襾硖幚矸治霭浚纯傻玫矫總€人定制化得到對特定廣告的點擊率债朵，從而實現(xiàn)定向廣告的目的。
通過最大熵模型的IIS方法可以直接訓(xùn)練邏輯回歸函數(shù)的參數(shù)
chapter 30
人工神經(jīng)網(wǎng)絡(luò)
特殊性
- 所有的節(jié)點都是分層的瀑凝，每一層節(jié)點可以通過有向弧指向上一層節(jié)點序芦，同一層節(jié)點之間沒有弧相互連接，且每一個節(jié)點不能越過一層連接到上上層的節(jié)點上粤咪。
2.每個弧上有一個權(quán)重谚中。
一般不會超過五層的網(wǎng)絡(luò)
擅長于在多維空間進行模式分類的問題。
