機器統(tǒng)計知識學(xué)習(xí)作業(yè)任務(wù)

1、、（R6）泛化誤差上界：對二分類問題，當(dāng)假設(shè)空間是有限個函數(shù)的集合Ff1, f2, , fd時，對任意一個函數(shù)f F ,至少以概率1-，以下不等式成立:R f R f d, N,其中，d, N,J2N logd log-即fN的泛化能力：fN arg min R f證明：在證明中要用到Hoeffd ing不等式,故先敘述如下:n設(shè)SnXi是獨立隨機變量是X1, X2,i 1Xn 之和，Xi ai,bi 1 ；nXi為n這組隨機變量X1, X2, Xn的均值，則t 0，以下不等式成立:expC 2. 2 2n tu2i 1 bi ai2ex p2n2t2n-2i b ai對任意函數(shù)f F , R

2、f是N個獨立的隨機變量L Y, f X 樣本均值，R f是隨機變量L Y, f X的期望值。如果損失函數(shù)取值于區(qū)間0,1 ,即對所有i ,ai ,bi0,1，那么有上述Hoeffding 不等式,0，以下不等式成立:由于Fexp2N 2fl,f2, fd是一有限集合,2d ex p 2N或者等價的,對任意f F，有21 dexD 2NXi Md exp2N 2故至少以概率1-有R f R f 二、（R8）以損失函數(shù)推導(dǎo)向量最小化感知機的損失函數(shù)min L w, bw,byi w x bXiM感知機學(xué)習(xí)算法是誤分類驅(qū)動的,具體采用隨機梯度下降法。首先，任意選取一個超平面，然后用梯度下降法不斷極小

3、化目標(biāo)函數(shù)， 極小化的過程不是 次使M中所有的誤分類點的梯度下降，而是一次隨機選取一個誤分類點使其梯 度下降.隨機梯度下降是一種迭代求解思路，而迭代法參數(shù)尋優(yōu)的基本原理：沿著（代價）函數(shù)下降的方向?qū)ふ覅?shù)，能夠找到極值點.在我們已經(jīng)學(xué)過的數(shù)學(xué)知識中，導(dǎo)數(shù)和方向?qū)?shù)是能找到函數(shù)變化方向的。導(dǎo)數(shù)表示了曲線的斜率（傾 斜度），方向?qū)?shù)表示了曲面沿著任意方向的斜率（傾斜度）。一維時，導(dǎo)數(shù)就 足夠了。但多維時，就需要借助方向?qū)?shù)了，而我們更希望能找到變化率最大的 方向。因此，多維下借用方向?qū)?shù)變化最大的情況：梯度，梯度的方向是函數(shù)某 點增長最快的方向，梯度的大小是該點的最大變化率故對于L w, byi

4、w X b損失函數(shù)L w,b的梯度是對w和b求偏導(dǎo):wLw,b 3wyiXiWX Mwyibxi Mwyi XiML w, bbL w,b byiW XiXi MbyibX Mbyi芻M，X24,3 ，負實三、（P29）如圖所示的訓(xùn)練數(shù)據(jù)集，其正實例點是 Xi3,3例點是X31,1,試用感知機學(xué)習(xí)算法的原始形式求感知機模型解 構(gòu)建最優(yōu)化問題:min Lw,bw,byi w x bxi M按照感知機學(xué)習(xí)算法的原始形式，求解 w ， b.1.(1) 取初值 w00 ，b0 0(2) 對 x1 3,3y1 w0 x1b00 ，未能被正確分類，更新 w， b.wiw0y1x13,3 ， b1 b0 y

5、1 1得到線性模型w1b13x1 3x 2 1(3)對 x1， x2，顯然， yi wi xbi0，被正確分類，不修改w , b .對x31,1y3 w1 x3 b1，被誤分類，更新得到線性模型得到線性模型(5)對 x31,1故得到線性模型6)對 x13，3故得到線性模型w2w1y3x32,2 ， b2 b1y3w2 xb22x 12x 2w3w2y3x3w3 xy3 w3 x3b3w4w3， y1 w4 x1w5 w41,1b3b2y3b3210，y3x3b4被誤分類，更新0,0， b4b3w4 x b420 ，被誤分類點，y1 x13,3 ， b5b4w，y3y1w， bw5 X b5 3

6、X1 3x 21(7)對 x31,1y3W5 X3b50,被誤分類點，更新w6W5¥3 X32,2， b6b5¥3故得到線性模型2X1 2X22(8)對 x31,1¥3w¥3X30，被誤分類點，更新W7W ¥3X31,1b7b6¥3故得到線性模型w7X b7而該模型對正實例點X13,3X24,3,負實例點x31,1,都有¥i Wi Xi bi0，則沒有分類點，損失函數(shù)達到最小.故分離超平面為感知機模型為f Xsign X1X33迭代過程如表爰九1的ft代過B迭代次ft分類點h枕電H + b0000II刃1Ji叫計+l2(X2

7、f0工工+ 2d：'3T宀宀14但時-2-25a)T一13屮口 3嚴(yán)】T6s2jr詼#2?聲壬27(ijy-J嚴(yán)nS0(bif-J利+宀3四、P37從統(tǒng)計角度考慮哪些因素影響k近鄰法的準(zhǔn)確度.我們知道K近鄰法是一種應(yīng)用廣泛的非參數(shù)分類方法，可用于線性不可分的多類樣本識別。它的優(yōu)點是事先并不要求知道待分樣本的分布函數(shù)。目前廣泛使用的K近鄰法是以待分類樣本為中心做超球體，逐漸擴大超球半徑直至超球內(nèi)包含K個已知模式樣本為止，判斷這k個近鄰樣本中多數(shù)屬于哪一類，就把待分類樣本歸為哪一類。分類算法描述如下假設(shè)有C個類別W1,W2, ,Wc, , I 12 ,C.測試樣本X和與其最近的樣本之間的距

8、離為gixk叫n x Xi ,kk 1,2，n，其中Xi的下標(biāo)i表示W(wǎng)i類，上標(biāo)k表示wi類ni個樣本中第k個樣本.在超球半徑r mi n g X的前提下，求L argmaxki , KO i c 1表示這k個近鄰中屬于w的樣本數(shù). i上述方法的弱點就是，半徑r的選取十分困難.r值過大，超球體的覆蓋面積 廣，會導(dǎo)致其他類樣本被錯誤的覆蓋,從而加大樣本的誤識率反之若r值過小， 則不能完全覆蓋該類別中可能的樣本點.并且近鄰點具有相似的預(yù)測值，所以r 的大小也會影響k近鄰法的準(zhǔn)確度.該方法易受噪聲影響，尤其是樣本點中孤立點 的影響而我們知道k近鄰法模型由三個部分構(gòu)成：距離度量，k的值，分類決策 規(guī)則

9、。所以K值的選取也會影響到分類結(jié)果.因為k值的選取是根據(jù)每類樣本的 數(shù)目和分散程度選取的，對不同的應(yīng)用選取的k值也不同所以我們是要在是在k值選定的情況下，對近鄰點的搜索區(qū)域進行合理的定位，即選取合適的r的大小，即全局到局部，同時還要保障分類結(jié)果的準(zhǔn)確性.具體方法：首先將樣本空間的樣本點進行小規(guī)模有目的性的聚類，聚類后樣 本空間中樣本分布的區(qū)域被劃分成，若干個半徑一定的小超球體如果能保證超球體內(nèi)主體類樣本數(shù)遠遠大于雜質(zhì)類樣本數(shù)，那么搜索時就可根據(jù)其條件將搜索范圍縮小到某些超球體內(nèi)，在這些超球體內(nèi)尋找待分樣本點的k個近鄰點s 1聚婁c示意ra定義C代表全體聚類的集合，即C中包含全部聚類中的數(shù)據(jù)-N

10、代表確定的近鄰 點的集合，1為最近間隔，P為競爭點集，即可能成為近鄰點的集合聚類后計算 指定點x到每個聚類中心的距離di,如圖1所示依據(jù)這些距離，聚類集C被劃 分，離X最近的聚類為C0 ,下一個距離較近的聚類為ci ,依次編號然后將聚類Co中的所有點添加到P中，計算P中所有點與X的距離，將滿足條件的點轉(zhuǎn)移到集 合N中這樣近鄰點的搜索區(qū)域就可以被大致定位求近鄰點的關(guān)鍵是確定點 X到C中聚類的搜索距離，為此需創(chuàng)建最近間隔I 每次近鄰點的搜索范圍便是以待分類點X為圓心，I值為半徑的球體.在整個搜 索過程中最近間隔I 一直處在變化過程中，1值修改時采用使間隔I內(nèi)包含盡量 少的需要計算的近鄰點的原則，已

11、確保搜索的準(zhǔn)確性當(dāng)聚類被初始劃分時，由于 采用局部聚類的方法，因此可能造成兩個聚類存在重疊區(qū)域為避免重疊區(qū)域的點 因重搜索而影響算法效率，所以在計算最近間隔I時，還必須考慮C中的聚類是 否有重疊區(qū)當(dāng)最近間隔I被初始創(chuàng)建時檢查Co與其他聚類是否有重疊區(qū)域，如 果沒有且do r di r，則Co中所有點皆放入P中，此時I d。r .如果有重疊區(qū)域或do di r，則I di r 當(dāng)被確定后，P中所有點Xi依據(jù)I值，將滿足條件 的點轉(zhuǎn)移到N中沖中的點搜索完畢，則按編號將下一個聚類中的點添加到 P中，重復(fù)上述操作，直到N中包含K個元素時為止.五、根據(jù)表2計算:(1)后驗概率;(2)離散屬性的類條件概率

12、;(3)連續(xù)屬性的類條件概率分布的參數(shù)(樣本均值和方差)Id有房婚姻狀況年收入拖欠貸款1直/、單身125KNo2否已婚100KNo3否單身70KNo4直/、已婚120KNo5否離婚95KYes6否已婚60KNo7直/、離婚220KNo8否單身85KYes9否已婚75KNo10否單身90KYes表2從該數(shù)據(jù)集計算得到的先驗概率以及每個離散屬性的類條件概率、連續(xù)屬性的類條件概率先驗概率：P (Yes)=3/10P(有房是 | No)3/7P有房否1 No4/7P有房是 |Yes0P有房否1 No1分布的參數(shù)(樣本均值和方差)如下:0.3 ； P(No)= 7/100.7p婚姻狀況單身| No2/7

13、p婚姻狀況離婚| No1/7p婚姻狀況已婚| No4/7P婚姻狀況單身|丫es2/3P婚姻狀況離婚|Yes1/3P婚姻狀況已婚|Yes0年收入：如果類=No:樣本均值=125 100 70 120 60 220 75110 ；樣本方差=2975;如果類=Yes:樣本均值=90 ;樣本方差=25待預(yù)測記錄：X =有房=否，婚姻狀況=已婚，年收入=120KP No p有房 否| No P婚姻狀況已婚| No0.7 4/7 4/7 0.0072 0.0024P年收入 120K | NoP Yes P有房 否| Yes p婚姻狀況已婚| Yes90.3 1 0 1.2 10 90P年收入 120K |Yes由于0.0024大于0 ,所以該記錄分類為 No。從上面的例子可以看出，如果有一個屬性的類條件概率等于0，則整個類的后驗概率就等于0。僅僅使用記錄比例來估計類條件概率的方法顯得太脆弱了,尤其是當(dāng)訓(xùn)練樣例很少而屬性數(shù)目又很多時。解決該問題的方法是使用m估計方法來估計條件概率nc mpn m其中，口是類戸中的憲例總數(shù)是類刀的訓(xùn)練樣本中取值兀的樣本數(shù)，m是稱為等價樣 本大水的參數(shù)，P是用戶指定的參數(shù)總還是上面的例子，條件概率P（婚姻狀祝二已婚|Ycs） = O, 使用m估計方袪，nk=3i p=L3 則：屮F