機器學習-theworld'sleadingsoftware

1、<p>　　機器學習的動機與應用</p><p><b>　　機器學習定義</b></p><p>　　廣義的來說，機器學習(wiki)是在不明確編程的情況下賦予機器學習的能力的一門科學。而機器學習經典的定義是Mitchell的《機器學習》中的一段：A computer program is said to learn from experience E w

2、ith respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E。(對于某類任務 T 和性能度量P，如果一個計算機程序在T 上以P 衡量的性能隨著經驗E 而自我完善，那么我們稱這個計算機程序在從經驗E 學習。)</

3、p><p>　　舉例子：垃圾郵件分類。任務T是判斷一封郵件是否是垃圾郵件，性能度量P是識別的準確率，經驗E是我們收集到的垃圾郵件和非垃圾郵件。我們的目標是設計一個算法，該算法能夠通過學習已有的數據，來準確的判斷一封新的郵件是否是垃圾郵件。</p><p>　　一個完整定義的學習問題需要一個明確界定的任務、性能度量標準以及訓練經驗的來源。</p><p>　　基礎知識需求

4、與常見應用</p><p>　　機器學習是近20多年興起的一門多領域交叉學科，涉及概率論、統(tǒng)計學、逼近論、凸分析、算法復雜度理論等多門學科。</p><p>　　基礎知識主要包括：①計算機科學的基本知識，包括基本的編程能力，知道算法復雜度等概念以及一些數據結構如隊列、棧、二叉樹等。②概率論與統(tǒng)計知識(達到本科要求)，如隨機變量，期望等等。③基本的線性代數課程(本科階段)，知道什么是矩陣以及

5、矩陣特征向量等等。</p><p>　　機器學習已經有了十分廣泛的應用，例如：數據挖掘、計算機視覺、自然語言處理、生物特征識別、搜索引擎、醫(yī)學診斷、檢測信用卡欺詐、證券市場分析、DNA序列測序、語音和手寫識別、戰(zhàn)略游戲和機器人運用。</p><p><b>　　機器學習算法分類</b></p><p>　　監(jiān)督學習：從給定的訓練數據集中學習出一

6、個函數，當新的數據到來時，可以根據這個函數預測結果。監(jiān)督學習的訓練集要求是包括輸入和輸出，也可以說是特征和目標。訓練集中的目標是由人標注的。常見的監(jiān)督學習算法包括回歸分析和統(tǒng)計分類。</p><p>　　無監(jiān)督學習與監(jiān)督學習相比，訓練集沒有人為標注的結果。常見的無監(jiān)督學習算法有聚類。</p><p>　　半監(jiān)督學習介于監(jiān)督學習與無監(jiān)督學習之間。</p><p>　　

7、增強學習通過觀察來學習做成如何的動作。每個動作都會對環(huán)境有所影響，學習對象根據觀察到的周圍環(huán)境的反饋來做出判斷。</p><p>　　具體的機器學習算法有：</p><p>　　構造條件概率：回歸分析和統(tǒng)計分類</p><p>　　人工神經網絡決策樹(Decision tree)高斯過程回歸</p><p>　　線性判別分析最近鄰居法

8、感知器徑向基函數核</p><p><b>　　支持向量機</b></p><p>　　通過再生模型構造概率密度函數(Probability density function)：</p><p>　　最大期望算法(Expectation-maximization algorithm)</p><p>　　graphi

9、cal model：包括貝葉斯網和Markov隨機場</p><p>　　Generative Topographic Mapping</p><p><b>　　近似推斷技術：</b></p><p>　　馬爾可夫鏈(Markov chain)蒙特卡羅方法變分法</p><p>　　最優(yōu)化(Optimization

10、)：大多數以上方法，直接或者間接使用最優(yōu)化算法。</p><p><b>　　監(jiān)督式學習</b></p><p>　　在監(jiān)督式學習中，如果預測的結果是連續(xù)的變量，我們稱之為回歸問題(regression)，比如房價預測問題，房子的價格是連續(xù)變量，可以使用回歸算法建模預測。如果預測的結果是離散變量，則稱之為分類(classification)，比如判斷病人的腫瘤是否是良

11、性，結果有是或否，是離散變量，可以使用分類算法建模預測。</p><p>　　監(jiān)督學習的應用與梯度下降</p><p><b>　　監(jiān)督學習</b></p><p>　　如上圖所示，監(jiān)督學習:對于給定的訓練集合，按照某一學習算法學習之后，得到一種好的假設(Hypotheses)用于預測新的數據。</p><p><

12、b>　　梯度下降</b></p><p>　　已知m組數據(x1,y1)…(xm, ym)，其中xi是具有n維特征的向量，此外，我們設定xi(0) =1(即截距項)。我們做如下假設：</p><p>　　h(x) = = (此為回歸模型的假設模型)</p><p>　　對于給定的訓練集合，如何選擇最優(yōu)的θ值(權重或參數)呢(這里的x是n+1*m

13、維矩陣)？一個合理的方法是：至少在訓練集合上，θ會使預測值h(x)越接近實際值y越好。因此，我們定義一個成本函數(cost function) J(θ)：</p><p><b>　　J(θ) =</b></p><p>　　該成本函數使用誤差的平方和，類似于普通最小二乘法(沒有平均化誤差平方和)。</p><p><b>　　最小均

14、方算法</b></p><p>　　給定的訓練集合，如何選擇最優(yōu)的θ值使J(θ)？這里我們采用梯度下降法。梯度下降法的基本思想是在起始隨機得到θ值后，之后每次更新θ值的方式如下：</p><p>　　θj := θj? α*(其中α稱之為學習速率)</p><p>　　即θ每次以一定的步伐按照J(θ)最快速下降的方向更新值。我們進一步分解參數更新公式的右

15、邊。</p><p><b>　　= = * </b></p><p>　　= (h(x)-y) * = (h(x)-y)*xi</p><p>　　因此，參數更新的方式如下：</p><p>　　θj := θj + α(y-h(xi))*xji</p><p>　　該更新方法稱之為LMS

16、算法(least mean squares，最小均方法)，也被稱為Widrow-Hoff 學習算法。該方法顯得很自然和直觀化。比如，當誤差(y-h(x))越大的時候，那么參數更新的步伐就越大。檢測是否收斂的方法：1) 檢測兩次迭代θj的改變量，若不再變化，則判定收斂；2) 更常用的方法：檢驗J(θ)，若不再變化，判定收斂。需要注意的是，學習系數一般為0.01或者0.005等，我們可以發(fā)現樣本量越大，(y-h(xi))*xji會

17、相對較大，所以在學習系數中用一個常數除以樣本來定相對合理，即0.005/m。</p><p>　　對于LMS算法，剛才推導的公式是針對于一個樣本，如果樣本多于一個，那么我們可以有兩種方式更新參數。一種是每一次更新都使用全部的訓練集合，該方法稱之為批量梯度下降(batch gradient descent)。需要注意的是，梯度下降法很可能得到局部最優(yōu)解，而我們這里的回歸分析模型僅有一個最優(yōu)解，因此局部最優(yōu)解就是最終

18、的最優(yōu)解。(成本函數為凸函數)。另外一種是針對訓練集合中每一個樣本，每次都更新所有的參數值，該方法稱之為隨機梯度下降(stochastic gradient descent)。當數據量很大的時候，批量梯度下降法計算量較大，而隨機梯度下降方法往往相對較優(yōu)。通常情況下，隨機梯度下降比批量梯度下降能更快的接近最優(yōu)值(但也許永遠也得不到最優(yōu)值)，數據量大的情況下，通常選擇使用隨機梯度下降法。</p><p>　　梯度下降

19、法的缺點是:靠近極小值時速度減慢(極小值處梯度為0)，直線搜索可能會產生一些問題(得到局部最優(yōu)等)，可能會'之字型'地下降(學習速率太大導致)。</p><p><b>　　標準方程組推導</b></p><p>　　最小化成本函數的方式不只是有梯度下降法，這里我們采用標準方程組的方式求解得到精確的解。對于成本函數J(θ) ，我們定義輸入變量X是m*(

20、n+1)維矩陣(包含了截距項)，其中m表示樣本數，n表示特征數。輸出是m*1維矩陣，參數θ是n+1*1維矩陣，則J(θ)可以如下表示：</p><p>　　J(θ) = (Xθ – )T * (Xθ-)</p><p>　　要求解θ使得J(θ)最小，那么只需要求解J(θ)對θ的偏微分方程即可。</p><p>　　?θJ(θ) = [(Xθ – )T * (Xθ-)

21、] </p><p>　　= T]*(Xθ – ) + (Xθ – )T ]*</p><p>　　= XT*(Xθ – ) + XT*(Xθ – )</p><p>　　= XT*(Xθ – ) </p><p>　　= XT*X*θ – XT*</p><p>　　因此，令?θJ(θ) = 0，即可求得使J

22、(θ)最小的θ的值，因此：XT*X*θ – XT* = 0，得到 θ = (XT*X)-1 * (XT*)。在求解回歸問題時候，可以直接使用該結果賦值于θ，不過這里存在的問題是對矩陣的求逆，該過程計算量較大，因此在訓練集合樣本較大的情況并不適合。</p><p>　　注：?θJ(θ)表示對J(θ)中的每一個θ參數求偏微分。這里化簡的方式是矩陣偏微分注意：AT*B) = BT)*A, AT = (A)T, AT

23、*B = (BT*A)T。</p><p><b>　　概率解釋</b></p><p>　　對于回歸問題，我們不禁要問為什么線性回歸或者說為什么最小均方法是一個合理的選擇呢？這里我們通過一系列的概率假設給出一個解釋。(下一講)</p><p><b>　　欠擬合與過擬合概念</b></p><p>

24、;<b>　　欠擬合與過擬合概念</b></p><p>　　圖3-1 欠擬合與過擬合概念演示</p><p>　　通常，你選擇讓交給學習算法處理的特征的方式對算法的工作過程有很大影響。如圖3-1中左圖所示，采用了y = θ0 + θ1x的假設來建立模型，我們發(fā)現較少的特征并不能很好的擬合數據，這種情況稱之為欠擬合(underfitting)。而如果我們采用了y =

25、 θ0 + θ1x+ θ2x2的假設來建立模型，發(fā)現能夠非常好的擬合數據(如中圖所示)；此外，如果我們采用了y = θ0 + θ1x+ θ2x2+ θ3x3 + θ4x4 + θ5x5，發(fā)現較多的特征導致了所有的訓練數據都被完美的擬合上了，這種情況稱之為過擬合(overfitting)。</p><p>　　這里，我們稍微談一下過擬合問題，過擬合的標準定義(來自Mitchell的機器學習)標準定義：給定一個假設空

26、間H，一個假設h屬于H，如果存在其他的假設h’屬于H,使得在訓練樣例上h的錯誤率比h’小，但在整個實例分布上h’比h的錯誤率小，那么就說假設h過度擬合訓練數據。過擬合問題往往是由于訓練數據少(無法覆蓋所有的特征學習，換句話也可以認為是特征太多)等原因造成的。在以后的課程會具體講解。</p><p>　　對于此類學習問題，一般使用特征選擇算法(有一講專門講)或非參數學習算法，下面將要降到的局部加權線性回歸就是屬于該

27、方法，以此緩解對于特征選取的需求。</p><p><b>　　局部加權線性回歸</b></p><p>　　局部加權線性回歸(locally weighted linear regression)屬于非參數學習算法的一種，也稱作Loess。</p><p>　　對于原始的回歸分析，我們基本的算法思想是：</p><p>

28、;　　1) 尋找合適的θ使得 最??；2) 預測輸出。</p><p>　　而對于局部加權線性回歸算法的基本思想是：</p><p>　　1) 尋找合適的θ使得 最?。?) 預測輸出。</p><p>　　這里，局部加權線性回歸與原始回歸分析不同在于，多了權重wi，該值是正的。對于特點的點，如果權重w較大，那么我們選擇合適的θ使得最?。蝗绻麢嘀豾較小，那么誤差的平方方

29、在擬合過程中將會被忽略掉。換言之，對于局部加權回歸，當要處理x時，會檢查數據集合，并且只考慮位于x周圍的固定區(qū)域內的數據點(較遠點不影響因權重較低而被忽略)，對這個區(qū)域內的點做線性回歸，擬合出一條直線，根據這條擬合直線對x的輸出，作為算法返回的結果。</p><p>　　一個標準的且常用的權重選擇如下：</p><p>　　wi = exp(-)</p><p>　

30、　需要注意，這里的x是我們要預測的輸入，而xi是訓練樣本數據。從公式看，離x越近的點，權重越大，而這里的權重公式雖然與高斯分布很像，但是沒有任何關系，當然用戶可以選擇不同的函數作為權重函數。而τ決定了各個點權重隨距離下降的速度，稱之為波長。τ越大，即波長越大，權重下降速度越慢。如何選擇合適的τ值，將會在模型選擇一講講述。另外需要注意的是，如果x是多維特征數據的時候，那么權重是多維特征參與計算后的結果(結果為一維)，即w(i) = exp

31、(?(x(i)?x)T (x(i)?x)/())。(i表示樣本下標，j表示特征下標)</p><p>　　參數學習算法(parametric learning algorithm)定義：參數學習算法是一類有固定數目參數，以用來進行數據擬合的算法。設該固定的參數集合為。線性回歸即使參數學習算法的一個例子。非參數學習算法(Non-parametric learning algorithm)定義：一個參數數量會隨m(訓

32、練集大小)增長的算法。通常定義為參數數量雖m線性增長。換句話說，就是算法所需要的東西會隨著訓練集合線性增長，算法的維持是基于整個訓練集合的，即使是在學習以后。</p><p>　　由于每次進行預測都要根據訓練集擬合曲線，如果訓練樣本非常大，那么該方法可能是代價較大，可以參考Andrew Moore的KD-tree方法來思考解決。此外，局部加權線性回歸依舊無法避免欠擬合和過擬合的問題。 </p>&l

33、t;p><b>　　回歸模型的概率解釋</b></p><p>　　對于回歸問題，我們不禁要問為什么線性回歸或者說為什么最小均方法是一個合理的選擇呢？這里我們通過一系列的概率假設給出一個解釋。</p><p>　　首先，我們假設預測值y與輸入變量滿足如下方程：</p><p>　　y(i) = θT*x(i) + ε(i)</p&g

34、t;<p>　　其中ε(i)表示由于各種未考慮的因素造成的殘差或者噪音等，我們進一步假設ε(i)獨立同分布(誤差項彼此之間是獨立的，并且他們服從均值和方差相同的高斯分布)，服從均值為0，方差為δ2的正態(tài)分布，即ε(i) ～(0, δ2)，(為什么如此假設呢？一個是便于數學計算，另一個是可以通過中心極限定理等證明該殘差服從正態(tài)分布)具體表示為：</p><p>　　p(ε(i)) = </p&g

35、t;<p><b>　　代入之后如下：</b></p><p>　　p(y(i)|x(i); θ) = </p><p>　　這里的θ不是隨機變量，而是具體的值。p(y(i)|x(i); θ)，表示對于給定的x(i)和θ，y(i)出現的概率。那么對于一組y的話，可以表示為p(|X; θ)，這就相當于θ的似然性。(注意似然性與概率性不同，概率用于在已知一些

36、參數的情況下，預測接下來的觀測所得到的結果，而似然性則是用于在已知某些觀測所得到的結果時，對有關事物的性質的參數進行估計。那么參數θ的似然函數如下：</p><p>　　L(θ) = L(θ;X, ) = p(|X; θ)</p><p>　　根據以上的假設和分析，我們得到：</p><p><b>　　L(θ) = </b></p&g

37、t;<p><b>　　= </b></p><p>　　對于該似然函數，我們已知了x,y，需要找一個合適且合理的方法求取θ。最大似然法則告訴我們選擇的θ應該是L(θ)最大。實際意義，選擇參數使數據出現的可能性盡可能的大(讓發(fā)生的事情概率最大化)。為了方便計算，我們通常對似然函數求取對數，將乘機項轉化成求和。化簡如下(注意本文中l(wèi)og的含義表示取自然對數，而不是取10為底對數)

38、：</p><p>　　?(θ) = log(L(θ)) </p><p><b>　　= log()</b></p><p><b>　　= </b></p><p>　　=m*log() - </p><p>　　對于上式，最大化似然函數L(θ)就相當于最小化，即J(θ

39、)。</p><p>　　總結而言，對于數據作出概率假設之后，最小二乘回歸方法相當于最大化θ的似然函數。通過概率假設，我們驗證該方法的合理性，然而這些概率假設對于最小二乘法的合理性卻并不是必要的，當然確實有其他的更自然的假設能夠證明最小二乘法的合理性。</p><p>　　需要注意的是，對于上面的討論，最終的θ選擇并不依賴于(我們假設的誤差俯沖的分布方差)盡管值并不知道。當討論到指數族和廣

40、義線性回歸的時候，我們還會提到這些。</p><p>　　注意：我們用到的假設，第一殘差項獨立同分布且分布均值為0，樣本之間相互獨立，此外，要想有結果需要輸入特征不存在多重共線性，即輸入特征是滿秩矩陣。</p><p>　　Logistic回歸模型</p><p>　　在以上的討論中，主要是關于回歸問題。借來下，我們討論分類問題，與回歸問題很類似，不過待預測的y不是

41、連續(xù)變量，而是有限的離散變量。這里，我們主要討論二元分類，即預測的結果只有是否或者對錯之類，習慣用01表示，其中0表示否定(negative)的結果，1表示肯定(positive)的結果。對于給定的輸入X，y也被稱之為標簽(label)。</p><p>　　針對分類問題，我們可以暫時忽略y的離散性，而采用回歸分析的方法進行分析。然而，我們很容易發(fā)現回歸分析效果很差，尤其是不好解釋預測值不等于{0,1}的情況。為

42、此，我們需要更改我們假設：</p><p>　　hθ(x) = g() = 這里的g(z) = ，被稱之為logistic函數或sigmoid函數。函數圖形如下：</p><p>　　當z趨近于無窮大的時候，g(z)趨近于1，當z趨近于無窮小的時候，g(z)趨近于0。這里需要注意的是：我們仍然設定截距x0=1,即 = θ0 + 。此外，對于g(z)的導數g’ (z) : g’(z)

43、= g(z)*(1-g(z))。因此，對于使用logistic函數作為假設H的模型，我們同樣采用假設和使用最小二乘法來最大化參數的最大似然函數。</p><p>　　我們假設：P(y=1 | x;θ) = hθ(x) P(y=0 | x;θ) = 1- hθ(x) 該假設可以歸結為：</p><p>　　p(y | x;θ) = (hθ(x))y* (1- hθ(x))(1-y)<

44、;/p><p>　　那么最大似然函數如下：</p><p><b>　　取對數優(yōu)化后：</b></p><p>　　同樣，我們采用梯度下降法來迭代求取參數值，即按照θj := θj? α*方式跟新參數值。</p><p>　　在推導過程中，我們使用g’(z)=g(z)*(1-g(z))該特性。最終的更新結果如下：</p

45、><p>　　對比LMS算法中更新參數的方法，與logistic回歸法更新權重的一樣。唯一不同的在于假設hθ(x)，這個時候的假設是非線性的。當我們將到廣義線性回歸的時候，我們再來看是不是所有的算法夠可以歸結到這樣的更新方式呢？</p><p><b>　　感知器學習模型</b></p><p>　　在logistic方法中，g(z)會生成[0,1

46、]之間的小數，但如何是g(z)只生成0或1？這里我們重新定義g(z)函數如下：</p><p>　　之后，我們同樣假設hθ(x) = g() ，按照之前的方法(梯度下降法)我們將會同樣得到參數更新的方式為：θj := θj + α(y-h(xi))*xji ，該模型稱之為感知器學習算法(perceptron learning algorithm)。</p><p>　　20世紀60年代，認

47、為在神經網絡模型采用“感知器學習”算法的神經元是較為粗糙的，但是他仍然能很好的表達學習算法理論。雖然從公式外形上來看，感知器學習與logistic回歸和線性回歸差不多，但是我們很難賦予感知器預測值的概率解釋，或者使用最大似然估計推導出感知器模型。</p><p>　　牛頓法與廣義線性模型</p><p><b>　　牛頓法求解最優(yōu)值</b></p>&l

48、t;p>　　在上面優(yōu)化cost function 的時候，我們采用了梯度下降法。在這里，我們采用另外一種方法求解J(θ)的最小值(極小值)——牛頓法(Newton’s method)。</p><p>　　首先，選擇一個接近函數f(x)零點的x0，計算相應的f(x0)和切線斜率f'(x0)(這里f'表示函數f的導數)。然后我們計算穿過點(x0, f(x0))并且斜率為f'(x0)的直

49、線和x軸的交點的x坐標，也就是求如下方程的解：</p><p>　　f(x0) = (x0-x) * f'(x0)</p><p>　　我們將新求得的點的x坐標命名為x1，通常x1會比x0更接近方程f(x)=0的解。因此我們現在可以利用x1開始下一輪迭代。迭代公式可化簡為如下所示：</p><p>　　xn+1= xn - f(xn) / f'(x

50、n)</p><p>　　已經證明，如果f'是連續(xù)的，并且待求的零點x是孤立的，那么在零點x周圍存在一個區(qū)域，只要初始值x0位于這個鄰近區(qū)域內，那么牛頓法必定收斂。 并且，如果f'(x)不為0, 那么牛頓法將具有平方收斂的性能. 粗略的說，這意味著每迭代一次，牛頓法結果的有效數字將增加一倍。</p><p>　　回歸到最大似然函數優(yōu)化? (θ)(或L(θ))，求解? (θ)

51、的最大值也就相當于令l(θ)對θ的導數為0，即求解θ使得? ' (θ) = 0，那么牛頓法迭代的過程就會變?yōu)椋?lt;/p><p>　　θ := θ – ? ' (θ) / ? ' '(θ) (一階導數除以二階導數)</p><p>　　其中 := 表示更新時的賦值。需要注意的是，無論是求解最大值還是最小值，該迭代公式都是減號。(求取的極值，既可以是極大值也可

52、以是極小值)</p><p>　　以上討論的θ都是一個值，而有時候θ也可能是一個矩陣，比如在選擇多個特征的線性回歸模型中。當θ是一個矩陣的時候，牛頓法需要變換如下：</p><p>　　θ := θ ? H?1 ?θ ?(θ)</p><p>　　其中，?θ ?(θ)表示?(θ)對θ的偏微分矩陣，而H是一個n*n的矩陣(n表示特征數目，實際上因加上截距項，常為(n+

53、1)*(n+1))，稱之為海森矩陣(hessian矩陣)，這里表示?(θ)對θ的偏微分后再對θ的偏微分，定義如下：</p><p><b>　　Hij = </b></p><p>　　通常而言，牛頓法比批量梯度下降法收斂速度要快(牛頓法沒有學習系數，且采用了二階導數)，但是由于需要求解hessian矩陣逆矩陣，因此計算量較大，故牛頓法不適合n較大(特征較多)的優(yōu)化求

54、解。當使用牛頓法來優(yōu)化logistic模型中的? (θ)時，該方法又稱為費歇爾得分(fisher scoring)。</p><p><b>　　廣義線性模型</b></p><p>　　目前為止，我們講解了一個回歸模型和一個分類模型，在線性回歸模型中，我們假設y|x; θ ～ N(μ, σ2)，在分類模型中，我們假設y|x; θ ～ Bernoulli(φ)，其中μ

55、,φ均是x和θ的函數。然而，這兩個模型只是一個廣義線性模型(Generalized Linear Models)下的兩種情況而已。</p><p><b>　　指數族分布</b></p><p><b>　　我們指定一類分布：</b></p><p>　　p(y; η) = b(y) exp( ηT T(y) ? a(η)

56、)</p><p>　　其中，η稱為該分布的自然參數(natural parameter)或標準參數(canonical parameter)，通常是一個實數(也可能是實數矩陣，注意轉置符號)；而T(y)稱之為充分統(tǒng)計量(sufficient statistic)，統(tǒng)計量，依賴且只依賴于樣本y1,y2…yn，它不含總體分布的任何未知參數，通常情況下T(y) = y；a(η)是累計函數(cumulant funct

57、ion，log partition function或normalization factor)，exp(?a(η))主要是為了歸一化，保證p(y; η)的值在0-1之間。指數族分布主要是a,b,T三個函數，而參數是η，不同的η值將會得到不同的概率分布，接下來分別以伯努力分布和高斯分布為例。</p><p>　　以伯努力(Bernoulli)分布為例：伯努力隨機變量只有兩個值y ∈ {0, 1}，假設伯努力分布服

58、從均值為φ 的B(φ)，那么p(y = 1; φ) = φ，p(y = 0; φ) =1- φ，綜合起來就是如下：</p><p>　　p(y; φ) = φy (1 ? φ)1?y</p><p>　　= exp( ylog(φ) + (1-y)log(1 ? φ) )</p><p>　　=exp( ylog(φ) + log(1 – φ) +ylog(

59、1/(1- φ)) )</p><p>　　= exp( ylog(φ /(1- φ) + log(1 – φ))</p><p>　　對比指數族分布，我們可以得到：η = log(φ /(1- φ)，反過來由η可以求得φ = 1/( 1+exp(-η) )(恰好是sigmoid函數)。繼續(xù)把b,a,T求解完整，那么T(y) = y，a(η) = ?log(1 ? φ) = log(1 +

60、 exp(η) )， b(y) = 1。即伯努力分布可以是指數族分布的一種。</p><p>　　同樣，我們考慮高斯分布。在推導回歸問題的時候，我們提到最終的結果與高斯分布中的σ2沒有關系，因此可以隨意選擇方差值，這里為了方便計算設定σ2=1，那么：</p><p>　　p(y; μ) = </p><p><b>　　= </b>&l

61、t;/p><p><b>　　= </b></p><p>　　因此，可以得到：η = μ，T(y) = y，a(η) = μ2/2 = η2/2，b(y) =</p><p>　　當然還有很多其他的分布，比如泊松分布(Poisson，適合于描述單位時間內隨機事件發(fā)生的次數的概率分布，如某一服務設施在一定時間內受到的服務請求的次數，電話交換機接到呼

62、叫的次數、汽車站臺的候客人數、機器出現的故障數、自然災害發(fā)生的次數、DNA序列的變異數、放射性原子核的衰變數等等)，伽馬分布(gamma，伽瑪函數可將整數拓展到了實數與復數域上)，指數分布(exponential，指數分布可以用來表示獨立隨機事件發(fā)生的時間間隔，比如旅客進機場的時間間隔、時間序列問題等等)，貝塔分布(beta)，狄利克雷分布(Dirichlet)等等。</p><p><b>　　廣義線

63、性模型結構</b></p><p>　　不管是回歸問題還是分類問題，我們可以推廣到：預測一個隨機變量y,且y是x的函數。為了推倒廣義線性回歸模型(GLM),我們需要以下三個假設：</p><p>　　y | x; θ ～ ExponentialFamily(η) ，假設試圖預測的變量y在給定x，以θ作為參數的條件概率，屬于以η作為自然參數的指數分布族。</p>&

64、lt;p>　　對于給定的x，我們的目標是預測T(y)的期望值。在我們的很多例子中，T(y) = y，這就意味著我們通過學習到的假設(hypothesis)的預測結果h(x)滿足h(x) = E[y|x]。</p><p>　　自然參數η與x是線性關系，即η = θT x。</p><p>　　為了證明普通最小二乘法和logistic回歸是GLM的一種特殊情況，我們使用GLM的基本假設

65、重新推倒一下最小二乘法和logistic回歸。</p><p>　　對于普通最小二乘法，根據GLM的第一個假設，我們有對于給定的x,y服從高斯分布N(μ, σ2)，根據假設二和假設三，我們知道hθ(x) = E[y|x; θ] = μ = η = θT x；(其中μ = η在上一小節(jié)已經求得)。</p><p>　　同樣對于logistic回歸，我們假設對于給定的x，y服從伯努力分布，即

66、y|x; θ ～ Bernoulli(φ)。對于φ，我們已經求得 φ = 1/(1 + exp(-η)) 。根據假設二和假設三，hθ(x) = E[y|x; θ] = φ = 1/(1 + exp(-η)) = 1/(1 + exp(-θT x))。</p><p>　　更技術上的來說，對于g(η) = E[T(y); η]而言，g是自然參數η的函數，稱之為正則響應函數(canonical response f

67、unction)，而對于g-1則稱之為正則關聯函數(canonical link function)。這樣看，對于指數分布組而言正則響應函數只是辨別函數，比如對于伯努力分布而言就是logis+tic函數。</p><p>　　Softmax 回歸</p><p>　　這里我們考慮一個更復雜的GLM模型。對于分類問題，我們這里分類結果不是二元分類，而是有k個分類結果，即y ∈ {1, 2,

68、. . . , k}，比如對于郵件分類，我們不想分成垃圾郵件和非垃圾郵件，而是分成私人郵件，工作郵件和垃圾郵件。對于我們的響應變量(目標變量)y仍然是離散的，不過數量超過兩個，這里我們采用多項分布(multinomial distribution)來分析。</p><p>　　為了推導出符合多分類的廣義線性模型，我們需要讓參數多項話。參數多項化的一種方式是設定k個參數分別為φ1, . . . , φk，來應對每一

69、個分類結果的概率。但是這樣的結果可能是冗余的，更準確的說是不能保證各個結果之間的相互獨立性(因為我們知道概率之和等于一，即所有φi之和等于1，那么最后一個類的參數值將會由之前的類的參數值決定)。因此，我們只需要設定k-1個參數φ1, . . . , φk-1，而φk = 1 – sum(φi)，但是我們需要注意的是：我們知道φk的值，但是φk并不是我們設定的參數。</p><p>　　為了更好的表示多項式指數族分

70、布，我們定義T(y)∈ Rk-1，如下：</p><p>　　與之前不同，不再有T(y) = y，而且T(y)是一個k-1維度的向量，(T(y))i表示向量T(y)的第i個元素。這里我們引入一種表達表達方式，1{·}表示如果大括號里為真，則結果為1，比如(1{True} = 1, 1{False} = 0，1{2 = 3} = 0。由此，我們找到了T(y)與y之間的關系，T(y)i = 1{y = i}

71、。因此，E[(T(y))i] = P(y = i) = φi。</p><p>　　因此，在多元廣義回歸模型下，我們根據獨立事件概率乘法原則有：</p><p>　　p(y; φ) = </p><p><b>　　= </b></p><p><b>　　= </b></p>

72、;<p>　　= exp((T(y))1 log(φ1) + (T(y))2 log(φ2) +· · · +log(φk))</p><p>　　= exp((T(y))1 log(φ1/φk) + (T(y))2 log(φ2/φk) + · · ·</p><p>　　+ (T(y))k?1 log(φk?1/

73、φk) + log(φk))</p><p>　　= b(y) exp(ηTT(y) ? a(η))</p><p>　　因此，針對參數有如下結果：</p><p>　　對于1至k-1，ηi = log(φi / φk)，轉換一下結果為：exp(ηi) = φi / φk ，繼續(xù)轉換得到， φk exp(ηi) = φi ，根據sum( φi) = 1，因此

74、可以得到：</p><p>　　φk = sum( φi) = 1</p><p>　　因此， φi = exp(ηi) / ，該方程將φi 和ηi 聯系起來了，稱之為softmax 函數。為了完成該模型，我們使用假設三，即對于i從1到k-1，ηi = T x，其中θ∈ Rn+1。此外，我們可以假設=0，那么就像之前的矩陣，ηk = T x = 0。因此，針對于給定xθ的y的條件概率：

75、</p><p>　　p(y = i|x; θ) = φi = exp(ηi) / = exp(T x) / </p><p>　　這個針對于y ∈ {1, . . . , k}的多元分類模型，稱之為softmax 回歸(softmax regression)。</p><p>　　我們的假設輸出結果是h θ (x) = E[T(y)|x; θ]，即</

76、p><p>　　從結果看，我們的輸出結果將包含1到k的各個結果的概率值，且概率值之和等于1。</p><p>　　最后，我們討論一下參數估計的問題。類似于最小二乘法和logistic回歸，假設我們有m組訓練數據集，那么利用最大似然函數如下：</p><p>　　接下來，我們可以使用梯度下降法或牛頓法求解其極大值。這里我們分別對k個θ分別求解偏微分，那么得到的迭代公式，最

77、終的結果與之前結果類似，如下：</p><p>　　關于更詳細的介紹請參見深度學習——softmax回歸。</p><p>　　注：如果需要對k個類別的數據分類，那么選擇使用 softmax 分類器呢，還是使用 logistic 回歸算法建立 k 個獨立的二元分類器呢？這一選擇取決于你的類別之間是否互斥，例如，如果互斥的話，可以選擇softmax 分類器。如果不互斥的話，選擇K個獨立的二分

78、類的 logistic 回歸分類器更為合適。</p><p><b>　　生成學習算法</b></p><p><b>　　生成學習算法引入</b></p><p>　　目前為止，我們主要講解了條件概率模型p(y|x,θ)的學習算法。接下來，我們將討論其他的學習算法。接下來舉個例子，比如現在遇到一個分類問題，基于一些特征來

79、判斷一個動物是大象 (y = 1) 還是小狗 (y = 0)?；诮o定的數據集，我們可以采用logistic回歸或者感知器學習的方法來尋找一條直線(稱之為決策邊界)把大象和小狗分割開割開來。之后預測新的動物時，只要判斷它在決策邊界的哪一邊就可以預測其所屬分類。</p><p>　　現在有另外一種方法。首先是查看大象的數據，然后建立一個什么是大象的模型，之后查看小狗的數據，建立一個什么是小狗的模型。之后，遇到新的動

80、物，只要分別代入兩個模型中，看更像小狗還是大象就可以分類了。</p><p>　　通過訓練集合來學習p(y | x)的學習算法稱之為判別學習算法(discriminative learning algorithms)，而通過訓練集合來學習得到p(x | y)的學習算法則稱之為生成學習算法(generative learning algorithms)。對于上大象和小狗的例子，p(x | y=0)表征了小狗的特征分

81、布。</p><p>　　在知道了類的先驗概率(class priors)p(y)之后，根據貝葉斯規(guī)則(Bayes rule)，可以得到：p(y | x) = p(x | y) p(y) / p(x)，其中分母p(x) = p(x | y=1)p(y = 1) + p(x | y =0) p(y = 0) (全概率公式)。如果只是為了預測(判斷哪一個p(y | x)更大)，我們就不需要計算分母，只需要比較分子的大

82、小就可以。</p><p><b>　　高斯判別模型</b></p><p>　　第一個生成學習算法，我們通過高斯判別分析(Gaussian discriminant analysis (GDA))講述。在這個模型中，將假設p(x | y)服從多元正態(tài)分布(multivariate normal distribution)。這里簡單的介紹下多元正態(tài)分布。</p&

83、gt;<p>　　多元正態(tài)分布，又稱為多元高斯分布，它的均值µ ∈ Rn，它的方差Σ稱為方差矩陣(covariance matrix)， Σ ∈ Rn*n，是一個對稱矩陣，表示為Ν (µ, Σ)，表示如下：</p><p>　　更多介紹可以參見(多元正態(tài)分布)</p><p>　　當我們遇到一個分類問題，且特征是連續(xù)變量時，我們可以采用高斯判別模型，通過多

84、元正態(tài)分布來表達p(x|y)，具體為y ～ Bernoulli(φ)，x|y = 0 ～ N (µ0, Σ)，x|y = 1 ～ N (µ1, Σ)，表達式如下：</p><p>　　這里，需要注意我們的假設條件中有兩個不同的µ(分別為µ0 µ1), 但是Σ卻只有一個(特征之間的方差)。之后，采用最大似然估計，可以得到：</p><p>　

85、　通過求解最大似然估計，我們得到各個參數的估計值(實際推導過程中，可以把樣本分成1-k,k-m分別表示結果為0和1的結果，這樣能夠將復雜的表達式簡單化，其中k=)：</p><p>　　形象的來說，該算法可以表述如下：對于用于訓練集合得到的兩個高斯分布，他們具有相同的輪廓和等高線(因為方差矩陣相同)，而均值不同。我們也可以看到決策邊界p(y = 1|x) = 0.5，將兩個類分開。</p><

86、p>　　GDA VS logistic回歸</p><p>　　GDA模型和logistic回歸模型具有相似的關系，即如果我們把概率質量p(y = 1|x; φ, µ0, µ1, Σ)看成是x的一個函數，那么我們可以用如下公式來表述：</p><p>　　p(y = 1|x; φ, µ0, µ1, Σ) =1 / (1 + exp(?θTx)&

87、lt;/p><p>　　其中θ是 φ, µ0, µ1, Σ的函數，這恰好是logistic回歸——是對于p(y =1|x)的高斯判別分析。然而，通常來說，GDA和logistic回歸會給出不同的決策邊界，那么哪一種模型更好呢，或者說我們該如何選擇GDA還是logistic回歸呢？</p><p>　　如果p(x|y)服從多元正態(tài)分布(且Σ相同)，那么p(y|x)可以使用lo

88、gistic函數。相反，如果p(y|x)是logistic函數，那么p(x|y)未必服從多元正態(tài)分布。這說明GDA比logistic對數據集的假設要求更強。特別的，如果p(x|y)服從多元正態(tài)分布(且Σ相同)，那么采用GDA將是漸進有效(asymptotically efficient)的。通俗的講，就是隨著樣本量的增加，分類精度將會增加。換句話說，如果樣本量足夠大的話，那么沒有任何方法能夠比GDA更準確的描述p(y|x)。此外，即使數

89、據集較小，我們也認為GDA模型更優(yōu)于logistic 回歸。</p><p>　　如果對數據集有較弱的假設，那么logistic回歸魯棒性(robust)更強，而且對不正確的數據分布假設也不會過于敏感。總結的說，GDA有更強的模型假設，對于服從模型假設或近似于假設的數據而言，GDA更依賴于數據的有效性。而logistic回歸具有較弱的模型假設，而且對于模型假設偏差魯棒性更好。此外，如果數據集分布不服從正態(tài)分布，那

90、么logistic回歸通常優(yōu)于GDA。</p><p><b>　　樸素貝葉斯</b></p><p><b>　　樸素貝葉斯模型</b></p><p>　　在GDA模型中，我們的特征數據是連續(xù)型變量，現在我們討論一種特征數據是離散變量的模型。在這里，我們通過機器學習在垃圾郵件中的分類案例，來講述該模型。即我們通過判斷一

91、封郵件是垃圾郵件還是非垃圾郵件來進行郵件的分類，在學習得到該模型之后，我們可以自動的判斷一封郵件是否是垃圾郵件。此外，垃圾郵件分類是屬于文本分類(text classification)的一種。</p><p>　　假設我們現在有一堆訓練集合(即已經標注為垃圾和非垃圾的一堆郵件)，我們首先需要做的就是尋找一組合適的特征xi來表示每一封郵件。這里我們采用字典里的所有單詞作為一封郵件的特征，即如果該郵件中出現字典中第

92、i個單詞，那么xi = 1，如果不包含，那么xi = 0。整體來說，我們使用如下向量：</p><p>　　來表示一封郵件的特征，即郵件中是否包含字典中的單詞。然而，通常情況下，我們不使用字典(所有單詞都用的話，特征太多)，而是使用一定的方法從訓練集合中找出合適的單詞(有的時候需要使用停用詞(stop words)或者tf-idf等方法來選擇合適的特征)。對于x中的所有單詞，我們稱之為詞匯表(vocabulary

93、)，特征屬性的大小就是詞匯表中詞匯的個數。在得到我們的特征向量(feature vector)之后，我們開始構建生成學習算法。</p><p>　　假設我們有50000個單詞，那么我們首先要構建p(x|y)，其中x ∈ {0, 1}50000(x is a 50000維向量，值僅含0和1)。如果我們通過明確的分布來描述x(直接構建p(x|y))，那么我們需要250000個結果，即250000-1維向量的參數，將會

94、有特別多的參數。為了方便p(x|y)建模，我們需要做出一個很強的假設：對于給定的y，xi 條件獨立(conditionally independent即特征之間相互獨立)，該假設稱之為樸素貝葉斯假設(Naive Bayes (NB) assumption)，因此該模型又稱之為樸素貝葉斯分類(Naive Bayes classifier)。舉例子而言，對于給定的郵件比如垃圾郵件，那么特征單詞buy是否出現并不影響特征單詞price的出現。

95、因此，有：</p><p>　　p(x1, . . . , x50000|y) = p(x1|y)p(x2|y, x1)p(x3|y, x1, x2) · · · p(x50000|y, x1, . . . , x49999)</p><p>　　= p(x1|y)p(x2|y)p(x3|y) · · · p(x50000|y)

96、 = </p><p>　　在第二步轉換過程中，我們使用了NB假設。需要注意的是，即使貝葉斯有很強的假設要求，但是該方法在很多問題上(特征并非完全條件獨立)仍然后較好的結果。</p><p>　　對于訓練集合{(x(i), y(i)); i =1, . . . , m}，我們的模型參數主要有</p><p>　　φi|y=1 = p(xi=1 | y=

97、1),</p><p>　　φi|y=0 = p(xi=1 | y=0)</p><p>　　φy = p(y=1)</p><p>　　那么我們的最大似然函數如下：</p><p>　　最大化似然函數之后，我們得到：</p><p>　　該公式比較容易理解，φj|y=1 分子是出現單詞j的垃圾郵件個數，分母是所有垃圾

98、郵件個數；而φy 分子表示垃圾郵件個數，而分母表示總樣本數。對于新出現的一封郵件，我們在得到特征向量之后，計算p(y=1|x)的值，就可以判斷其所屬類別。</p><p>　　此外，我們也可以擴展NB模型。比如x=1,2,3…k，那么我們可以使用多項分布來替代伯努力分布。如果x是連續(xù)變量，可以將x離散化。當原始數據是連續(xù)型的，且不能很好的滿足多元正態(tài)分布，此時采用離散化后，使用貝葉斯分類(相比于GDA)，通常會有

99、較好的結果。</p><p><b>　　拉普拉斯平滑</b></p><p>　　對于很多問題，采用樸素貝葉斯方法都能夠取得很好的結果，但是有些情況則需要對樸素貝葉斯分類進行一定的優(yōu)化，尤其是在文本分類領域。接下來，我們討論樸素貝葉斯方法在使用過程存在的缺陷，并探討如何去優(yōu)化。</p><p>　　仍然考慮垃圾郵件分類問題。比如在預測一封信郵

100、件是否是垃圾郵件過程中，特征單詞中的第3500個單詞nips恰好在訓練集合中從來沒有出現，那么通過最大似然估計得到的φ35000|y如下：</p><p>　　因為單詞nips從來沒有出現，因此垃圾郵件和非垃圾郵件的條件概率均為0，因此在計算是否是垃圾郵件的后驗概率中，因為分子中存在一個0項，導致最終結果無法判斷。</p><p>　　推而廣之，即因為訓練集合的有限性而使某些特征值沒有被包

101、含，導致統(tǒng)計得到的條件概率為0。為了方便說明，我們取某一個特征z來說明，z的取值在{1, . . . , k }，在給定的m個訓練集里m， {z(1), . . . , z(m)}，根據傳統(tǒng)的最大似然估計，我們得到條件概率：</p><p>　　我們知道該方法存在一定缺陷，因此采用拉普拉斯平滑(Laplace smoothing)進行優(yōu)化，即在分子中加1(即默認每一個值都已經出現過一次)，考慮左右的頻率和為1，因

102、此分母加上k(k個值)，如下：</p><p>　　這樣如果一個特征沒有出現，那么條件概率將不會是0，解決了剛才提到的問題。對于垃圾郵件分類，那么我們知道一個單詞只有兩個值(0，1)，因此分子需要加1，而分母需要加2。實際應用中對于先驗概率φy(不是條件概率φx|y)是否采用拉普拉斯平滑，并沒有很大的影響，因為收集的數據集相對公平，不會導致0值的出現。</p><p>　　此外，需要注意的

103、是，在計算新郵件的后驗概率的分子的時候，φi|y=1 = p(xi=1 | y=1),這里不管是y=1還是y=0，都只計算x=1的情況，即只計算存在的單詞(即出現的單詞，不出現的單詞不用計算)。此外，因為條件概率值介于0到1之間，50000特征的條件概率相乘(分子的計算)將會出現極小值，在某些情況下可能無法進行比較，因此，可以針對條件概率取對數，這樣不僅可以放大概率值，還可以將乘法轉化成加法，并得到可比較的值。</p>&

104、lt;p><b>　　樸素貝葉斯算法</b></p><p><b>　　文本分類模型</b></p><p>　　在結束生成算法模型之前，我們將一種專門用于文本分類的算法。對于分類問題，樸素貝葉斯算法通常效果很好，而對于文本分類而言，則有更好的模型。</p><p>　　對于文本分類，之前提到的樸素貝葉斯算法又稱之

105、為多元伯努力事件模型(multi-variate Bernoulli event model)。模型分析，在之前已經討論過了。這里，我們解釋一下如何理解數據的生成呢？在該模型中，我們假設郵件是按照先驗概率(p(y))隨機發(fā)送郵件或垃圾郵件到用戶手里的，之后遍歷詞匯表，以伯努力分布生成該郵件單詞(特征向量，同時假設了各個單詞在郵件中出現的概率是條件獨立)，之后根據p(xi= 1|y) =φi|y進行后驗概率的計算，得到p(y)(只要計算后

106、驗概率的分子即可，各個類分母均相等，用于歸一化)。該模型中，x取值僅有{0，1}，且生成特征的方式是以遍歷詞匯表的方式。</p><p>　　這里我們介紹另外一種方法，稱之為多項事件模型(multinomial event model)。為了更好的表示，這里采用另一種表示的方法。其中，xi表示單詞i在詞匯表中的地址，那么xi取值范圍是{1,2,3…|V|}，其中 |V| 是詞匯表的詞匯數量。舉個例子而言，一封郵件

107、有n個單詞，表示為向量(x1, x2, . . . , xn)，注意這里的n對于不同的文檔來說是不一樣的。舉例而言，一封郵件開頭是“a nips…”那么x1=1,x2=3500(詞匯表中，a是第一個單詞，nips是第3500個)。</p><p>　　在多項事件模型中，同樣看看數據是如何生成呢？我們假設以隨機的方式產生(當然還是存在先驗概率p(y))垃圾郵件或非垃圾郵件，之后按照多項分布生成郵件中的第一個單詞，在

108、同樣的分布下，生成其他的單詞直到xn(每次的生成都相互獨立)，因此產生該郵件的全部概率值就是p(y)，雖然該生成概率值與之前的多項伯努力分布很像，但是代表含義不同，尤其是xi|y現在是多項分布而不是伯努力分布。</p><p>　　對于新模型中的參數如下，注意這里假設了對于所有的j(j是樣本的下標), p(xj|y)的值均相等(生成哪個單詞的概率分布并不依賴于該樣本在整體中的位置)，其中k表示具體的單詞。<

109、/p><p>　　φy = p(y=1)</p><p>　　φk|y=1 = p(xj=k | y=1)(對于每一個j)</p><p>　　φk|y=0 = p(xj=k | y=0) )(對于每一個j)</p><p>　　對于給定的數據集{(x(i), y(i)); i = 1, . . . , m}，其中x(i)=(x(i)1, x(i