機器學習——斯坦福大學講義

第一課機器學習的動機與應用

工具：需正版:Matlab,免費:Octave

定義(ArthurSamuel1959)：

在不直接針對問題進行編程的情況下，賦予計算機學習能力的研究領域。

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

想)

定義2(TomMitchell1998)：

一個合埋的學習問題應該這樣定義：對一個計算機程序來說，給它一個任務T和一個性能測量方法P,

如果在經驗E的影響下，P對T的測量結果得到了改良，那么就說改程序從E中學習了。

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

課程的四大局部：

1、有監督學習

(1)回歸問題

例：收集某地房屋價格統計、房屋大小和價格對應情況：

畫出一條擬合曲線，就可以通過房屋大小估計價格。

-有監督學習即給出一個數據集(正確的房屋價格及對應大小)

-此例為I可歸問題。回歸意味著需要預測的變量是連續的

(2)分類問題

分類問題中需要處理的變量是離散的

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

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

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

圖，分析患腫瘤的區域

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

-無限維空間如何處理？將無限維映射到內存的算法?

2、學習理論

學習理論即解釋學習型算法有效的原因（學習算法的理論根底）

尋找什么樣的算法能很好地近似不同的函數，訓練集的規模是否適宜

3、無監督學習

例：如上述腫瘤例子，圖中的點不知道正確答案，而是由你從中找去一定的結構，即聚類。應用于生

物基因工程，圖像處理，計算機視覺等領域

例：雞尾酒會問題

在嘈雜的雞尾酒會中，將你感興趣的聲音提取出來

運用兩個不同位置的麥克分開來自不同位置的聲音

還能應用于文本處理等領域

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

4、強化學習

通過決策產生的結論或對或錯，故產生一系列的決策。

例：對一個模型飛機編寫一個起飛程序，飛機在程序做了一連串錯誤決策是才會墜毀，只要做出連續

的整體還不錯的決策，即可保持飛機正常飛行

強化學習的根本概念：回報函數（正反應及負反應），程序做出正確決策時給出正反應，反之亦然。

程序不斷做出決策，在不斷嘗試獲得盡量多的正反應時，逐漸學習并做出正確決策

關鍵在于要定義什么是正確決策，什么是錯誤決策，再設計算法獲取盡量多的正反應

第二課監督學習應用與梯度下降

本課內容:

1、線性回歸

2、梯度下降

3、正規方程組

（復習）監督學習：告訴算法每個樣木的正確答案，學習后的算法對新的愉入也能輸入正確的答案

1、線性回歸

例：Alvin汽車，先讓人開車，Alvin攝像頭觀看（訓練），而后實現自動駕駛。

本質是一個回歸問題，汽車嘗試預測行駛方向。

例：上一節課的房屋大小與價格數據集

引入通用符號：

m=訓練樣本數

x=輸入變量（特征）

丫=輸出變量（目標變量）

（x,y）-一個樣本

2-第i個訓練樣本

本例中：m：數據個數，x：房屋大小，y：價格

監督學習過程：

"將訓練樣本提供應學習算法

2;算法生成一個輸出函數（一般用h表示，成為假設）

3）這個函數接收輸入，輸出結果。（本例中為，接收房屋面積，輸出房價）將x映射到y.

如下列圖所示:

對假設進行線性表示：Mx)=6。+

通常來說，回歸問題有多個輸入特征。如上例中，我們還房屋的臥室數，即有個第二個特征，即。表

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

n

h(x)=^iXi=

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

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

I巾

J⑻=512(3(小))一/)產

計算每個樣本的平方差，最后為了簡化結果乘以1/2,即：i=l

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

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

2、梯度下降

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

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

一開始選擇。向量作為初始值，假設該三維圖為一個三維地表，。向量的點位于一座“山”上。梯度下降

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

續下降，以此類推。結果到達一個局部最小值，如下列圖：

當然，假設初始點不同，那么結果可能為另一個完全不同的局部最小值，如下:

Jeu

說明梯度下降的結果

依賴于參數初始值。

梯度下降算法的數學表示:

.一為賦值運算符:，即表示程序中的的賦值語句。

每一次將/減去仇對,伊)求偏導的結果，即沿最陡峭的“山坡”下降

將偏導數展開分析:

代入?式：%=%+°（嚴-九"⑴））

Q：學習速度，即決定你下山時每一步邁多大。設的過小，收斂時間長，設的過大，可能會超過最小

值

(1)批梯度下降算法:

上述為處理一個訓練樣本的公式，將其派生成包含m個訓練樣本的算法，循環下式直至收斂:

復雜度分析:

對于每個*的每次迭代，即上式所示，時間為0(m)

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

一般來說，這種二次函數的的三維圖形為一個碗狀，有一個唯一的全局最小值。其等高線為一個

套一個的橢圓形，運用梯度下降會快速收斂到圓心。

梯度下降性質：接近收斂時，每次的步子會越來越小。其原因是每次減去。乘以梯度，但是梯度會越

來越小，所以步子會越來越小。

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

檢測是否收斂的方法：

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

2）更常用的方法：檢驗"6）,假設不再變化，判定收斂

抵梯度下降算法的優點是能找到局部最優解，但是假設訓練樣本rn很大的話，其每次迭代都要“算所

有樣本的偏導數的和，時間過慢，于是采用下述另一種梯度下降方法。

（2）隨機梯度下降算法（增量梯度下降算法）：

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

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

每次迭代復雜度為0（n）0當m人樣本用完時，繼續循環到第1個樣本。

上述使用了迭代的方法求最小值，實際上對于這類特定的最小二乘回歸問題，或者普通最小二乘問

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

迭代求解了。

3、正規方程組

給定一個函數J,J是一個關于參數數組的函數，定義J的梯度關于的導數，它自己也是一個向量。向

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

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

更普遍的講，對于一個函數f，f的功能是將一個m*n的矩陣映射到實數空間上，即：

/:Rmxn1R

假設輸入為m*n人小的矩陣A,定義f關于矩陣A的導數為:

導數本身也是個矩陣，包含了f關于A的每個元素的偏導數。

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

trA即為tr(A)的簡化。

一些關于跡運算符和導數的定理：

ljtrAB=trBA

2]trABC=trCAB=trBCA

r

3，V4trAB=B

^trA=trAT

5:假設^tra=a

6，%trABMC=CAB+CTABT

有了上述性質，可以開始推導了：

定義矩陣X,稱為設計矩陣，包含了訓練集中所有輸入的矩陣：第i行為第i組輸入數據，即:

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

又因為對于向量Z,有z,z二￡izZ那么有：

由上述最后一個性質可得：4rC"+

通過上述6個性質，推導：

倒數第三行中，運用最后一個性質

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

稱為正規方程組

可得:e=(XTX)-xXTy.

第三課欠擬合與過擬合概念

本次課程大綱：

1.局部加權回歸：線性回歸的變化版本

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

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

4、感知器算法：對于3的延伸，簡要講

復習：

a①，y嘰第i個訓練樣本

令=L以參數向量e為條件，對于輸入X,輸出為：

n為掙征數量

定義本錢函數J,定義為：

m為訓練樣本

通過正規方程組推導的結論：

1、過擬合與欠擬合

通常，你選擇交給學習算法處理的特征的方式對算法的工作過程有很大影響。

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

畫出擬合曲線。回歸的曲線方程為：00+01X1

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

次函數,在圖中即為一個拋物線，即：0O+0lXl+02Xl2

以此類推，假設訓練集有7個數據，那么可擬合出最高6次的多項式，可以找到一條完美的曲線，該

曲線經過每個數據點。但是這樣的模型又過于復雜，擬合結果僅僅反映了所給的特定數據的特質，不

具有通過房屋大小來估計房價佗普遍性。而線性回歸的結果可能無法捕獲所有訓練集的信息，

所以，時丁一個監督學習模型來說，過小的特征集合使得模型過于簡單，過大的特征集合使得模型過

于復雜。

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

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

解決此類學習問題的方法：

1)特征選擇算法：一類自動化算法，在這類回歸問題中選擇用到的特征

2)非參數學習算法：緩解對于選取特征的需求，引出局部加權回歸

參數學習算法(parametriclearningalgorithm)

定義：參數學習算法是?類有固定數目參數，以用來進行數據擬合的算法。設該固定的參數集合為°。

線性回歸即使參數學習算法的一個例子

非參數學習算法(Non-parametriclearningalgorithm)

定義：一個參數數量會隨m(訓練集大小)增長的算法。通常定義為參數數量雖m線性增長。換句話

說，就是算法所需要的東西會隨著訓練集合線性增長，算法的維持是基于整個訓練集合的，即使是在

學習以后。

2、局部加權回歸(LocallyWeightedRegression)

一種特定的非參數學習算法。也稱作Loess。

算法思想：

假設對于一個確定的查詢點x,在x處對你的假設h(x)求值。

對于線性回歸，步驟如下:

1）擬合出"使EV一"￡"）產最小

2）返回臚x

對于局部加權回歸，當要處理x時：

1）檢查數據集合，并且只考慮位于x周圍的固定區域內的數據點

2）對這個區域內的點做線性回歸，擬合出一條直線

3）根據這條擬合直線對x的輸出，作為算法返回的結果

用數學語言描述即：

州合出8,使（嚴一八⑴%小

2）w為權值，有很多可能的選擇，比方：

■其意義在于，所選取的x（i）越接近x,相應的w（i）越接近1；x（i）越遠離x,w（i）越接近0。直觀的說，就

是離得近的點權值大，離得遠的點權值小。

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

-P被稱作波長函數，它控制了權值隨距離下降的速率。它越小，鐘形越窄，w衰減的很快；它越大，

衰減的就越慢。

3）返回曠”

總結：對于局部加權I可歸，每進行一次預測，都要重新擬合一條曲線。但如果沿著x釉對每個點都進

行同樣的操作，你會得到對于這個數據集的局部加權回歸預測結果，追蹤到一條非線性曲線，

*局部加權回歸的問題：

由于每次進行預測都要根據訓練集擬合曲線，假設訓練集太大，每次進行預測的用到的訓練集就會變

得很大，有方法可以讓局部加權回歸對「大型數據集更高效，詳情參見AndrewMoore的關于KD-tree

的工作。

3、概率解釋

概率解釋所解決的問題:

在線性回歸中，為什么選擇最小二乘作為計算參數的指標，使得假設預測出的值和真正y值之間面積

的平方最小化？

我們提供一組假設，證明在這組假設下最小二乘是有意義的，但是這組假設不唯一，還有其他很多方

法可以證明其有意義。

(1)假設1：

假設輸入與輸出為線性函數關系，表示為：/=夕］⑴+￡⑴

其中，為誤差項，這個參數可以理解為對未建模效應的捕獲，如果還有其他特征，這個誤差項表示

了一種我們沒有捕獲的特征，或者看成一種隨機的噪聲。

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

的高斯分布。

高斯分布的概率密度函數：

根據.匕述兩式可得：

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

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

*為什么選取高斯分布？

1)便于數學處理

2)對絕大?多數問潁，如果便用了線性回歸模型，然后測曷誤差分布，通常會發現誤差是?高斯分布的。

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

因素造成的效應的總和接近服從高斯分布。

注意：e并不是一個隨機變量，而是一個嘗試估計的值，就是說它本身是一個常量，只不過我們不知道

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

服從高斯分布”。

假設每個為HD(independentlyandidenticallydistributed)獨立同分布

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

⑵假設2：

設6的似然性為1即給定x（i）以為參數的y（i）的概率）：L（'）=心（優、，協=P?X；8）

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

⑶假設3：

極大似然估計：選取8使似然性L（e）最大化（數據出現的可能性盡可能大）

定義對數似然函數為（①：

上式兩個加項，前一項為常數。所以，使似然函數最大，就是使后一項最小，即：

這一項就是之前的J（e）,由此得證，即之前的最小二乘法計算參數，實際上是假設了誤差項滿足高斯分

布，且獨立同分布的情況，使似然最大化來計算參數。

注意：高斯分布的方差對最終結果沒有影響，由丁方差定為正數，所以無論取什么值，最后結果都

相同。這個性質會在下節課講到。

4、Logistic回歸

這是我們要學習的第一個分類算法c之前的回歸問題嘗試預測的變量y是連續變量，在這個分類算法

中，變量y是離散的，y只取｛0,1｝兩個值。

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

比例很大是，線性回歸的直線斜率就會越來越小，y=0.5時對應的x判決點就會比3大，造成預測錯

誤。

假設y取值｛0,1｝,首先改變假設的形式,使假設得到的值總在［。,段之間,即：h（x）q。」］

所以，選取如下函數：

其中:

g函數一般被稱為logistic函數，圖像如下：

Z很小時，g(z)趨于0,z很大時,g(z)趨于1,z=0時，g(z)=0.5

對假設的概率解釋：

假設給定x以為參數的y=l和y=0的概率：

P?I引。)=(加⑺產(1一加⑺尸

可以簡與成：

參數的似然性：

求對數似然性：

為了使似然性最大化，類似于線性回歸使用梯度卜.降的方法，求對數似然性對8的偏導，即：

因為求最大值，此時為梯度上升。

偏導數展開：

那么：

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

數，但實質上和線性回歸是不同的學習算法。

5、感知器算法

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

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

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

盡管看起來和之前的學習算法類似，但感知器算法是?種非常簡便的學習算法，臨界值和輸出只能是0

或1,是比logistic更簡單的算法。后續講到學習理論是，會將其作為根本的構造步驟。

第四課牛頓方法

本次課程人綱:

1、牛頓方法：對Logistic模型進行擬合

2、指數分布族

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

更習：Logistic回歸：分類算法

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

求對數似然性：

對其求偏導數，應用梯度上升方法，求得：

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

1、牛頓方法

假設有函數f（e）,需要找使f⑼=0的?

步驟：

工）給出一個?的初始值

2）對,⑼求導，求導數為。時8的值（就是求f⑼切線與x軸交點）

3）重復步驟2

因為該點的導數值即為切線斜率，而斜率=該點y軸的值，該點x軸的變化值，所以。每次的變化值:

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

*一般初始化為0

應用于Logistic回歸：

求對數似然的最大值，即求.伊）為o時的句根據上述推論，更新規則如下:

牛頓方法的收斂速度：二次收斂

每次迭代使解的有效數字的數目加倍：假設當前誤差是0.1,一次迭代后，誤差為0.001,再一次迭

代，誤差為0.0000001。該性質當解距離最優質的足夠近才會發現。

牛頓方法的一般化：

e是一個向量而不是一個數字，一般化的公式為：

Vo"。）是目標函數的梯度，H為Hessian矩陣，規模是n*n,n為特征的數量，它的每個元素表示一

個二階導數：

上述公式的意義就是，用一個一階導數的向量乘以一個二階導數矩陣的逆

優點：假設特征數和樣本數合理，牛頓方法的迭代次數比梯度上升要少得多

缺點：每次迭代都要重新計算Hessian矩陣，如果特征很多，那么H矩陣計算代價很大

2、指數分布族

回憶學過的兩種算法：

對于P（y|x；e）：

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

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

問題：如LogisticI可歸中，為何選擇sigmoid函數？sigmoid函數是最自然的默認選擇。

接下來，會以這兩個算法為例，說明它們都是廣義線性模型的特例。

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

1）伯努利分布

設有一組只能取0或1的數據，用伯努利隨機變量對其建模:

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

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

2)高斯分布

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

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

指數分布族的定義：

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

n?自然參數，通常是一個實數

T(y)-允分統計量，通常，T(y)=y,實際上是一個概率分布的充分統計量I統計學知識)

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

的概率分布。

證明伯努利分布是指數分布族：

可知：

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

那么：

證明高斯分布是指數分布族：

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

這種情況下高斯密度函數為：

可得：

*指數分布族包括：

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

伯努利分布(01問題建模)，多項式分布(對k個結果的事件建模)；

泊松分布（對計數過程建模）；

伽馬分布，指數分布（對實數的間隔問題建模）；

B分布，Dirichlet分布（對小數建模）；

Wishart分布（協方差矩陣的分布）…

3、廣義線性模型GLM

選定了一個指數分布族后，怎樣來推導出一個GLM呢？

假設：

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

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

例：假設要統計網站點擊量y,用泊松分布建模

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

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

義。假設n是一個向量，3=修工

推導伯努利分布的GLM：

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

對給定的X,6,學習算法進行一次預測的輸出：

得到logistic回歸算法。

正那么響應函數：g（n）=E[y；n].將自然參數n和y的期望聯系起來

正那么關聯函數：屋

推導多項式分布的GLM：

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

病中的一種等問題。

(1)將多項式分布寫成指數分布族的形式：

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

參數可以由前k-1個推導出，所以只將前k-1個01，???，°及-1視為參數。

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

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

*定義符號：指示函數，1{.}

l{True)=lzl{Fdlse)=0,即大括號內命題為真，值為1,;否那么為0。

例：1{2=3}=0,1{1+1=2}=1

用T(y)i表示T(y)的第i個元素，那么T(y)i=l{y=i}

根據參數(P的意義(<pi表示第i個取值的概率分布)，可推出：

可得：

證明多項式分布式指數分布族。

再用n表示(P：

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

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

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

Softmax回歸的訓練方法和logistic相似，通過極人似然估計找到參數6,其對數似然性為：

771

￡（。）=

i=l

T（<）

m卜/X'I?'*'}

=f>gfi

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

再通過梯度上升或牛頓方法找對數似然性的最大值，即可求出參數e.

第五課生成學習算法

本次課程大綱：

1、生成學習算法

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

-高斯分布（簡要）

-比照生成學習算法&判別學習算法（簡要）

3、樸素貝葉斯

4、Laplace平滑

復習：

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

直線將圖中不同的類分開，如卜列圖。

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

1、生成學習算法

例：對惡性腫瘤和良性腫瘤的分類

除了尋找一個將兩類數據區分的直線外，還可以用如下方法：

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

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

腫瘤模型和良性腫瘤模型，看哪個模型匹配的更好，預測屬于惡性還是良性。

這種方法就是生成學習算法。

兩種學習算法的定義：

1)判別學習算法：

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

?或學習得到一個假設h0(x),直接輸出0或1

2)生成學習算法：

-對p(x|y)進行建模，p(x|y)表示在給定所屬的類的情況下，顯示某種特征的概率。處于技術上的考慮,

也會對p(y)進行建模。

-p(x|y)中的x表示一個生成模型對樣本特征建立概率模型，y表示在給定樣本所屬類的條件卜.

例：在上例中，假定一個腫瘤情況y為惡性和良性，生成模型會對該條件下的腫瘤病癥x的概率分布

遂行建模

-對p(x|y)和p(y)建模后，根據貝葉斯公式p(y|x)=p(xy)/p(x)=p(x|y)p(y)/p(x),可以計算：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是一種生成學習算法。

GDA的假設條件：

1)假設輸入特征并且是連續值。

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

*高斯分布根底知識：

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

其概率密度函數為:

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

多元高斯分布注意兩個參數即可：

-均值向量|J

-協'方差矩陣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

」可見增加矩陣對角元素的值,

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

即增加下對角線的元素，圖形會沿45。角，偏轉成一個橢圓形狀。

假設E對角線元素為負，圖形如F：

Z分別為：

不同p的圖形如下：

P分別為：

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

GDA擬合：

給出訓練樣本如下列圖所示：

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

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

-通過這兩個高斯分布的密度函數，定義出兩個類別的分隔器，即圖中的五線

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

GDA模型：

寫出其概率分布：

參數包括cp，pO,pl,Z，對數似然性為：

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

*比照logistic回歸中的對數似然性：

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

通過對上面對數似然性求極大似然估計，參數的結果為：

(P：訓練樣本中標簽為1的樣本所占的比例

M0：分母為標簽為。的樣本數，分子是對標簽為。的樣本的x(i)求和，結合起來就是對對標簽為。的樣

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

pl：與M0同理，標簽改為1

GDA預測：

預測結果應該是給定x的情況下最可能的y,等式左邊的運算符argmax表示計算p(y|x)最大時的y

值，預測公式如下：

因為p(x)獨立于y,所以可以忽略p(x)。

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

那個y。不過這種情況并不常見，

GDA和logistic回歸的聯系：

例：假設有一個一維訓練集，包含一些正樣本和負樣本，如下列圖x軸的叉和圈，設叉為0,圈為1,

用GDA對兩類樣本分別擬合高斯概率密度函數p(x|y=0)和p(x|y=l),如下列圖的兩個鐘形曲線。沿x軸

遍歷樣本，在x軸上方畫出其相應的p(y=l|x)o

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

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

和sigmoid函數曲線很相似。

簡單來講,就是當使用GDA模型時，p(x|y)屬于高斯分布,計算米y|x)時,幾乎能得到和logistic回歸

中使用的sigmoid函數一樣的函數。但實際上還是存在本質區別的。

使用生成學習算法的優缺點：

給出兩個推論：

推論1：

x|y服從高斯分布=>p(y=l|x)是logistic函數

該推論在反方向不成立。

推論2：

x|y=l~Poisson(Al),x|y=0~Poisson(AO)=>p(y=l|x)是logistic函數

x|y=l~Poisson(入1)表示x|y=l服從參數為XI泊松分布

推論3：

x|y=l~ExpFamily(r|l),x|y=0~ExpFamily(q0)=>p(y=l|x)是logistic函數

推論2的推廣，即x|y的分布屬于指數分布族，均可推出結論，顯示了logistic回歸在建模假設選擇方

面的魯棒性。

優點：

推論1反方向不成立，因為x|y服從高斯分布這個假設更強，GDA模型做出了一個更強的假設，所

以，假設x|y服從或近似服從高斯分布，那么GDA會比logistic回歸更好，因為它利用了更多關于數據

的信息，即算法知道數據服從高斯分布。

缺點：

如果不確定x|y的分布情況，那么判別算法logistic回歸性能更好。例如，預先假設數據服從高斯分

布，但是實際上數據服從泊松分布，根據推論2,logistic回歸仍能獲得不錯的效果。

生成學習算法比判決學習算法需要更少的數據。如GDA的假設較強，所以用較少的數據能擬合出不錯

的模型。而logistic回歸的假設較弱，對模型的假設更為健壯，擬合數據需要更多的樣本。

3、樸素貝葉斯

另一種生成學習算法。例：垃圾郵件分類

實現一個垃圾郵件分類器，以腋件輸入流作為輸入，確定郵件是否為垃圾郵件。輸出y為。1},1為垃

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

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

表示字典中的第i個詞是否出現在郵件中，x例如如下：

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

是用多項式分布進行建模(伯努利分布對01建模，多項式分布對k個結果建模)，這樣就需要

2A50000-1個參數，可見參數過多，下面介紹樸素貝葉斯的方法。

假設xi在給定y的時候是條件獨立的，那么x在給定y下的概率可簡化為：

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

你預測其他的詞是否出現在郵件中。雖然這個假設不是完全正確的，但是樸素貝葉斯依然應用于對郵

件進行分類，對網頁進行分類等用途。

*對于樸素貝葉斯，我的理解為：通過指定一些垃圾郵件的關健詞來計算某個郵件是垃圾郵件的概率。

具體講，就是給定字典后，給出每個詞的p(xi|y=l),即這個詞xi在垃圾郵件中出現的概率，然后對于

一個郵件，將郵件所有詞的p(xi|y)的相乘，就是郵件為垃圾郵件的概率。再簡化一些，規定

p|xi|y=l)={0,l}>即劃定一些關鍵詞，這些關鍵詞在郵件中出現的概率就是這封郵件為垃圾郵件的概

率。

模型參數包括：

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

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

①y=p(y=l)

聯合似然性：

求得參數結果:

<ti|y=i的分子為標記為1的郵仁中出現詞j的郵件數目和，分母為垃圾郵件數，總體意義就是訓練集

中出現詞j的垃圾郵件在垃圾郵件中的比例。

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

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

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

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

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

x(i)為詞向量，標記出現在第i個郵件中的詞，y(i)為第i個郵件是否是垃圾郵件。用郵件中的所有出現

的詞構造字典，或者選擇出現次數k次以上的詞構造字典。

樸素貝葉斯的問題：

設有一封新郵件中出現一個字典沒有的新詞，設其標號為30000,因為這個詞在垃圾郵件和非垃圾郵件

中都不存在,那么p(x3000|y=l)=0,p(x30000|y=0)=0,計算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,那么

結果是未定義的。

其問題在于，統計上認為p(x30000|y)=0是不合理的。即在過去兩個月郵件里未出現過這個詞，就認為

其出現概率為0,并不合理。

概括來講，即之前沒有見過的事件，就認為這些事件不會發生，是不合理的。通過Laplace立滑解決這

個問題。

4、Laplace平滑

根據極大似然估計,即為的概率是樣本中的數目在所有樣本中的

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

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

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

例：給出一支球隊5場比賽的結果作為樣本，5場比賽都輸了，記為0,那么要預測第六場比賽的勝

率，按照樸素貝葉斯為：即樣本中沒有勝場，那么勝率為顯然這是不合理的。

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

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

減小，但不會為0。

更一般的，假設y取k中可能的值，比方嘗試估計多項式分布的參數，得到下式:

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

對于樸素貝葉斯，得到的結果為：

在分子上加1,分母上加2,解決了0概率的問題。

第六課樸素貝葉斯

本次課程大綱：

1、樸素貝葉斯

-樸素貝葉斯事件模型

2、神經網絡(簡要)

3、支撐向量機(SVM)鋪墊-最大間隔分類器

復習：

1、樸素貝葉斯

一種生成學習算法，對p(x|y)建模。

例：垃圾郵件分類

以郵件輸入流作為輸入，輸出y為{0,1},1為垃圾郵件，。為非垃圾郵件。

將郵件文本表示為一個輸入向量x

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

2)x長度為n,n為字典的詞數

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

假設xi在給定y的時候是條件獨立的，那么x在給定y下的概率可簡化為：

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

算法變化版本:

1)讓xi取多個值,xi￡{l,2,...,k},類似上式有:p(x|y)=nP(xi|y)，但是p(xi|y)變成多項式分布,而不

是伯努利分布。

例：估計房屋面積預測房屋能否被賣掉，將房屋面積分成幾個離散區間，如0-,1000為xi=l,1000-1500

為xi=2,1500-2000為xi=3,2000以上為xi=4

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

多項式事件模型

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

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

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

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

?

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

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

n為郵件長度

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

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

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

模型參數：

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

給出訓練集后，求極大似然估計：

得到：

上面第一個式子，分子的意思是，對所有標簽為1的郵件求和，之后對垃圾郵件中的詞k求和，所以

分子實際上就是訓練集中所有垃圾郵件中詞k出現的次數。分母是訓練集中所有垃圾郵件的長度。比

值的含義就是所有垃圾郵件中，詞k占的比例。表示生成垃圾郵件時選擇詞k的概率。

應用Laplace平滑，分子加1,分母加總詞數(字典人小，xi可能取值的數目)：

事實上，多項式事件模型比之前的模型要好，可能是因為考慮了詞出現的次數這個因素工但此問題仍

存在爭論。

非線性分類算法

例：logistic回歸中，假設值小于0.5預測0,大廣0.5預測1。即給定一個訓練集，logistic回歸會找到

一條直線〔牛頓方法或梯度卜.降J,將正負樣本合埋分開。但右時數據不能被一條直線分開，需要一

種算法，學習非線性的分界線。

上一講的推論：

x|y=l**ExpFamily(ql),x|y=0~ExpFamily(r)0)=>p(y=l|x)是logistic函數

即x|y的分布屬于指數分布族，可推出后驗分布是logistic函數。

樸素貝葉斯模型也屬手指數分布族，所以也是用logistic線性分類器。下面介紹一種非線性分類器。

2、神經網絡

假設特征是x0,xl,x2,x3,x0設置為1,用連線表示logistic回歸單元，圓圈表示計算節點，下列圖中間

的節點以x0等特征作為輸入，卜6(x)作為輸出，這是一個sigmoid函數。為了找到非線性的界限，需要

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

將之前畫的小單元拼在一起，得到神經網絡。特征輸入到假設干個sigmoid單元，在輸入到另外一個

sigmoid單元，得到輸出。中間節點的輸出值設為al,a2,a3。這些中間節點稱為隱藏層，神經網絡可以

由多個隱層。

每個中間節點有一系列參數：

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

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

一種學習模型參數的方法是，利用本錢函數J(5,使用梯度下降使J(5最小。即用梯度下降使得神經網

絡的預測結果和你觀察到的訓練集中的樣本標簽盡可能接近。在神經網絡中，這種方法稱為反向傳

播.

3、支撐向量機鋪墊-最大間隔分類器

另外一種能生成非線性分類器佗學習算法。本節課先介紹另外一類線性分類器，在下一講或者下下講

中，利用支撐向量機的想法，進行一些巧妙的改動和擴展，讓它可以生成非線性分界線。

兩種對于分類的直觀理解：

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

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

如果的<>>0,相當確定的預測y=l；如果UxccO,相當確定的預測y=0

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

根據訓練集找到了參數，我們的學習算法不僅需要保證分類結果正確，更要進一步保證分類結果確實

定性。

2)假設訓練集是線性可分割的，即一定有一條直線可以將訓練集分開。那么直觀來看，我們一定會選

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

支撐向量機中改動的符號：

輸出y￡{-l,+l}

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

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

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

T

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

距b單提出來，方便引出支撐向最機。

函數間隔：

一個超平面(w,b)和某個特定訓練樣本(x(i),y(i))對應的函數間隔定義為：

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

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

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

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

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

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

離樣本越遠效果越好)。

幾何間隔：

幾何距離定義為：一個訓練樣本對應的點到由超平面確定的分隔線的距離。如下列圖A到分隔線的距

離AB就是幾何距離。

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

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

由于點B在分隔線上，它應該還滿足：

可以解出：

上式說明，對于一個訓練樣本x(i),到由參數w和b確定的分隔平面之間的距離，可以由上式得到。

由于上述一直假設對樣本進行了正確的分類，所以更一般的，將幾何間隔定義為：

這個定義和函數間隔很相似，不同點是對向量w進行了標準化。同樣，希望幾何間隔也是越大越好。

結論：如果||w||=l,函數間隔等于幾何間隔。更一般的，兒何間隔等于函數間隔除以||w||。

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

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

學習算法，選擇特定的w和b,使幾何間隔最大化。最大分類間隔是下述這樣的優化問題：

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

為Y。

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

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

第七課最優間隔分類器問題

本次課程大綱：

1、最優間隔分類器

2、原始優化問題&對偶優化問題(KKT條件)

3、SVM對偶問題

4、核方法(下一講)

復習：

支撐向景機中改動的符號：

輸出y￡{?l,+l}

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

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

T

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

距b單提出來，方便引出支撐向量機。

函數間隔：

一個超平面(w,b)和某個特定訓練樣本(x(i),y(i))對應的函數間隔定義為：

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

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

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

如果y(i)(wTx(i)+b)>0,意味著分類結果正確

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

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

離樣本越遠效果越好)。

幾何間隔：

幾何間隔定義為：

這個定義和函數間隔很相似，不同點是對向量w進行了標準化。同樣，希望幾何間隔也是越大越好。

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

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

和函數間隔類似，取樣本中最小的幾何間隔。性質：可以任意比例縮放W和b,因為任意縮放W和b

都不會改變超平面wTx+b=O的位置。這一性質在后續討論中帶來很大便利。

1、最優間隔分類器

最優間隔分類器可以看做是支撐向量機的前身，是一種學習算法，選擇特定的W和b,使幾何間隔最

大化。最優分類間隔是下述這樣的優化問題：

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

為Y。即，找到一個超平面，在將正負樣本分開的同時，使超平面到正負樣本間的距離盡可能大。

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

非常糟糕的非凸性約束。要求解的參數w在一個球體外表，如果想得到一個凸優化問題，必須保證如

梯度下降算法這種局部最優值搜索算法不會找到局部最優值，而非凸性約束不能滿足這個條件，所以

需要改變優化問題。

為了解決上述問題，提出下面的最優化問題：

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