機(jī)器學(xué)習(xí)斯坦福大學(xué)講義

機(jī)器學(xué)習(xí)一斯坦福大學(xué)講義第一課機(jī)器學(xué)習(xí)的動(dòng)機(jī)與應(yīng)用工具:需正版：Matlab.免費(fèi):Octave定義(ArthurSamuel1959)：在不直接針對(duì)問題進(jìn)行編程的情況下，賦予計(jì)算機(jī)學(xué)習(xí)能力的研究領(lǐng)域。例：Arthur的下棋程序，計(jì)算走每一步獲勝的概率，最終打敗程序作者本人.(感覺使用決策樹思想)定義2(TomMitchell1998)：一個(gè)合理的學(xué)習(xí)問題應(yīng)該這樣定義：對(duì)一個(gè)計(jì)算機(jī)程序來說，給它一個(gè)任務(wù)T和一個(gè)性能測(cè)量方法P,如果在經(jīng)驗(yàn)E的影響下，P對(duì)T的測(cè)量結(jié)果得到了改進(jìn)，那么就說改程序從E中學(xué)習(xí)了。如上例：E：程序不斷和自己下棋的經(jīng)歷，T：下棋，P：和人類選手對(duì)弈的勝率課程的四大部分：1、有監(jiān)督學(xué)習(xí)回歸問題例：收集某地房屋價(jià)格統(tǒng)計(jì)、房屋大小和價(jià)格對(duì)應(yīng)情況：畫出一條擬合曲線，就可以通過房屋大小估計(jì)價(jià)格。有監(jiān)督學(xué)習(xí)即給出一個(gè)數(shù)據(jù)集(正確的房屋價(jià)格及對(duì)應(yīng)大小)此例為回歸問題?；貧w意味著需要預(yù)測(cè)的變量是連續(xù)的分類問題分類問題中需要處理的變量是離散的例：判斷腫瘤是惡性還是兩性收集腫瘤大小和惡性/良性數(shù)據(jù)，大小為橫軸，是否是惡性為縱軸（只有0,1）畫圖腫瘤可能由多個(gè)因素導(dǎo)致，引入年齡，大小為橫軸，年齡為縱軸，惡性以叉表示，良性以圓圈表示畫圖，分析患腫瘤的區(qū)域還可引入更多屬性，畫在多維空間中無限維空間如何處理？將無限維映射到內(nèi)存的算法？2,學(xué)習(xí)理論學(xué)習(xí)理論即解釋學(xué)習(xí)型算法有效的原因（學(xué)習(xí)算法的理論基礎(chǔ)）尋找什么樣的算法能很好地近似不同的函數(shù)，訓(xùn)練集的規(guī)模是否合適3、無監(jiān)督學(xué)習(xí)例：如上述腫瘤例子，圖中的點(diǎn)不知道正確答案，而是由你從中找去一定的結(jié)構(gòu)，即聚類。應(yīng)用于生物基因工程，圖像處理，計(jì)算機(jī)視覺等領(lǐng)域例：雞尾酒會(huì)問題在嘈雜的雞尾酒會(huì)中，將你感興趣的聲音提取出來運(yùn)用兩個(gè)不同位置的麥克分開來自不同位置的聲音還能應(yīng)用于文本處理等領(lǐng)域使用ICA算法，Matlab一行代碼即可解決4、強(qiáng)化學(xué)習(xí)通過決策產(chǎn)生的結(jié)論或?qū)蝈e(cuò)，故產(chǎn)生一系列的決策。例：對(duì)一個(gè)模型飛機(jī)編寫一個(gè)起飛程序，飛機(jī)在程序做了一連串錯(cuò)誤決策是才會(huì)墜毀，只要做出連續(xù)的整體還不錯(cuò)的決策，即可保持飛機(jī)正常飛行強(qiáng)化學(xué)習(xí)的基本概念：回報(bào)函數(shù)（正反饋及負(fù)反饋），程序做出正確決策時(shí)給出正反饋，反之亦然。程序不斷做出決策，在不斷嘗試獲得盡量多的正反饋時(shí)，逐漸學(xué)習(xí)并做出正確決策關(guān)鍵在于要定義什么是正確決策，什么是錯(cuò)誤決策，再設(shè)計(jì)算法獲取盡量多的正反饋第二課監(jiān)督學(xué)習(xí)應(yīng)用與梯度下降本課內(nèi)容：1、線性回歸2、梯度下降3、正規(guī)方程組（復(fù)習(xí)）監(jiān)督學(xué)習(xí)：告訴算法每個(gè)樣本的正確答案，學(xué)習(xí)后的算法對(duì)新的輸入也能輸入正確的答案1、線性回歸例：Alvin汽車，先讓人開車，Alvin攝像頭觀看（訓(xùn)練），而后實(shí)現(xiàn)自動(dòng)駕駛。本質(zhì)是一個(gè)回歸問題，汽車嘗試預(yù)測(cè)行駛方向。例：上一節(jié)課的房屋大小與價(jià)格數(shù)據(jù)集Livingarea(feet2)Price(1000$s)2104Ilin1C00330240036914162323000540

引入通用符號(hào)：m=訓(xùn)練樣本數(shù)乂=輸入變量(特征)丫=輸出變量(目標(biāo)變量)(x,y)-一個(gè)樣本第i個(gè)訓(xùn)練樣本本例中：m：數(shù)據(jù)個(gè)數(shù)，X：房屋大小，y：價(jià)格監(jiān)督學(xué)習(xí)過程：將訓(xùn)練樣本提供給學(xué)習(xí)算法算法生成一個(gè)輸出函數(shù)(一般用h表示，成為假設(shè))這個(gè)函數(shù)接收輸入，輸出結(jié)果。(本例中為，接收房屋面積，輸出房?jī)r(jià))將x映射到y(tǒng)?如下圖所示：Training

setILearningalgoritliin4(Ixvmgmaofx ah-apredictedy(Ixvmgmaof(predictedpnc?)ofbouse)

對(duì)假設(shè)進(jìn)行線性表示：Mx)=魚+"%通常來說，回歸問題有多個(gè)輸入特征。如上例中，我們還已知房屋的臥室數(shù)，即有個(gè)第二個(gè)特征。即x塞示大小,小表示臥室數(shù)，則可將假設(shè)寫成：‘坨⑴=%+ati+%工2oh（工）=￡OtXi=91x為了將公式寫整潔，定義Co=1,則h可寫成： i=On=特征數(shù)目，6參數(shù)。選擇e的目的，是使h(x)與y的平方差盡量小。又由于有m個(gè)訓(xùn)練樣本，需要計(jì)算每個(gè)樣本的平方差，最后為了簡(jiǎn)化結(jié)果乘以1/2,即：我們要做的就是求:min(J(4)我們要做的就是求:min(J(4)求min。?))方法：梯度下降和正規(guī)方程組2、梯度下降梯度下降是一種搜索算法，基本思想：先給出參數(shù)向量一個(gè)初始值，比如0向量；不斷改變，使得J(6)不斷縮小。改變的方法：梯度下降如圖所示，水平坐標(biāo)軸表示名和”,垂直坐標(biāo)表示J(6)

一開始選擇0向量作為初始值，假設(shè)該三維圖為一個(gè)三維地表,。向量的點(diǎn)位于一座“山”上。梯度下降的方法是，你環(huán)視一周，尋找下降最快的路徑，即為梯度的方向，每次下降一小步,再環(huán)視四周，繼續(xù)下降，以此類推。結(jié)果到達(dá)一個(gè)局部最小值，如下圖：當(dāng)然，若初始點(diǎn)不同，則結(jié)果可能為另一個(gè)完全不同的局部最小值，如下:表明梯度下降的結(jié)果依賴于參數(shù)初始值。梯度下降算法的數(shù)學(xué)表示：d,、6:=Gj

:=為賦值運(yùn)算符，即表示程序中的的賦值語句。每一次將仇減去3對(duì)/(,)求偏導(dǎo)的結(jié)果，即沿最陡峭的“山坡”下降將偏導(dǎo)數(shù)展開分析：套咐=磊面付5=2-1(/(工)-y)-9(2(0-y)=(h0(x)-y)xj%：=%+a僅⑴一版(才⑴))婢).代入上式： J 3a：學(xué)習(xí)速度，即決定你下山時(shí)每?步邁多大。設(shè)的過小，收斂時(shí)間長(zhǎng)，設(shè)的過大，可能會(huì)超過最小值(1) 批梯度下降算法：上述為處理一個(gè)訓(xùn)練樣本的公式，將其派生成包含m個(gè)訓(xùn)練樣本的算法，循環(huán)下式直至收斂：%:=%+a 僅⑴—法(1⑴))可)復(fù)雜度分析：對(duì)于每個(gè)師的每次迭代，即上式所示，時(shí)間為0(m)每次迭代(走一步)需要計(jì)算n個(gè)特征的梯度值，復(fù)雜度為。(mn)

一般來說，這種二次函數(shù)的/(')的三維圖形為一個(gè)碗狀，有?”個(gè)唯一的全局最小值。其等高線為一個(gè)套一個(gè)的橢圓形，運(yùn)用梯度下降會(huì)快速收斂到圓心.梯度下降性質(zhì)：接近收斂時(shí)，每次的步子會(huì)越來越小。其原因是每次減去a乘以梯度，但是梯度會(huì)越來越小，所以步子會(huì)越來越小。下圖為使用梯度下降擬合的上例房屋大小和價(jià)格的曲線檢測(cè)是否收斂的方法：檢測(cè)兩次迭代仇的改變量，若不再變化，則判定收斂更常用的方法：檢驗(yàn)/(6),若不再變化，判定收斂批梯度下降算法的優(yōu)點(diǎn)是能找到局部最優(yōu)解，但是若訓(xùn)練樣本m很大的話，其每次迭代都要計(jì)算所有樣本的偏導(dǎo)數(shù)的和，時(shí)間過慢，于是采用下述另一種梯度下降方法。(2) 隨機(jī)梯度下降算法(增量梯度下降算法)：Loop{fori=ltom,{0j:=%+a("⑴——("))x(j] (foreveryj).))每次計(jì)算可不需要再遍歷所有數(shù)據(jù)，而是只需計(jì)算樣本i即可。即批梯度下降中，走一步為考慮m個(gè)樣本；隨機(jī)梯度下降中，走一步只考慮1個(gè)樣本。每次迭代復(fù)雜度為0(n)。當(dāng)m個(gè)樣本用完時(shí)，繼續(xù)循環(huán)到第1個(gè)樣本。上述使用了迭代的方法求最小值，實(shí)際上對(duì)于這類特定的最小二乘回歸問題，或者普通最小二乘問題，存在其他方法給出最小值，接下來這種方法可以給出參數(shù)向量的解析表達(dá)式,如此一來就不需要迭代求解了。3、正規(guī)方程組給定一個(gè)函數(shù)J,J是一個(gè)關(guān)于參數(shù)數(shù)組的函數(shù)，定義J的梯度關(guān)于的導(dǎo)數(shù)，它自己也是一個(gè)向量。向量大小為n+1維(從0到n),如下：也兩%/=： e/?n+1dj腐J所以，梯度下降算法可寫成：

更普遍的講，對(duì)于一個(gè)函數(shù)f,f的功能是將一個(gè)m*n的矩陣映射到實(shí)數(shù)空間上，即:f:RmxniR假設(shè)輸入為m*n大小的矩陣A,定義f關(guān)于矩陣A的導(dǎo)數(shù)為:r_?z_dAwV"⑷= i-DAml導(dǎo)數(shù)本身也是個(gè)矩陣，包含了f關(guān)于A的每個(gè)元素的偏導(dǎo)數(shù)。如果A是一個(gè)方陣，即n*n的矩陣，則將A的跡定義為A的對(duì)角元素之和，即:ntrA=4t=itrA即為tr(A)的簡(jiǎn)化。一些關(guān)于跡運(yùn)算符和導(dǎo)數(shù)的定理：trAB=trBAtrABC=trCAB=trBCA%trAB=BTtrA=trAT若2?匕tra=a6) 匕trABHC=CAB+CTABT有了上述性質(zhì)，可以開始推導(dǎo)了:

定義矩陣X,稱為設(shè)計(jì)矩陣，包含了訓(xùn)練集中所有輸入的矩陣，第i行為第i組輸入數(shù)據(jù),即：（工⑴）7―一（工⑵）T一（的/_則由于/（工⑴）=（工⑴）的，所以可得:（Hd（（Hd（工⑴）_y⑴7'_ 2則有:又因?yàn)閷?duì)于向量z,有Z2=2^4,則有:1工\（xe-yfiXO-y]=2*二1

=J⑻由上述最后一個(gè)性質(zhì)可得：1萬trAB^C=BT^TCT+BATC通過上述6個(gè)性質(zhì)，推導(dǎo):▽〃⑹=^0^(XO-y)T(XO-y)= (el'xTxe-鏟x%-/xe+fy)=tr(OTXTX0-OTXTy-fXG+= (treTXTXe-2tryrX0)=1(XrXO+xl'xe-2XTy)=xTxe-倒數(shù)第三行中，運(yùn)用最后一個(gè)性質(zhì)將“/⑻置為0,則有：XrX0=XTy稱為正規(guī)方程組可得：e=第三課欠擬合與過擬合概念本次課程大綱：1、局部加權(quán)回歸：線性回歸的變化版本2、概率解釋：另一種可能的對(duì)于線性回歸的解釋3、Logistic回歸：基于2的一個(gè)分類算法4、感知器算法：對(duì)于3的延伸，簡(jiǎn)要講復(fù)習(xí)：(”卜⑴)-第i個(gè)訓(xùn)練樣本令7。=1,以參數(shù)向量為條件，對(duì)于輸入x,輸出為：h(x)—仇勺=9T],i=0n為特征數(shù)量定義成本函數(shù)J,定義為：咐=若("I"m為訓(xùn)練樣本通過正規(guī)方程組推導(dǎo)的結(jié)論：0=[XTX)~lXTy.1、過擬合與欠擬合通常，你選擇交給學(xué)習(xí)算法處理的特征的方式對(duì)算法的工作過程有很大影響。例：上次課的例子中，用X1表示房間大小。通過線性回歸，在橫軸為房間大小，縱軸為價(jià)格的圖中，畫出擬合曲線。回歸的曲線方程為：8。+8逐]若定義特征集合為：xl表示房子大小，x2表示房子大小的平方，使用相同的算法，擬合得到一個(gè)二次函數(shù)，在圖中即為一個(gè)拋物線，即：0o+0ixi+02Xi：以此類推，若訓(xùn)練集有7個(gè)數(shù)據(jù)，則可擬合出最高6次的多項(xiàng)式,可以找到一條完美的曲線，該曲線經(jīng)過每個(gè)數(shù)據(jù)點(diǎn)。但是這樣的模型又過于復(fù)雜，擬合結(jié)果僅僅反映了所給的特定數(shù)據(jù)的特質(zhì)，不具有通過房屋大小來估計(jì)房?jī)r(jià)的普遍性。而線性回歸的結(jié)果可能無法捕獲所有訓(xùn)練集的信息。所以，對(duì)于一個(gè)監(jiān)督學(xué)習(xí)模型來說，過小的特征集合使得模型過于簡(jiǎn)單，過大的特征集合使得模型過于復(fù)雜。對(duì)于特征集過小的情況，稱之為欠擬合(underfitting)；對(duì)于特征集過大的情況，稱之為過擬合(overfitting)解決此類學(xué)習(xí)問題的方法：特征選擇算法：一類自動(dòng)化算法，在這類回歸問題中選擇用到的特征非參數(shù)學(xué)習(xí)算法：緩解對(duì)于選取特征的需求，引出局部加權(quán)回歸參數(shù)學(xué)習(xí)算法(parametriclearningalgorithm)定義：參數(shù)學(xué)習(xí)算法是一類有固定數(shù)目參數(shù)，以用來進(jìn)行數(shù)據(jù)擬合的算法。設(shè)該固定的參數(shù)集合為立線性回歸即使參數(shù)學(xué)習(xí)算法的一個(gè)例子非參數(shù)學(xué)習(xí)算法(Non-parametriclearningalgorithm)定義：一個(gè)參數(shù)數(shù)量會(huì)隨m(訓(xùn)練集大小)增長(zhǎng)的算法。通常定義為參數(shù)數(shù)量雖m線性增長(zhǎng)。換句話說，就是算法所需要的東西會(huì)隨著訓(xùn)練集合線性增長(zhǎng)，算法的維持是基于整個(gè)訓(xùn)練集合的，即使是在學(xué)習(xí)以后。2、局部加權(quán)回歸(LocallyWeightedRegression)一種特定的非參數(shù)學(xué)習(xí)算法。也稱作Loess。算法思想:假設(shè)對(duì)于一個(gè)確定的查詢點(diǎn)X,在X處對(duì)你的假設(shè)h(x)求值。對(duì)于線性回歸，步驟如下：1)擬合出e,使￡i(y⑴-尹工⑴)2最小2)返回對(duì)于局部加權(quán)回歸，當(dāng)要處理X時(shí)：檢查數(shù)據(jù)集合，并且只考慮位于X周圍的固定區(qū)域內(nèi)的數(shù)據(jù)點(diǎn)對(duì)這個(gè)區(qū)域內(nèi)的點(diǎn)做線性回歸，擬合出一條直線根據(jù)這條擬合直線對(duì)x的輸出，作為算法返回的結(jié)果用數(shù)學(xué)語言描述即：D擬“，使(嚴(yán)一心⑴產(chǎn)最小w為權(quán)值，有很多可能的選擇，比如：其意義在于，所選取的x(i)越接近X,相應(yīng)的w(i)越接近1；x(i)越遠(yuǎn)離x,w(i)越接近Oo直觀的說，就是離得近的點(diǎn)權(quán)值大，離得遠(yuǎn)的點(diǎn)權(quán)值小。這個(gè)衰減函數(shù)比較具有普遍意義，雖然它的曲線是鐘形的，但不是高斯分布。°被稱作波長(zhǎng)函數(shù)，它控制了權(quán)值隨距離下降的速率。它越小，鐘形越窄，w衰減的很快；它越大，衰減的就越慢。3)返回總結(jié)：對(duì)于局部加權(quán)回歸，每進(jìn)行一次預(yù)測(cè)，都要重新擬合一條曲線。但如果沿著X軸對(duì)每個(gè)點(diǎn)都進(jìn)行同樣的操作，你會(huì)得到對(duì)于這個(gè)數(shù)據(jù)集的局部加權(quán)回歸預(yù)測(cè)結(jié)果，追蹤到一條非線性曲線。局部加權(quán)回歸的問題：由于每次進(jìn)行預(yù)測(cè)都要根據(jù)訓(xùn)練集擬合曲線，若訓(xùn)練集太大，每次進(jìn)行預(yù)測(cè)的用到的訓(xùn)練集就會(huì)變得很大，有方法可以讓局部加權(quán)回歸對(duì)于大型數(shù)據(jù)集更高效，詳情參見AndrewMoore的關(guān)于KD-tree的工作。3、概率解釋概率解釋所解決的問題：在線性回歸中，為什么選擇最小二乘作為計(jì)算參數(shù)的指標(biāo)，使得假設(shè)預(yù)測(cè)出的值和真正y值之間面積的平方最小化？我們提供一組假設(shè)，證明在這組假設(shè)下最小二乘是有意義的，但是這組假設(shè)不唯一，還有其他很多方法可以證明其有意義。(1)假設(shè)1：假設(shè)輸入與輸出為線性函數(shù)關(guān)系，表示為：=〃工⑴+■”其中，為誤差項(xiàng)，這個(gè)參數(shù)可以理解為對(duì)未建模效應(yīng)的捕獲，如果還有其他特征，這個(gè)誤差項(xiàng)表示了一種我們沒有捕獲的特征，或者看成一種隨機(jī)的噪聲。假設(shè)服從某個(gè)概率分布，如高斯分布(正態(tài)分布)：￡°)~研0.。2),表示一個(gè)均值是0,方差是°’的高斯分布。高斯分布的概率密度函數(shù)：v27ro\ 2。)根據(jù)上述兩式可得:”忖)洌二會(huì)呻(一吟爐)V27ra\ 2a- /即，在給定了特征與參數(shù)之后，輸出是一個(gè)服從高斯分布的隨機(jī)變量，可描述為：y("|工⑴;6 (尹工⑴,02)*為什么選取高斯分布？便于數(shù)學(xué)處理對(duì)絕大多數(shù)問題，如果使用了線性回歸模型，然后測(cè)量誤差分布，通常會(huì)發(fā)現(xiàn)誤差是高斯分布的。中心極限定律：若干獨(dú)立的隨機(jī)變量之和趨向于服從高斯分布。若誤差有多個(gè)因素導(dǎo)致，這些因素造成的效應(yīng)的總和接近服從高斯分布。注意：e并不是一個(gè)隨機(jī)變量，而是一個(gè)嘗試估計(jì)的值，就是說它本身是一個(gè)常量，只不過我們不知道它的值，所以上式中用分號(hào)表示。分號(hào)應(yīng)讀作“以…作為參數(shù)”，上式讀作“給定x(i)以為參數(shù)的y(i)的概率服從高斯分布”。假設(shè)每個(gè)為IID(independentlyandidenticallydistributed)獨(dú)立同分布即誤差項(xiàng)彼此之間是獨(dú)立的，并且他們服從均值和方差相同的高斯分布假設(shè)2：設(shè)e的似然性為(即給定x(i)以為參數(shù)的州的概率=L(優(yōu)工㈤=p⑷、：6)由于只“是獨(dú)立同分布，所以上式可寫成所有分布的乘積：

假設(shè)3：極大似然估計(jì)：選取e使似然性L（e）最大化（數(shù)據(jù)出現(xiàn)的可能性盡可能大）定義對(duì)數(shù)似然函數(shù)為K8）：的）=°y/2rcro22父"-'上式兩個(gè)加項(xiàng)，前一項(xiàng)為常數(shù)。所以，使似然函數(shù)最大，就是使后一項(xiàng)最小，即：1尸工（嚴(yán)一心⑴產(chǎn)i=l這一項(xiàng)就是之前的〕（e）,由此得證，即之前的最小二乘法計(jì)算參數(shù)，實(shí)際上是假設(shè)了誤差項(xiàng)滿足高斯分布，且獨(dú)立同分布的情況，使似然最大化來計(jì)算參數(shù)。注意：高斯分布的方差對(duì)最終結(jié)果沒有影響，由于方差一定為正數(shù)，所以無論取什么值，最后結(jié)果都相同。這個(gè)性質(zhì)會(huì)在下節(jié)課講到。

4、Logistic回歸這是我們要學(xué)習(xí)的第一個(gè)分類算法。之前的回歸問題嘗試預(yù)測(cè)的變量y是連續(xù)變量，在這個(gè)分類算法中，變量y是離散的，y只取。1｝兩個(gè)值。一般這種離散二值分類問題用線性回歸效果不好。比如x<=3,y=0；x>3,Y=l,那么當(dāng)x>3的樣本占得比例很大是，線性回歸的直線斜率就會(huì)越來越小，y=0.5時(shí)對(duì)應(yīng)的x判決點(diǎn)就會(huì)比3大，造成預(yù)測(cè)錯(cuò)誤。若y取值。1｝，首先改變假設(shè)的形式，使假設(shè)得到的值總在[0禺之間，即：h(x)U°，l]所以，選取如下函數(shù):,、 ，T、 1h如=9(0tx)=]其中:g(?)=g(?)=1+e-zg函數(shù)一般被稱為logistic函數(shù)，圖像如下:z很小時(shí)，g(z)趨于0,z很大時(shí)，g(z)趨于1,z=0時(shí)，g(z)=0.5對(duì)假設(shè)的概率解釋:假設(shè)給定X以為參數(shù)的y=l和y=0的概率:P(y=l\x\0)=h0(x)P(y=0|x;0)=1—he(x)的EP??h⑼=SG））"0一加（工））”"可以簡(jiǎn)與成：參數(shù)的似然性：附=p（y\X；e）m=Hp"”工⑴網(wǎng)i=lm=n（原則嚴(yán)（「/（叫產(chǎn)”?=i求對(duì)數(shù)似然性：幽=10gL⑹m=^2bgM工⑴）+（1—y⑴）log（i—力（工⑴））S=1為了使似然性最大化，類似于線性回歸使用梯度下降的方法，求對(duì)數(shù)似然性對(duì)e的偏導(dǎo)，即:0=0+。▽招。）因?yàn)榍笞畲笾担藭r(shí)為梯度上升。偏導(dǎo)數(shù)展開:卻⑻=（，薪j(luò)Ti）廣嬴0Q心=（y（i-g?7））-（i-！/）g（。％））叼=（y-ho（x））xj則：4：=%+a（嚴(yán)-砧］⑴））c?即類似上節(jié)課的隨機(jī)梯度上升算法，形式上和線性回歸是相同的，只是符號(hào)相反，八式x）為logistic函數(shù)，但實(shí)質(zhì)上和線性回歸是不同的學(xué)習(xí)算法。5、感知器算法在logistic方法中，g⑵會(huì)生成［0,1）之間的小數(shù)，但如何是g⑵只生成0或1?所以，感知器算法將g⑵定義如下：、（1ifz>0g⑶=［0ifzv0同樣令瓦）（工）=g（e］），和logistic回歸的梯度上升算法類似，學(xué)習(xí)規(guī)則如下：%：=%+a（y⑴一M（工⑴））工，盡管看起來和之前的學(xué)習(xí)算法類似，但感知器算法是一種非常簡(jiǎn)便的學(xué)習(xí)算法，臨界值和輸出只能是。或1,是比logistic更簡(jiǎn)單的算法。后續(xù)講到學(xué)習(xí)理論是，會(huì)將其作為基本的構(gòu)造步驟。第四課牛頓方法本次課程大綱：1、牛頓方法：對(duì)Logistic模型進(jìn)行擬合2、指數(shù)分布族3、廣義線性模型(GLM)：聯(lián)系Logistic回歸和最小二乘模型復(fù)習(xí)：Logistic回歸：分類算法假設(shè)給定x以為參數(shù)的y=l和y=0的概率：P(y=\| =h0(x)P(y=0|x;0)=1-h0(x)赤1+€求對(duì)數(shù)似然性：絢)=logL(0)m=Xlog/i(x(,))+(1—y⑴)log(l—f二l對(duì)其求偏導(dǎo)數(shù)，應(yīng)用梯度上升方法，求得：%：=4+°(嚴(yán)一加(工⑴))本次課程介紹的牛頓方法是一種比梯度上升快很多的方法，用于擬合Logistic回歸1、牛頓方法假設(shè)有函數(shù)限），需要找使f⑼=0的e步驟：給出一個(gè)'的初始值對(duì)眼⑴求導(dǎo)，求導(dǎo)數(shù)為o時(shí)e的值（就是求f（e）切線與x軸交點(diǎn)）重復(fù)步驟2因?yàn)樵擖c(diǎn)的導(dǎo)數(shù)值即為切線斜率，而斜率=該點(diǎn)y軸的值/該點(diǎn)X軸的變化值，所以e每次的變化值:*使用這個(gè)方法需要f滿足一定條件，適用于Logistic回歸和廣義線性模型*一般初始化為0應(yīng)用于Logistic回歸:求對(duì)數(shù)似然的最大值，即求'（8）為。時(shí)的句根據(jù)上述推論，更新規(guī)則如下:牛頓方法的收斂速度：二次收斂每次迭代使解的有效數(shù)字的數(shù)目加倍：假設(shè)當(dāng)前誤差是0.1,一次迭代后，誤差為0.001,再一次迭代，誤差為0.0000001。該性質(zhì)當(dāng)解距離最優(yōu)質(zhì)的足夠近才會(huì)發(fā)現(xiàn)。牛頓方法的一般化：e是一個(gè)向量而不是一個(gè)數(shù)字，一般化的公式為：0:=0-▽4(g)是目標(biāo)函數(shù)的梯度，H為Hessian矩陣，規(guī)模是n*n,n為特征的數(shù)量，它的每個(gè)元素表示一個(gè)二階導(dǎo)數(shù)：—必⑻L麗麗上述公式的意義就是，用一個(gè)一階導(dǎo)數(shù)的向量乘以一個(gè)二階導(dǎo)數(shù)矩陣的逆優(yōu)點(diǎn)：若特征數(shù)和樣本數(shù)合理，牛頓方法的迭代次數(shù)比梯度上升要少得多缺點(diǎn)：每次迭代都要重新計(jì)算Hessian矩陣，如果特征很多，則H矩陣計(jì)算代價(jià)很大2、指數(shù)分布族回顧學(xué)過的兩種算法：對(duì)于P(y|x；e)：若y屬于實(shí)數(shù)，滿足高斯分布，得到基于最小二乘法的線性回歸；若丫取{0,1},滿足伯努利分布，得到Logistic回歸。問題：如Logistic回歸中，為何選擇sigmoid函數(shù)？sigmoid函數(shù)是最自然的默認(rèn)選擇。接下來，會(huì)以這兩個(gè)算法為例，說明它們都是廣義線性模型的特例。考慮上述兩個(gè)分布，伯努利分布和高斯分布：伯努利分布設(shè)有一組只能取0或1的數(shù)據(jù)，用伯努利隨機(jī)變量對(duì)其建模：切方’~Bernoulli(<j)f則P(y=l；(p)=巴改變參數(shù)年，y=i這一事件就會(huì)有不同概率，會(huì)得到一類概率分布(而非固定的)。高斯分布引工冶?八乂""”改變參數(shù)口，也會(huì)得到不同的高斯分布，即一類概率分布。上述這些分布都是一類分布的特例，這類分布稱為指數(shù)分布族.指數(shù)分布族的定義：若一類概率分布可以寫成如下形式，那么它就屬于指數(shù)分布族：P(y；〃)=b(g)exp(/r(y)—a(〃))n-自然參數(shù)，通常是一個(gè)實(shí)數(shù)T(y)-充分統(tǒng)計(jì)量，通常，T(y)=y,實(shí)際上是一個(gè)概率分布的充分統(tǒng)計(jì)量(統(tǒng)計(jì)學(xué)知識(shí))對(duì)于給定的a,b,T三個(gè)函數(shù)，上式定義了一個(gè)以n為參數(shù)的概率分布集合，即改變f］可以得到不同的概率分布。證明伯努利分布是指數(shù)分布族：Ber(<P).P(y=1;<p)=<p可知:p(y;p(y;。)exp(ylogd+(1-y)log(l-</>))y+log(l-0))y+log(l-0))由上式可見,n=log((p/(l?(p))，可解出：cp=l/(l+exp(-r))),發(fā)現(xiàn)得到logistic函數(shù)(之后討論其原因)，則:T\y)=y麗)=-log(l-0)=log(l4-e。)帥)=1證明高斯分布是指數(shù)分布族：引工；'?人廣(〃,02),設(shè)方差為1(方差并不影響結(jié)果，僅僅是變量y的比例因子)這種情況下高斯密度函數(shù)為：b[y)=(l/\/27r)exp(-j/2/2)*指數(shù)分布族包括：高斯分布(正態(tài)分布)，多元正態(tài)分布;

伯努利分布(01問題建模)，多項(xiàng)式分布(對(duì)k個(gè)結(jié)果的事件建模)：泊松分布(對(duì)計(jì)數(shù)過程建模)；伽馬分布，指數(shù)分布(對(duì)實(shí)數(shù)的間隔問題建模)；B分布，Dirichlet分布(對(duì)小數(shù)建模)；Wishart分布(協(xié)方差矩陣的分布)...3、廣義線性模型GLM選定了一個(gè)指數(shù)分布族后，怎樣來推導(dǎo)出一個(gè)GLM呢?假設(shè)：⑴y|上:ExponcntialFamilyS),即假設(shè)試圖預(yù)測(cè)的變量y在給定x,以e作為參數(shù)的條件概率，屬于以n作為自然參數(shù)的指數(shù)分布族例：若要統(tǒng)計(jì)網(wǎng)站點(diǎn)擊量y,用泊松分布建模(2)給定X,目標(biāo)是求出以x為條件的T(y)的期望E[T(y)|x],即讓學(xué)習(xí)算法輸出h(x)=E[T(y)|x]即自然參數(shù)和輸入特征x之間線性相關(guān)，關(guān)系由e決定。僅當(dāng)n是實(shí)數(shù)時(shí)才有意義。若n是一個(gè)向量，仍=9ix推導(dǎo)伯努利分布的GLM：y\i\0^ExponentialFamily(7/),伯努利分布屬于指數(shù)分布族對(duì)給定的X,0,學(xué)習(xí)算法進(jìn)行一次預(yù)測(cè)的輸出：ho(x)=E[y\x-,0]=6=1/(1+ef)=1/(1+0-叼得到logistic回歸算法。正則響應(yīng)函數(shù)：g(n)=E[y；n],將自然參數(shù)n和y的期望聯(lián)系起來正則關(guān)聯(lián)函數(shù)：g1推導(dǎo)多項(xiàng)式分布的GLM：多項(xiàng)式分布是在k個(gè)可能取值上的分布，即y￡{l，…,k},如將收到的郵件分成k類，診斷某病人為k種病中的一種等問題。(1)將多項(xiàng)式分布寫成指數(shù)分布族的形式：設(shè)多項(xiàng)式分布的參數(shù)：°1 且2二1,5表示第i個(gè)取值的概率分布，最后一個(gè)參數(shù)可以由前k-1個(gè)推導(dǎo)出，所以只將前k-1個(gè)01，???，以T視為參數(shù)。多項(xiàng)式分布是少數(shù)幾個(gè)T(y)!=y的分布，?、湃~化)都定義成一個(gè)k-l維的列向量，表示為：丁。)="1"00,?、?'0-10,T(3)=.0.01-0'00，丁的=■00000010這樣定義T(y)是為了將多項(xiàng)式分布寫成指數(shù)分布族形式。*定義符號(hào)：指示函數(shù)，1{Jl{True}=1,l{False}=0,即大括號(hào)內(nèi)命題為真，值為1,；否則為0。例：1{2=3}=0,1{1+1=2}=1用T(y)i表示T(y)的第i個(gè)元素，則T(y)i=l{y=i}根據(jù)參數(shù)<p的意義(<pi表示第i個(gè)取值的概率分布)，可推出:

p(y;。)=而V=i}p(y;。)=樸E}/{7...就￡3lg}°『(小理(加…碗-E匕|(7?Lexp((T(y))ilog(01)+(T(!/))2log(內(nèi))+…+(1—￡：二；(丁5)))log(@Q)cxp((T(y))ilog(%/以)+(T(y))2bg(曲/娟+…+ log(a-i/<M+bg(c〃))My)exp(7，T(y)-a(〃))可得:log(珈/如log(如AMn= ;10gsi/<Ma(q)=Tog(以)咐)=I.證明多項(xiàng)式分布式指數(shù)分布族。再用n表示（p：/=IogOkMe”史<t>k6Me”。人?￡e”。人?￡e”￡6=1

i=l（2）根據(jù)上述假設(shè)（3）中自然參數(shù)和輸入x的線性關(guān)系，可求得:（3）根據(jù)上述假設(shè)（2）中的輸出h（x）=E[T（y）|x],可求得:he(x)=E[T(y)|x;0]1{〃=1}l{y=A:-1}010252)=1exp(^i)

OXp(^T)稱這種回歸算法為softmax回歸，是logistic回歸的推廣。Softmax回歸的訓(xùn)練方法和logistic相似，通過極大似然估計(jì)找到參數(shù)6,其對(duì)數(shù)似然性為:mW=Ebgp（y"3"；e）

再通過梯度上升或牛頓方法找對(duì)數(shù)似然性的最大值，即可求出參數(shù)e?第五課生成學(xué)習(xí)算法本次課程大綱：1、生成學(xué)習(xí)算法2、高斯判別分析（GDA,GaussianDiscriminantAnalysis）高斯分布（簡(jiǎn)要）對(duì)比生成學(xué)習(xí)算法&判別學(xué)習(xí)算法（簡(jiǎn)要）3、樸素貝葉斯4、Laplace平滑復(fù)習(xí)：分類算法：給出一個(gè)訓(xùn)練集，若使用logistic回歸算法，其工作方式是觀察這組數(shù)據(jù)，嘗試找到一條直線將圖中不同的類分開，如下圖。之前講的都是判別學(xué)習(xí)算法，本課介紹一種不同的算法：生成學(xué)習(xí)算法。1、生成學(xué)習(xí)算法例：對(duì)惡性腫瘤和良性腫瘤的分類除了尋找一個(gè)將兩類數(shù)據(jù)區(qū)分的直線外，還可以用如下方法：遍歷訓(xùn)練集，找到所有惡性腫瘤樣本，直接對(duì)惡性腫瘤的特征建模：同理，對(duì)良性腫瘤建模。對(duì)一個(gè)新的樣本分類時(shí)，即有一個(gè)新的病人時(shí)，要判斷其是惡性還是良性，用該樣本分別匹配惡性腫瘤模型和良性腫瘤模型，看哪個(gè)模型匹配的更好，預(yù)測(cè)屬于惡性還是良性。這種方法就是生成學(xué)習(xí)算法。兩種學(xué)習(xí)算法的定義：判別學(xué)習(xí)算法：直接學(xué)習(xí)p(y|x),即給定輸入特征，輸出所屬的類或?qū)W習(xí)得到一個(gè)假設(shè)hB(x),直接輸出0或1生成學(xué)習(xí)算法：對(duì)p(x|y)進(jìn)行建模，p(x|y)表示在給定所屬的類的情況下，顯示某種特征的概率。處于技術(shù)上的考慮，也會(huì)對(duì)p(y)進(jìn)行建模。p(x|y)中的x表示一個(gè)生成模型對(duì)樣本特征建立概率模型，y表示在給定樣本所屬類的條件下例：在上例中，假定一個(gè)腫瘤情況y為惡性和良性，生成模型會(huì)對(duì)該條件下的腫瘤癥狀x的概率分布進(jìn)行建模- 對(duì)p(x|y)和p(y)建模后，根據(jù)貝葉斯公式p(y|x)=p(xy)/p(x)=p(x|y)p(y)/p(x),可以計(jì)算：p(y=l|x)=p(x|y=l)p(y=l)/p(x),其中，p(x)=p(x|y=O)p(y=O)+p(x|y=l)p(y=l)2、高斯判別分析GDAGDA是一種生成學(xué)習(xí)算法。GDA的假設(shè)條件:假設(shè)輸入特征XGRn,并且是連續(xù)值。假設(shè)p(x|y)滿足高斯分布高斯分布基礎(chǔ)知識(shí)：設(shè)隨機(jī)變量z滿足多元高斯分布，z~N(p，E),均值向量為P，協(xié)方差矩陣為Z。其概率密度函數(shù)為：以工；出E)=.°XP(W(工一?(工一")多元高斯分布為一元高斯分布的推廣，也是鐘形曲線，z是一個(gè)高維向量。多元高斯分布注意兩個(gè)參數(shù)即可：均值向量p協(xié)方差矩陣z=E[(Z-E[Z])(Z-E[Z])t]=E[(x-m)(x-p)t]多元高斯分布圖：左圖：p=0,Z=I(單位矩陣)中圖：尸0,X=0.6l,圖形變陡峭右圖：口=0,E=2I,圖形變扁平三圖中M=0,10.50.51；工=10.80.81三圖中M=0,10.50.51；工=10.80.81J可見增加矩陣對(duì)角元素的值，即變量間增加相關(guān)性,高斯曲面會(huì)沿zl=z2（兩個(gè)水平軸）方向趨于扁平。其水平面投影圖如下:即增加2對(duì)角線的元素，圖形會(huì)沿45°角，偏轉(zhuǎn)成一個(gè)橢圓形狀。若Z若Z對(duì)角線元素為負(fù)，圖形如下:1 -0.5-0.5 11 1 -0.5-0.5 11 -0.8-0.8 130.80.81不同p的圖形如下:M分別為:-0.5

0-1-1.5y決定分布曲線中心的位置。GDA擬合:給出訓(xùn)練樣本如下圖所示:觀察正樣本(圖中的x),擬合正樣本的高斯分布，如圖中左下方的圓，表示p(x|y=l)觀察負(fù)樣本(圖中的圈)，擬合負(fù)樣本的高斯分布，如圖中右上方的圓，表示p(x|y=O)通過這兩個(gè)高斯分布的密度函數(shù)，定義出兩個(gè)類別的分隔器，即圖中的直線這條分隔器宜線比之前的logistic擬合的直線要復(fù)雜GDA模型：yzBernoulli（^）x\y—0zE）x\y=1z寫出其概率分布：p（y）=/P（h?=0）=加二Z0exp（一,（1?謝」（工一閑P（l|y=l）=（27T）n/；E1/2exp（J（工一出）'￡1（丁一”）參數(shù)包括（P，po,pl,3對(duì)數(shù)似然性為：m=logjjp（工⑴，嚴(yán):

d=l

m=logJJp（yl/；〃oM,Z）P（"0）.

i=l由于第一個(gè)等式為xy的聯(lián)合概率，將這個(gè)模型命名為聯(lián)合似然性(Jointlikelihood)o*對(duì)比logistic回歸中的對(duì)數(shù)似然性：m1(0)=logJ""!p(yw|xw；0)由于計(jì)算的是y在x條件下的概率，將此模型命名為條件似然性(conditionallikelihood)通過對(duì)上面對(duì)數(shù)似然性求極大似然估計(jì)，參數(shù)的結(jié)果為：1二。{嚴(yán)=1}，=1-￡；小{*=0}〃 _ ￡21{-=1}工⑴1工s=— 工⑴-)(工⑴一"W))74=1<p:訓(xùn)練樣本中標(biāo)簽為1的樣本所占的比例M0：分母為標(biāo)簽為0的樣本數(shù)，分子是對(duì)標(biāo)簽為0的樣本的x(i)求和，結(jié)合起來就是對(duì)對(duì)標(biāo)簽為0的樣本的x(i)求均值，與高斯分布參數(shù)p為均值的意義相符pl：與pO同理，標(biāo)簽改為1GDA預(yù)測(cè)：預(yù)測(cè)結(jié)果應(yīng)該是給定x的情況下最可能的y,等式左邊的運(yùn)算符argmax表示計(jì)算p(y|x)最大時(shí)的y值，預(yù)測(cè)公式如下：argmaxp(j/|x)My)p(y)argmaxp(j/|x)=argmax - y p(")=argmaxp(x|3/)p(y).因?yàn)閜(x)獨(dú)立于y,所以可以忽略p(x)。*如果p(y)為均勻分布，即每種類型的概率都相同，那么也可以忽略p(y)，要求的就是使p(x|y)最大的那個(gè)y。不過這種情況并不常見。GDA和logistic回歸的聯(lián)系:例：假設(shè)有一個(gè)一維訓(xùn)練集，包含一些正樣本和負(fù)樣本，如下圖x軸的叉和圈，設(shè)叉為0,圈為1,用GDA對(duì)兩類樣本分別擬合高斯概率密度函數(shù)p(x|y=0)和p(x|y=l),如下圖的兩個(gè)鐘形曲線。沿x軸遍歷樣本，在x軸上方畫出其相應(yīng)的p(y=l|x)。如選x軸靠左的點(diǎn)，那么它屬于1的概率幾乎為0,p(y=l|x)=0,兩條鐘形曲線交點(diǎn)處，屬于0或1的概率相同，p(y=l|x)=0.5,x軸靠右的點(diǎn)，輸出1的概率幾乎為1,p(y=l|x)=l。最終發(fā)現(xiàn)，得到的曲線和sigmoid函數(shù)曲線很相似。簡(jiǎn)單來講，就是當(dāng)使用GDA模型時(shí),p(x|y)屬于高斯分布，計(jì)算p(y|x)時(shí)，幾乎能得到和logistic回歸中使用的sigmoid函數(shù)一樣的函數(shù)。但實(shí)際上還是存在本質(zhì)區(qū)別的。使用生成學(xué)習(xí)算法的優(yōu)缺點(diǎn)：給出兩個(gè)推論：推論1：x|y服從高斯分布=>p(y=l|x)是logistic函數(shù)該推論在反方向不成立。推論2：x|y=l~Poisson(Xl),x|y=0~Poisson(XO)=>p(y=l|x)是logistic函數(shù)x|y=l~Poisson(入1)表示x|y=l服從參數(shù)為XI泊松分布推論3：x|y=l~ExpFamily(r]l),x|y=0~ExpFamily(r]0)=>p(y=l|x)是logistic函數(shù)推論2的推廣，即x|y的分布屬于指數(shù)分布族，均可推出結(jié)論。顯示了logistic回歸在建模假設(shè)選擇方面的魯棒性。優(yōu)點(diǎn)：推論1反方向不成立，因?yàn)閤|y服從高斯分布這個(gè)假設(shè)更強(qiáng)，GDA模型做出了一個(gè)更強(qiáng)的假設(shè)，所以，若x|y服從或近似服從高斯分布，那么GDA會(huì)比logistic回歸更好，因?yàn)樗昧烁嚓P(guān)于數(shù)據(jù)的信息，即算法知道數(shù)據(jù)服從高斯分布。缺點(diǎn)：如果不確定x|y的分布情況，那么判別算法logistic回歸性能更好。例如，預(yù)先假設(shè)數(shù)據(jù)服從高斯分布,但是實(shí)際上數(shù)據(jù)服從泊松分布，根據(jù)推論2,logistic回歸仍能獲得不錯(cuò)的效果。生成學(xué)習(xí)算法比判決學(xué)習(xí)算法需要更少的數(shù)據(jù)。如GDA的假設(shè)較強(qiáng)，所以用較少的數(shù)據(jù)能擬合出不錯(cuò)的模型。而logistic回歸的假設(shè)較弱，對(duì)模型的假設(shè)更為健壯，擬合數(shù)據(jù)需要更多的樣本。3、樸素貝葉斯另一種生成學(xué)習(xí)算法。例：垃圾郵件分類實(shí)現(xiàn)一個(gè)垃圾郵件分類器，以郵件輸入流作為輸入，確定郵件是否為垃圾郵件。輸出y為。1},1為垃圾郵件，0為非垃圾郵件。首先，要將郵件文本表示為一個(gè)輸入向量x,設(shè)已知一個(gè)含有n個(gè)詞的字典，那么向量x的第i個(gè)元素。1}表示字典中的第i個(gè)詞是否出現(xiàn)在郵件中，x示例如下：aaardvarkaardwolf1buy0Jzygmurgy要對(duì)p(x|y)建模，x是一個(gè)n維的{0,1}向量，假設(shè)n=50000,那么x有2A50000種可能的值，一種方法是用多項(xiàng)式分布進(jìn)行建模(伯努利分布對(duì)01建模，多項(xiàng)式分布對(duì)k個(gè)結(jié)果建模)，這樣就需要”50000-1個(gè)參數(shù)，可見參數(shù)過多，下面介紹樸素貝葉斯的方法。假設(shè)xi在給定y的時(shí)候是條件獨(dú)立的，則x在給定y下的概率可簡(jiǎn)化為：P(Q,…，工50000?)=p(x\\y)pixi\y,Xi)p(xs\y,xi,X2)???p(xsooooh，????,^49999)=P(^lMHghOp(司y)….(±50000》)n=JJp(詞!/)t=l這個(gè)假設(shè)直觀理解為，已知一封郵件是不是垃圾郵件(y),以及一些詞是否出現(xiàn)在郵件中，這些并不會(huì)幫助你預(yù)測(cè)其他的詞是否出現(xiàn)在郵件中。雖然這個(gè)假設(shè)不是完全正確的，但是樸素貝葉斯依然應(yīng)用于對(duì)郵件進(jìn)行分類，對(duì)網(wǎng)頁進(jìn)行分類等用途。*對(duì)于樸素貝葉斯，我的理解為：通過指定一些垃圾郵件的關(guān)鍵詞來計(jì)算某個(gè)郵件是垃圾郵件的概率。具體講，就是給定字典后，給出每個(gè)詞的p(xi|y=l),即這個(gè)詞xi在垃圾郵件中出現(xiàn)的概率，然后對(duì)于一個(gè)郵件，將郵件所有詞的p(xi|y)的相乘，就是郵件為垃圾郵件的概率。再簡(jiǎn)化一些，規(guī)定p(xi|y=l)={0,l},即劃定一些關(guān)鍵詞，這些關(guān)鍵詞在郵件中出現(xiàn)的概率就是這封郵件為垃圾郵件的概率。模型參數(shù)包括：0i|y=l=p(xi=l|y=l)<Di|y=0=p(xi=l|y=0)

①y=p(y=l)

聯(lián)合似然性:m￡(如，如吟1)=ne，嚴(yán))

i=l求得參數(shù)結(jié)果：Ojg0j|y=O如￡3g=15=Ojg0j|y=O如￡31{“)=1}-1{7？=1八*=0}￡?1{…。}-￡乙1{嚴(yán)=1}mei|y=l的分子為標(biāo)記為1的郵件中出現(xiàn)詞j的郵件數(shù)目和，分母為垃圾郵件數(shù)，總體意義就是訓(xùn)練集中出現(xiàn)詞j的垃圾郵件在垃圾郵件中的比例。0i|y=O就是出現(xiàn)詞j的非垃圾郵件在非垃圾郵件中的比例。0y就是垃圾郵件在所有郵件中的比例。求出上述參數(shù)，就知道了p(x|y)和p(y),用伯努利分布對(duì)p(y)建模，用上式中p(xi|y)的乘積對(duì)p(x|y)建模，通過貝葉斯公式就可求得p(y|x)*實(shí)際操作中，例如將最近兩個(gè)月的郵件都標(biāo)記上“垃圾”或“非垃圾”，然后得到(x(l),y(l))...(x(m),y(m)),x(i)為詞向量，標(biāo)記出現(xiàn)在第i個(gè)郵件中的詞，y(i)為第i個(gè)郵件是否是垃圾郵件。用郵件中的所有出現(xiàn)的詞構(gòu)造字典，或者選擇出現(xiàn)次數(shù)k次以上的詞構(gòu)造字典。樸素貝葉斯的問題：設(shè)有一封新郵件中出現(xiàn)一個(gè)字典沒有的新詞，設(shè)其標(biāo)號(hào)為30000,因?yàn)檫@個(gè)詞在垃圾郵件和非垃圾郵件中都不存在，則p(x3000|y=l)=0,p(x30000|y=0)=0,計(jì)算p(y=l|x)如下：p(y=l|x)=p(x|y=l)p(y=l)/(p(x|y=l)p(y=l)+p(x|y=0)p(y=0))STp(x|y=l)=p(x|y=0)=0(p(x30000|y=l)=p(x30000|y=0)=0.則乘積為0),則p(y=l|x)=0/0,則結(jié)果是未定義的。其問題在于，統(tǒng)計(jì)上認(rèn)為p(x30000|y)=0是不合理的。即在過去兩個(gè)月郵件里未出現(xiàn)過這個(gè)詞，就認(rèn)為其出現(xiàn)概率為0,并不合理。概括來講，即之前沒有見過的事件，就認(rèn)為這些事件不會(huì)發(fā)生，是不合理的。通過Laplace平滑解決這個(gè)問題。4、Laplace平滑根據(jù)極大似然估計(jì)，P(y=l)=#"l"s/(#"O"s+#"l"s),即y為1的概率是樣本中1的數(shù)目在所有樣本中的比例。Laplace平滑就是將分子分母的每一項(xiàng)都加1,,即：p(y=l)=(#"l"s+l)/(#"0"s+l+riMs+l)例：給出一支球隊(duì)5場(chǎng)比賽的結(jié)果作為樣本，5場(chǎng)比賽都輸了，記為0,那么要預(yù)測(cè)第六場(chǎng)比賽的勝率，按照樸素貝葉斯為：p(y=l)=0/(5+0)=0,即樣本中沒有勝場(chǎng)，則勝率為0,顯然這是不合理的。按照Laplace平滑處理，p(y=l)=0+1/(5+1+0+1)=1/7,并不為0,且隨著負(fù)場(chǎng)次的增加，p(y=l)會(huì)一直減小，但不會(huì)為0。更一般的，若y取k中可能的值，比如嘗試估計(jì)多項(xiàng)式分布的參數(shù)，得到下式：如一m,即值為j的樣本所占比例，對(duì)其用Laplace平滑如下式：%= ?對(duì)于樸素貝葉斯，得到的結(jié)果為：_￡3時(shí))=1八?=1}+16g"一￡下{”)=1}+2—_W=")=o}+1*。--￡21{/)=0}+2-在分子上加1,分母上加2,解決了0概率的問題。第六課樸素貝葉斯本次課程大綱：1、樸素貝葉斯-樸素貝葉斯事件模型2、神經(jīng)網(wǎng)絡(luò)（簡(jiǎn)要）3、支撐向量機(jī)（SVM）鋪墊-最大間隔分類器復(fù)習(xí)：1、樸素貝葉斯一種生成學(xué)習(xí)算法，對(duì)p（x|y）建模。例：垃圾郵件分類以郵件輸入流作為輸入，輸出y為{0,1},1為垃圾郵件，。為非垃圾郵件。將郵件文本表示為一個(gè)輸入向量xxie{0,1},表示字典中的第i個(gè)詞是否出現(xiàn)在郵件中x長(zhǎng)度為n,n為字典的詞數(shù)3）該模型稱為多元伯努利事件模型aaardvark

aardwolfbuyzygmiirgy

假設(shè)Xi在給定y的時(shí)候是條件獨(dú)立的，則x在給定y下的概率可簡(jiǎn)化為：P(G tsooooW)=pCn|y)p(工2?,工i)p(g|y,乃,n)…p(x5oooo|j/,工i,…，工.iwoo)=p(x1|y)p(工2W)p(工3舊)…p(x5/oooo\y)n=根據(jù)樸素貝葉斯公式，求p(y|x)根據(jù)樸素貝葉斯公式，求p(y|x)最大時(shí)的y：argmaxp(^|x)=成也)p(y)argmax y p(工)argmaxp(x|t/)p(j/).y算法變化版本：1)讓xi取多個(gè)值,xi€{l,2，…,k},類似上式有：p(x|y)=TTP(xi|y),但是p(xi|y)變成多項(xiàng)式分布，而不是伯努利分布。例：估計(jì)房屋面積預(yù)測(cè)房屋能否被賣掉，將房屋面積分成幾個(gè)離散區(qū)間，如0-,1000為xi=l,1000-1500為xi=2,1500-2000為xi=3,2000以上為xi=42)如上例處理郵件(文本)中，x向量記錄每個(gè)詞出現(xiàn)的次數(shù)(而不是是否出現(xiàn))多項(xiàng)式事件模型/(0(0 (0\接上例，給出一封郵件，將它表示成特征向量：(/，12，?一，]凡),ni表示郵件中詞的數(shù)量，xj是個(gè)到詞典的索引，表示該詞在詞典的位置。如郵件中有300個(gè)詞，那么特征向量x(i)長(zhǎng)度為300,若詞典有50000個(gè)詞，每個(gè)元素xj的取值范圍為{1,2,.,50000}?P(xy)=(]-[p(xjy))p(y)則生成模型的聯(lián)合概率p(xy)為:n為郵件長(zhǎng)度上式理解：郵件內(nèi)容滿足一些概率分布，有一些隨機(jī)分布在生成這些郵件。過程為：首先確定y,即是否為垃圾郵件，決定一個(gè)人是否向你發(fā)送垃圾郵件后，遍歷郵件的300個(gè)詞，按照某種概率分布生成一些詞，基于他們是否向你發(fā)送垃圾郵件模型參數(shù)：(iPkly.1=P(Xj=A|y=1)表示某人決定向你發(fā)送垃圾郵件(y=i)時(shí)，選擇詞k的概率，類似有：3kb=o=P(Xj=A|y=。)<Py=p(y=1)給出訓(xùn)練集后，求極大似然估計(jì)：m°。,0i|y=l)=i=lm(z \=JJI]7「(工丁|%刖=0，廂=1))P?⑴;。!/).i=l\J=1 /得到：*~ ￡颶1{-=im_￡圈￡蜀1{4)=人-八嚴(yán)=0}- ￡匚1{/)=0m——=1}%= .m上面第一個(gè)式子，分子的意思是，對(duì)所有標(biāo)簽為1的郵件求和，之后對(duì)垃圾郵件中的詞k求和，所以分子實(shí)際上就是訓(xùn)練集中所有垃圾郵件中詞k出現(xiàn)的次數(shù)。分母是訓(xùn)練集中所有垃圾郵件的長(zhǎng)度。比值的含義就是所有垃圾郵件中，詞k占的比例。表示生成垃圾郵件時(shí)選擇詞k的概率。應(yīng)用Laplace平滑，分子加1,分母加總詞數(shù)(字典大小，xi可能取值的數(shù)目)：_-W=2=i}+i的1--匯力{/=1}"卜1￡隨￡%1{3"=A八*=0}+1的"*" —{/)=o}%+IH-事實(shí)上，多項(xiàng)式事件模型比之前的模型要好，可能是因?yàn)榭紤]了詞出現(xiàn)的次數(shù)這個(gè)因素。但此問題仍存在爭(zhēng)論。非線性分類算法例:logistic回歸中，假設(shè)值小于0.5預(yù)測(cè)0,大于0.5預(yù)測(cè)1。即給定一個(gè)訓(xùn)練集，logistic回歸會(huì)找到一條直線(牛頓方法或梯度下降)，將正負(fù)樣本合理分開.但有時(shí)數(shù)據(jù)不能被一條直線分開，需要一種算法，學(xué)習(xí)非線性的分界線。上一講的推論：x|y=l~ExpFamily(ql),x|y=0~ExpFamily(q0)=>p(y=l|x)是logistic函數(shù)即x|y的分布屬于指數(shù)分布族，可推出后驗(yàn)分布是logistic函數(shù)。樸素貝葉斯模型也屬于指數(shù)分布族，所以也是用logistic線性分類器。下面介紹一種非線性分類器。2、神經(jīng)網(wǎng)絡(luò)假設(shè)特征是x0,xl,x2,x3,x0設(shè)置為1,用連線表示logistic回歸單元，圓圈表示計(jì)算節(jié)點(diǎn)，下圖中間的節(jié)點(diǎn)以x0等特征作為輸入，h/x)作為輸出，這是一個(gè)sigmoid函數(shù)。為了找到非線性的界限，需要找到一種方式，表示出能夠輸出非線性分界限的假設(shè)。

將之前畫的小單元拼在一起，得到神經(jīng)網(wǎng)絡(luò)。特征輸入到若干個(gè)sigmoid單元，在輸入到另外一個(gè)sigmoid單元，得到輸出。中間節(jié)點(diǎn)的輸出值設(shè)為al,a2,a3。這些中間節(jié)點(diǎn)稱為隱藏層，神經(jīng)網(wǎng)絡(luò)可以由多個(gè)隱層。每個(gè)中間節(jié)點(diǎn)有一系列參數(shù):%=g(x3a)),g(z)=7-X—X?ca2,a3同理。g為sigmoid函數(shù)。最終的輸出值為:3G)=9(k心)其中，a向量由al,a2,a3組成。一種學(xué)習(xí)模型參數(shù)的方法是，利用成本函數(shù)j(e),使用梯度下降使j(e)最小。即用梯度下降使得神經(jīng)網(wǎng)絡(luò)的預(yù)測(cè)結(jié)果和你觀察到的訓(xùn)練集中的樣本標(biāo)簽盡可能接近。在神經(jīng)網(wǎng)絡(luò)中，這種方法稱為反向傳播。3、支撐向量機(jī)鋪墊-最大間隔分類器另外一種能生成非線性分類器的學(xué)習(xí)算法。本節(jié)課先介紹另外一類線性分類器，在下一講或者下下講中，利用支撐向量機(jī)的想法，進(jìn)行一些巧妙的改動(dòng)和擴(kuò)展，讓它可以生成非線性分界線。兩種對(duì)于分類的直觀理解：考慮logistic回歸，計(jì)算Ux：輸出1<=>eTx>=o；輸出o<=>eTx<o如果Mx>〉。，相當(dāng)確定的預(yù)測(cè)y=l；如果eTx<<0,相當(dāng)確定的預(yù)測(cè)y=0對(duì)于所有的i，如果y=l,eTx(il?o,如果y=o,eTx(i)?o,那么我們認(rèn)為分類器是良好的。即如果我們根據(jù)訓(xùn)練集找到了參數(shù)，我們的學(xué)習(xí)算法不僅需要保證分類結(jié)果正確，更要進(jìn)一步保證分類結(jié)果的確定性。假設(shè)訓(xùn)練集是線性可分割的，即一定有一條直線可以將訓(xùn)練集分開。那么直觀來看,我們一定會(huì)選擇和正負(fù)樣本都有一定距離的直線。后面講到分類器的幾何間隔時(shí)，再正式討論。支撐向量機(jī)中改動(dòng)的符號(hào)：輸出ye{-1,+1)h輸出的假設(shè)值也改為{-1,+1}g(z)={1,如果z>=0;-1,如果z<0}之前在使用式：h6(x尸g(Mx)時(shí)，假設(shè)xO=l且X為n+1維向量，現(xiàn)在忽略這兩個(gè)假設(shè)，表示為：hw,b(x)=g(wTx+b),這里的b相當(dāng)于原來的w相當(dāng)于原來。除去剩余部分，長(zhǎng)度為n維。將截距b單提出來，方便引出支撐向量機(jī)。函數(shù)間隔:

一個(gè)超平面(w,b)和某個(gè)特定訓(xùn)練樣本(x(i),y(i))對(duì)應(yīng)的函數(shù)間隔定義為一個(gè)超平面(w,b)和整個(gè)訓(xùn)練集的函數(shù)間隔定義為分界線距離樣本越遠(yuǎn)效果越好)幾何間隔一個(gè)超平面(w,b)和某個(gè)特定訓(xùn)練樣本(x(i),y(i))對(duì)應(yīng)的函數(shù)間隔定義為一個(gè)超平面(w,b)和整個(gè)訓(xùn)練集的函數(shù)間隔定義為分界線距離樣本越遠(yuǎn)效果越好)幾何間隔隔線的距離AB就是幾何距離即相對(duì)于整個(gè)訓(xùn)練集的函數(shù)間隔定義為所有相對(duì)于樣本的函數(shù)間隔的最壞情形(上述講到幾何距離定義為：一個(gè)訓(xùn)練樣本對(duì)應(yīng)的點(diǎn)到由超平面確定的分隔線的距離。如下圖A到分參數(shù)(w,b)定義了一個(gè)分類器，例如定義了一個(gè)線性分界線如果y(i)=l，為了獲得較大的函數(shù)間隔，需要令wTx(i)+b>>0如果y(i)=-l,為了獲得較大的函數(shù)間隔，需要令wTx(i)+b<<0如果y(i"wTx(i)+b)>0,意味著分類結(jié)果正確和分隔線垂直的單位向量表示為：w/||w||,AB這段距離表示為丫(i),丫上有小三角表示函數(shù)間隔，沒有表示幾何間隔。若A點(diǎn)表示x(i),那么點(diǎn)B表示為：由于點(diǎn)B在分隔線上，它應(yīng)該還滿足："扁)可以解出：⑴“工⑴+b/?/⑴b。=(血］+阿,上式說明，對(duì)于一個(gè)訓(xùn)練樣本x(i),到由參數(shù)W和b確定的分隔平面之間的距離，可以由上式得到。由于上述一直假設(shè)對(duì)樣本進(jìn)行了正確的分類，所以更一般的，將幾何間隔定義為：這個(gè)定義和函數(shù)間隔很相似，不同點(diǎn)是對(duì)向量W進(jìn)行了標(biāo)準(zhǔn)化。同樣，希望幾何間隔也是越大越好。結(jié)論：如果I|w|1=1,函數(shù)間隔等于幾何間隔。更一般的，幾何間隔等于函數(shù)間隔除以||w|I。一個(gè)超平面(w,b)和整個(gè)訓(xùn)練集的幾何間隔定義為：(a)7=min7?和函數(shù)間隔類似,取樣本中最小的幾何間隔。最大間隔分類器可以看做是支撐向量機(jī)的前身,是一種學(xué)習(xí)算法，選擇特定的W和b,使幾何間隔最大化。最大分類間隔是下述這樣的優(yōu)化問題：max7mb7s.t.y⑴ ⑴+6)27,z=1,....mIHI=L即選擇Y，w,b是丫最大，同時(shí)滿足條件：所選取的最大幾何間隔必須保證每個(gè)樣本的結(jié)合間隔至少為丫。最大間隔分類器的效果和logistic回歸結(jié)果差不多好，深入研究這個(gè)分分類器，可以用一種更巧妙的方法讓其支持無限維的特征空間，得到有效的非線性分類器第七課最優(yōu)間隔分類器問題本次課程大綱：1、最優(yōu)間隔分類器2、原始優(yōu)化問題&對(duì)偶優(yōu)化問題(KKT條件)3、SVM對(duì)偶問題4、核方法(下一講)復(fù)習(xí)：支撐向量機(jī)中改動(dòng)的符號(hào)：輸出yF{-l,+l}h輸出的假設(shè)值也改為g(z)={1,如果z>=0;-1,如果z<0}hw.b(x)=g(wTx+b),這里的b相當(dāng)于原來的w相當(dāng)于原來。除去。0剩余部分，長(zhǎng)度為n維。將截距b單提出來，方便引出支撐向量機(jī)。函數(shù)間隔：一個(gè)超平面(w,b)和某個(gè)特定訓(xùn)練樣本(x(i),y(i))對(duì)應(yīng)的函數(shù)間隔定義為:夕⑴=嚴(yán)(mJx+b).參數(shù)(w,b)定義了一個(gè)分類器，例如定義了一個(gè)線性分界線。如果y(i)=l,為了獲得較大的函數(shù)間隔，需要令wTx(i)+b>>0；如果y(i)=-l,為了獲得較大的函數(shù)間隔，需要令wTx(i)+b<<0如果y(D(wTx(i)+b)>0,意味著分類結(jié)果正確一個(gè)超平面(w,b)和整個(gè)訓(xùn)練集的函數(shù)間隔定義為：7=min夕⑴.3=1,…,m即相對(duì)于整個(gè)訓(xùn)練集的函數(shù)間隔定義為所有相對(duì)于樣本的函數(shù)間隔的最壞情形(上述講到,分界線距離樣本越遠(yuǎn)效果越好)。幾何間隔：幾何間隔定義為：f(―)-這個(gè)定義和函數(shù)間隔很相似，不同點(diǎn)是對(duì)向量W進(jìn)行了標(biāo)準(zhǔn)化。同樣，希望幾何間隔也是越大越好。結(jié)論：如果I|w|1=1,函數(shù)間隔等于幾何間隔。更一般的，幾何間隔等于函數(shù)間隔除以I|w|I.一個(gè)超平面(w,b)和整個(gè)訓(xùn)練集的幾何間隔定義為：7=min

d=l,…,m和函數(shù)間隔類似，取樣本中最小的幾何間隔。性質(zhì)：可以任意比例縮放W和b,因?yàn)槿我饪s放w和b都不會(huì)改變超平面wTx+b=0的位置。這一性質(zhì)在后續(xù)討論中帶來很大便利。1、最優(yōu)間隔分類器最優(yōu)間隔分類器可以看做是支撐向量機(jī)的前身，是一種學(xué)習(xí)算法，選擇特定的W和b,使幾何間隔最大化。最優(yōu)分類間隔是下述這樣的優(yōu)化問題：max^,Wi67s.t. a:⑴+b）27,i=1,...,mIHl=i.即選擇Y，w,b使丫最大，同時(shí)滿足條件：所選取的最大幾何間隔必須保證每個(gè)樣本的幾何間隔至少為Y。即，找到一個(gè)超平面，在將正負(fù)樣本分開的同時(shí)，使超平面到正負(fù)樣本間的距離盡可能大。由于w和b可隨意縮放，約束條件||w||=l,使得函數(shù)間隔等于幾何間隔。但是這個(gè)約束本身是一個(gè)非常糟糕的非凸性約束。要求解的參數(shù)w在一個(gè)球體表面，如果想得到一個(gè)凸優(yōu)化問題，必須保證如梯度下降算法這種局部最優(yōu)值搜索算法不會(huì)找到局部最優(yōu)值，而非凸性約束不能滿足這個(gè)條件，所以需要改變優(yōu)化問題。為了解決上述問題，提出下面的最優(yōu)化問題：Amax7wfc扁s.t.嚴(yán)（w7工⑴+b）?夕,z=I,....m即將函數(shù)間隔除以I|w|I的值最大化，而這個(gè)值其實(shí)就是幾何間隔，只是上一個(gè)優(yōu)化問題的另一種表述。最優(yōu)化目標(biāo)是，最大化幾何間隔，同時(shí)保證函數(shù)間隔不小于丫八，即求最大的Y"，但是丫八上限是最小的函數(shù)間隔的值。對(duì)w添加約束條件：丫A=1，即函數(shù)間隔為1，即使,"（"/工⑴+6）式子的最小值為1。這個(gè)一個(gè)隱含的縮放條件。將這個(gè)約束加入到第二個(gè)最優(yōu)化問題中，得到最終的最優(yōu)間隔分類器：min-y.w.b511Ml2s.t.y⑴（u/工⑴+b）21,i=1,...,m這是一個(gè)凸優(yōu)化問題，且沒有局部最優(yōu)值，可以通過梯度下降找到全局最優(yōu)值。2,原始優(yōu)化問題&對(duì)偶優(yōu)化問題（KKT條件）原始問題如要求下式的值：minu,f(w)s.t.hi(w)=0,i=1,...,Z.即最小化函數(shù)f(w),并滿足約束條件hi(w)=0,可以將hi寫成0向量。創(chuàng)建拉格朗日算子：￡(孫夕)=/(w)+￡即

i=l即等于原始目標(biāo)函數(shù)加限制函數(shù)的線性組合，其中參數(shù)B稱為拉格朗日乘數(shù)。則，如果對(duì)下式求偏導(dǎo)數(shù)置為0,即可求出解：de八de——=0；>ttt=0,

dwid(3i對(duì)上述兩個(gè)偏導(dǎo)數(shù)方程求解，檢查得到的解是否為最小值即可.拉格朗日乘數(shù)法的一般形式，也稱為原始問題：min”，f(w)s.t.<0,ht(w)=0,i=1,...此時(shí)，拉格朗日算子為：k I￡(w,a,°)=/(w)4-￡ongi(w)+￡0ihi(w).

i=l i=l此時(shí)a和B為拉格朗日乘數(shù)，定義:

Op(w)=max￡(w,a,/?).a,0：Qi>Q上式中的p表示原始問題(primal),如果w違反了約束條