1、機器學(xué)習(xí)斯坦福大學(xué)講義第一課機器學(xué)習(xí)的動機與應(yīng)用工具：需正版：Matlab，免費：Octave定義（Arthur Samuel 1959）：在不直接針對問題進行編程的情況下，賦予計算機學(xué)習(xí)能力的研究領(lǐng)域。例：Arthur的下棋程序，計算走每一步獲勝的概率，最終打敗程序作者本人。（感覺使用決策樹思想）定義2（Tom Mitchell 1998）：一個合理的學(xué)習(xí)問題應(yīng)該這樣定義：對一個計算機程序來說，給它一個任務(wù)T和一個性能測量方法P，如果在經(jīng)驗E的影響下，P對T的測量結(jié)果得到了改進，那么就說改程序從E中學(xué)習(xí)了。如上例：E：程序不斷和自己下棋的經(jīng)歷，T：下棋，P：和人類選手對弈的勝率課程的四大部分

2、：1、有監(jiān)督學(xué)習(xí)（1）回歸問題例：收集某地房屋價格統(tǒng)計、房屋大小和價格對應(yīng)情況：畫出一條擬合曲線，就可以通過房屋大小估計價格。-有監(jiān)督學(xué)習(xí)即給出一個數(shù)據(jù)集（正確的房屋價格及對應(yīng)大小）-此例為回歸問題。回歸意味著需要預(yù)測的變量是連續(xù)的（2）分類問題分類問題中需要處理的變量是離散的例：判斷腫瘤是惡性還是兩性-收集腫瘤大小和惡性/良性數(shù)據(jù)，大小為橫軸，是否是惡性為縱軸（只有0,1）畫圖-腫瘤可能由多個因素導(dǎo)致，引入年齡，大小為橫軸，年齡為縱軸，惡性以叉表示，良性以圓圈表示畫圖，分析患腫瘤的區(qū)域-還可引入更多屬性，畫在多維空間中-無限維空間如何處理？將無限維映射到內(nèi)存的算法？2、學(xué)習(xí)理論學(xué)習(xí)理論即解釋

3、學(xué)習(xí)型算法有效的原因（學(xué)習(xí)算法的理論基礎(chǔ)）尋找什么樣的算法能很好地近似不同的函數(shù)，訓(xùn)練集的規(guī)模是否合適3、無監(jiān)督學(xué)習(xí)例：如上述腫瘤例子，圖中的點不知道正確答案，而是由你從中找去一定的結(jié)構(gòu)，即聚類。應(yīng)用于生物基因工程，圖像處理，計算機視覺等領(lǐng)域例：雞尾酒會問題在嘈雜的雞尾酒會中，將你感興趣的聲音提取出來運用兩個不同位置的麥克分開來自不同位置的聲音還能應(yīng)用于文本處理等領(lǐng)域使用ICA算法，Matlab一行代碼即可解決4、強化學(xué)習(xí)通過決策產(chǎn)生的結(jié)論或?qū)蝈e，故產(chǎn)生一系列的決策。例：對一個模型飛機編寫一個起飛程序，飛機在程序做了一連串錯誤決策是才會墜毀，只要做出連續(xù)的整體還不錯的決策，即可保持飛機正常飛

4、行強化學(xué)習(xí)的基本概念：回報函數(shù)（正反饋及負反饋），程序做出正確決策時給出正反饋，反之亦然。程序不斷做出決策，在不斷嘗試獲得盡量多的正反饋時，逐漸學(xué)習(xí)并做出正確決策關(guān)鍵在于要定義什么是正確決策，什么是錯誤決策，再設(shè)計算法獲取盡量多的正反饋第二課監(jiān)督學(xué)習(xí)應(yīng)用與梯度下降本課內(nèi)容：1、線性回歸2、梯度下降3、正規(guī)方程組（復(fù)習(xí)）監(jiān)督學(xué)習(xí)：告訴算法每個樣本的正確答案，學(xué)習(xí)后的算法對新的輸入也能輸入正確的答案1、線性回歸例：Alvin汽車，先讓人開車，Alvin攝像頭觀看（訓(xùn)練），而后實現(xiàn)自動駕駛。本質(zhì)是一個回歸問題，汽車嘗試預(yù)測行駛方向。例：上一節(jié)課的房屋大小與價格數(shù)據(jù)集引入通用符號：m =訓(xùn)練樣本數(shù)x

5、=輸入變量（特征）y =輸出變量（目標變量）(x,y) 一個樣本第i個訓(xùn)練樣本=本例中：m：數(shù)據(jù)個數(shù)，x：房屋大小，y：價格監(jiān)督學(xué)習(xí)過程：1)將訓(xùn)練樣本提供給學(xué)習(xí)算法2)算法生成一個輸出函數(shù)（一般用h表示，成為假設(shè)）3)這個函數(shù)接收輸入，輸出結(jié)果。（本例中為，接收房屋面積，輸出房價）將x映射到y(tǒng)。如下圖所示：對假設(shè)進行線性表示：通常來說，回歸問題有多個輸入特征。如上例中，我們還已知房屋的臥室數(shù)，即有個第二個特征。即表示大小，表示臥室數(shù)，則可將假設(shè)寫成：。為了將公式寫整潔，定義，則h可寫成：n =特征數(shù)目，：參數(shù)。選擇的目的，是使h(x)與y的平方差盡量小。又由于有m個訓(xùn)練樣本，需要計算每個樣本

6、的平方差，最后為了簡化結(jié)果乘以1/2，即：我們要做的就是求：min(J()求min(J()方法：梯度下降和正規(guī)方程組2、梯度下降梯度下降是一種搜索算法，基本思想：先給出參數(shù)向量一個初始值，比如0向量；不斷改變，使得J()不斷縮小。改變的方法：梯度下降如圖所示，水平坐標軸表示，垂直坐標表示J()一開始選擇0向量作為初始值，假設(shè)該三維圖為一個三維地表，0向量的點位于一座“山”上。梯度下降的方法是，你環(huán)視一周，尋找下降最快的路徑，即為梯度的方向，每次下降一小步，再環(huán)視四周，繼續(xù)下降，以此類推。結(jié)果到達一個局部最小值，如下圖：當然，若初始點不同，則結(jié)果可能為另一個完全不同的局部最小值，如下：表明梯度下

7、降的結(jié)果依賴于參數(shù)初始值。梯度下降算法的數(shù)學(xué)表示：為賦值運算符，即表示程序中的的賦值語句。每一次將減去對求偏導(dǎo)的結(jié)果，即沿最陡峭的“山坡”下降將偏導(dǎo)數(shù)展開分析：代入上式：學(xué)習(xí)速度，即決定你下山時每一步邁多大。設(shè)的過小，收斂時間長，設(shè)的過大，可能會超過最小值（1）批梯度下降算法：上述為處理一個訓(xùn)練樣本的公式，將其派生成包含m個訓(xùn)練樣本的算法，循環(huán)下式直至收斂：復(fù)雜度分析：對于每個的每次迭代，即上式所示，時間為O(m)每次迭代（走一步）需要計算n個特征的梯度值，復(fù)雜度為O(mn)一般來說，這種二次函數(shù)的的三維圖形為一個碗狀，有一個唯一的全局最小值。其等高線為一個套一個的橢圓形，運用梯度下降會快速收

8、斂到圓心。梯度下降性質(zhì)：接近收斂時，每次的步子會越來越小。其原因是每次減去乘以梯度，但是梯度會越來越小，所以步子會越來越小。下圖為使用梯度下降擬合的上例房屋大小和價格的曲線檢測是否收斂的方法：1)檢測兩次迭代的改變量，若不再變化，則判定收斂2)更常用的方法：檢驗，若不再變化，判定收斂批梯度下降算法的優(yōu)點是能找到局部最優(yōu)解，但是若訓(xùn)練樣本m很大的話，其每次迭代都要計算所有樣本的偏導(dǎo)數(shù)的和，時間過慢，于是采用下述另一種梯度下降方法。（2）隨機梯度下降算法（增量梯度下降算法）：每次計算不需要再遍歷所有數(shù)據(jù)，而是只需計算樣本i即可。即批梯度下降中，走一步為考慮m個樣本；隨機梯度下降中，走一步只考慮1個

9、樣本。每次迭代復(fù)雜度為O(n)。當m個樣本用完時，繼續(xù)循環(huán)到第1個樣本。上述使用了迭代的方法求最小值，實際上對于這類特定的最小二乘回歸問題，或者普通最小二乘問題，存在其他方法給出最小值，接下來這種方法可以給出參數(shù)向量的解析表達式，如此一來就不需要迭代求解了。3、正規(guī)方程組給定一個函數(shù)J，J是一個關(guān)于參數(shù)數(shù)組的函數(shù)，定義J的梯度關(guān)于的導(dǎo)數(shù)，它自己也是一個向量。向量大小為n+1維（從0到n），如下：所以，梯度下降算法可寫成：更普遍的講，對于一個函數(shù)f，f的功能是將一個m*n的矩陣映射到實數(shù)空間上，即：假設(shè)輸入為m*n大小的矩陣A，定義f關(guān)于矩陣A的導(dǎo)數(shù)為：導(dǎo)數(shù)本身也是個矩陣，包含了f關(guān)于A的每個元

10、素的偏導(dǎo)數(shù)。如果A是一個方陣，即n*n的矩陣，則將A的跡定義為A的對角元素之和，即：trA即為tr(A)的簡化。一些關(guān)于跡運算符和導(dǎo)數(shù)的定理：1)trAB = trBA2)trABC = trCAB = trBCA3)4)5)若，tra = a6)有了上述性質(zhì)，可以開始推導(dǎo)了：定義矩陣X，稱為設(shè)計矩陣，包含了訓(xùn)練集中所有輸入的矩陣，第i行為第i組輸入數(shù)據(jù)，即：則由于，所以可得：又因為對于向量z，有，則有：由上述最后一個性質(zhì)可得：通過上述6個性質(zhì)，推導(dǎo)：倒數(shù)第三行中，運用最后一個性質(zhì)將置為0，則有：稱為正規(guī)方程組可得：第三課欠擬合與過擬合概念本次課程大綱：1、局部加權(quán)回歸：線性回歸的變化版本2、

11、概率解釋：另一種可能的對于線性回歸的解釋3、Logistic回歸：基于2的一個分類算法4、感知器算法：對于3的延伸，簡要講復(fù)習(xí)：第i個訓(xùn)練樣本令，以參數(shù)向量為條件，對于輸入x，輸出為：n為特征數(shù)量定義成本函數(shù)J，定義為：m為訓(xùn)練樣本通過正規(guī)方程組推導(dǎo)的結(jié)論：1、過擬合與欠擬合通常，你選擇交給學(xué)習(xí)算法處理的特征的方式對算法的工作過程有很大影響。例：上次課的例子中，用x1表示房間大小。通過線性回歸，在橫軸為房間大小，縱軸為價格的圖中，畫出擬合曲線。回歸的曲線方程為：若定義特征集合為：x1表示房子大小，x2表示房子大小的平方，使用相同的算法，擬合得到一個二次函數(shù)，在圖中即為一個拋物線，即：以此類推，

12、若訓(xùn)練集有7個數(shù)據(jù)，則可擬合出最高6次的多項式，可以找到一條完美的曲線，該曲線經(jīng)過每個數(shù)據(jù)點。但是這樣的模型又過于復(fù)雜，擬合結(jié)果僅僅反映了所給的特定數(shù)據(jù)的特質(zhì)，不具有通過房屋大小來估計房價的普遍性。而線性回歸的結(jié)果可能無法捕獲所有訓(xùn)練集的信息。所以，對于一個監(jiān)督學(xué)習(xí)模型來說，過小的特征集合使得模型過于簡單，過大的特征集合使得模型過于復(fù)雜。對于特征集過小的情況，稱之為欠擬合（underfitting）；對于特征集過大的情況，稱之為過擬合（overfitting）解決此類學(xué)習(xí)問題的方法：1)特征選擇算法：一類自動化算法，在這類回歸問題中選擇用到的特征2)非參數(shù)學(xué)習(xí)算法：緩解對于選取特征的需求，引出

13、局部加權(quán)回歸參數(shù)學(xué)習(xí)算法（parametric learning algorithm）定義：參數(shù)學(xué)習(xí)算法是一類有固定數(shù)目參數(shù)，以用來進行數(shù)據(jù)擬合的算法。設(shè)該固定的參數(shù)集合為。線性回歸即使參數(shù)學(xué)習(xí)算法的一個例子非參數(shù)學(xué)習(xí)算法（Non-parametric learning algorithm）定義：一個參數(shù)數(shù)量會隨m（訓(xùn)練集大小）增長的算法。通常定義為參數(shù)數(shù)量雖m線性增長。換句話說，就是算法所需要的東西會隨著訓(xùn)練集合線性增長，算法的維持是基于整個訓(xùn)練集合的，即使是在學(xué)習(xí)以后。2、局部加權(quán)回歸（Locally Weighted Regression）一種特定的非參數(shù)學(xué)習(xí)算法。也稱作Loess。算法

14、思想：假設(shè)對于一個確定的查詢點x，在x處對你的假設(shè)h(x)求值。對于線性回歸，步驟如下：1)擬合出，使最小2)返回對于局部加權(quán)回歸，當要處理x時：1)檢查數(shù)據(jù)集合，并且只考慮位于x周圍的固定區(qū)域內(nèi)的數(shù)據(jù)點2)對這個區(qū)域內(nèi)的點做線性回歸，擬合出一條直線3)根據(jù)這條擬合直線對x的輸出，作為算法返回的結(jié)果用數(shù)學(xué)語言描述即：1)擬合出，使最小2)w為權(quán)值，有很多可能的選擇，比如：-其意義在于，所選取的x(i)越接近x，相應(yīng)的w(i)越接近1；x(i)越遠離x，w(i)越接近0。直觀的說，就是離得近的點權(quán)值大，離得遠的點權(quán)值小。-這個衰減函數(shù)比較具有普遍意義，雖然它的曲線是鐘形的，但不是高斯分布。-被稱

15、作波長函數(shù)，它控制了權(quán)值隨距離下降的速率。它越小，鐘形越窄，w衰減的很快；它越大，衰減的就越慢。3)返回總結(jié)：對于局部加權(quán)回歸，每進行一次預(yù)測，都要重新擬合一條曲線。但如果沿著x軸對每個點都進行同樣的操作，你會得到對于這個數(shù)據(jù)集的局部加權(quán)回歸預(yù)測結(jié)果，追蹤到一條非線性曲線。*局部加權(quán)回歸的問題：由于每次進行預(yù)測都要根據(jù)訓(xùn)練集擬合曲線，若訓(xùn)練集太大，每次進行預(yù)測的用到的訓(xùn)練集就會變得很大，有方法可以讓局部加權(quán)回歸對于大型數(shù)據(jù)集更高效，詳情參見Andrew Moore的關(guān)于KD-tree的工作。3、概率解釋概率解釋所解決的問題：在線性回歸中，為什么選擇最小二乘作為計算參數(shù)的指標，使得假設(shè)預(yù)測出的值

16、和真正y值之間面積的平方最小化？我們提供一組假設(shè)，證明在這組假設(shè)下最小二乘是有意義的，但是這組假設(shè)不唯一，還有其他很多方法可以證明其有意義。（1）假設(shè)1：假設(shè)輸入與輸出為線性函數(shù)關(guān)系，表示為：其中，為誤差項，這個參數(shù)可以理解為對未建模效應(yīng)的捕獲，如果還有其他特征，這個誤差項表示了一種我們沒有捕獲的特征，或者看成一種隨機的噪聲。假設(shè)服從某個概率分布，如高斯分布（正態(tài)分布）：，表示一個均值是0，方差是的高斯分布。高斯分布的概率密度函數(shù)：根據(jù)上述兩式可得：即，在給定了特征與參數(shù)之后，輸出是一個服從高斯分布的隨機變量,可描述為：*為什么選取高斯分布？1)便于數(shù)學(xué)處理2)對絕大多數(shù)問題，如果使用了線性回

17、歸模型，然后測量誤差分布，通常會發(fā)現(xiàn)誤差是高斯分布的。3)中心極限定律：若干獨立的隨機變量之和趨向于服從高斯分布。若誤差有多個因素導(dǎo)致，這些因素造成的效應(yīng)的總和接近服從高斯分布。注意：并不是一個隨機變量，而是一個嘗試估計的值，就是說它本身是一個常量，只不過我們不知道它的值，所以上式中用分號表示。分號應(yīng)讀作“以作為參數(shù)”，上式讀作“給定x(i)以為參數(shù)的y(i)的概率服從高斯分布”。假設(shè)每個為IID（independently and identically distributed）獨立同分布即誤差項彼此之間是獨立的，并且他們服從均值和方差相同的高斯分布（2）假設(shè)2：設(shè)的似然性為（即給定x(i)

18、以為參數(shù)的y(i)的概率）：由于是獨立同分布，所以上式可寫成所有分布的乘積：（3）假設(shè)3：極大似然估計：選取使似然性最大化（數(shù)據(jù)出現(xiàn)的可能性盡可能大）定義對數(shù)似然函數(shù)為：上式兩個加項，前一項為常數(shù)。所以，使似然函數(shù)最大，就是使后一項最小，即：這一項就是之前的，由此得證，即之前的最小二乘法計算參數(shù)，實際上是假設(shè)了誤差項滿足高斯分布，且獨立同分布的情況，使似然最大化來計算參數(shù)。注意：高斯分布的方差對最終結(jié)果沒有影響，由于方差一定為正數(shù)，所以無論取什么值，最后結(jié)果都相同。這個性質(zhì)會在下節(jié)課講到。4、Logistic回歸這是我們要學(xué)習(xí)的第一個分類算法。之前的回歸問題嘗試預(yù)測的變量y是連續(xù)變量，在這個分

19、類算法中，變量y是離散的，y只取0,1兩個值。一般這種離散二值分類問題用線性回歸效果不好。比如x3，y=1，那么當x3的樣本占得比例很大是，線性回歸的直線斜率就會越來越小，y=0.5時對應(yīng)的x判決點就會比3大，造成預(yù)測錯誤。若y取值0,1，首先改變假設(shè)的形式，使假設(shè)得到的值總在0,1之間，即：所以，選取如下函數(shù)：其中：g函數(shù)一般被稱為logistic函數(shù)，圖像如下：z很小時，g(z)趨于0，z很大時，g(z)趨于1，z=0時，g(z)=0.5對假設(shè)的概率解釋：假設(shè)給定x以為參數(shù)的y=1和y=0的概率：可以簡寫成：參數(shù)的似然性：求對數(shù)似然性：為了使似然性最大化，類似于線性回歸使用梯度下降的方法，

20、求對數(shù)似然性對的偏導(dǎo)，即：因為求最大值，此時為梯度上升。偏導(dǎo)數(shù)展開：則：即類似上節(jié)課的隨機梯度上升算法，形式上和線性回歸是相同的，只是符號相反，為logistic函數(shù)，但實質(zhì)上和線性回歸是不同的學(xué)習(xí)算法。5、感知器算法在logistic方法中，g(z)會生成0,1之間的小數(shù)，但如何是g(z)只生成0或1？所以，感知器算法將g(z)定義如下：同樣令，和logistic回歸的梯度上升算法類似，學(xué)習(xí)規(guī)則如下：盡管看起來和之前的學(xué)習(xí)算法類似，但感知器算法是一種非常簡便的學(xué)習(xí)算法，臨界值和輸出只能是0或1，是比logistic更簡單的算法。后續(xù)講到學(xué)習(xí)理論是，會將其作為基本的構(gòu)造步驟。第四課牛頓方法本次

21、課程大綱：1、牛頓方法：對Logistic模型進行擬合2、指數(shù)分布族3、廣義線性模型（GLM）：聯(lián)系Logistic回歸和最小二乘模型復(fù)習(xí)：Logistic回歸：分類算法假設(shè)給定x以為參數(shù)的y=1和y=0的概率：求對數(shù)似然性：對其求偏導(dǎo)數(shù)，應(yīng)用梯度上升方法，求得：本次課程介紹的牛頓方法是一種比梯度上升快很多的方法，用于擬合Logistic回歸1、牛頓方法假設(shè)有函數(shù)，需要找使=0的步驟：1)給出一個的初始值2)對求導(dǎo)，求導(dǎo)數(shù)為0時的值（就是求切線與x軸交點）3)重復(fù)步驟2因為該點的導(dǎo)數(shù)值即為切線斜率，而斜率=該點y軸的值/該點x軸的變化值，所以每次的變化值：*使用這個方法需要f滿足一定條件，適用

22、于Logistic回歸和廣義線性模型*一般初始化為0應(yīng)用于Logistic回歸：求對數(shù)似然的最大值，即求為0時的，根據(jù)上述推論，更新規(guī)則如下：牛頓方法的收斂速度：二次收斂每次迭代使解的有效數(shù)字的數(shù)目加倍：假設(shè)當前誤差是0.1，一次迭代后，誤差為0.001，再一次迭代，誤差為0.0000001。該性質(zhì)當解距離最優(yōu)質(zhì)的足夠近才會發(fā)現(xiàn)。牛頓方法的一般化：是一個向量而不是一個數(shù)字，一般化的公式為：是目標函數(shù)的梯度，H為Hessian矩陣，規(guī)模是n*n，n為特征的數(shù)量，它的每個元素表示一個二階導(dǎo)數(shù)：上述公式的意義就是，用一個一階導(dǎo)數(shù)的向量乘以一個二階導(dǎo)數(shù)矩陣的逆優(yōu)點：若特征數(shù)和樣本數(shù)合理，牛頓方法的迭代

23、次數(shù)比梯度上升要少得多缺點：每次迭代都要重新計算Hessian矩陣，如果特征很多，則H矩陣計算代價很大2、指數(shù)分布族回顧學(xué)過的兩種算法：對于：若y屬于實數(shù)，滿足高斯分布，得到基于最小二乘法的線性回歸；若y取0,1，滿足伯努利分布，得到Logistic回歸。問題：如Logistic回歸中，為何選擇sigmoid函數(shù)？sigmoid函數(shù)是最自然的默認選擇。接下來，會以這兩個算法為例，說明它們都是廣義線性模型的特例。考慮上述兩個分布，伯努利分布和高斯分布：1)伯努利分布設(shè)有一組只能取0或1的數(shù)據(jù)，用伯努利隨機變量對其建模：，則，改變參數(shù)，y=1這一事件就會有不同概率，會得到一類概率分布（而非固定的）

24、。2)高斯分布，改變參數(shù)，也會得到不同的高斯分布，即一類概率分布。上述這些分布都是一類分布的特例，這類分布稱為指數(shù)分布族。指數(shù)分布族的定義：若一類概率分布可以寫成如下形式，那么它就屬于指數(shù)分布族：-自然參數(shù)，通常是一個實數(shù)T(y) 充分統(tǒng)計量，通常，T(y)=y，實際上是一個概率分布的充分統(tǒng)計量（統(tǒng)計學(xué)知識）對于給定的a，b，T三個函數(shù)，上式定義了一個以為參數(shù)的概率分布集合，即改變可以得到不同的概率分布。證明伯努利分布是指數(shù)分布族：可知：由上式可見，=log(/(1-)，可解出：=1/(1+exp(-)，發(fā)現(xiàn)得到logistic函數(shù)（之后討論其原因），則：證明高斯分布是指數(shù)分布族：，設(shè)方差為1

25、（方差并不影響結(jié)果，僅僅是變量y的比例因子）這種情況下高斯密度函數(shù)為：可得：*指數(shù)分布族包括：高斯分布（正態(tài)分布），多元正態(tài)分布；伯努利分布（01問題建模），多項式分布（對k個結(jié)果的事件建模）；泊松分布（對計數(shù)過程建模）；伽馬分布，指數(shù)分布（對實數(shù)的間隔問題建模）；分布，Dirichlet分布（對小數(shù)建模）；Wishart分布（協(xié)方差矩陣的分布）3、廣義線性模型GLM選定了一個指數(shù)分布族后，怎樣來推導(dǎo)出一個GLM呢？假設(shè)：（1），即假設(shè)試圖預(yù)測的變量y在給定x，以作為參數(shù)的條件概率，屬于以作為自然參數(shù)的指數(shù)分布族例：若要統(tǒng)計網(wǎng)站點擊量y，用泊松分布建模（2）給定x，目標是求出以x為條件的T(y

26、)的期望ET(y)|x，即讓學(xué)習(xí)算法輸出h(x) = ET(y)|x（3），即自然參數(shù)和輸入特征x之間線性相關(guān)，關(guān)系由決定。僅當是實數(shù)時才有意義。若是一個向量，推導(dǎo)伯努利分布的GLM：，伯努利分布屬于指數(shù)分布族對給定的x，學(xué)習(xí)算法進行一次預(yù)測的輸出：得到logistic回歸算法。正則響應(yīng)函數(shù)：g() = Ey;，將自然參數(shù)和y的期望聯(lián)系起來正則關(guān)聯(lián)函數(shù)：g-1推導(dǎo)多項式分布的GLM：多項式分布是在k個可能取值上的分布，即y1,k，如將收到的郵件分成k類，診斷某病人為k種病中的一種等問題。（1）將多項式分布寫成指數(shù)分布族的形式：設(shè)多項式分布的參數(shù)：，且，i表示第i個取值的概率分布，最后一個參數(shù)可

27、以由前k-1個推導(dǎo)出，所以只將前k-1個視為參數(shù)。多項式分布是少數(shù)幾個T(y)!=y的分布，T(1)T(k)都定義成一個k-1維的列向量，表示為：這樣定義T(y)是為了將多項式分布寫成指數(shù)分布族形式。*定義符號：指示函數(shù)，1.1True = 1, 1False = 0，即大括號內(nèi)命題為真，值為1,；否則為0。例：12=3 = 0, 11+1=2 = 1用T(y)i表示T(y)的第i個元素，則T(y)i = 1y=i根據(jù)參數(shù)的意義（i表示第i個取值的概率分布），可推出：可得：證明多項式分布式指數(shù)分布族。再用表示：（2）根據(jù)上述假設(shè)（3）中自然參數(shù)和輸入x的線性關(guān)系，可求得：（3）根據(jù)上述假設(shè)（2

28、）中的輸出h(x) = ET(y)|x，可求得：稱這種回歸算法為softmax回歸，是logistic回歸的推廣。Softmax回歸的訓(xùn)練方法和logistic相似，通過極大似然估計找到參數(shù)，其對數(shù)似然性為：再通過梯度上升或牛頓方法找對數(shù)似然性的最大值，即可求出參數(shù)。第五課生成學(xué)習(xí)算法本次課程大綱：1、生成學(xué)習(xí)算法2、高斯判別分析（GDA，Gaussian Discriminant Analysis）-高斯分布（簡要）-對比生成學(xué)習(xí)算法&判別學(xué)習(xí)算法（簡要）3、樸素貝葉斯4、Laplace平滑復(fù)習(xí)：分類算法：給出一個訓(xùn)練集，若使用logistic回歸算法，其工作方式是觀察這組數(shù)據(jù)，嘗試找到一條

29、直線將圖中不同的類分開，如下圖。之前講的都是判別學(xué)習(xí)算法，本課介紹一種不同的算法：生成學(xué)習(xí)算法。1、生成學(xué)習(xí)算法例：對惡性腫瘤和良性腫瘤的分類除了尋找一個將兩類數(shù)據(jù)區(qū)分的直線外，還可以用如下方法：1)遍歷訓(xùn)練集，找到所有惡性腫瘤樣本，直接對惡性腫瘤的特征建模；同理，對良性腫瘤建模。2)對一個新的樣本分類時，即有一個新的病人時，要判斷其是惡性還是良性，用該樣本分別匹配惡性腫瘤模型和良性腫瘤模型，看哪個模型匹配的更好，預(yù)測屬于惡性還是良性。這種方法就是生成學(xué)習(xí)算法。兩種學(xué)習(xí)算法的定義：1)判別學(xué)習(xí)算法：-直接學(xué)習(xí)p(y|x)，即給定輸入特征，輸出所屬的類-或?qū)W習(xí)得到一個假設(shè)h(x)，直接輸出0或1

30、2)生成學(xué)習(xí)算法：-對p(x|y)進行建模，p(x|y)表示在給定所屬的類的情況下，顯示某種特征的概率。處于技術(shù)上的考慮，也會對p(y)進行建模。-p(x|y)中的x表示一個生成模型對樣本特征建立概率模型，y表示在給定樣本所屬類的條件下例：在上例中，假定一個腫瘤情況y為惡性和良性，生成模型會對該條件下的腫瘤癥狀x的概率分布進行建模-對p(x|y)和p(y)建模后，根據(jù)貝葉斯公式p(y|x) = p(xy)/p(x) = p(x|y)p(y)/p(x)，可以計算：p(y=1|x) = p(x|y=1)p(y=1)/p(x)，其中，p(x) = p(x|y=0)p(y=0) + p(x|y=1)p

31、(y=1)2、高斯判別分析GDAGDA是一種生成學(xué)習(xí)算法。GDA的假設(shè)條件：1)假設(shè)輸入特征xRn，并且是連續(xù)值。2)假設(shè)p(x|y)滿足高斯分布*高斯分布基礎(chǔ)知識：設(shè)隨機變量z滿足多元高斯分布，zN(,)，均值向量為，協(xié)方差矩陣為。其概率密度函數(shù)為：多元高斯分布為一元高斯分布的推廣，也是鐘形曲線，z是一個高維向量。多元高斯分布注意兩個參數(shù)即可：-均值向量-協(xié)方差矩陣= E(Z-EZ)(Z-EZ)T=E(x-)(x-)T多元高斯分布圖：左圖：=0，=I（單位矩陣）中圖：=0，=0.6I，圖形變陡峭右圖：=0，=2I，圖形變扁平三圖中=0，如下：可見增加矩陣對角元素的值，即變量間增加相關(guān)性，高斯

32、曲面會沿z1=z2（兩個水平軸）方向趨于扁平。其水平面投影圖如下：即增加對角線的元素，圖形會沿45角，偏轉(zhuǎn)成一個橢圓形狀。若對角線元素為負，圖形如下：分別為：不同的圖形如下：分別為：決定分布曲線中心的位置。GDA擬合：給出訓(xùn)練樣本如下圖所示：-觀察正樣本（圖中的x），擬合正樣本的高斯分布，如圖中左下方的圓，表示p(x|y=1)-觀察負樣本（圖中的圈），擬合負樣本的高斯分布，如圖中右上方的圓，表示p(x|y=0)-通過這兩個高斯分布的密度函數(shù)，定義出兩個類別的分隔器，即圖中的直線-這條分隔器直線比之前的logistic擬合的直線要復(fù)雜GDA模型：寫出其概率分布：參數(shù)包括，0，1，對數(shù)似然性為：由

33、于第一個等式為xy的聯(lián)合概率，將這個模型命名為聯(lián)合似然性（Joint likelihood）。*對比logistic回歸中的對數(shù)似然性：由于計算的是y在x條件下的概率，將此模型命名為條件似然性（conditional likelihood）通過對上面對數(shù)似然性求極大似然估計，參數(shù)的結(jié)果為：訓(xùn)練樣本中標簽為1的樣本所占的比例0：分母為標簽為0的樣本數(shù)，分子是對標簽為0的樣本的x(i)求和，結(jié)合起來就是對對標簽為0的樣本的x(i)求均值，與高斯分布參數(shù)為均值的意義相符1：與0同理，標簽改為1GDA預(yù)測：預(yù)測結(jié)果應(yīng)該是給定x的情況下最可能的y，等式左邊的運算符argmax表示計算p(y|x)最大時的

34、y值，預(yù)測公式如下：因為p(x)獨立于y，所以可以忽略p(x)。*如果p(y)為均勻分布，即每種類型的概率都相同，那么也可以忽略p(y)，要求的就是使p(x|y)最大的那個y。不過這種情況并不常見。GDA和logistic回歸的聯(lián)系：例：假設(shè)有一個一維訓(xùn)練集，包含一些正樣本和負樣本，如下圖x軸的叉和圈，設(shè)叉為0，圈為1，用GDA對兩類樣本分別擬合高斯概率密度函數(shù)p(x|y=0)和p(x|y=1)，如下圖的兩個鐘形曲線。沿x軸遍歷樣本，在x軸上方畫出其相應(yīng)的p(y=1|x)。如選x軸靠左的點，那么它屬于1的概率幾乎為0，p(y=1|x)=0，兩條鐘形曲線交點處，屬于0或1的概率相同，p(y=1|

35、x)=0.5，x軸靠右的點，輸出1的概率幾乎為1，p(y=1|x)=1。最終發(fā)現(xiàn)，得到的曲線和sigmoid函數(shù)曲線很相似。簡單來講，就是當使用GDA模型時，p(x|y)屬于高斯分布，計算p(y|x)時，幾乎能得到和logistic回歸中使用的sigmoid函數(shù)一樣的函數(shù)。但實際上還是存在本質(zhì)區(qū)別的。使用生成學(xué)習(xí)算法的優(yōu)缺點：給出兩個推論：推論1：x|y服從高斯分布= p(y=1|x)是logistic函數(shù)該推論在反方向不成立。推論2：x|y=1 Poisson(1)，x|y=0 Poisson(0) =p(y=1|x)是logistic函數(shù)x|y=1 Poisson(1)表示x|y=1服從參

36、數(shù)為1泊松分布推論3：x|y=1 ExpFamily(1)，x|y=0 ExpFamily (0) = p(y=1|x)是logistic函數(shù)推論2的推廣，即x|y的分布屬于指數(shù)分布族，均可推出結(jié)論。顯示了logistic回歸在建模假設(shè)選擇方面的魯棒性。優(yōu)點：推論1反方向不成立，因為x|y服從高斯分布這個假設(shè)更強，GDA模型做出了一個更強的假設(shè)，所以，若x|y服從或近似服從高斯分布，那么GDA會比logistic回歸更好，因為它利用了更多關(guān)于數(shù)據(jù)的信息，即算法知道數(shù)據(jù)服從高斯分布。缺點：如果不確定x|y的分布情況，那么判別算法logistic回歸性能更好。例如，預(yù)先假設(shè)數(shù)據(jù)服從高斯分布，但是實

37、際上數(shù)據(jù)服從泊松分布，根據(jù)推論2，logistic回歸仍能獲得不錯的效果。生成學(xué)習(xí)算法比判決學(xué)習(xí)算法需要更少的數(shù)據(jù)。如GDA的假設(shè)較強，所以用較少的數(shù)據(jù)能擬合出不錯的模型。而logistic回歸的假設(shè)較弱，對模型的假設(shè)更為健壯，擬合數(shù)據(jù)需要更多的樣本。3、樸素貝葉斯另一種生成學(xué)習(xí)算法。例：垃圾郵件分類實現(xiàn)一個垃圾郵件分類器，以郵件輸入流作為輸入，確定郵件是否為垃圾郵件。輸出y為0,1，1為垃圾郵件，0為非垃圾郵件。首先，要將郵件文本表示為一個輸入向量x，設(shè)已知一個含有n個詞的字典，那么向量x的第i個元素0,1表示字典中的第i個詞是否出現(xiàn)在郵件中，x示例如下：要對p(x|y)建模，x是一個n維的

38、0,1向量，假設(shè)n=50000，那么x有250000種可能的值，一種方法是用多項式分布進行建模（伯努利分布對01建模，多項式分布對k個結(jié)果建模），這樣就需要250000-1個參數(shù)，可見參數(shù)過多，下面介紹樸素貝葉斯的方法。假設(shè)xi在給定y的時候是條件獨立的，則x在給定y下的概率可簡化為：這個假設(shè)直觀理解為，已知一封郵件是不是垃圾郵件(y)，以及一些詞是否出現(xiàn)在郵件中，這些并不會幫助你預(yù)測其他的詞是否出現(xiàn)在郵件中。雖然這個假設(shè)不是完全正確的，但是樸素貝葉斯依然應(yīng)用于對郵件進行分類，對網(wǎng)頁進行分類等用途。*對于樸素貝葉斯，我的理解為：通過指定一些垃圾郵件的關(guān)鍵詞來計算某個郵件是垃圾郵件的概率。具體講

39、，就是給定字典后，給出每個詞的p(xi|y=1)，即這個詞xi在垃圾郵件中出現(xiàn)的概率，然后對于一個郵件，將郵件所有詞的p(xi|y)的相乘，就是郵件為垃圾郵件的概率。再簡化一些，規(guī)定p(xi|y=1)=0,1，即劃定一些關(guān)鍵詞，這些關(guān)鍵詞在郵件中出現(xiàn)的概率就是這封郵件為垃圾郵件的概率。模型參數(shù)包括：i|y=1 = p(xi=1|y=1)i|y=0 = p(xi=1|y=0)y = p(y=1)聯(lián)合似然性：求得參數(shù)結(jié)果：i|y=1的分子為標記為1的郵件中出現(xiàn)詞j的郵件數(shù)目和，分母為垃圾郵件數(shù)，總體意義就是訓(xùn)練集中出現(xiàn)詞j的垃圾郵件在垃圾郵件中的比例。i|y=0就是出現(xiàn)詞j的非垃圾郵件在非垃圾郵件

40、中的比例。y就是垃圾郵件在所有郵件中的比例。求出上述參數(shù)，就知道了p(x|y)和p(y)，用伯努利分布對p(y)建模，用上式中p(xi|y)的乘積對p(x|y)建模，通過貝葉斯公式就可求得p(y|x)*實際操作中，例如將最近兩個月的郵件都標記上“垃圾”或“非垃圾”，然后得到(x(1),y(1)(x(m),y(m)，x(i)為詞向量，標記出現(xiàn)在第i個郵件中的詞，y(i)為第i個郵件是否是垃圾郵件。用郵件中的所有出現(xiàn)的詞構(gòu)造字典，或者選擇出現(xiàn)次數(shù)k次以上的詞構(gòu)造字典。樸素貝葉斯的問題：設(shè)有一封新郵件中出現(xiàn)一個字典沒有的新詞，設(shè)其標號為30000，因為這個詞在垃圾郵件和非垃圾郵件中都不存在，則p(x

41、3000|y=1)=0，p(x30000|y=0)=0，計算p(y=1|x)如下：p(y=1|x) = p(x|y=1)p(y=1) / ( p(x|y=1)p(y=1) + p(x|y=0)p(y=0)由于p(x|y=1)=p(x|y=0)=0（p(x30000|y=1)=p(x30000|y=0)=0，則乘積為0），則p(y=1|x)=0/0，則結(jié)果是未定義的。其問題在于，統(tǒng)計上認為p(x30000|y)=0是不合理的。即在過去兩個月郵件里未出現(xiàn)過這個詞，就認為其出現(xiàn)概率為0，并不合理。概括來講，即之前沒有見過的事件，就認為這些事件不會發(fā)生，是不合理的。通過Laplace平滑解決這個問題。

42、4、Laplace平滑根據(jù)極大似然估計，p(y=1) = #”1”s / (#”0”s + #”1”s)，即y為1的概率是樣本中1的數(shù)目在所有樣本中的比例。Laplace平滑就是將分子分母的每一項都加1,，即：p(y=1) = (#”1”s+1) / (#”0”s+1 + #”1”s+1)例：給出一支球隊5場比賽的結(jié)果作為樣本，5場比賽都輸了，記為0，那么要預(yù)測第六場比賽的勝率，按照樸素貝葉斯為：p(y=1) = 0/(5+0) = 0，即樣本中沒有勝場，則勝率為0，顯然這是不合理的。按照Laplace平滑處理，p(y=1) = 0+1/(5+1+0+1) = 1/7，并不為0，且隨著負場次的

43、增加，p(y=1)會一直減小，但不會為0。更一般的，若y取k中可能的值，比如嘗試估計多項式分布的參數(shù)，得到下式：即值為j的樣本所占比例，對其用Laplace平滑如下式：對于樸素貝葉斯，得到的結(jié)果為：在分子上加1，分母上加2，解決了0概率的問題。第六課樸素貝葉斯本次課程大綱：1、樸素貝葉斯-樸素貝葉斯事件模型2、神經(jīng)網(wǎng)絡(luò)（簡要）3、支撐向量機（SVM）鋪墊最大間隔分類器復(fù)習(xí)：1、樸素貝葉斯一種生成學(xué)習(xí)算法，對p(x|y)建模。例：垃圾郵件分類以郵件輸入流作為輸入，輸出y為0,1，1為垃圾郵件，0為非垃圾郵件。將郵件文本表示為一個輸入向量x1）xi0,1，表示字典中的第i個詞是否出現(xiàn)在郵件中2）x

44、長度為n，n為字典的詞數(shù)3）該模型稱為多元伯努利事件模型假設(shè)xi在給定y的時候是條件獨立的，則x在給定y下的概率可簡化為：根據(jù)樸素貝葉斯公式，求p(y|x)最大時的y：算法變化版本：1）讓xi取多個值，xi1,2,k，類似上式有：p(x|y) = p(xi|y)，但是p(xi|y)變成多項式分布，而不是伯努利分布。例：估計房屋面積預(yù)測房屋能否被賣掉，將房屋面積分成幾個離散區(qū)間，如0-,1000為xi=1,1000-1500為xi=2，1500-2000為xi=3,2000以上為xi=42）如上例處理郵件（文本）中，x向量記錄每個詞出現(xiàn)的次數(shù)（而不是是否出現(xiàn)）多項式事件模型接上例，給出一封郵件，

45、將它表示成特征向量：，ni表示郵件中詞的數(shù)量，xj是個到詞典的索引，表示該詞在詞典的位置。如郵件中有300個詞，那么特征向量x(i)長度為300，若詞典有50000個詞，每個元素xj的取值范圍為1,2,50000則生成模型的聯(lián)合概率p(xy)為：n為郵件長度上式理解：郵件內(nèi)容滿足一些概率分布，有一些隨機分布在生成這些郵件。過程為：首先確定y，即是否為垃圾郵件，決定一個人是否向你發(fā)送垃圾郵件后，遍歷郵件的300個詞，按照某種概率分布生成一些詞，基于他們是否向你發(fā)送垃圾郵件模型參數(shù)：表示某人決定向你發(fā)送垃圾郵件(y=1)時，選擇詞k的概率，類似有：給出訓(xùn)練集后，求極大似然估計：得到：上面第一個式子

46、，分子的意思是，對所有標簽為1的郵件求和，之后對垃圾郵件中的詞k求和，所以分子實際上就是訓(xùn)練集中所有垃圾郵件中詞k出現(xiàn)的次數(shù)。分母是訓(xùn)練集中所有垃圾郵件的長度。比值的含義就是所有垃圾郵件中，詞k占的比例。表示生成垃圾郵件時選擇詞k的概率。應(yīng)用Laplace平滑，分子加1，分母加總詞數(shù)（字典大小，xi可能取值的數(shù)目）：事實上，多項式事件模型比之前的模型要好，可能是因為考慮了詞出現(xiàn)的次數(shù)這個因素。但此問題仍存在爭論。非線性分類算法例：logistic回歸中，假設(shè)值小于0.5預(yù)測0，大于0.5預(yù)測1。即給定一個訓(xùn)練集，logistic回歸會找到一條直線（牛頓方法或梯度下降），將正負樣本合理分開。但有

47、時數(shù)據(jù)不能被一條直線分開，需要一種算法，學(xué)習(xí)非線性的分界線。上一講的推論：x|y=1 ExpFamily(1)，x|y=0 ExpFamily (0) = p(y=1|x)是logistic函數(shù)即x|y的分布屬于指數(shù)分布族，可推出后驗分布是logistic函數(shù)。樸素貝葉斯模型也屬于指數(shù)分布族，所以也是用logistic線性分類器。下面介紹一種非線性分類器。2、神經(jīng)網(wǎng)絡(luò)假設(shè)特征是x0,x1,x2,x3，x0設(shè)置為1，用連線表示logistic回歸單元，圓圈表示計算節(jié)點，下圖中間的節(jié)點以x0等特征作為輸入，h(x)作為輸出，這是一個sigmoid函數(shù)。為了找到非線性的界限，需要找到一種方式，表示出

48、能夠輸出非線性分界限的假設(shè)。將之前畫的小單元拼在一起，得到神經(jīng)網(wǎng)絡(luò)。特征輸入到若干個sigmoid單元，在輸入到另外一個sigmoid單元，得到輸出。中間節(jié)點的輸出值設(shè)為a1,a2,a3。這些中間節(jié)點稱為隱藏層，神經(jīng)網(wǎng)絡(luò)可以由多個隱層。每個中間節(jié)點有一系列參數(shù)：a2,a3同理。g為sigmoid函數(shù)。最終的輸出值為：其中，a向量由a1,a2,a3組成。一種學(xué)習(xí)模型參數(shù)的方法是，利用成本函數(shù)J()，使用梯度下降使J()最小。即用梯度下降使得神經(jīng)網(wǎng)絡(luò)的預(yù)測結(jié)果和你觀察到的訓(xùn)練集中的樣本標簽盡可能接近。在神經(jīng)網(wǎng)絡(luò)中，這種方法稱為反向傳播。3、支撐向量機鋪墊最大間隔分類器另外一種能生成非線性分類器的學(xué)

49、習(xí)算法。本節(jié)課先介紹另外一類線性分類器，在下一講或者下下講中，利用支撐向量機的想法，進行一些巧妙的改動和擴展，讓它可以生成非線性分界線。兩種對于分類的直觀理解：1)考慮logistic回歸，計算Tx：輸出1 Tx=0；輸出0 Tx0，相當確定的預(yù)測y=1；如果Tx0，如果y=0，Tx(i)=0; -1,如果z 0；如果y(i)=-1，為了獲得較大的函數(shù)間隔，需要令wTx(i)+b 0，意味著分類結(jié)果正確一個超平面(w,b)和整個訓(xùn)練集的函數(shù)間隔定義為：即相對于整個訓(xùn)練集的函數(shù)間隔定義為所有相對于樣本的函數(shù)間隔的最壞情形（上述講到，分界線距離樣本越遠效果越好）。幾何間隔：幾何距離定義為：一個訓(xùn)練樣本對應(yīng)的點到由超平面確定的分隔線的距離。如下圖A到分隔線的距離AB就是幾何距離。和分隔線垂直的單位向量表示為：w/|w|，AB這段距離表示為(i)，上有小三角表示函數(shù)間隔，沒有表示幾何間隔。若A點表示x(i)，那么點B表示為：由于點B在分隔線上，它應(yīng)該還滿足：可以解出：上式說明，對于一個訓(xùn)練樣本x(i)，到由參數(shù)w和b確定的分隔平面之間的距離，可以由上式得到。由于上述一直假設(shè)對樣本進行了正確的分類，所以更一般的，將幾何間