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

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

第一課機(jī)器學(xué)習(xí)的動(dòng)機(jī)與應(yīng)用

工具：需正版:Matlab,免費(fèi):Octave

定義(ArthurSamuel1959)：

在不直接針對(duì)問(wèn)題進(jìn)行編程的情況下，賦予計(jì)算機(jī)學(xué)習(xí)能力的研究領(lǐng)域。

例：Arthur的下棋程序，計(jì)算走每一步獲勝的概率，最終打敗程序作者本人。［感覺(jué)使用決策樹(shù)思

想)

定義2(TomMitchell1998)：

一個(gè)合埋的學(xué)習(xí)問(wèn)題應(yīng)該這樣定義：對(duì)一個(gè)計(jì)算機(jī)程序來(lái)說(shuō)，給它一個(gè)任務(wù)T和一個(gè)性能測(cè)量方法P,

如果在經(jīng)驗(yàn)E的影響下，P對(duì)T的測(cè)量結(jié)果得到了改良，那么就說(shuō)改程序從E中學(xué)習(xí)了。

如上例：E：程序不斷和自己下棋的經(jīng)歷，T：下棋，P：和人類選手對(duì)弈的勝率

課程的四大局部：

1、有監(jiān)督學(xué)習(xí)

(1)回歸問(wèn)題

例：收集某地房屋價(jià)格統(tǒng)計(jì)、房屋大小和價(jià)格對(duì)應(yīng)情況：

畫出一條擬合曲線，就可以通過(guò)房屋大小估計(jì)價(jià)格。

-有監(jiān)督學(xué)習(xí)即給出一個(gè)數(shù)據(jù)集(正確的房屋價(jià)格及對(duì)應(yīng)大小)

-此例為I可歸問(wèn)題?；貧w意味著需要預(yù)測(cè)的變量是連續(xù)的

(2)分類問(wèn)題

分類問(wèn)題中需要處理的變量是離散的

例：判斷腫瘤是惡性還是兩性

-收集腫瘤大小和惡性/良性數(shù)據(jù)，大小為橫軸，是否是惡性為縱軸(只有0,1)畫圖

-腫瘤可能由多個(gè)因素導(dǎo)致，引入年齡，大小為橫軸，年齡為縱軸，惡性以叉表示，良性以圓圈表示畫

圖，分析患腫瘤的區(qū)域

-還可引入更多屬性，畫在多維空間中

-無(wú)限維空間如何處理？將無(wú)限維映射到內(nèi)存的算法?

2、學(xué)習(xí)理論

學(xué)習(xí)理論即解釋學(xué)習(xí)型算法有效的原因（學(xué)習(xí)算法的理論根底）

尋找什么樣的算法能很好地近似不同的函數(shù)，訓(xùn)練集的規(guī)模是否適宜

3、無(wú)監(jiān)督學(xué)習(xí)

例：如上述腫瘤例子，圖中的點(diǎn)不知道正確答案，而是由你從中找去一定的結(jié)構(gòu)，即聚類。應(yīng)用于生

物基因工程，圖像處理，計(jì)算機(jī)視覺(jué)等領(lǐng)域

例：雞尾酒會(huì)問(wèn)題

在嘈雜的雞尾酒會(huì)中，將你感興趣的聲音提取出來(lái)

運(yùn)用兩個(gè)不同位置的麥克分開(kāi)來(lái)自不同位置的聲音

還能應(yīng)用于文本處理等領(lǐng)域

使用ICA算法，Matlab一行代碼即可解決

4、強(qiáng)化學(xué)習(xí)

通過(guò)決策產(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ù)（正反應(yīng)及負(fù)反應(yīng)），程序做出正確決策時(shí)給出正反應(yīng)，反之亦然。

程序不斷做出決策，在不斷嘗試獲得盡量多的正反應(yīng)時(shí)，逐漸學(xué)習(xí)并做出正確決策

關(guān)鍵在于要定義什么是正確決策，什么是錯(cuò)誤決策，再設(shè)計(jì)算法獲取盡量多的正反應(yīng)

第二課監(jiān)督學(xué)習(xí)應(yīng)用與梯度下降

本課內(nèi)容:

1、線性回歸

2、梯度下降

3、正規(guī)方程組

（復(fù)習(xí)）監(jiān)督學(xué)習(xí)：告訴算法每個(gè)樣木的正確答案，學(xué)習(xí)后的算法對(duì)新的愉入也能輸入正確的答案

1、線性回歸

例：Alvin汽車，先讓人開(kāi)車，Alvin攝像頭觀看（訓(xùn)練），而后實(shí)現(xiàn)自動(dòng)駕駛。

本質(zhì)是一個(gè)回歸問(wèn)題，汽車嘗試預(yù)測(cè)行駛方向。

例：上一節(jié)課的房屋大小與價(jià)格數(shù)據(jù)集

引入通用符號(hào)：

m=訓(xùn)練樣本數(shù)

x=輸入變量（特征）

丫=輸出變量（目標(biāo)變量）

（x,y）-一個(gè)樣本

2-第i個(gè)訓(xùn)練樣本

本例中：m：數(shù)據(jù)個(gè)數(shù)，x：房屋大小，y：價(jià)格

監(jiān)督學(xué)習(xí)過(guò)程：

"將訓(xùn)練樣本提供應(yīng)學(xué)習(xí)算法

2;算法生成一個(gè)輸出函數(shù)（一般用h表示，成為假設(shè)）

3）這個(gè)函數(shù)接收輸入，輸出結(jié)果。（本例中為，接收房屋面積，輸出房?jī)r(jià)）將x映射到y(tǒng).

如下列圖所示:

對(duì)假設(shè)進(jìn)行線性表示：Mx)=6。+

通常來(lái)說(shuō)，回歸問(wèn)題有多個(gè)輸入特征。如上例中，我們還房屋的臥室數(shù)，即有個(gè)第二個(gè)特征，即。表

示大小，心表示臥室數(shù)，那么可將假設(shè)寫成：h?⑺=9。+9閉+映2。為了將公式寫整

n

h(x)=^iXi=

潔，定義No=1，那么h可寫成：i=0

n=特征數(shù)目，仇參數(shù)。選擇8的目的，是使h(x)與y的平方差盡量小。又由于有m個(gè)訓(xùn)練樣本，需要

I巾

J⑻=512(3(小))一/)產(chǎn)

計(jì)算每個(gè)樣本的平方差，最后為了簡(jiǎn)化結(jié)果乘以1/2,即：i=l

我們要做的就是求：min(Jp))

求min(Jp))方法：梯度下降和正規(guī)方程組

2、梯度下降

梯度下降是一種搜索算法，根本思想：先給出參數(shù)向量一個(gè)初始值，比方0向量：不斷改變，使得

Jp)不斷縮小。改變的方法；梯度下降如下圖，水平坐標(biāo)軸表示，和叢,垂直坐標(biāo)表示J(8)

一開(kāi)始選擇。向量作為初始值，假設(shè)該三維圖為一個(gè)三維地表，。向量的點(diǎn)位于一座“山”上。梯度下降

的方法是，你環(huán)視一周，尋找下降最快的路徑，即為梯度的方向，每次下降一小步，再環(huán)視四周，繼

續(xù)下降，以此類推。結(jié)果到達(dá)一個(gè)局部最小值，如下列圖：

當(dāng)然，假設(shè)初始點(diǎn)不同，那么結(jié)果可能為另一個(gè)完全不同的局部最小值，如下:

Jeu

說(shuō)明梯度下降的結(jié)果

依賴于參數(shù)初始值。

梯度下降算法的數(shù)學(xué)表示:

.一為賦值運(yùn)算符:，即表示程序中的的賦值語(yǔ)句。

每一次將/減去仇對(duì),伊)求偏導(dǎo)的結(jié)果，即沿最陡峭的“山坡”下降

將偏導(dǎo)數(shù)展開(kāi)分析:

代入?式：%=%+°（嚴(yán)-九"⑴））

Q：學(xué)習(xí)速度，即決定你下山時(shí)每一步邁多大。設(shè)的過(guò)小，收斂時(shí)間長(zhǎng)，設(shè)的過(guò)大，可能會(huì)超過(guò)最小

值

(1)批梯度下降算法:

上述為處理一個(gè)訓(xùn)練樣本的公式，將其派生成包含m個(gè)訓(xùn)練樣本的算法，循環(huán)下式直至收斂:

復(fù)雜度分析:

對(duì)于每個(gè)*的每次迭代，即上式所示，時(shí)間為0(m)

每次迭代［走一步)需要計(jì)算n個(gè)特征的梯度值，復(fù)雜度為O(mn)

一般來(lái)說(shuō)，這種二次函數(shù)的的三維圖形為一個(gè)碗狀，有一個(gè)唯一的全局最小值。其等高線為一個(gè)

套一個(gè)的橢圓形，運(yùn)用梯度下降會(huì)快速收斂到圓心。

梯度下降性質(zhì)：接近收斂時(shí)，每次的步子會(huì)越來(lái)越小。其原因是每次減去。乘以梯度，但是梯度會(huì)越

來(lái)越小，所以步子會(huì)越來(lái)越小。

下列圖為使用梯度下降擬合的上例房屋大小和價(jià)格的曲線

檢測(cè)是否收斂的方法：

1:檢測(cè)兩次迭代*的改變量，假設(shè)不再變化，那么判定收斂

2）更常用的方法：檢驗(yàn)"6）,假設(shè)不再變化，判定收斂

抵梯度下降算法的優(yōu)點(diǎn)是能找到局部最優(yōu)解，但是假設(shè)訓(xùn)練樣本rn很大的話，其每次迭代都要“算所

有樣本的偏導(dǎo)數(shù)的和，時(shí)間過(guò)慢，于是采用下述另一種梯度下降方法。

（2）隨機(jī)梯度下降算法（增量梯度下降算法）：

每次計(jì)算可不需要再遍歷所有數(shù)據(jù)，而是只需計(jì)算樣本i即可。

即批梯度下降中，走一步為考慮m個(gè)樣本；隨機(jī)梯度下降中，走一步只考慮1個(gè)樣本。

每次迭代復(fù)雜度為0（n）0當(dāng)m人樣本用完時(shí)，繼續(xù)循環(huán)到第1個(gè)樣本。

上述使用了迭代的方法求最小值，實(shí)際上對(duì)于這類特定的最小二乘回歸問(wèn)題，或者普通最小二乘問(wèn)

題，存在其他方法給出最小值，接下來(lái)這種方法可以給出參數(shù)向量的解析表達(dá)式，如此一來(lái)就不需要

迭代求解了。

3、正規(guī)方程組

給定一個(gè)函數(shù)J,J是一個(gè)關(guān)于參數(shù)數(shù)組的函數(shù)，定義J的梯度關(guān)于的導(dǎo)數(shù)，它自己也是一個(gè)向量。向

量大小為n+1維（從0到n）,如下：

所以，梯度下降算法可寫成：

更普遍的講，對(duì)于一個(gè)函數(shù)f，f的功能是將一個(gè)m*n的矩陣映射到實(shí)數(shù)空間上，即：

/:Rmxn1R

假設(shè)輸入為m*n人小的矩陣A,定義f關(guān)于矩陣A的導(dǎo)數(shù)為:

導(dǎo)數(shù)本身也是個(gè)矩陣，包含了f關(guān)于A的每個(gè)元素的偏導(dǎo)數(shù)。

如果A是一個(gè)方陣，即n*n的矩陣，那么將A的跡定義為A的對(duì)角元素之和，即：

trA即為tr(A)的簡(jiǎn)化。

一些關(guān)于跡運(yùn)算符和導(dǎo)數(shù)的定理：

ljtrAB=trBA

2]trABC=trCAB=trBCA

r

3，V4trAB=B

^trA=trAT

5:假設(shè)^tra=a

6，%trABMC=CAB+CTABT

有了上述性質(zhì)，可以開(kāi)始推導(dǎo)了：

定義矩陣X,稱為設(shè)計(jì)矩陣，包含了訓(xùn)練集中所有輸入的矩陣：第i行為第i組輸入數(shù)據(jù)，即:

那么由于上(了⑴)=3v,所以可得：

又因?yàn)閷?duì)于向量Z,有z,z二￡izZ那么有：

由上述最后一個(gè)性質(zhì)可得：4rC"+

通過(guò)上述6個(gè)性質(zhì)，推導(dǎo)：

倒數(shù)第三行中，運(yùn)用最后一個(gè)性質(zhì)

將▽)(&)置為0,那么有：*X。=XTy

稱為正規(guī)方程組

可得:e=(XTX)-xXTy.

第三課欠擬合與過(guò)擬合概念

本次課程大綱：

1.局部加權(quán)回歸：線性回歸的變化版本

2、概率解釋：另一種可能的對(duì)于線性回歸的解釋

3、Logistic回歸:基于2的一個(gè)分類算法

4、感知器算法：對(duì)于3的延伸，簡(jiǎn)要講

復(fù)習(xí)：

a①，y嘰第i個(gè)訓(xùn)練樣本

令=L以參數(shù)向量e為條件，對(duì)于輸入X,輸出為：

n為掙征數(shù)量

定義本錢函數(shù)J,定義為：

m為訓(xùn)練樣本

通過(guò)正規(guī)方程組推導(dǎo)的結(jié)論：

1、過(guò)擬合與欠擬合

通常，你選擇交給學(xué)習(xí)算法處理的特征的方式對(duì)算法的工作過(guò)程有很大影響。

例：上次課的例子中，用xl表示房間大小。通過(guò)線性回歸，在橫軸為房間大小，縱軸為價(jià)格的圖中,

畫出擬合曲線?；貧w的曲線方程為：00+01X1

假設(shè)定義特征集合為：XI表示房子人小，X2表示房子人小的平方，使用相同的算法，擬合得到一個(gè)二

次函數(shù),在圖中即為一個(gè)拋物線，即：0O+0lXl+02Xl2

以此類推，假設(shè)訓(xùn)練集有7個(gè)數(shù)據(jù)，那么可擬合出最高6次的多項(xiàng)式，可以找到一條完美的曲線，該

曲線經(jīng)過(guò)每個(gè)數(shù)據(jù)點(diǎn)。但是這樣的模型又過(guò)于復(fù)雜，擬合結(jié)果僅僅反映了所給的特定數(shù)據(jù)的特質(zhì)，不

具有通過(guò)房屋大小來(lái)估計(jì)房?jī)r(jià)佗普遍性。而線性回歸的結(jié)果可能無(wú)法捕獲所有訓(xùn)練集的信息，

所以，時(shí)丁一個(gè)監(jiān)督學(xué)習(xí)模型來(lái)說(shuō)，過(guò)小的特征集合使得模型過(guò)于簡(jiǎn)單，過(guò)大的特征集合使得模型過(guò)

于復(fù)雜。

對(duì)于特征集過(guò)小的情況，稱之為欠擬合(underfitting)；

對(duì)「特征集過(guò)大的情況，稱之為過(guò)擬合(overfitting)

解決此類學(xué)習(xí)問(wèn)題的方法：

1)特征選擇算法：一類自動(dòng)化算法，在這類回歸問(wèn)題中選擇用到的特征

2)非參數(shù)學(xué)習(xí)算法：緩解對(duì)于選取特征的需求，引出局部加權(quán)回歸

參數(shù)學(xué)習(xí)算法(parametriclearningalgorithm)

定義：參數(shù)學(xué)習(xí)算法是?類有固定數(shù)目參數(shù)，以用來(lái)進(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)。換句話

說(shuō)，就是算法所需要的東西會(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）擬合出"使EV一"￡"）產(chǎn)最小

2）返回臚x

對(duì)于局部加權(quán)回歸，當(dāng)要處理x時(shí)：

1）檢查數(shù)據(jù)集合，并且只考慮位于x周圍的固定區(qū)域內(nèi)的數(shù)據(jù)點(diǎn)

2）對(duì)這個(gè)區(qū)域內(nèi)的點(diǎn)做線性回歸，擬合出一條直線

3）根據(jù)這條擬合直線對(duì)x的輸出，作為算法返回的結(jié)果

用數(shù)學(xué)語(yǔ)言描述即：

州合出8,使（嚴(yán)一八⑴%小

2）w為權(quán)值，有很多可能的選擇，比方：

■其意義在于，所選取的x（i）越接近x,相應(yīng)的w（i）越接近1；x（i）越遠(yuǎn)離x,w（i）越接近0。直觀的說(shuō)，就

是離得近的點(diǎn)權(quán)值大，離得遠(yuǎn)的點(diǎn)權(quán)值小。

-這個(gè)衰減函數(shù)比擬具有普遍意義，雖然它的曲線是鐘形的，但不是高斯分布。

-P被稱作波長(zhǎng)函數(shù)，它控制了權(quán)值隨距離下降的速率。它越小，鐘形越窄，w衰減的很快；它越大，

衰減的就越慢。

3）返回曠”

總結(jié)：對(duì)于局部加權(quán)I可歸，每進(jìn)行一次預(yù)測(cè)，都要重新擬合一條曲線。但如果沿著x釉對(duì)每個(gè)點(diǎn)都進(jìn)

行同樣的操作，你會(huì)得到對(duì)于這個(gè)數(shù)據(jù)集的局部加權(quán)回歸預(yù)測(cè)結(jié)果，追蹤到一條非線性曲線，

*局部加權(quán)回歸的問(wèn)題：

由于每次進(jìn)行預(yù)測(cè)都要根據(jù)訓(xùn)練集擬合曲線，假設(shè)訓(xùn)練集太大，每次進(jìn)行預(yù)測(cè)的用到的訓(xùn)練集就會(huì)變

得很大，有方法可以讓局部加權(quán)回歸對(duì)「大型數(shù)據(jù)集更高效，詳情參見(jiàn)AndrewMoore的關(guān)于KD-tree

的工作。

3、概率解釋

概率解釋所解決的問(wèn)題:

在線性回歸中，為什么選擇最小二乘作為計(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)表示

了一種我們沒(méi)有捕獲的特征，或者看成一種隨機(jī)的噪聲。

假設(shè)服從某個(gè)概率分布，如高斯分布(正態(tài)分布)：￡°)~N(0Q2),表示一個(gè)均值是0,方差是d

的高斯分布。

高斯分布的概率密度函數(shù)：

根據(jù).匕述兩式可得：

即，在給定了特征與參數(shù)之后，輸出是一個(gè)服從高斯分布的隨機(jī)變量，可描述為：

g⑴|n⑴;。?"(尹］⑴,。?)

*為什么選取高斯分布？

1)便于數(shù)學(xué)處理

2)對(duì)絕大?多數(shù)問(wèn)潁，如果便用了線性回歸模型，然后測(cè)曷誤差分布，通常會(huì)發(fā)現(xiàn)誤差是?高斯分布的。

3)中心極限定律：假設(shè)干獨(dú)立的隨機(jī)變量之和趨向于服從高斯分布。假設(shè)誤差有多個(gè)因素導(dǎo)致，這些

因素造成的效應(yīng)的總和接近服從高斯分布。

注意：e并不是一個(gè)隨機(jī)變量，而是一個(gè)嘗試估計(jì)的值，就是說(shuō)它本身是一個(gè)常量，只不過(guò)我們不知道

它的值，所以上式中用分號(hào)表示。分號(hào)應(yīng)讀作“以…作為參數(shù)”，上式讀作“給定x(i)以為參數(shù)的y(i)的概率

服從高斯分布”。

假設(shè)每個(gè)為HD(independentlyandidenticallydistributed)獨(dú)立同分布

即誤差項(xiàng)彼此之間是獨(dú)立的，并且他們服從均值和方差相同的高斯分布

⑵假設(shè)2：

設(shè)6的似然性為1即給定x（i）以為參數(shù)的y（i）的概率）：L（'）=心（優(yōu)、，協(xié)=P?X；8）

由于￡⑴是獨(dú)立同分布，所以上式可寫成所有分布的乘積：

⑶假設(shè)3：

極大似然估計(jì)：選取8使似然性L（e）最大化（數(shù)據(jù)出現(xiàn)的可能性盡可能大）

定義對(duì)數(shù)似然函數(shù)為（①：

上式兩個(gè)加項(xiàng)，前一項(xiàng)為常數(shù)。所以，使似然函數(shù)最大，就是使后一項(xiàng)最小，即：

這一項(xiàng)就是之前的J（e）,由此得證，即之前的最小二乘法計(jì)算參數(shù)，實(shí)際上是假設(shè)了誤差項(xiàng)滿足高斯分

布，且獨(dú)立同分布的情況，使似然最大化來(lái)計(jì)算參數(shù)。

注意：高斯分布的方差對(duì)最終結(jié)果沒(méi)有影響，由丁方差定為正數(shù)，所以無(wú)論取什么值，最后結(jié)果都

相同。這個(gè)性質(zhì)會(huì)在下節(jié)課講到。

4、Logistic回歸

這是我們要學(xué)習(xí)的第一個(gè)分類算法c之前的回歸問(wèn)題嘗試預(yù)測(cè)的變量y是連續(xù)變量，在這個(gè)分類算法

中，變量y是離散的，y只?。?,1｝兩個(gè)值。

一般這種離散一值分類問(wèn)題用線性回歸效果不好。比方x<=3,y=0；x>3,y=l,那么當(dāng)x>3的樣本占得

比例很大是，線性回歸的直線斜率就會(huì)越來(lái)越小，y=0.5時(shí)對(duì)應(yīng)的x判決點(diǎn)就會(huì)比3大，造成預(yù)測(cè)錯(cuò)

誤。

假設(shè)y取值｛0,1｝,首先改變假設(shè)的形式,使假設(shè)得到的值總在［。,段之間,即：h（x）q?！梗?/p>

所以，選取如下函數(shù)：

其中:

g函數(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?I引。)=(加⑺產(chǎn)(1一加⑺尸

可以簡(jiǎn)與成：

參數(shù)的似然性：

求對(duì)數(shù)似然性：

為了使似然性最大化，類似于線性回歸使用梯度卜.降的方法，求對(duì)數(shù)似然性對(duì)8的偏導(dǎo)，即：

因?yàn)榍笞畲笾担藭r(shí)為梯度上升。

偏導(dǎo)數(shù)展開(kāi)：

那么：

即類似，節(jié)課的隨機(jī)梯度JL升算法，形式，和線性回歸是相同的，只是符號(hào)相反，入式義)為logistic函

數(shù)，但實(shí)質(zhì)上和線性回歸是不同的學(xué)習(xí)算法。

5、感知器算法

在logistic方法中，g⑵會(huì)生成［0,1］之間的小數(shù)，但如何是g(z)只生成0或1?

所以，感知器算法將g⑵定義如下：

同樣令的(丁)=9(/工)，和logistic回歸的梯度上升算法類似，學(xué)習(xí)觀那么如下：

盡管看起來(lái)和之前的學(xué)習(xí)算法類似，但感知器算法是?種非常簡(jiǎn)便的學(xué)習(xí)算法，臨界值和輸出只能是0

或1,是比logistic更簡(jiǎn)單的算法。后續(xù)講到學(xué)習(xí)理論是，會(huì)將其作為根本的構(gòu)造步驟。

第四課牛頓方法

本次課程人綱:

1、牛頓方法：對(duì)Logistic模型進(jìn)行擬合

2、指數(shù)分布族

3、廣義線性模型（GLM）：聯(lián)系Logistic回歸和最小二乘模型

更習(xí)：Logistic回歸：分類算法

假設(shè)給定x以e為參數(shù)的y=l和*0的概率：

求對(duì)數(shù)似然性：

對(duì)其求偏導(dǎo)數(shù)，應(yīng)用梯度上升方法，求得：

本次課程介紹的牛頓方法是一種比梯度上升快很多的方法，用于擬合Logistic回歸

1、牛頓方法

假設(shè)有函數(shù)f（e）,需要找使f⑼=0的?

步驟：

工）給出一個(gè)?的初始值

2）對(duì),⑼求導(dǎo)，求導(dǎo)數(shù)為。時(shí)8的值（就是求f⑼切線與x軸交點(diǎn)）

3）重復(fù)步驟2

因?yàn)樵擖c(diǎn)的導(dǎo)數(shù)值即為切線斜率，而斜率=該點(diǎn)y軸的值，該點(diǎn)x軸的變化值，所以。每次的變化值:

*使用這個(gè)方法需要f滿足一定條件，適用于Logistic回歸和廣義線性模型

*一般初始化為0

應(yīng)用于Logistic回歸：

求對(duì)數(shù)似然的最大值，即求.伊）為o時(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ù)字，一般化的公式為：

Vo"。）是目標(biāo)函數(shù)的梯度，H為Hessian矩陣，規(guī)模是n*n,n為特征的數(shù)量，它的每個(gè)元素表示一

個(gè)二階導(dǎo)數(shù)：

上述公式的意義就是，用一個(gè)一階導(dǎo)數(shù)的向量乘以一個(gè)二階導(dǎo)數(shù)矩陣的逆

優(yōu)點(diǎn)：假設(shè)特征數(shù)和樣本數(shù)合理，牛頓方法的迭代次數(shù)比梯度上升要少得多

缺點(diǎn)：每次迭代都要重新計(jì)算Hessian矩陣，如果特征很多，那么H矩陣計(jì)算代價(jià)很大

2、指數(shù)分布族

回憶學(xué)過(guò)的兩種算法：

對(duì)于P（y|x；e）：

假設(shè)V屬于實(shí)數(shù)，滿足高斯分布，得到基于最小二乘法的線性回歸；

假設(shè)y取{0,1},滿足伯努利分布，得到Logistic回歸。

問(wèn)題：如LogisticI可歸中，為何選擇sigmoid函數(shù)？sigmoid函數(shù)是最自然的默認(rèn)選擇。

接下來(lái)，會(huì)以這兩個(gè)算法為例，說(shuō)明它們都是廣義線性模型的特例。

考慮上述兩個(gè)分布，伯努利分布和高斯分布：

1）伯努利分布

設(shè)有一組只能取0或1的數(shù)據(jù)，用伯努利隨機(jī)變量對(duì)其建模:

對(duì)耳夕~Bernoulli(0),那么p(y=i；(p)=(p,改變參數(shù)9，y=i這一事件就會(huì)有不同概率，會(huì)得

到一類概率分布(而非固定的)。

2)高斯分布

y\x\0~Af(/i,a2)改變參數(shù)內(nèi)也會(huì)得到不同的高斯分布，印一類概率分布。

上述這些分布都是一類分布的特例，這類分布稱為指數(shù)分布族。

指數(shù)分布族的定義：

假設(shè)一類概率分布可以寫成如下形式，那么它就屬于指數(shù)分布族：

n?自然參數(shù)，通常是一個(gè)實(shí)數(shù)

T(y)-允分統(tǒng)計(jì)量，通常，T(y)=y,實(shí)際上是一個(gè)概率分布的充分統(tǒng)計(jì)量I統(tǒng)計(jì)學(xué)知識(shí))

對(duì)于給定的a,b,T三個(gè)函數(shù)，上式定義了一個(gè)以n為參數(shù)的概率分布集合，即改變Q可以得到不同

的概率分布。

證明伯努利分布是指數(shù)分布族：

可知：

由上式可見(jiàn),r|=log(W(l-(p)),可解出:(p=l/(l+exp(-r))),發(fā)現(xiàn)得到logistic函數(shù)(之后討論其原因)，

那么：

證明高斯分布是指數(shù)分布族：

y\x\0~Af(/i,cr2)設(shè)方差為11方差并不影響結(jié)果，僅僅是變量y的比例因子)

這種情況下高斯密度函數(shù)為：

可得：

*指數(shù)分布族包括：

高斯分布(正態(tài)分布)，多元正態(tài)分布；

伯努利分布(01問(wèn)題建模)，多項(xiàng)式分布(對(duì)k個(gè)結(jié)果的事件建模)；

泊松分布（對(duì)計(jì)數(shù)過(guò)程建模）；

伽馬分布，指數(shù)分布（對(duì)實(shí)數(shù)的間隔問(wèn)題建模）；

B分布，Dirichlet分布（對(duì)小數(shù)建模）；

Wishart分布（協(xié)方差矩陣的分布）…

3、廣義線性模型GLM

選定了一個(gè)指數(shù)分布族后，怎樣來(lái)推導(dǎo)出一個(gè)GLM呢？

假設(shè)：

{1]y\x\OExponentialFamily（77）,即假設(shè)試圖預(yù)測(cè)的變量丫在給定x,以e作為參數(shù)的

條件概率，屬于以n作為自然參數(shù)的指數(shù)分布族

例：假設(shè)要統(tǒng)計(jì)網(wǎng)站點(diǎn)擊量y,用泊松分布建模

⑵給定X,目標(biāo)是求出以x為條件的T（y）的期望E[T（y）|x],即讓學(xué)習(xí)算法輸出h（x）=E[T（y）岡

（3）n=°工,即自然參數(shù)和輸入特征X之間線性相關(guān)，關(guān)系由e決定。僅當(dāng)n是實(shí)數(shù)時(shí)才有意

義。假設(shè)n是一個(gè)向量，3=修工

推導(dǎo)伯努利分布的GLM：

V|耳。~ExponentialFamily（力，伯努利分布屬于指數(shù)分布族

對(duì)給定的X,6,學(xué)習(xí)算法進(jìn)行一次預(yù)測(cè)的輸出：

得到logistic回歸算法。

正那么響應(yīng)函數(shù)：g（n）=E[y；n].將自然參數(shù)n和y的期望聯(lián)系起來(lái)

正那么關(guān)聯(lián)函數(shù)：屋

推導(dǎo)多項(xiàng)式分布的GLM：

多項(xiàng)式分布是在k個(gè)可能取值上的分布，即y￡{l，…,k},如將收到的郵件分成k類，診斷某病人為k種

病中的一種等問(wèn)題。

(1)將多項(xiàng)式分布寫成指數(shù)分布族的形式：

設(shè)多項(xiàng)式分布的參數(shù)：弧，…，弧,且￡上15=I(pi表示第i個(gè)取值的概率分布，最后一個(gè)

參數(shù)可以由前k-1個(gè)推導(dǎo)出，所以只將前k-1個(gè)01，???，°及-1視為參數(shù)。

多項(xiàng)式分布是少數(shù)幾個(gè)T(丫)!=丫的分布，T(l)~T(k)都定義成一個(gè)k-1維的列向量，表示為：

這樣定義T(y)是為了將多項(xiàng)式分布寫成指數(shù)分布族形式。

*定義符號(hào)：指示函數(shù)，1{.}

l{True)=lzl{Fdlse)=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è)取值的概率分布)，可推出：

可得：

證明多項(xiàng)式分布式指數(shù)分布族。

再用n表示(P：

(2)根據(jù)上述假設(shè)(3)中自然參數(shù)和輸入x的線性關(guān)系，可求得：

(3)根據(jù)上述假設(shè)(2)中的輸出h(x)=E[T(y)|x],可求得:

稱這種回歸算法為softmax回歸，是logistic回歸的推廣。

Softmax回歸的訓(xùn)練方法和logistic相似，通過(guò)極人似然估計(jì)找到參數(shù)6,其對(duì)數(shù)似然性為：

771

￡（。）=

i=l

T（<）

m卜/X'I?'*'}

=f>gfi

1=11=1\Q2^kj=“ieJ/

再通過(guò)梯度上升或牛頓方法找對(duì)數(shù)似然性的最大值，即可求出參數(shù)e.

第五課生成學(xué)習(xí)算法

本次課程大綱：

1、生成學(xué)習(xí)算法

2、高斯判別分析（GDA,GaussianDiscriminantAnalysis）

-高斯分布（簡(jiǎn)要）

-比照生成學(xué)習(xí)算法&判別學(xué)習(xí)算法（簡(jiǎn)要）

3、樸素貝葉斯

4、Laplace平滑

復(fù)習(xí)：

分類算法：給出一個(gè)訓(xùn)練集，假設(shè)使用logistic回歸算法，其工作方式是觀察這組數(shù)據(jù)，嘗試找到一條

直線將圖中不同的類分開(kāi)，如卜列圖。

之前講的都是判別學(xué)習(xí)算法，本課介紹一種不同的算法：生成學(xué)習(xí)算法。

1、生成學(xué)習(xí)算法

例：對(duì)惡性腫瘤和良性腫瘤的分類

除了尋找一個(gè)將兩類數(shù)據(jù)區(qū)分的直線外，還可以用如下方法：

1）遍歷訓(xùn)練集，找到所有惡性腫瘤樣本，直接對(duì)惡性腫瘤的特征建模；同理，對(duì)良性腫瘤建模。

2)對(duì)一個(gè)新的樣本分類時(shí)，即有一個(gè)新的病人時(shí)，要判斷其是惡性還是良性，用該樣本分別匹配惡性

腫瘤模型和良性腫瘤模型，看哪個(gè)模型匹配的更好，預(yù)測(cè)屬于惡性還是良性。

這種方法就是生成學(xué)習(xí)算法。

兩種學(xué)習(xí)算法的定義：

1)判別學(xué)習(xí)算法：

■直接學(xué)習(xí)p(y|x),即給定輸入特征，輸出所屬的類

?或?qū)W習(xí)得到一個(gè)假設(shè)h0(x),直接輸出0或1

2)生成學(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的概率分布

遂行建模

-對(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、高斯判別分析GDA

GDA是一種生成學(xué)習(xí)算法。

GDA的假設(shè)條件：

1)假設(shè)輸入特征并且是連續(xù)值。

2)假設(shè)p(x|y)滿足高斯分布

*高斯分布根底知識(shí)：

設(shè)隨機(jī)變量z滿足多元高斯分布，z~N(p>),均值向量為p,協(xié)方差矩陣為

其概率密度函數(shù)為:

多元高斯分布為一元高斯分布的推廣，也是鐘形曲線，Z是一個(gè)高維向量。

多元高斯分布注意兩個(gè)參數(shù)即可：

-均值向量|J

-協(xié)'方差矩陣2=E[(Z-E[Z])(Z-E[Z])T|=E[(X-#(X-|J)T]

多元高斯分布圖：

左圖：p=0,g=|(單位矩陣)

中圖：|J=0,Z=0.6l,圖形變陡峭

右圖：p=0,g=2l,圖形變扁平

三圖中p=o,g如下:

1010.510.8-

01；匕=0.510.81

」可見(jiàn)增加矩陣對(duì)角元素的值,

即變量間增加相關(guān)性，高斯曲面會(huì)沿zl=z21兩個(gè)水平軸)方向趨于扁平。其水平面投影圖如下：

即增加下對(duì)角線的元素，圖形會(huì)沿45。角，偏轉(zhuǎn)成一個(gè)橢圓形狀。

假設(shè)E對(duì)角線元素為負(fù)，圖形如F：

Z分別為：

不同p的圖形如下：

P分別為：

□決定分布曲線中心的位置。

GDA擬合：

給出訓(xùn)練樣本如下列圖所示：

?觀察正樣本(圖中的x)，擬合正樣本的高斯分布，如圖中左下方的圓，表示p(x|y=l)

-觀察負(fù)樣本(圖中的圈)，擬合負(fù)樣本的高斯分布，如圖中右上方的圓，表示p(x|y=O)

-通過(guò)這兩個(gè)高斯分布的密度函數(shù)，定義出兩個(gè)類別的分隔器，即圖中的五線

-這條分隔器直線比之前的logistc擬合的直線要復(fù)雜

GDA模型：

寫出其概率分布：

參數(shù)包括cp，pO,pl,Z，對(duì)數(shù)似然性為：

由于第一個(gè)等式為xy的聯(lián)合概率，將這個(gè)模型命名為聯(lián)合似然性(Jointlikelihood)o

*比照l(shuí)ogistic回歸中的對(duì)數(shù)似然性：

由于計(jì)算的是y在x條件下的概率，將此模型命名為條件似然性：conditionallikelihood)

通過(guò)對(duì)上面對(duì)數(shù)似然性求極大似然估計(jì)，參數(shù)的結(jié)果為：

(P：訓(xùn)練樣本中標(biāo)簽為1的樣本所占的比例

M0：分母為標(biāo)簽為。的樣本數(shù)，分子是對(duì)標(biāo)簽為。的樣本的x(i)求和，結(jié)合起來(lái)就是對(duì)對(duì)標(biāo)簽為。的樣

本的x(i)求均值，與高斯分布參數(shù)|J為均值的意義相符

pl：與M0同理，標(biāo)簽改為1

GDA預(yù)測(cè)：

預(yù)測(cè)結(jié)果應(yīng)該是給定x的情況下最可能的y,等式左邊的運(yùn)算符argmax表示計(jì)算p(y|x)最大時(shí)的y

值，預(yù)測(cè)公式如下：

因?yàn)閜(x)獨(dú)立于y,所以可以忽略p(x)。

*如果P(y)為均勻分布，即每種類型的概率都相同，那么也可以忽略p(y),要求的就是使p(x|y)最大的

那個(gè)y。不過(guò)這種情況并不常見(jiàn)，

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)o

如選X軸靠左的點(diǎn)，那么它屬于1的概率幾乎為0,p(y=l|x)=0,兩條鐘形曲線交點(diǎn)處，屬于?；?的

概率相同，p(y=l|x)=0.5,x軸靠右的點(diǎn)，輸出1的概率兒乎為1,p(y=l|x)=lo最終發(fā)現(xiàn)，得到的曲線

和sigmoid函數(shù)曲線很相似。

簡(jiǎn)單來(lái)講,就是當(dāng)使用GDA模型時(shí)，p(x|y)屬于高斯分布,計(jì)算米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(Al),x|y=0~Poisson(AO)=>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(q0)=>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è)，所

以，假設(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為垃

圾郵件，。為非垃圾郵件。

首先，要將郵件文本表示為一個(gè)輸入向量x,設(shè)一個(gè)含有n個(gè)詞的字典，那么向量x的第i個(gè)元素{0,1}

表示字典中的第i個(gè)詞是否出現(xiàn)在郵件中，x例如如下：

要對(duì)p(x|y)建模,x是一個(gè)n維的。1}向量，假設(shè)n=50000,那么x有2A50000種可能的值,一種方法

是用多項(xiàng)式分布進(jìn)行建模(伯努利分布對(duì)01建模，多項(xiàng)式分布對(duì)k個(gè)結(jié)果建模)，這樣就需要

2A50000-1個(gè)參數(shù)，可見(jiàn)參數(shù)過(guò)多，下面介紹樸素貝葉斯的方法。

假設(shè)xi在給定y的時(shí)候是條件獨(dú)立的，那么x在給定y下的概率可簡(jiǎn)化為：

這個(gè)假設(shè)直觀理解為，一封郵件是不是垃圾郵件(y)，以及一些詞是否出現(xiàn)在郵件中，這些并不會(huì)幫助

你預(yù)測(cè)其他的詞是否出現(xiàn)在郵件中。雖然這個(gè)假設(shè)不是完全正確的，但是樸素貝葉斯依然應(yīng)用于對(duì)郵

件進(jìn)行分類，對(duì)網(wǎng)頁(yè)進(jìn)行分類等用途。

*對(duì)于樸素貝葉斯，我的理解為：通過(guò)指定一些垃圾郵件的關(guān)健詞來(lái)計(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ù)包括：

<t>i|y=l=p(xi=l|y=l)

0i|y=O=p(xi=l|y=0)

①y=p(y=l)

聯(lián)合似然性：

求得參數(shù)結(jié)果:

<ti|y=i的分子為標(biāo)記為1的郵仁中出現(xiàn)詞j的郵件數(shù)目和，分母為垃圾郵件數(shù)，總體意義就是訓(xùn)練集

中出現(xiàn)詞j的垃圾郵件在垃圾郵件中的比例。

Qi|y=O就是出現(xiàn)詞j的非垃圾郵件在非垃圾郵件中的比例。

，丫就是垃圾郵件在所有郵件中的比例。

求出上述參數(shù),就知道了p(x|y)和p(y),用伯努利分布對(duì)p(y)建模,用上式中p(xi|y)的乘積對(duì)p(x|y)建

模，通過(guò)貝葉斯公式就可求得p(y|x)

*實(shí)際操作中，例如將最近兩個(gè)月的郵件都標(biāo)記上“垃圾”或“非垃圾”，然后得到(x(l),y(l))...(x(E,y(m)),

x(i)為詞向量，標(biāo)記出現(xiàn)在第i個(gè)郵件中的詞，y(i)為第i個(gè)郵件是否是垃圾郵件。用郵件中的所有出現(xiàn)

的詞構(gòu)造字典，或者選擇出現(xiàn)次數(shù)k次以上的詞構(gòu)造字典。

樸素貝葉斯的問(wèn)題：

設(shè)有一封新郵件中出現(xiàn)一個(gè)字典沒(méi)有的新詞，設(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=lIx)=p(x|y=l)p(y=l)/(p(x|y=l)p(y=l)+p(x|y=0)p(y=0))

由于p(x|y=l)=p(x|y=0)=0(p(x300001y=l)=p(x300001y=0)=0,那么乘積為0),那么p(y=l|x)=0/0,那么

結(jié)果是未定義的。

其問(wèn)題在于，統(tǒng)計(jì)上認(rèn)為p(x30000|y)=0是不合理的。即在過(guò)去兩個(gè)月郵件里未出現(xiàn)過(guò)這個(gè)詞，就認(rèn)為

其出現(xiàn)概率為0,并不合理。

概括來(lái)講，即之前沒(méi)有見(jiàn)過(guò)的事件，就認(rèn)為這些事件不會(huì)發(fā)生，是不合理的。通過(guò)Laplace立滑解決這

個(gè)問(wèn)題。

4、Laplace平滑

根據(jù)極大似然估計(jì),即為的概率是樣本中的數(shù)目在所有樣本中的

p(y=i)=rrs/(ro^s+rrs),y11

比例。Laplace平滑就是將分子分母的每一項(xiàng)都加1,,即：

p(y=l)=(#"l"s+l)/(ro,,s+l+鏟Ts+1)

例：給出一支球隊(duì)5場(chǎng)比賽的結(jié)果作為樣本，5場(chǎng)比賽都輸了，記為0,那么要預(yù)測(cè)第六場(chǎng)比賽的勝

率，按照樸素貝葉斯為：即樣本中沒(méi)有勝場(chǎng)，那么勝率為顯然這是不合理的。

p(y=l)=0/(5+0)=0,0,

按照Laplace平滑處理,p(y=l)=0+1/(5+1+0+1)=1/7,并不為0,且隨著負(fù)場(chǎng)次的增加，p(y=l)會(huì)一直

減小，但不會(huì)為0。

更一般的，假設(shè)y取k中可能的值，比方嘗試估計(jì)多項(xiàng)式分布的參數(shù)，得到下式:

即值為j的樣本所占比例，對(duì)其用Laplace平滑如下式：

對(duì)于樸素貝葉斯，得到的結(jié)果為：

在分子上加1,分母上加2,解決了0概率的問(wèn)題。

第六課樸素貝葉斯

本次課程大綱：

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è)輸入向量x

1)XiG{0,1},表示字典中的笫i個(gè)詞是否出現(xiàn)在郵件中

2)x長(zhǎng)度為n,n為字典的詞數(shù)

3)該模型稱為多元伯努利事件模型

假設(shè)xi在給定y的時(shí)候是條件獨(dú)立的，那么x在給定y下的概率可簡(jiǎn)化為：

根據(jù)樸素貝葉斯公式，求p(y|x)最大時(shí)的y：

算法變化版本:

1)讓xi取多個(gè)值,xi￡{l,2,...,k},類似上式有:p(x|y)=nP(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=4

2)如上例處理郵件〔文本)中，x向量記錄每個(gè)詞出現(xiàn)的次數(shù)[而不是是否出現(xiàn))

多項(xiàng)式事件模型

接上例，給出一封郵件，將它表示成特征向量：(1H???,斕)

,ni表示郵件中詞的數(shù)量，xj是個(gè)到詞典的索引，表示該詞在詞典的位置。

如郵件中有300個(gè)詞，那么特征向量x(i)長(zhǎng)度為300,假設(shè)詞典有50000個(gè)詞，每個(gè)元素xj的取值范圍

為{1,2,...,50000}

?

p(xy)=(J-]p(%ily))p(y)

那么生成模型的聯(lián)合概率p(xy)為：

n為郵件長(zhǎng)度

上式理解：郵件內(nèi)容滿足一些概率分布，有一些隨機(jī)分布在生成這些郵件。過(guò)程為：首先確定y,即是

否為垃圾郵件，決定一個(gè)人是否向你發(fā)送垃圾郵件后，遍歷郵件的300個(gè)詞，按照某種概率分布生成

一些詞，基于他們是否向你發(fā)送垃圾郵件

模型參數(shù)：

表示某人決定向你發(fā)送垃圾郵件(y=l)時(shí)，選擇詞k的概率，類似有：

給出訓(xùn)練集后，求極大似然估計(jì)：

得到：

上面第一個(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ù)目)：

事實(shí)上，多項(xiàng)式事件模型比之前的模型要好，可能是因?yàn)榭紤]了詞出現(xiàn)的次數(shù)這個(gè)因素工但此問(wèn)題仍

存在爭(zhēng)論。

非線性分類算法

例：logistic回歸中，假設(shè)值小于0.5預(yù)測(cè)0,大廣0.5預(yù)測(cè)1。即給定一個(gè)訓(xùn)練集，logistic回歸會(huì)找到

一條直線〔牛頓方法或梯度卜.降J,將正負(fù)樣本合埋分開(kāi)。但右時(shí)數(shù)據(jù)不能被一條直線分開(kāi)，需要一

種算法，學(xué)習(xí)非線性的分界線。

上一講的推論：

x|y=l**ExpFamily(ql),x|y=0~ExpFamily(r)0)=>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等特征作為輸入，卜6(x)作為輸出，這是一個(gè)sigmoid函數(shù)。為了找到非線性的界限，需要

找到一種方式，表示出能夠輸出非線性分界限的假設(shè)。

將之前畫的小單元拼在一起，得到神經(jīng)網(wǎng)絡(luò)。特征輸入到假設(shè)干個(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ù)：

a2,a3同理。g為sigmoid函數(shù)。最終的輸出值為：

其中，a向量由al,a2,a3組成。

一種學(xué)習(xí)模型參數(shù)的方法是，利用本錢函數(shù)J(5,使用梯度下降使J(5最小。即用梯度下降使得神經(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ì)于分類的直觀理解：

1)考慮logistic回歸，計(jì)算0Tx：

輸出1<=>eTx>=o：輸出o<=>eTx<o

如果的<>>0,相當(dāng)確定的預(yù)測(cè)y=l；如果UxccO,相當(dāng)確定的預(yù)測(cè)y=0

對(duì)于所有的i,如果y=l,。T則>>0,如果y=0,。丁叫<<0,那么我們認(rèn)為分類器是良好的。即如果我們

根據(jù)訓(xùn)練集找到了參數(shù)，我們的學(xué)習(xí)算法不僅需要保證分類結(jié)果正確，更要進(jìn)一步保證分類結(jié)果確實(shí)

定性。

2)假設(shè)訓(xùn)練集是線性可分割的，即一定有一條直線可以將訓(xùn)練集分開(kāi)。那么直觀來(lái)看，我們一定會(huì)選

擇和正負(fù)樣本都有一定距離的直線。后面講到分類器的幾何間隔時(shí)，再正式討論。

支撐向量機(jī)中改動(dòng)的符號(hào)：

輸出y￡{-l,+l}

h輸出的假設(shè)值也改為{-1,+1}

g(z)={1，如果z>=0;-1,如果z<0}

之前在使用式:h0(x)=g(6Tx)0?j,假設(shè)xO=l且x為n+1維向量,現(xiàn)在忽略這兩個(gè)假設(shè)，表示為:

T

hw.b(x)=g(wx+b),這里的b相當(dāng)「原來(lái)的00,w相當(dāng)于原來(lái)6除去90剩余局部，長(zhǎng)度為n維。將截

距b單提出來(lái)，方便引出支撐向最機(jī)。

函數(shù)間隔：

一個(gè)超平面(w,b)和某個(gè)特定訓(xùn)練樣本(x(i),y(i))對(duì)應(yīng)的函數(shù)間隔定義為：

參數(shù)(w,b)定義了一個(gè)分類器，例如定義了一個(gè)線性分界線。

如果y(i)=l,為了獲得較大的函數(shù)間隔，需要令wTx(i)+b>>0；

如果y(i)=-l,為了獲得較大的函數(shù)間隔，需要令wTx⑴+b<<0

如果y(i)(w，x(i)+b)>0,意味著分類結(jié)果正確

一個(gè)超平面(w,b)和整個(gè)訓(xùn)練集的函數(shù)間隔定義為：

即相對(duì)于整個(gè)訓(xùn)練集的函數(shù)間限定義為所有相對(duì)于樣本的函數(shù)間隔的最壞情形(上述講到，分界線距

離樣本越遠(yuǎn)效果越好)。

幾何間隔：

幾何距離定義為：一個(gè)訓(xùn)練樣本對(duì)應(yīng)的點(diǎn)到由超平面確定的分隔線的距離。如下列圖A到分隔線的距

離AB就是幾何距離。

和分隔線垂直的單位向量表示為：w/||w||,AB這段距離表示為Y(i)，Y上有小三角表示函數(shù)間隔，沒(méi)

有表示幾何間隔。假設(shè)A點(diǎn)表示x(i),那么點(diǎn)B表示為：

由于點(diǎn)B在分隔線上，它應(yīng)該還滿足：

可以解出：

上式說(shuō)明，對(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é)論：如果||w||=l,函數(shù)間隔等于幾何間隔。更一般的，兒何間隔等于函數(shù)間隔除以||w||。

一個(gè)超平面(w,b)和整個(gè)訓(xùn)練集的幾何間隔定義為：

和函數(shù)間隔類似，取樣本中最小的幾何間隔。最大間隔分類器可以看做是支撐向量機(jī)的前身，是一種

學(xué)習(xí)算法，選擇特定的w和b,使幾何間隔最大化。最大分類間隔是下述這樣的優(yōu)化問(wèn)題：

即選擇Y，w,b是丫最大，同時(shí)滿足條件：所選取的最大幾何間隔必須保證每個(gè)樣本的結(jié)合間隔至少

為Y。

最大間隔分類器的效果和logistic回歸結(jié)果差不多好，深入研究這個(gè)分分類器，可以用一種更巧妙的方

法讓其支持無(wú)限維的特征空間，得到有效的非線性分類器

第七課最優(yōu)間隔分類器問(wèn)題

本次課程大綱：

1、最優(yōu)間隔分類器

2、原始優(yōu)化問(wèn)題&對(duì)偶優(yōu)化問(wèn)題(KKT條件)

3、SVM對(duì)偶問(wèn)題

4、核方法(下一講)

復(fù)習(xí)：

支撐向景機(jī)中改動(dòng)的符號(hào)：

輸出y￡{?l,+l}

h輸出的假設(shè)值也改為{-L+1}

g(z)={1,如果z>=0;-1,如果z<0}

T

hw.b(x)=g(wx+b),這里的b相當(dāng)于原來(lái)的80,w相當(dāng)于原來(lái)8除去80剩余局部，長(zhǎng)度為n維。將截

距b單提出來(lái)，方便引出支撐向量機(jī)。

函數(shù)間隔：

一個(gè)超平面(w,b)和某個(gè)特定訓(xùn)練樣本(x(i),y(i))對(duì)應(yīng)的函數(shù)間隔定義為：

參數(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é)果正確

一個(gè)超平面(w,b)和整個(gè)訓(xùn)練集的函數(shù)間隔定義為：

即相對(duì)于整個(gè)訓(xùn)練集的函數(shù)間限定義為所有相對(duì)于樣本的函數(shù)間隔的最壞情形(上述講到，分界線距

離樣本越遠(yuǎn)效果越好)。

幾何間隔：

幾何間隔定義為：

這個(gè)定義和函數(shù)間隔很相似，不同點(diǎn)是對(duì)向量w進(jìn)行了標(biāo)準(zhǔn)化。同樣，希望幾何間隔也是越大越好。

結(jié)論：如果||w||二l,函數(shù)間隔等于幾何間隔。更一般的，幾何間隔等于函數(shù)間隔除以||w||。

一個(gè)超平面(w,b)和整個(gè)訓(xùn)練集的兒何間隔定義為：

和函數(shù)間隔類似，取樣本中最小的幾何間隔。性質(zhì)：可以任意比例縮放W和b,因?yàn)槿我饪s放W和b

都不會(huì)改變超平面wTx+b=O的位置。這一性質(zhì)在后續(xù)討論中帶來(lái)很大便利。

1、最優(yōu)間隔分類器

最優(yōu)間隔分類器可以看做是支撐向量機(jī)的前身，是一種學(xué)習(xí)算法，選擇特定的W和b,使幾何間隔最

大化。最優(yōu)分類間隔是下述這樣的優(yōu)化問(wèn)題：

即選擇Y，w,b使Y最大，同時(shí)滿足條件：所選取的最大幾何間隔必須保證每個(gè)樣本的幾何間隔至少

為Y。即，找到一個(gè)超平面，在將正負(fù)樣本分開(kāi)的同時(shí)，使超平面到正負(fù)樣本間的距離盡可能大。

由于w和b可隨意縮放，約束條件||w||二l,使得函數(shù)間隔等于幾何間隔。但是這個(gè)約束本身是一個(gè)

非常糟糕的非凸性約束。要求解的參數(shù)w在一個(gè)球體外表，如果想得到一個(gè)凸優(yōu)化問(wèn)題，必須保證如

梯度下降算法這種局部最優(yōu)值搜索算法不會(huì)找到局部最優(yōu)值，而非凸性約束不能滿足這個(gè)條件，所以

需要改變優(yōu)化問(wèn)題。

為了解決上述問(wèn)題，提出下面的最優(yōu)化問(wèn)題：

即將函數(shù)間隔除以||w||的值最大化，而這個(gè)值其實(shí)就是幾何間隔，只是上一個(gè)