MOOC臺(tái)大林軒田老師“機(jī)器學(xué)習(xí)基石”筆記

1、先簡(jiǎn)單介紹下這門課程，這門課是在著名的MOOC（Massive Online Open Course大型在線公開課）Coursera上的一門關(guān)于機(jī)器學(xué)習(xí)領(lǐng)域的課程，由國(guó)立臺(tái)灣大學(xué)的年輕老師林軒田講授。這門叫做機(jī)器學(xué)習(xí)基石的課程，共8 周的課程為整個(gè)機(jī)器學(xué)習(xí)課程的上半部分，更偏重于理論和思想而非算法，主要分為四大部分來(lái)講授。  When can Machine Learn？在何時(shí)可以使用機(jī)器學(xué)習(xí)？Why can Machine Learn？ 為什么機(jī)器可以學(xué)習(xí)？How can Machine Learn？機(jī)器可以怎樣學(xué)習(xí)？How can Machine Learn Better？怎樣能

2、使機(jī)器學(xué)習(xí)更好？每一大塊又分為幾周來(lái)講授，每周的課時(shí)分為兩個(gè)大課，每個(gè)大課一般又分為四個(gè)小塊來(lái)教學(xué)，一個(gè)小塊一般在十分鐘到二十分鐘之間。以VC bound （VC限制）作為總線將整個(gè)基礎(chǔ)課程貫通講解了包括PLA（Perceptron learning algorithm感知器）、pocket、二元分類、線性回歸（linear regression）、logistic回歸（logistic regression）等等。以下不用大課小課來(lái)敘述了，寫起來(lái)感覺怪怪的，就用章節(jié)來(lái)分別代表大課時(shí)和小課時(shí)。一、The learning problem機(jī)器學(xué)習(xí)問題。1. Course Introduction

3、課程簡(jiǎn)介。第一小節(jié)的內(nèi)容就是課程簡(jiǎn)介，如上已進(jìn)行了詳細(xì)的介紹，這里就不多贅述。1.2 What is Machine Learning什么是機(jī)器學(xué)習(xí)？在搞清這個(gè)問題之前，先要搞清什么是學(xué)習(xí)。學(xué)習(xí)可以是人或者動(dòng)物通過觀察思考獲得一定的技巧過程。而機(jī)器學(xué)習(xí)與之類似，是計(jì)算機(jī)通過數(shù)據(jù)和計(jì)算獲得一定技巧的過程。注意這一對(duì)比，學(xué)習(xí)是通過觀察而機(jī)器學(xué)習(xí)是通過數(shù)據(jù)（是計(jì)算機(jī)的一種觀察）。對(duì)比圖如圖1-1。（本筆記的圖和公式如不加說明皆是出自林老師的課件，下文不會(huì)對(duì)此在做說明）圖1-1 學(xué)習(xí)與機(jī)器學(xué)習(xí)對(duì)比圖 a）學(xué)習(xí)        

4、0; b）機(jī)器學(xué)習(xí)那么緊接著就是要解決上述中出現(xiàn)的一個(gè)新的名詞"技巧"（skill）。什么是技巧呢？技巧是一些能力表現(xiàn)的更加出色。機(jī)器學(xué)習(xí)中的技巧如預(yù)測(cè)（prediction）、識(shí)別（recognition）。來(lái)一個(gè)例子：從股票的數(shù)據(jù)中獲得收益增多的這種技巧，這就是一種機(jī)器學(xué)習(xí)的例子。那既然人也可以通過觀察獲得一個(gè)技巧，為什么還需要機(jī)器學(xué)習(xí)呢？這就是為什么需要機(jī)器學(xué)習(xí)，簡(jiǎn)單來(lái)說，就是兩大原因：一些數(shù)據(jù)或者信息，人來(lái)無(wú)法獲取，可能是一些人無(wú)法識(shí)別的事物，或是數(shù)據(jù)信息量特別大；另一個(gè)原因是人的處理滿足不了需求，比如：定義很多很多的規(guī)則滿足物體識(shí)別或者其他需求；在短時(shí)間內(nèi)通過大量

5、信息做出判斷等等。上面說的是為什么使用機(jī)器學(xué)習(xí)，那么什么情況下使用機(jī)器學(xué)習(xí)呢？是不是所有的情況都使用機(jī)器學(xué)習(xí)呢？這里給出了三個(gè)ML（機(jī)器學(xué)習(xí)的英文縮寫）的關(guān)鍵要素：1、存在一個(gè)模式或者說表現(xiàn)可以讓我們對(duì)它進(jìn)行改進(jìn)提高；2、規(guī)則并不容易那么定義；3、需要有數(shù)據(jù)。1.3 Applications of Machine Learning機(jī)器學(xué)習(xí)的應(yīng)用。這一小節(jié)主要介紹的就是機(jī)器學(xué)習(xí)能用在哪些方面。個(gè)人感覺不是理論介紹的重點(diǎn)（不是說應(yīng)用不重要，剛好相反，其實(shí)個(gè)人認(rèn)為機(jī)器學(xué)習(xí)甚至整個(gè)計(jì)算機(jī)學(xué) 科最重要的還是應(yīng)用），就簡(jiǎn)述下機(jī)器學(xué)習(xí)可以應(yīng)用在在衣食住行育樂，包含了人類生活的方方面面，所以機(jī)器學(xué)習(xí)的應(yīng)用場(chǎng)景

6、很廣泛很有市場(chǎng)。1.4 Components of Machine Learning機(jī)器學(xué)習(xí)的組成部分。這一小節(jié)是第一章的重點(diǎn)，因?yàn)樗鼘C(jī)器學(xué)習(xí)的理論應(yīng)用符號(hào)及數(shù)學(xué)知識(shí)進(jìn)行表示，而以下各章內(nèi)容也都是在這小節(jié)內(nèi)容的基礎(chǔ)上展開的。從一個(gè)銀行是否會(huì)發(fā)信用卡給用戶的例子引出了機(jī)器學(xué)習(xí)可以分為哪幾個(gè)部分（組件）。1.輸入(input)：xX（代表銀行所掌握的用戶信息）2.輸出(output)：yY （是否會(huì)發(fā)信用卡給用戶）3.未知的函數(shù)，即目標(biāo)函數(shù)（target function）：f：XY（理想的信用卡發(fā)放公式）4.數(shù)據(jù)或者叫做資料（ data），即訓(xùn)練樣本（ training examples）：D

7、 = （）, ( ), , ( )（銀行的歷史記錄）5.假設(shè)（hypothesis），即前面提到的技能，能夠具有更好地表現(xiàn)：g：XY （能夠?qū)W習(xí)到的公式）可以通過一個(gè)簡(jiǎn)單的流程圖表示，如圖1-2所示。 圖1-2 機(jī)器學(xué)習(xí)的簡(jiǎn)單流程圖從圖中可以清楚機(jī)器學(xué)習(xí)就是從我們未知但是卻存在的一個(gè)規(guī)則或者公式f中得到大量的數(shù)據(jù)或者說資料（訓(xùn)練樣本），在這些資料的基礎(chǔ)上得到一個(gè)近似于未知規(guī)則g的過程。這么說還是有點(diǎn)抽象，特別是目標(biāo)函數(shù)f又是未知的，那為什么還能找到一個(gè)假設(shè)g能夠接近f呢？還是以一個(gè)更加詳細(xì)的流程圖來(lái)說明這一問題，如圖1-3。圖1-3 詳細(xì)的機(jī)器學(xué)習(xí)流程圖 這個(gè)流程圖和圖1-

8、2有些不同，其中ML被更詳細(xì)的定義為機(jī)器學(xué)習(xí)算法（learning algorithm）一般用A表示。還多出來(lái)一個(gè)新的項(xiàng)目，就是假設(shè)空間或者叫做假設(shè)集合（hypothesis set）一般用H表示，它是包含各種各樣的假設(shè)，其中包括好的假設(shè)和壞的假設(shè)，而這時(shí)A的作用就體現(xiàn)了，它可以從H這個(gè)集合中挑選出它認(rèn)為最好的假設(shè)作為 g。注：1、這里還要說明的是機(jī)器學(xué)習(xí)的輸入在這個(gè)流程圖中就變成了兩個(gè)部分，一個(gè)是訓(xùn)練樣本集，而另一個(gè)就是假設(shè)空間H。2、還有一點(diǎn)需要注意的是，我們所說的機(jī)器學(xué)習(xí)模型在這個(gè)流程圖中也不僅僅是算法A，而且還包含了假設(shè)空間H。3、要求得g來(lái)近似于未知目標(biāo)函數(shù)f。4、給出了機(jī)器學(xué)習(xí)的一

9、個(gè)更準(zhǔn)確點(diǎn)的定義，就是通過數(shù)據(jù)來(lái)計(jì)算得到一個(gè)假設(shè)g使它接近未知目標(biāo)函數(shù)。 圖1-3是還是一個(gè)相對(duì)比較簡(jiǎn)單的機(jī)器學(xué)習(xí)流程圖，在往后的章節(jié)中會(huì)不斷的根據(jù)新學(xué)的知識(shí)繼續(xù)擴(kuò)展這幅圖的元素。1.5 Machine Learning and Other Fields機(jī)器學(xué)習(xí)與其他各個(gè)領(lǐng)域的關(guān)系。1.5.1 ML VS DM （Data Mining）機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘者叫知識(shí)發(fā)現(xiàn)（KDD Knowledge Discovery in Dataset）。上一節(jié)中已經(jīng)給出了機(jī)器學(xué)習(xí)的概念，因此只介紹下數(shù)據(jù)挖掘的概念，就是從大量的數(shù)據(jù)中找出有用的信息。從定義出發(fā)，我們可以將兩者之間的關(guān)系分為3種。1.

10、 兩者是一致的：能夠找出的有用信息就是我們要求得的近似目標(biāo)函數(shù)的假設(shè)。2. 兩者是互助的：能夠找出的有用信息就能幫助我們找出近似的假設(shè)，反之也可行。3. 傳統(tǒng)的數(shù)據(jù)挖掘更關(guān)注與從大量的數(shù)據(jù)中的計(jì)算問題。總的來(lái)時(shí)，兩者密不可分。1.5.2 M L VS AI （artificial intelligence）機(jī)器學(xué)習(xí)與人工智能。人工智能的大概概念就是電腦能夠表現(xiàn)出一些智慧行為。從定義可以得到，機(jī)器學(xué)習(xí)是實(shí)現(xiàn)人工智能的一種方式。1.5.3 ML VS statistic機(jī)器學(xué)習(xí)與統(tǒng)計(jì)。統(tǒng)計(jì)也需要通過數(shù)據(jù)，來(lái)做一個(gè)未知的推論。因此統(tǒng)計(jì)是一種實(shí)現(xiàn)機(jī)器學(xué)習(xí)的方法。傳統(tǒng)的統(tǒng)計(jì)學(xué)習(xí)更關(guān)注與數(shù)學(xué)公式，而非計(jì)算

11、本身。二、Learning to Answer Yes/No二元分類。解決上一章提出的銀行發(fā)行信用卡的問題。2.1 Perceptron Hypothesis Set感知器的假設(shè)空間。還是銀行發(fā)信用卡的例子，銀行可能掌握了用戶的各種屬性，如年齡，年薪，工作年限，負(fù)債情況等等，這些屬性可以作為上面提到的樣本輸入的向量屬性值。但是這樣還是無(wú)法進(jìn)行機(jī)器學(xué)習(xí)，因?yàn)槲覀冞€需要另一個(gè)輸入，即假設(shè)空間H。假設(shè)空間該如何表示呢？本節(jié)提出了一種表示方式，這種學(xué)習(xí)的模型稱之為感知器（Perceptron）。其實(shí)感知器的產(chǎn)生很早，算是第一代的單層神經(jīng)網(wǎng)絡(luò)，這里就不多做介紹，在其他的讀書筆記中進(jìn)行說明。這種假設(shè)空間的

12、思想就類似考試給的成績(jī)，對(duì)每一題給一個(gè)特定的分?jǐn)?shù)，即權(quán)重，說白了就是給輸入向量的每個(gè)屬性乘以一個(gè)加權(quán)值，在設(shè)計(jì)一個(gè)及格線，即所謂的閾值或者叫門檻值（threshold），如果加權(quán)求和的分?jǐn)?shù)大于這個(gè)及格線就叫及格了，即對(duì)應(yīng)的輸出值為1，小于這個(gè)及格線成為不及格，對(duì)應(yīng)的輸出值為-1。其中h(x)H，如公式2-1所示。    （公式2-1）其中sign括號(hào)中所包含的內(nèi)容大于0時(shí)，取+1；小于0時(shí)，取-1。此時(shí)可以對(duì)h(x)做一些數(shù)學(xué)上的簡(jiǎn)化，注意這僅僅是一種數(shù)學(xué)表示方式的簡(jiǎn)化，如公式2-2所示。    (公式2-2）如上

13、所示，將閾值的負(fù)數(shù)表示為權(quán)值向量中的一項(xiàng)，用 表示，而對(duì)應(yīng)權(quán)值分量的輸入分量則被默認(rèn)為1，用 最終將公式簡(jiǎn)化為兩個(gè)向量?jī)?nèi)積的形式，其中T表示轉(zhuǎn)置。這里必須說明一個(gè)問題，就是不同h(x) 對(duì)應(yīng)著不同的向量，即可以說假設(shè)空間H就是向量 的取值范圍。這么描述還是很抽象，因此引入一種方式就是使用圖像（或者可以說是幾何）來(lái)更形象更具體的來(lái)說明以上函數(shù)。（這里說點(diǎn)題外話，由于二元函數(shù)和三元函數(shù)可以使用幾何圖像來(lái)一一對(duì)應(yīng)，用幾何的方式更直觀的表示函數(shù)的意義，方便大家理解，這在以后的章節(jié)中會(huì)不斷使用）為了理解的方便將輸入向量的維度限制為兩個(gè)，即h函數(shù)可以表示成公式2-3。   &

14、#160;(公式2-3）將輸入向量對(duì)應(yīng)于一個(gè)二維平面上的點(diǎn)（如果向量的維度更高，對(duì)應(yīng)于一個(gè)高維空間中的點(diǎn)）。輸出y（在分類問題中又稱作標(biāo)簽，label）使用表示+1，×表示-1。假設(shè)h對(duì)應(yīng)一條條的直線（如果在輸入向量是高維空間的話，則對(duì)應(yīng)于一個(gè)超平面）這里不止一條，不同的權(quán)值向量對(duì)應(yīng)不同的直線，因?yàn)閟ign是以0為分界線的函數(shù)，所以可以設(shè) ，該式恰是一條直線的表示。因此每條邊的一邊為正的，而另一邊為表示為負(fù)的。最終得到的圖像如圖2-1所示。 圖2-1 感知器在維度為2時(shí)的幾何表示 因此這里將感知器作為一條二元線性分類器（linear ( binary) class

15、ifiers）。2.2 Perceptron Learning Algorithm (PLA)感知器學(xué)習(xí)算法。在第一章中，我們介紹過一個(gè)機(jī)器學(xué)習(xí)模型由兩部分組成，而上一節(jié)僅僅介紹了它其中的一部分即假設(shè)空間H如何表示。本節(jié)我們將更詳細(xì)的介紹感知器的算法A，即如何從假設(shè)空間中找到一個(gè)近似未知目標(biāo)函數(shù)f的最好假設(shè)g(x)。問題是，我們?nèi)绾握业竭@個(gè)g(x)呢？首先考慮，g(x)和目標(biāo)函數(shù)f越接近越好，但問題是我們不知道f（如果知道了就不需要學(xué)習(xí)了）但是我們知道些什么呢？知道的是樣本輸入x在f(x)作用下得到的標(biāo)記y。所以如果我們能使得g(x)在所有的樣本輸入中都能夠得到跟f函數(shù)作用過輸入得到的輸出一樣

16、的話，我們認(rèn)為這時(shí)的g是不錯(cuò)的。（在后面的章節(jié)還會(huì)在這種思想的基礎(chǔ)上更深入的討論這一問題）但是問題又來(lái)了，假設(shè)空間H的函數(shù)h(x)有無(wú)數(shù)種表示，即向量w有無(wú)數(shù)種取值。（如在二元輸入時(shí)，假設(shè)空間對(duì)于在二維平面上的直線，在那個(gè)空間中可以畫出無(wú)數(shù)條直線）面對(duì)這無(wú)數(shù)多種情況，我們又該如何求解？我們想到一個(gè)簡(jiǎn)單的方式，就是一步一步的修正錯(cuò)誤的分類，在二維平面中可以想象成一條初始的直線，在經(jīng)過不斷的糾正它的錯(cuò)誤（就是旋轉(zhuǎn)平移之類的）使得最終的結(jié)果可以達(dá)到希望的效果。還要在重復(fù)上一節(jié)中已經(jīng)得到的一個(gè)結(jié)論，在感知器模型中，每一個(gè)假設(shè)函數(shù)h都對(duì)應(yīng)一個(gè)權(quán)值向量。因此我們要做的就是不斷修正這個(gè)權(quán)值向量使得最接近目標(biāo)

17、函數(shù)f。下面來(lái)詳細(xì)介紹一下PLA。首先我們?cè)谠O(shè)置初始 （注意此處是向量不是向量的分量?。?，比如設(shè)置為0向量，然后使用訓(xùn)練樣本來(lái)將權(quán)值向量修正的更接近目標(biāo)函數(shù)f。其修正步驟如下：將權(quán)值向量的修正次數(shù)表示為t，t=0,1,2,在何種情況下需要修正向量 呢？如公式2-4所示。         (公式2-4）其中訓(xùn)練樣本 ，為在t次時(shí)使用的輸入向量，而為在t次時(shí)的標(biāo)記量。該公式2-4的意思就是在t次時(shí)，選擇的權(quán)值向量，有一個(gè)訓(xùn)練樣本使得在經(jīng)過 （即）假設(shè)計(jì)算的得到的標(biāo)簽與f(x)得到的標(biāo)簽不一致。在這種情況下就需要對(duì)權(quán)值向

18、量進(jìn)行修改，使它符合條件。修改的公式如公式2-5所示。（公式2-5）從直覺上理解這個(gè)公式相對(duì)困難，我們還是將它化成一個(gè)幾何圖形，更準(zhǔn)確的說法變成向量加減的形式去理解它，如圖2-2所示。 圖2-2 公式2-5的幾何解 a) b) 圖2-2a中是在本身標(biāo)記為+1時(shí)，權(quán)值向量和輸入向量的內(nèi)積為負(fù)數(shù)，對(duì)權(quán)值向量略作修改，加上一個(gè)標(biāo)記y和輸入向量的乘積，得到一個(gè)新的權(quán)值向量，可以看出新的權(quán)值向量和輸入向量的相乘之后符合了標(biāo)記的要求。圖2-2b中是在本身標(biāo)記為-1時(shí)，權(quán)值向量和輸入向量的內(nèi)積為正數(shù)，對(duì)權(quán)值向量略作修改，加上一個(gè)標(biāo)記y和輸入向量的乘積，得到一個(gè)新的權(quán)值向量，可以看出新的權(quán)

19、值向量和輸入向量的相乘之后符合了標(biāo)記的要求。而非常巧合的是，只需要乘以一個(gè)該訓(xùn)練樣本的標(biāo)記就可以將這兩種情況合為一種情況如公式2-5所示。如此這般的重復(fù)查找錯(cuò)誤樣本和修改加權(quán)向量，直到再也找不到可以使公式2-4成立的樣本為止，此時(shí)得到的加權(quán)向量，即為我們想要的最終g。描述了上面內(nèi)容之后，你很可能有一個(gè)疑問就如何查找錯(cuò)誤樣本點(diǎn)，或者如何確定沒有錯(cuò)誤的點(diǎn)了。一個(gè)簡(jiǎn)單的方式就是將訓(xùn)練樣本編號(hào)，從1到n，整個(gè)訓(xùn)練樣本就有n個(gè)點(diǎn)。以按從1到n的順序不斷查找錯(cuò)誤點(diǎn)，如果沒有錯(cuò)就自動(dòng)的用下一個(gè)樣本點(diǎn)繼續(xù)查找，當(dāng)從1到n這n個(gè)樣本點(diǎn)都沒有產(chǎn)生錯(cuò)誤時(shí)，算法即結(jié)束得到g。將這種方式的算法叫做Cyclic PLA。

20、這時(shí)候就又出來(lái)幾個(gè)新的問題，第一，這個(gè)算法一定會(huì)找到一個(gè)能使所有的樣本都不符合（即都被分對(duì)了類）的情況嗎？就是這個(gè)算法會(huì)不會(huì)停止？第二個(gè)問題這個(gè)算法找到的真的是最好的g嗎？看起來(lái)好像只是在訓(xùn)練樣本中才符合這一性質(zhì)，如果出現(xiàn)新的樣本的話又會(huì)如何呢？第一個(gè)問題下一小節(jié)將進(jìn)行介紹，而其他問題會(huì)在后面的章節(jié)中討論。2.3 Guarantee of PLAPLA算法可行的保障。PLA算法只有在滿足訓(xùn)練樣本是線性可分（linear separable）的情況下才可以停止。什么是線性可分呢？簡(jiǎn)單的說就是存在一條直線能將兩類樣本點(diǎn)完全分開。如圖2-3所示。圖2-3 線性可分與線性不可分其中最左邊的為線性可分的

21、訓(xùn)練樣本，而右邊兩個(gè)圖形為線性不可分的兩種情況，這兩種情況會(huì)在后面的章節(jié)一一解釋。我們需要證明在線性可分的情況下，權(quán)值向量在經(jīng)過一段時(shí)間的修正會(huì)停止，即t次修正會(huì)有一個(gè)上界。首先我們考慮是否每次修正都可以使得權(quán)值向量 變得更好，就是是否會(huì)更接近未知的目標(biāo)函數(shù)所表示的向量。有了這個(gè)思路，我們先假設(shè)目標(biāo)函數(shù)的權(quán)值向量為，可以求解出兩個(gè)向量相似度的度量方式有很多，其中比較常用的一種方式就是求兩個(gè)向量的內(nèi)積，于是我們對(duì)和做內(nèi)積。其中T表示為停止時(shí)的次數(shù)。直接使用這兩個(gè)向量做內(nèi)積，其內(nèi)積越大并不能代表這兩個(gè)向量越接近，因?yàn)橄蛄勘旧淼淖冮L(zhǎng)也可以導(dǎo)致這一現(xiàn)象。因此我們需要求解的是這兩個(gè)向量做歸一化（就是各自

22、除以自身的L1范式得到單位向量）之后的內(nèi)積，這時(shí)它倆的內(nèi)積有了上界即為1，如公式2-6所示。        (公式2-6）乍一看公式2-6完全無(wú)從下手，是未知目標(biāo)向量，是終止時(shí)的向量，也是一個(gè)未知向量，因此思路就是將其中一個(gè)未知量消除，消除的可能性不大，因此選擇消除在公式中的不確定性，如公式2-7所示是解決歸一化之前兩個(gè)向量?jī)?nèi)積的問題。取所有的樣本中的最小乘積（因?yàn)槭窃诰€性可分情況下的目標(biāo)函數(shù)，所以所有的必定大于等于0。）進(jìn)行迭代又因?yàn)槌跏贾翟O(shè)置為0向量，因此    (公式2

23、-7）除了不容易確定之外，的L1范式也不容易得出，如公式2-8是求解L1范式的不等式，其思想如公式2-7。因?yàn)橹挥性诜稿e(cuò)的情況下才會(huì)進(jìn)行改變，那什么時(shí)候是犯錯(cuò)，就是在公式2-4成立的情況，即，該公式等價(jià)于 ，因此如下    （公式2-8）通過公式2-7和公式2-8可以將公式2-6寫成如公式2-9，如下式所示。（公式2-9）將公式2-9中的常數(shù)設(shè)置為C，該公式如公式2-10所示。    (公式2-10）可以看出權(quán)值向量和目標(biāo)函數(shù)內(nèi)積會(huì)以的速度不斷的增長(zhǎng)，但是這種增長(zhǎng)不是沒有限制的，它最多只能等于1。因此有以下結(jié)論，如

24、公式2-11所示。    （公式2-11）求解得到公式2-12的結(jié)論。    （公式2-12）將公式2-12中的值分別使用簡(jiǎn)單的數(shù)字符號(hào)代替，如公式2-13和公式2-14所示。    （公式2-13）    （公式2-14）從公式2-12中就可以看出T是有上界，即在線性可分的情況下PLA算法最終會(huì)停止，找到一個(gè)最接近目標(biāo)函數(shù)的假設(shè)函數(shù)g。2.4 Non-Separable Data線性不可分的數(shù)據(jù)。上一節(jié)的闡述PLA這個(gè)算法一定會(huì)停下來(lái)

25、這一結(jié)論，是建立在存在一個(gè)目標(biāo)函數(shù)，可以將所有的數(shù)據(jù)點(diǎn)都線性分開這個(gè)假設(shè)的基礎(chǔ)之上。對(duì)于一堆復(fù)雜的數(shù) 據(jù)，如何能確定它一定是線性可分的？比如一個(gè)PLA算法運(yùn)行了很長(zhǎng)時(shí)間仍然沒有停止，此時(shí)存在兩種可能性，一是該數(shù)據(jù)集是線性可分的，但是還沒有運(yùn)行結(jié) 束；另一種，壓根就不存在一條直線可以將數(shù)據(jù)集分開，就是壓根這個(gè)算法就不會(huì)終止。假如是后者又該如何處理？首先還是要解釋下為什么會(huì)出現(xiàn)后者，此種情況出現(xiàn)的概率大嗎？出現(xiàn)不可分的一種可能是從未知目標(biāo)函數(shù)中產(chǎn)生的訓(xùn)練樣本存在噪音（noise），如錄入樣本時(shí)有人工的錯(cuò)誤等情況導(dǎo)致數(shù)據(jù)本身不正確，使得最終本可以線性可分的樣本集變得線性不可分了，如圖2-4所示。圖2

26、-4 加入噪音的機(jī)器學(xué)習(xí)流程圖 而噪音占整個(gè)數(shù)據(jù)集的比例一般不會(huì)太大，如圖2-5所示。這種情況下我們又該如何計(jì)算出最佳的假設(shè)g呢？圖2-5 存在噪音時(shí)線性不可分的情況其實(shí)圖2-5已經(jīng)在前面的小節(jié)中出現(xiàn)過。一種新的思路是找出犯錯(cuò)最少的權(quán)值向量 ，如公式2-15所示。（公式2-15）其中表示當(dāng)滿足條件時(shí)輸出1，否則為0。但是這個(gè)公式在數(shù)學(xué)上是NP難問題，我們無(wú)法直接求解，于是我們需要找出一種近似的算法來(lái)求解這個(gè)問題。這里介紹一個(gè)叫pocket的算法，它的本質(zhì)是一種貪心算法，做一簡(jiǎn)單的介紹：1. 也是隨機(jī)的初始化一個(gè)權(quán)值向量2. 隨機(jī)的使用n個(gè)點(diǎn)中的一個(gè)點(diǎn)去發(fā)現(xiàn)是否有錯(cuò)誤（此處與cycli

27、c PLA使用的循環(huán)方式有所不同，不是按順序一個(gè)一個(gè)的查看是否符合條件，而是在n個(gè)點(diǎn)中隨機(jī)的抽取，這種方式可以增加其尋找最優(yōu)解的速度）3. 和PLA一樣使用公式2-5進(jìn)行修正. 4. 如果有了修正，則計(jì)算出剛剛修正過的權(quán)值向量和上一個(gè)權(quán)值向量到底誰(shuí)犯的錯(cuò)誤比較少，將少的保留重復(fù)第2步到第4步的動(dòng)作。假如很長(zhǎng)時(shí)間都沒有新的權(quán)值向量比當(dāng)前的權(quán)值向量犯錯(cuò)更少，則返回該向量作為函數(shù)g。三、Types of Learning各種類型的機(jī)器學(xué)習(xí)問題。3.1 Learning with Different Output Space不同類型的輸出空間。3.1.1 binary classification二元

28、分類問題。前兩章中提到的銀行發(fā)信用卡問題就是一個(gè)典型的二元分類問題，其輸出空間只包含兩個(gè)標(biāo)記+1和-1，分別對(duì)應(yīng)著發(fā)卡與不發(fā)卡。當(dāng)然二元分類問題包含多種情況，如2.3節(jié)中提到過，如圖3-1所示。 圖3-1 a) 線性可分 b) 線性不可分包含噪音 c) 多項(xiàng)式可分 圖3-1a為線性可分（linear binary separable），如可以使用PLA求解；b是包含噪音可以使用pocket求解，而c會(huì)在后面章節(jié)中詳細(xì)敘述，屬于多項(xiàng)式可分解。當(dāng)然解決以上三種 二元分類問題的機(jī)器學(xué)習(xí)方法很多，因?yàn)槎诸悊栴}是機(jī)器學(xué)習(xí)中很重要、核心的問題。 3.1.2 Multicl

29、ass Classification多元分類。有二元分類，就不難想到多元分類的問題，該類問題輸出標(biāo)簽不止兩種，而是1,2,K。這在人們的生活中非常常見，比如給水果的圖像分類，識(shí)別硬幣等等，其主要的應(yīng)用場(chǎng)景就是模式識(shí)別。 3.1.3 Regression回歸分析。該問題的輸出空間為整個(gè)實(shí)數(shù)集上或者在一定的實(shí)數(shù)范圍內(nèi)，這和前面講的分類問題完全不一樣，該輸出不是一種毫無(wú)意義的標(biāo)記，而是有實(shí)際意義的輸出值。比如給定一個(gè)大氣數(shù)據(jù)可以推出明天的天氣等等之類的問題。統(tǒng)計(jì)學(xué)習(xí)對(duì)該類問題的研究比較成熟。 3.1.4 Structured Learning結(jié)構(gòu)學(xué)習(xí)。當(dāng)然還有其他更為復(fù)雜的問題，

30、比如很多很多類型的分類問題。 3.2 Learning with Different Data Label不同的數(shù)據(jù)標(biāo)記。3.2.1 Supervised Learning監(jiān)督學(xué)習(xí)。知道數(shù)據(jù)輸入的同時(shí)還知道數(shù)據(jù)的標(biāo)記。就相當(dāng)于告訴你題目的同時(shí)還告訴你答案，讓你在這種環(huán)境下學(xué)習(xí)，稱之為監(jiān)督學(xué)習(xí)（supervised learning）或者叫有師學(xué)習(xí)（learning with a teacher），之前討論的一些算法都是這類問題。舉個(gè)例子，硬幣分類問題，如圖3-2所示，其中橫軸標(biāo)示硬幣的大小，縱軸標(biāo)示硬幣聚集的堆。 圖3-2 有監(jiān)督的多類別分類問題 其中這幾種類別的

31、硬幣已經(jīng)被各種不同的顏色所標(biāo)示好。 3.2.2 Unsupervised Learning無(wú)監(jiān)督學(xué)習(xí)。這是一種沒有標(biāo)示（就是沒有輸出y）的問題，就是不告訴你題目的正確答案讓你自己去尋找，再以硬幣分類為例進(jìn)行闡述，如圖3-3所示。 圖3-3 無(wú)監(jiān)督的多類別分類問題 這種類型的問題最常見的是聚類或者叫分群（clustering），從圖中不難看出無(wú)標(biāo)示的難度比有標(biāo)示的難度增加不少，而且極有可能犯錯(cuò)，但是這 種問題卻擁有廣泛的應(yīng)用場(chǎng)景（畢竟標(biāo)示需要花費(fèi)大量人力物力），如將新聞按照不同的主題聚類，按用戶的屬性將用戶聚成不同類型的用戶群等等。除了聚類之外還有其他的無(wú)監(jiān)督學(xué)習(xí)，

32、如密度評(píng)估（density estimation）和離群點(diǎn)檢測(cè)（outlier detection）等等。 3.2.3 Semi-supervised Learning半監(jiān)督學(xué)習(xí)。是否能在監(jiān)督式學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)之間取一個(gè)中庸的方法呢？答案是可以的，就是半監(jiān)督學(xué)習(xí)，它通過少量有標(biāo)記的訓(xùn)練點(diǎn)和大量無(wú)標(biāo)記的訓(xùn)練點(diǎn)達(dá)到學(xué)習(xí)的 目的。還是以硬幣為例，如圖3-4所示。這種類型的例子也有很多，比如圖像的識(shí)別，很多情況下我們不可能把每張圖片都做上標(biāo)記（因?yàn)樽鲞@種標(biāo)記需要耗費(fèi)大 量的人力物力，是一種昂貴的行為），此時(shí)，使用半監(jiān)督學(xué)習(xí)是一種不錯(cuò)的選擇。 圖3-4 半監(jiān)督學(xué)習(xí) 3.2.

33、4 Reinforcement Learning強(qiáng)化學(xué)習(xí)。前面三個(gè)是機(jī)器學(xué)習(xí)中最傳統(tǒng)的三種方式，除此之外，還有一種方式是通過對(duì)一個(gè)行為作出獎(jiǎng)勵(lì)或者懲罰，以此獲得的輸出，進(jìn)而進(jìn)行學(xué)習(xí)，這種學(xué)習(xí)方式稱之為強(qiáng)化學(xué)習(xí)。一般可以表示為，其中向量還是為輸入向量，表示一種輸出，注意并不一定是最佳輸出，最后一項(xiàng)是對(duì)輸出做出的評(píng)判。比如一個(gè)廣告系統(tǒng)可以寫成如下形式 。 3.3 Learning with Different Protocol不同方式獲取數(shù)據(jù)。對(duì)此節(jié)的內(nèi)容進(jìn)行簡(jiǎn)單闡述，在不同的協(xié)議中可以將機(jī)器學(xué)習(xí)分為三大類：1. 批量（batch）學(xué)習(xí)就是將很多數(shù)據(jù)一次性的給算法進(jìn)行學(xué)習(xí)，最常見的方式；

34、2. 在線（online）學(xué)習(xí)就是一點(diǎn)一點(diǎn)將數(shù)據(jù)傳輸進(jìn)去，如PLA和增強(qiáng)學(xué)習(xí)都適用于這種形式；3. 主動(dòng)（active）學(xué)習(xí)是主動(dòng)提出問題讓算法解決，可以節(jié)省大量的訓(xùn)練和標(biāo)記消耗。 3.4 Learning with Different Input Space不同的輸入空間。輸入又可以稱之為特征（features），其主要分為三種：1. 具體特征（Concrete Features），具體特征最大特點(diǎn)就是便于機(jī)器學(xué)習(xí)的處理，也是基礎(chǔ)篇中主要討論的情形。這種情況是人類或者機(jī)器通過一定的方式提取獲得的，具有實(shí)用性。2. 原始特征（Raw Features），如圖片的像素等等，是最為常見到

35、的資料，但是需要經(jīng)過處理，轉(zhuǎn)換成具體特征，才容易使用，實(shí)用性不太大。3. 抽象特征（Abstract Features），如一些ID之類的看似無(wú)意義的數(shù)據(jù)，這就更需要特征的轉(zhuǎn)換、提取等工作（相對(duì)于原始特征而言），幾乎沒有實(shí)用性。四、Feasibility of Learning機(jī)器學(xué)習(xí)的可能性。4.1 Learning is Impossible學(xué)習(xí)可能是做不到的。在訓(xùn)練樣本集（in-sample）中，可以求得一個(gè)最佳的假設(shè)g，該假設(shè)最大可能的接近目標(biāo)函數(shù)f，但是在訓(xùn)練樣本集之外的其他樣本（out-of-sample）中，假設(shè)g和目標(biāo)函數(shù)f可能差別很遠(yuǎn)。 4.2 Probabilit

36、y to the Rescue可能的補(bǔ)救方式。通過上一小節(jié)，我們得到一個(gè)結(jié)論,機(jī)器學(xué)習(xí)無(wú)法求得近似目標(biāo)函數(shù)f的假設(shè)函數(shù)g?；貞浽谝郧皩W(xué)過的知識(shí)中，有無(wú)遇到過類似的問題：通過少量的已知樣本推論整個(gè)樣本集的情況。是否想到一個(gè)曾經(jīng)學(xué)過的知識(shí)，其實(shí)就是概率統(tǒng)計(jì)中的知識(shí)。通過一個(gè)例子來(lái)復(fù)習(xí)下該知識(shí)。有一個(gè)罐子，這個(gè)罐子里盛放著橙色和綠色兩種顏色的小球，我們?nèi)绾卧诓徊楸樗行∏虻那闆r下，得知罐子中橙子小球所占的比例呢？抽取樣本，如圖4-1所示。 圖4-1 抽取樣本 假設(shè)罐子中橙色小球的概率為，不難得出綠色小球的概率為，其中 為未知值；而通過抽樣查出的橙色小球比例為，綠色小球的比例為 ，

37、 是從抽樣數(shù)據(jù)中計(jì)算出的，因此為已知值。如何通過已知樣本，求得未知的樣本？可以想象到，在很大的幾率上接近的結(jié)果。因?yàn)樵诠拮永锏男∏蚓鶆驍嚢柽^后，抽出小球中的橙色小球比例很有可能接近整個(gè)罐子中橙色小球的比例，不難想象在抽出的小球數(shù)量等于罐中小球數(shù)量時(shí)，兩者完全一致。這其中不了解的是，到底有多大的可能性兩者接近？此處使用數(shù)學(xué)的方式給予答案，如公式4-1所示。     (公式4-1） 該公式稱之為霍夫丁不等式（Hoeffding's Inequality），其中P為概率符號(hào)， 表示與的接近程度， 為此程度的下界，N表示樣本數(shù)量，其中

38、不等式左邊表示 與 之間相差大于某值時(shí)的概率。從該不等式不難得出，隨著樣本量的增大， 與 相差較大的概率就不斷變小。兩者相差越多，即越大，該概率越低，就意味著 與 相等的結(jié)論大概近似正確（probably approximately correct PAC）。同時(shí)可以得出當(dāng)N足夠大時(shí)，能夠從已知的 推導(dǎo)出未知的 。 4.3 Connection to Learning聯(lián)系到機(jī)器學(xué)習(xí)上。上一節(jié)得出的結(jié)論可以擴(kuò)展到其他應(yīng)用場(chǎng)景，其中包括機(jī)器學(xué)習(xí)。為方便理解，做一個(gè)對(duì)比表，如表4-1所示。 表4-1 機(jī)器學(xué)習(xí)與統(tǒng)計(jì)中的對(duì)比罐子小球機(jī)器學(xué)習(xí)未知的橙色小球比例某一確定的假設(shè)在整個(gè)X輸

39、入空間中，輸入向量x滿足條件 的占整個(gè)輸入空間的比例抽取的小球整個(gè)罐子中的小球訓(xùn)練輸入樣本集 整個(gè)數(shù)據(jù)集X橙色小球假設(shè)h作用于此輸入向量x與給定的輸出不相等綠色小球假設(shè)h作用于此輸入向量x與給定的輸出相等小球樣本是從罐子中獨(dú)立隨機(jī)抽取的輸入樣本x是從整個(gè)數(shù)據(jù)集D中獨(dú)立隨機(jī)選擇的 更通俗一點(diǎn)的解釋上表表達(dá)的內(nèi)容：訓(xùn)練輸入樣本集類比隨機(jī)抽取的小球樣本；此樣本集中，先確定一個(gè)假設(shè)函數(shù)h，滿足條件的輸入向量x占整個(gè)樣本的比例類比于橙色小球在隨機(jī)抽取小球樣本的比例，寫成公式的形式可以入公式4-2所示；因此使用上一節(jié)中的PAC（可能近似正確的理論），在整個(gè)輸入空間中這個(gè)固定的假設(shè)函數(shù)h同目標(biāo)函數(shù)

40、f不相等的輸入量占整個(gè)輸入空間數(shù)量的概率 （ 的取值如公式4-3所示）與上述隨機(jī)樣本中兩個(gè)函數(shù)不相等的樣本數(shù)占抽樣數(shù)的比例 相同，這一結(jié)論也是大概近似正確的。 （公式4-2）（公式4-3） 其中N為隨機(jī)獨(dú)立抽樣的樣本數(shù)，X為整個(gè)輸入空間， 滿足條件為1否則為0，E為取期望值。對(duì)1.4節(jié)的機(jī)器學(xué)習(xí)流程圖進(jìn)行擴(kuò)展，得到如圖4-2所示。 圖4-2 引入統(tǒng)計(jì)學(xué)知識(shí)的機(jī)器學(xué)習(xí)流程圖 其中虛線表示未知概率P對(duì)隨機(jī)抽樣以及概率 的影響，實(shí)線表示已經(jīng)隨機(jī)抽出的訓(xùn)練樣本及某一確定的假設(shè)對(duì)比例 的影響。得出的結(jié)論如下：對(duì)任意已確定的假設(shè)函數(shù)h，都可以通過已知的求出未知的 。

41、以后我們將使用和 這種專業(yè)的符號(hào)，分別表示在某一確定的假設(shè)函數(shù)h中，隨機(jī)抽樣得到的樣本錯(cuò)誤率和整個(gè)輸入空間的錯(cuò)誤率，同樣可以使用霍夫丁不等式對(duì)以上得到的結(jié)論做出相應(yīng)的數(shù)學(xué)表達(dá)，如公式4-4所示。     （公式4-4） 但是，我們想得到的不是給定一個(gè)已確定的假設(shè)函數(shù)h，通過樣本的錯(cuò)誤比例來(lái)推斷出在整個(gè)輸入空間上的錯(cuò)誤概率，而是在整個(gè)輸入空間上同目標(biāo)函數(shù)f最接近的假設(shè)函數(shù)h。那如何實(shí)現(xiàn)最接近呢？說白了錯(cuò)誤率最低。只需在上述結(jié)論上再加一個(gè)條件，即錯(cuò)誤比例 很小即可?？偨Y(jié)下，在結(jié)論基礎(chǔ)之上，加上 很小，可以推出 也很小，即在整個(gè)輸入空間中h

42、f。上面說了那么多，可能很多人已經(jīng)糊涂了，因?yàn)檫@并不是一個(gè)學(xué)習(xí)問題，而是一個(gè)固定假設(shè)函數(shù)h，判斷該假設(shè)函數(shù)是否滿足上述性質(zhì)，這準(zhǔn)確的講是一種確認(rèn)（Verification），確實(shí)如此，這種形式不能稱為學(xué)習(xí)，如圖4-3所示。 圖4-3 確認(rèn)流程圖 4.4 Connection to Real Learning聯(lián)系到真正的學(xué)習(xí)上。首先我們要再次確認(rèn)下我們上一小節(jié)確定的概念，要尋找的是一個(gè)使得 很小的假設(shè)函數(shù)h，這樣就可以使得h和目標(biāo)函數(shù)f在整個(gè)輸入空間中也很接近。繼續(xù)以丟硬幣為例，形象的觀察這種學(xué)習(xí)方法有無(wú)問題，如圖4-4所示。 圖4-4 丟硬幣的例子 假設(shè)

43、有150個(gè)人同時(shí)丟五次硬幣，統(tǒng)計(jì)其中有一個(gè)人丟出五次全部正面向上的概率是多少，不難得出一個(gè)人丟出五次正面向上的概率為 ，則150人中有一人丟出全正面向上的概率為 。這其中拋出正面類比于綠色小球的概率也就是。當(dāng)然從選擇的角度肯定要選擇犯錯(cuò)最小的，即正面盡可能多的情況，此例中不難發(fā)現(xiàn)存在全部都為正面的概率是非常大的，此處應(yīng)注意，選擇全為正面的或者說 為0 并不正確（因?yàn)橄氲玫降慕Y(jié)果是 ，而不是99%）這一結(jié)論與真實(shí)的情況或者說 差的太遠(yuǎn)（我們不僅僅要滿足 很小條件，同時(shí)還要使得 與 不能有太大差距）。因此這種不好的樣本的存在得到了很糟糕的結(jié)果。上面介紹了壞的樣例（bad sample），把本來(lái)很高

44、的，通過一個(gè)使得的壞抽樣樣本進(jìn)行了錯(cuò)誤的估計(jì)。到底是什么造成了這種錯(cuò)誤，要深入了解。我們還需要介紹壞的數(shù)據(jù)（bad data）的概念。（這里寫一下自己的理解，壞的樣本bad sample壞的數(shù)據(jù)bad data）壞的數(shù)據(jù)就是使得 與 相差很大時(shí)，抽樣到的N個(gè)輸入樣本（我的理解不是這N個(gè)輸入樣本都不好，可能只是有幾個(gè)不好的樣本，導(dǎo)致該次抽樣的數(shù)據(jù)產(chǎn)生不好的結(jié)果，但此次抽樣的數(shù)據(jù) 集被統(tǒng)一叫做壞的數(shù)據(jù)），根據(jù)霍夫丁不等式這種情況很少出現(xiàn)，但是并不代表沒有，特別是當(dāng)進(jìn)行假設(shè)函數(shù)的選擇時(shí)，它的影響會(huì)被放大，以下進(jìn)行一個(gè)具體的說 明，如表4-2所示。 表4-2 單個(gè)假設(shè)函數(shù)時(shí)的霍夫丁不等式&#

45、160;D1D2D1126D5678霍夫丁hBAD    BAD  計(jì)算所有不好的D出現(xiàn)的概率如公式4-5所示。     （公式4-5） 單一假設(shè)函數(shù)中不好的D出現(xiàn)的概率其實(shí)不算高，但是當(dāng)在做選擇時(shí)，面對(duì)的是從整個(gè)假設(shè)空間選出的無(wú)數(shù)種可能的假設(shè)，因此不好D的計(jì)算就有所改變，當(dāng)然我們先討論假設(shè)函數(shù)是有限多種的情況，如表4-3所示。 表4-3 M個(gè)假設(shè)情況下的霍夫丁不等式 D1D2D1126D5678霍夫丁 BAD   

46、 BAD   BAD      BADBAD   BAD           BAD    BAD ALLBADBAD   BAD ? 這其中包含了M個(gè)假設(shè)，而不好的D不是由單一假設(shè)就確定的，而是只要有一個(gè)假設(shè)在此抽樣D上表現(xiàn)不好則該抽樣被標(biāo)記為壞的，因此霍夫

47、丁不等式如公式4-6所示。 (聯(lián)合上界)    (公式4-6) 因此如果|H|=M的這種有限情況下，抽樣樣本N足夠大時(shí)，可以確保假設(shè)空間中每個(gè)假設(shè)都滿足。如果通過算法找出的g滿足 ，則通過PAC的規(guī)則可以保證。五、Training versus Testing訓(xùn)練與測(cè)試。5.1 Recap and Preview回顧以及預(yù)覽。首先回顧一下上一章學(xué)過的內(nèi)容，學(xué)習(xí)在何種情況下是可行的。在可學(xué)習(xí)的數(shù)據(jù)來(lái)自于一個(gè)統(tǒng)一的分布（distribution），且假設(shè)空間中的假設(shè)函數(shù)為有限個(gè)的情況下，其學(xué)習(xí)流程圖如圖5-1所示。 圖5-1 一

48、種可行的學(xué)習(xí)流程圖 此圖和前幾章中的流程圖最大的不同是加入了一個(gè)模塊，準(zhǔn)確的說是一種假設(shè)情況，假設(shè)訓(xùn)練數(shù)據(jù)樣本和未知的測(cè)試樣本來(lái)自同一的分布（這點(diǎn)尤為重要現(xiàn)有 的大部分機(jī)器學(xué)習(xí)算法都從這點(diǎn)出發(fā)，好像遷移學(xué)習(xí)不是），并且假設(shè)空間的假設(shè)是有限的情況下，即|H| = M，M是有限的值，在訓(xùn)練樣本N足夠大，假設(shè)空間中的所有的假設(shè)都會(huì)遵循PAC準(zhǔn)則，確保，每一個(gè)假設(shè)函數(shù)都可以滿足近似相等的性質(zhì)，因此可以通過算法在這些假設(shè)空間中找一個(gè)的假設(shè)，同樣PAC也保證了。因此可以說機(jī)器學(xué)習(xí)在這種情況下是可行的。（訓(xùn)練樣本和測(cè)試樣本滿足同分布，假設(shè)空間有限，并且訓(xùn)練數(shù)據(jù)足夠大）接著回顧一下之前四章的內(nèi)容：第

49、一章介紹了存在一個(gè)未知的目標(biāo)函數(shù)f，機(jī)器學(xué)習(xí)的任務(wù)是找出一個(gè)假設(shè)函數(shù)g，使得假設(shè)g和目標(biāo)函數(shù)f很接近，即 ，用第四章的概念可以解釋為在測(cè)試時(shí)的錯(cuò)誤率接近零，即。第二章介紹了在訓(xùn)練時(shí)使假設(shè)函數(shù)g和目標(biāo)函數(shù)f很接近就可以了，用第四章的概念可以解釋為訓(xùn)練時(shí)的錯(cuò)誤率接近零，即 。第三章介紹了一種機(jī)器學(xué)習(xí)最基礎(chǔ)、最核心的方法：使用批量的數(shù)據(jù)和監(jiān)督式的學(xué)習(xí)來(lái)做二元分類。第四章介紹了在假設(shè)空間不是太多，即假設(shè)函數(shù)有限的情況下，訓(xùn)練時(shí)的錯(cuò)誤率和測(cè)試時(shí)的錯(cuò)誤率很接近，即 。從以上各章節(jié)中可以看出將機(jī)器學(xué)習(xí)分為了兩個(gè)主要問題來(lái)解決：1. 是否能確保是足夠接近的？這是連接第一章和第二章的橋梁。2. 如何使得足夠?。?/p>

50、這是第二章的內(nèi)容，當(dāng)然后面的章節(jié)還會(huì)繼續(xù)介紹其他的技巧。在第四章中介紹的假設(shè)空間的大小M與上述兩個(gè)問題存在何種關(guān)系？通過一個(gè)表格進(jìn)行分析，如表5-1所示。 表5-1 M的大小與兩個(gè)條件的關(guān)系 M很小的時(shí)候M很大的時(shí)候第一個(gè)問題滿足，M小的時(shí)候，兩者不相等的幾率變小了不滿足，M大的時(shí)候，兩者不相等的幾率變大了第二個(gè)問題不滿足，在M變小時(shí)，假設(shè)的數(shù)量變小，算法的選擇變小，可能無(wú)法找到 接近0的假設(shè)。滿足，在M變大時(shí)，假設(shè)的數(shù)量變大，算法的選擇變大，找到 接近0的假設(shè)的幾率變大。 顯然M趨于無(wú)窮大時(shí)，表現(xiàn)非常不好，如何解決這個(gè)問題呢？需要尋找一個(gè)小于無(wú)限大M的替代值，并

51、且這個(gè)值還和假設(shè)空間有關(guān)系，用 表示。以后的幾章中討論如何在M為無(wú)限大時(shí)，保證。 5.2 Effective Number of Lines線的有效數(shù)量。第四章的結(jié)尾求出了在有限假設(shè)空間中 的上限，當(dāng)時(shí)，使用聯(lián)合上限（union bound），實(shí)際不等式的上界被放大了太多。假設(shè)在假設(shè)空間中包含無(wú)限多的假設(shè)函數(shù)，則此上限為無(wú)窮大，而真正合理的上界是不應(yīng)該大于1（因?yàn)槭莻€(gè)概率問題，其最大值也不會(huì)超過1）。造成這一問題的原因是什么呢？很容易想到這個(gè)聯(lián)合上界是不是過于寬松了。對(duì)，問題確實(shí)出在此處，學(xué)過集合的同學(xué)肯定都知道，兩個(gè)集合的或集寫成兩個(gè) 集合相加的形式時(shí)，一定要減去它倆的交集。而我們

52、這里的問題出在，這幾個(gè)集合不僅相交，而且交集很大，卻沒有被減掉，因此上界過于寬松。繼續(xù)回到假設(shè)空間的問題上，兩個(gè)假設(shè)函數(shù)出現(xiàn)完全相同壞數(shù)據(jù)的可能性很大，如上一章表4-3的h2和h3就出現(xiàn)了幾個(gè)相同的壞數(shù)據(jù)。舉個(gè)簡(jiǎn)單的例 子，在二維平面上進(jìn)行二元線性分類，假設(shè)兩條直線h1和h2很接近，那么就不難得出兩種假設(shè)的壞數(shù)據(jù)也基本重疊，其實(shí)這種數(shù)據(jù)的分布應(yīng)為圖5-2所示。 圖5-2 不好數(shù)據(jù)的分布 如果可以將這無(wú)限大的假設(shè)空間分成有限的幾類，按照樣本數(shù)據(jù)劃分方式進(jìn)行分類，如是 和 被定義為兩種不同的類別。這一思路的原因個(gè)人認(rèn)為有兩個(gè)：一是這本身就是一個(gè)數(shù)據(jù)分類錯(cuò)誤率的問題，從數(shù)據(jù)分類方

53、式著手也很切要害；二是訓(xùn)練樣本必然是有限的，分類的方式也是有限的，可以將無(wú)限的問題轉(zhuǎn)換成有限的問題。先從最簡(jiǎn)單的分一個(gè)樣本點(diǎn)著手，假設(shè)是一個(gè)二元線性分類問題，一個(gè)樣本的例子比較容易理解，如圖 5-3所示。 圖5-3 單一訓(xùn)練樣本分類問題 一個(gè)樣本點(diǎn)分類可以有幾種方式？無(wú)非兩種，該樣本為正，或者為負(fù)。而假設(shè)空間中的所有假設(shè)或者稱之為直線，都只能分屬于這兩種情況。繼續(xù)觀察兩個(gè)樣本的情況，如圖5-4所示。 圖5-4 兩個(gè)訓(xùn)練樣本分類問題 這種情況可以分為如圖所示的4種情況，也就是所有的直線可以分屬這4個(gè)類中。繼續(xù)觀察三個(gè)樣本的情況，如圖5-5所示。 

54、圖5-5三個(gè)訓(xùn)練樣本分類問題 出現(xiàn)了8種情況，但是如果樣本的分布轉(zhuǎn)變一下呢？比如三排成一線，就只有6類，如圖5-6所示。 圖5-6三個(gè)訓(xùn)練樣本排成一條直線的分類問題 繼續(xù)觀察四個(gè)樣本的情況，如圖5-7所示。 圖5-7四個(gè)訓(xùn)練樣本分類問題 說明一下此處只畫了8種情況（其中一種還不可能線性可分），因?yàn)橹苯訉⑵漕嵉咕涂梢缘玫绞Ｏ碌?種情況，完全是對(duì)稱的，所示總共有14種可以劃分的種類。不再無(wú)休止的繼續(xù)舉例，做一個(gè)總結(jié)。從上述內(nèi)容可以看出，將無(wú)限多的假設(shè)和有限多的訓(xùn)練數(shù)據(jù)建立了一種關(guān)系，如圖5-為是樣本為二維時(shí)，二元線性可分的類型與樣本數(shù)量的關(guān)系圖。&

55、#160;圖5-7二元線性可分的類型與樣本數(shù)量的關(guān)系圖 從圖中可以推到出下述公式成立，如公式5-1所示。     （公式5-1） 其中N在大于3的情況下，必然遠(yuǎn)小于2的N次方。其實(shí)即使是等于2的N次方，也可以說明右邊的式子在N趨于無(wú)窮大的情況下是一個(gè)趨近于零的值，原因很簡(jiǎn)單，e這個(gè)自然常數(shù)的值大于2.7也大于2，因此右式是個(gè)遞減函數(shù)，此處不做過多的推導(dǎo)了。 5.3 Effective Number of Hypotheses超平面的有效數(shù)量。上一節(jié)的內(nèi)容介紹了，將無(wú)限多的假設(shè)轉(zhuǎn)換成為有限多種類型上。這種以訓(xùn)練樣本的

56、分類情況來(lái)確定一類假設(shè)的方式，稱之為二分類（dichotomy），使用符號(hào)表示為H(x1,x2,xN)，即假設(shè)空間在特定的訓(xùn)練樣本集合（x1,x2,xN）上被分為幾類。如表5-2所示，對(duì)二分類空間與假設(shè)空間做出比較。 表5-2 假設(shè)空間與二分空間的對(duì)比 假設(shè)空間H二分H(x1,x2,xN)舉例在空間中所有的線×, , ××,.大小無(wú)限大上限為 以二元線性可分的情況舉例，假設(shè)空間是在二維平面上的所有直線，它一定是無(wú)限的；而二分空間就是能將二維平面上的樣本點(diǎn)劃分為不同情況的直線種類（不同情況具體是什么意思，參見上一節(jié)），而它最多只是，因此

57、是有限的。現(xiàn)在的思路就是使用H(x1,x2,xN)的大小來(lái)取代無(wú)限大的M，如何取代呢？會(huì)發(fā)現(xiàn)H(x1,x2,xN)的取值取決于訓(xùn)練樣本的分布情況，因此要取消這種依賴的關(guān)系，取消的方式就是尋找在樣本點(diǎn)個(gè)數(shù)固定的情況下最大的H(x1, x2, , xN)取值，公式如5-2所示。     (公式5-2） 符號(hào)表示一個(gè)比無(wú)限大的M小且與假設(shè)空間H有關(guān)的關(guān)于樣本大小N的函數(shù)。這一函數(shù)叫做成長(zhǎng)函數(shù)（growth function）。如何具體化（就是只使用訓(xùn)練樣本的大小N來(lái)表達(dá)出該函數(shù)）成長(zhǎng)函數(shù)成為接下來(lái)需要解決的問題。先從簡(jiǎn)單的例子著手一步一步的

58、推導(dǎo)到在感知器下該函數(shù)的具體表達(dá)。第一個(gè)例子是舉一個(gè)最簡(jiǎn)單的情況，在一維實(shí)數(shù)的情況下，并且限制分類的正方向指向固定的一邊，求解成長(zhǎng)函數(shù)。給這一分類情況起名叫做正射線（positive rays），如圖5-8所示。 圖5-8 正射線的二元分類 用數(shù)學(xué)的方式表示如下：1. 輸入數(shù)據(jù)樣本為，R為實(shí)數(shù)集；1. 其假設(shè)空間可以表示為，其中a是閾值，表示大于某個(gè)實(shí)數(shù)a數(shù)據(jù)被分為正類，反之為負(fù)類。1. 本質(zhì)是在一維平面上的感知器，只是比一維感知器少了相反方向可以為正的情況（此種分類已經(jīng)規(guī)定向右的方向?yàn)檎?，而一維感知器可以規(guī)定相反的方向也為正，就比它多了一倍）。正射線分類的成長(zhǎng)函數(shù)很容易得

59、出，如公式5-3所示。 （公式5-3） 求出的思路很簡(jiǎn)單， N個(gè)點(diǎn)兩兩之間的空隙個(gè)數(shù)為N-1，再加上端點(diǎn)的個(gè)數(shù)2（左端點(diǎn)是全正，右端點(diǎn)是全負(fù)），且可得出在N很大的情況下公式5-4成立。 （公式5-4） 課后題中提到了不規(guī)定正方向的情況下成長(zhǎng)函數(shù)的計(jì)算即求在一維情況下感知器的分類情況，如公式5-5所示。 （公式5-5） 求解的思路為，在N個(gè)點(diǎn)上兩兩之間有2·(N-1)中可能，因?yàn)檎较驔]有規(guī)定了，所以此處比正射線的種類多出了一倍，剩下樣本點(diǎn)都為正類，或者都為負(fù)，這兩種情形，因此再加上一個(gè)2。下一個(gè)例子還是在一維空間里，與正射線分類不同的是，這是一種中間為正兩邊為負(fù)的情況，叫做中間為正的分類（positive interval），如圖5-9所示。 圖5-9 中間為正的分類 其成長(zhǎng)函數(shù)不難求出，如公式5-6所示。     (公式5-6） 求解思路如下：此為一個(gè)兩端都不固定范圍的分類（正射線是固定一個(gè)端點(diǎn)，直接到頭都為一種類型），因此在N+1個(gè)空隙中選擇兩個(gè)作為端點(diǎn)（樣本兩兩之間有N-1個(gè)空隙，兩端還各有一個(gè)），因此為一個(gè)組合問題 ，但是少算了一種全負(fù)情況，即兩個(gè)端點(diǎn)在同