復(fù)試人工智能機(jī)器學(xué)習(xí)05

1、第5章 評(píng)估假設(shè)動(dòng)機(jī)估計(jì)假設(shè)精度采樣理論基礎(chǔ)推導(dǎo)置信區(qū)間的一般方法兩個(gè)假設(shè)錯(cuò)誤率間的差異學(xué)習(xí)算法比較小結(jié)和補(bǔ)充讀物第5章 評(píng)估假設(shè)對(duì)假設(shè)的精度進(jìn)行評(píng)估是機(jī)器學(xué)習(xí)中的基本問(wèn)題。用統(tǒng)計(jì)方法估計(jì)假設(shè)精度，主要為解決以下三個(gè)問(wèn)題：1）已知一個(gè)假設(shè)在有限數(shù)據(jù)樣本上觀察到的精度，怎樣估計(jì)它在其他實(shí)例上的精度？2）如果一個(gè)假設(shè)在某些數(shù)據(jù)樣本上好于另一個(gè)，那么一般情況下該假設(shè)是否更準(zhǔn)確？3）當(dāng)數(shù)據(jù)有限時(shí)，怎樣高效地利用這些數(shù)據(jù)，通過(guò)它們既能學(xué)到假設(shè)，還能估計(jì)其精度？5.1 動(dòng)機(jī)對(duì)假設(shè)進(jìn)行性能評(píng)估的原因包括：1）為了知道是否可以使用該假設(shè)2）對(duì)假設(shè)的評(píng)估是許多學(xué)習(xí)方法的重要的組成部分5.1 動(dòng)機(jī)當(dāng)數(shù)據(jù)十分充足時(shí)

2、，假設(shè)精度的估計(jì)相對(duì)容易。然而當(dāng)給定的數(shù)據(jù)集非常有限時(shí)，要學(xué)習(xí)一個(gè)概念并估計(jì)其將來(lái)的精度，存在兩個(gè)很關(guān)鍵的困難：1）估計(jì)的偏差（Bias in the estimate）。首先，學(xué)習(xí)到的概念在訓(xùn)練樣例上的觀察精度通常不能很好地用于估計(jì)將來(lái)樣例上的精度。尤其在學(xué)習(xí)器采用了很大的假設(shè)空間并過(guò)度擬合訓(xùn)練樣例時(shí)2）估計(jì)的方差（Variance in the estimate）。即使假設(shè)精度在獨(dú)立的無(wú)偏測(cè)試樣例上測(cè)量，得到的精度仍可能與真實(shí)精度不同，這取決于特定測(cè)試樣例集合的組成。測(cè)試樣例越少，產(chǎn)生的方差越大。5.2 估計(jì)假設(shè)精度在評(píng)估一個(gè)假設(shè)時(shí)，一般對(duì)估計(jì)這個(gè)假設(shè)對(duì)未來(lái)實(shí)例的分類的精度更感興趣。同時(shí)，

3、也需要知道這一精度估計(jì)中的誤差（即與此估計(jì)相聯(lián)系的誤差門限）學(xué)習(xí)問(wèn)題的框架如下：有一所有可能實(shí)例的空間X（如所有人的集合），其上定義了若干個(gè)目標(biāo)函數(shù)（如計(jì)劃本年度購(gòu)買滑雪板的人）。假定X不同實(shí)例具有不同的出現(xiàn)頻率，一種合適的建模方式是，假定存在一未知的概率分布D，它定義了X中每一實(shí)例出現(xiàn)的概率（如19歲的人的概率比109歲的人的概率高）。注意D并沒有說(shuō)明x是一正例還是一反例，只確定了其出現(xiàn)概率。學(xué)習(xí)任務(wù)是在假設(shè)空間H上學(xué)習(xí)一個(gè)目標(biāo)概念（即目標(biāo)函數(shù)）f。目標(biāo)函數(shù)f的訓(xùn)練樣例由施教者提供給學(xué)習(xí)器：每一個(gè)實(shí)例按照分布D被獨(dú)立地抽取，然后連同正確的目標(biāo)值f(x)被提供給學(xué)習(xí)器。5.2 估計(jì)假設(shè)精度在一

4、般的框架中，感興趣的是以下兩個(gè)問(wèn)題：1）給定假設(shè)h和包含若干按D分布隨機(jī)抽取的樣例的數(shù)據(jù)集，如何針對(duì)將來(lái)按同樣分布抽取的實(shí)例，得到對(duì)h的精度的最好的估計(jì)？2）這一精度估計(jì)的可能的誤差是多少？5.2.1 樣本錯(cuò)誤率和真實(shí)錯(cuò)誤率需要確切地分出兩種精度（或兩種錯(cuò)誤率）。其一是可用數(shù)據(jù)樣本上該假設(shè)的錯(cuò)誤率。其二是在分布為D的整個(gè)實(shí)例集合上該假設(shè)的錯(cuò)誤率。它們分別被稱為樣本錯(cuò)誤率和真實(shí)錯(cuò)誤率。定義：假設(shè)h關(guān)于目標(biāo)函數(shù)f和數(shù)據(jù)樣本S的樣本錯(cuò)誤率（標(biāo)記為errors(h)為：定義：假設(shè)h關(guān)于目標(biāo)函數(shù)f和分布的真實(shí)錯(cuò)誤率（標(biāo)記為error (h)，為h按分布隨機(jī)抽取實(shí)例被誤分類的概率。本節(jié)所考慮的主要問(wèn)題是e

5、rrors(h)在何種程度上提供了對(duì)error (h)的估計(jì)？5.2.2 離散值假設(shè)的置信區(qū)間基于某離散值假設(shè)h在樣本S上觀察到的樣本錯(cuò)誤率估計(jì)它的真實(shí)錯(cuò)誤率。其中 樣本S包含n個(gè)樣例，它們的抽取按照概率分布，抽取過(guò)程是相互獨(dú)立的，并且不依賴于h。 n=30 假設(shè)h在這n個(gè)樣例上犯了r個(gè)錯(cuò)誤（例如errors(h)=r/n)已知這些條件，統(tǒng)計(jì)理論可給出以下斷言： 沒有其他信息的話， error (h)最可能的值是errors(h) 有大約95%的可能性，真實(shí)錯(cuò)誤率處于下面的區(qū)間內(nèi)：5.2.2 離散值假設(shè)的置信區(qū)間上面的95%置信區(qū)間表達(dá)式可推廣到一般情形以計(jì)算任意置信度。一般表達(dá)式為：該表達(dá)式

6、只提供了近似的置信區(qū)間，在至少包含30個(gè)樣例并且樣本錯(cuò)誤率不太靠近0或1時(shí)很接近真實(shí)情況。判斷這一近似是否接近真實(shí)，更精確的規(guī)則為n errors(h)(1- errors(h)=55.3 采樣理論基礎(chǔ)隨機(jī)變量（random variable）可看作是有概率輸出的一個(gè)實(shí)驗(yàn)的名字。它的值為實(shí)驗(yàn)的輸出結(jié)果。某隨機(jī)變量Y的概率分布（probability distribution）指定了取值為任一可能值yi的可能性Pr(Y=yi)隨機(jī)變量Y的期望值（expected value）或均值（mean）為隨機(jī)變量的方差（variance）為它描述了Y關(guān)于其均值分布的寬度或分散度5.3 采樣理論基礎(chǔ)Y的標(biāo)準(zhǔn)

7、差（Standard deviation）為通常用符號(hào)來(lái)表示正態(tài)分布（二項(xiàng)分布（Binominal distribution）是在硬幣投擲問(wèn)題中，若出現(xiàn)正面的概率為p，那么在n個(gè)獨(dú)立的實(shí)驗(yàn)中出現(xiàn)r次正面的分布情況正態(tài)分布（Normal distribution）是一個(gè)鐘形的概率分布，它在許多自然現(xiàn)象中都會(huì)出現(xiàn)。5.3 采樣理論基礎(chǔ)中心極限定理（Central limit theorem）：說(shuō)明獨(dú)立同分布的隨機(jī)變量的總和遵循正態(tài)分布估計(jì)量（Estimator）為一個(gè)隨機(jī)變量Y，它被用來(lái)估計(jì)一個(gè)基準(zhǔn)總體的某一參數(shù)pY的估計(jì)偏差（estimation bias）作為p的估計(jì)量是（EY-p）。無(wú)偏估計(jì)

8、量是指該偏差為0N%置信區(qū)間（confidence interval）用于估計(jì)參數(shù)p，該區(qū)間包含p的概率為N%5.3.1 錯(cuò)誤率估計(jì)和二項(xiàng)比例估計(jì)測(cè)量樣本錯(cuò)誤率相當(dāng)于在作一個(gè)有隨機(jī)輸出的實(shí)驗(yàn)。我們先從分布中隨機(jī)抽取n個(gè)獨(dú)立的實(shí)例，形成樣本S，然后測(cè)量樣本錯(cuò)誤率errors(h)。如果將實(shí)驗(yàn)重復(fù)多次，每次抽取大小為n的不同的樣本Si，將可以得到不同的的值error Si(h)，它取決于不同Si組成中的隨機(jī)差異。在這種情況下，第i個(gè)實(shí)驗(yàn)的輸出error Si(h)被稱為一隨機(jī)變量（random variable）。一般情況下，可以將隨機(jī)變量看成一個(gè)有隨機(jī)輸出的實(shí)驗(yàn)。隨機(jī)變量值即為隨機(jī)實(shí)驗(yàn)的觀察輸出

9、。當(dāng)k不斷增長(zhǎng)，5-3表中描述的概率分布稱為二項(xiàng)分布（Binomial distribution）5.3.2 二項(xiàng)分布二項(xiàng)分布描述的是對(duì)任一可能的r值（r從0到n），這個(gè)正面概率為p的硬幣投擲n次恰好出現(xiàn)r次正面的概率。應(yīng)用二項(xiàng)分布的條件包括：1）有一基本實(shí)驗(yàn)，其輸出可被描述為一隨機(jī)變量Y。隨機(jī)變量Y有兩種取值2）在實(shí)驗(yàn)的任一次嘗試中Y=1的概率為常數(shù)p。它與其他的實(shí)驗(yàn)無(wú)關(guān)。一般p為預(yù)先未知的，面臨的問(wèn)題就在于如何估計(jì)它3）基本實(shí)驗(yàn)的n次獨(dú)立嘗試按序列執(zhí)行，生成一個(gè)獨(dú)立同分布的隨機(jī)變量序列Y1, Y2, Yn，另R代表實(shí)驗(yàn)中出現(xiàn)Yi=1的次數(shù)。4）隨機(jī)變量R取特定值r的概率由二項(xiàng)分布給出。5.

10、3.3 均值和方差定義：考慮隨機(jī)變量Y可能的取值為y1, y2,yn，Y的期望值（expected value）EY為：定義：隨機(jī)變量Y的方差（variance）VarY為：定義：隨機(jī)變量Y的標(biāo)準(zhǔn)差（standard deviation）為：5.3.4 估計(jì)量、偏差和方差定義：針對(duì)任意參數(shù)p估計(jì)量Y的估計(jì)偏差為：如果估計(jì)偏差為0，稱Y為p的無(wú)偏估計(jì)量（unbiased estimator）。在此情況下由多次重復(fù)實(shí)驗(yàn)生成的Y的多個(gè)隨機(jī)值的平均（即EY)將收斂于p5.3.5 置信區(qū)間描述某估計(jì)的不確定性的方法是使用置信區(qū)間，真實(shí)的值以一定的概率落入該區(qū)間中。這樣的估計(jì)成為置信區(qū)間（confiden

11、ce interval）估計(jì)。定義：某個(gè)參數(shù)p的N%置信區(qū)間是一個(gè)以N%的概率包含p的區(qū)間。5.3.6 雙側(cè)和單側(cè)邊界由一個(gè)有下界L和上界U的100(1-a)%置信區(qū)間，可得到一個(gè)下界為L(zhǎng)且無(wú)上界的100(1-a/2)%置信區(qū)間，或得到一個(gè)上界為R且無(wú)下界的100(1-a/2)%置信區(qū)間。5.4 推導(dǎo)置信區(qū)間的一般方法前面介紹的是針對(duì)某一特定情況推導(dǎo)置信區(qū)間估計(jì)：基于獨(dú)立抽取的n個(gè)樣本，估計(jì)離散值假設(shè)的errorD(h)。這里介紹的方法是在許多估計(jì)問(wèn)題中用到的通用的方法，將此看做是基于大小為n的隨機(jī)抽取樣本的均值，來(lái)估計(jì)總體均值的問(wèn)題。通用的過(guò)程包括以下步驟：）確定基準(zhǔn)總體中要估計(jì)的參數(shù)p，例

12、如errorD(h)）定義一個(gè)估計(jì)量Y（如errorS(h) ），它的選擇應(yīng)是最小方差的無(wú)偏估計(jì)量。）確定控制估計(jì)量Y的概率分布DY，包括其均值和方差。）通過(guò)尋找閥值L和U確定N%置信區(qū)間，以使這個(gè)按DY分布的隨機(jī)變量有N%機(jī)會(huì)落入L和U之間。中心極限定理中心極限定理是簡(jiǎn)化置信區(qū)間推導(dǎo)的一個(gè)基本依據(jù)?？紤]如下的一般框架：在n個(gè)獨(dú)立抽取的且服從同樣概率分布的隨機(jī)變量Y1Yn中觀察實(shí)驗(yàn)值（如一枚硬幣的n次拋擲）。令代表每一變量Yi服從的未知分布的均值，并令代表標(biāo)準(zhǔn)差，稱這些變量Yi為獨(dú)立同分布（independent, identically distributed）隨機(jī)變量。因?yàn)樗鼈兠枋龅氖歉髯?/p>

13、獨(dú)立且服從同樣概率分布的實(shí)驗(yàn)。為估計(jì)Yi服從的分布的均值，計(jì)算樣本的均值（如n次投擲硬幣中出現(xiàn)正面的比例）中心極限定理說(shuō)明在時(shí)所服從的概率分布為一正態(tài)分布，且不論Yi本身服從什么樣的分布。中心極限定理考慮獨(dú)立同分布的隨機(jī)變量Y1Yn的集合，它們服從一任意的概率分布，均值為，有限方差為。定義樣本均值則當(dāng)時(shí)下面的式子服從正態(tài)分布，均值為且標(biāo)準(zhǔn)差為。結(jié)論令人吃驚，因?yàn)樗f(shuō)明在不知道獨(dú)立的Yi所服從的基準(zhǔn)分布的情況下，可以得知樣本均值的分布形式。中心極限定理說(shuō)明了怎樣使用 的均值和方差來(lái)確定獨(dú)立的Yi的均值和方差。中心極限定理中心極限定理是一個(gè)非常有用的結(jié)論，因?yàn)樗硎救我鈽颖揪档墓烙?jì)量（如erro

14、rS(h)為平均錯(cuò)誤率）服從的分布在n足夠大時(shí)可近似為正態(tài)分布。如果還知道這一近似的正態(tài)分布的方差，就可以計(jì)算置信區(qū)間。一個(gè)通常的規(guī)則是在n大于30時(shí)可使用這一近似5.6 兩個(gè)假設(shè)錯(cuò)誤率間的差異考慮對(duì)某離散目標(biāo)函數(shù)有兩個(gè)假設(shè)h1和h2。假設(shè)h1在一擁有n1個(gè)隨機(jī)抽取的樣本S1上測(cè)試，且h2在擁有n2個(gè)從相同分布中抽取的樣例的樣本S2上測(cè)試。假定要估計(jì)這兩個(gè)假設(shè)的真實(shí)錯(cuò)誤率間的差異：在確定d為待估計(jì)的參數(shù)后，下面要定義一估計(jì)量。顯然，這里可選擇樣本錯(cuò)誤率之間的差異作為估計(jì)量這里雖不加證明，但可以認(rèn)為即為d的無(wú)偏估計(jì)量，即5.6 兩個(gè)假設(shè)錯(cuò)誤率間的差異隨機(jī)變量服從的概率分布是什么？對(duì)于較大的n1和

15、n2，errorss1(h1)和 errorss2(h2)都近似遵從正態(tài)分布。由于兩個(gè)正態(tài)分布的差仍為一正態(tài)分布，因此也近似遵從正態(tài)分布，均值為d。同時(shí)可得出分布的方差為兩個(gè)方差的和：已經(jīng)確定了估計(jì)量所服從的概率分布，很容易推導(dǎo)出置信區(qū)間以說(shuō)明使用來(lái)估計(jì)d的可能誤差。隨機(jī)變量服從均值d方差的正態(tài)分布，其N%置信區(qū)間估計(jì)為5.6 兩個(gè)假設(shè)錯(cuò)誤率間的差異雖然上面的分析考慮的是h1和h2在相互獨(dú)立的數(shù)據(jù)樣本上測(cè)試的情況，但是在一個(gè)樣本S（S仍然獨(dú)立于h1和h2）上測(cè)試h1和h2并計(jì)算置信區(qū)間也是可接受的。被重新定義為：當(dāng)用S來(lái)代替S1和S2時(shí)，新的的方差通常小于式中給出的方差。這是因?yàn)槭褂脝蝹€(gè)的樣本

16、S消除了由S1和S2組合帶來(lái)的隨機(jī)差異假設(shè)檢驗(yàn)我們感興趣的是某個(gè)特定的猜想正確的概率，而不是對(duì)某參數(shù)的置信區(qū)間的估計(jì)。比如下面的問(wèn)題errorD(h1) errorD(h2)的可能性多大？假定要測(cè)量h1和h2的樣本錯(cuò)誤率，使用大小為100的獨(dú)立樣本S1和S2，并且知道errorsS1(h1)0.3和errorsS2(h2)0.2，因此差異為0.1。當(dāng)然，由于數(shù)據(jù)樣本的隨機(jī)性，即使errorsD(h1) errorsD(h2)的概率是多少？如何計(jì)算在=0.1時(shí)，d0的概率？假設(shè)檢驗(yàn)概率Pr(d0)等于對(duì)d的過(guò)高估計(jì)不大于0.1的概率，也就是這個(gè)概率為落入單側(cè)區(qū)間 errorD(h2)這一假設(shè)，置

17、信度為0.95。5.6 學(xué)習(xí)算法比較我們感興趣的是比較兩個(gè)學(xué)習(xí)算法LA和LB的性能，而不是具體的兩個(gè)假設(shè)本身。怎樣近似地檢驗(yàn)多個(gè)學(xué)習(xí)算法，如何確定兩個(gè)算法之間的差異在統(tǒng)計(jì)學(xué)上是有意義的？在機(jī)器學(xué)習(xí)領(lǐng)域，關(guān)于學(xué)習(xí)算法比較哪個(gè)方法最好仍存在激烈的爭(zhēng)論。通常，先指定要估計(jì)的參數(shù)，假定有LA和LB兩個(gè)算法，要確定為了學(xué)習(xí)一特定目標(biāo)函數(shù)f，平均來(lái)說(shuō)哪個(gè)算法最好。定義“平均”的一種合理方法是，從一基準(zhǔn)實(shí)例分布D中抽取包含n個(gè)樣例的訓(xùn)練集合，在所有這樣的集合中測(cè)量?jī)蓚€(gè)算法的平均性能。換句話說(shuō)，需要估計(jì)假設(shè)錯(cuò)誤率之間差異的期望值：其中L(S)代表在給定訓(xùn)練數(shù)據(jù)的樣本S時(shí)，學(xué)習(xí)算法L輸出的假設(shè)。下標(biāo)表示期望值是

18、在基準(zhǔn)分布D中抽取的樣本S上計(jì)算。5.6 學(xué)習(xí)算法比較在實(shí)際的學(xué)習(xí)算法比較中，只有一個(gè)有限的樣本D0。在這種情況下，需要將D0分割成訓(xùn)練集合S0和與之不相交的測(cè)試集合T0 。訓(xùn)練數(shù)據(jù)既可以用來(lái)訓(xùn)練LA ，又訓(xùn)練LB 。而測(cè)試數(shù)據(jù)則用來(lái)比較兩個(gè)學(xué)習(xí)到的假設(shè)的準(zhǔn)確度。一種改進(jìn)的方法是將數(shù)據(jù)D0多次分割為不相交的訓(xùn)練和測(cè)試集合，然后在其中計(jì)算這些不同的試驗(yàn)的錯(cuò)誤率的平均值。該過(guò)程首先將數(shù)據(jù)拆分為k個(gè)不相交的相等子集，子集的大小至少為30，然后訓(xùn)練和測(cè)試算法k次，每次使用其中一個(gè)子集作為測(cè)試數(shù)據(jù)集，其他k-1個(gè)子集為訓(xùn)練集。使用這種方法，學(xué)習(xí)算法在k個(gè)獨(dú)立測(cè)試集上測(cè)試，而把錯(cuò)誤率的差異的均值作為學(xué)習(xí)算法間差異的估計(jì)。5.6 學(xué)習(xí)算法比較估計(jì)兩個(gè)學(xué)習(xí)算法LA和LB錯(cuò)誤率差