機器學習基于實例的學習課件

1、2022/10/41 第8章 基于實例的學習8.1簡介8.2 k一近鄰算法8.3局部加權回歸8.4徑向基函數8.5基于案例的推理8.6對消極學習和積極學習的評論8.7小結和補充讀物2022/10/42 8.1簡介（1/3）思想：基于實例的學習方法先把訓練樣例存儲起來。泛化的工作被推遲到必須分類新的實例時。每當學習器遇到一個新的查詢實例，它分析這個新實例與以前存儲的實例的關系，并據此把一個目標函數值賦給新實例。基于實例的學習方法有時被稱為消極(lazy)學習法，因為它們把處理工作延遲到必須分類新的實例時。與其相對的方法稱為積極的（eager)。延遲的或消極的學習方法有一個關鍵的優(yōu)點，即它們不是在

2、整個實例空間上一次性地估計目標函數，而是針對每個待分類新實例作出局部的和相異的估計。2022/10/438.1簡介（2/3）基于實例的學習方法包括最近鄰法(nearest neighbor NN) 和局部加權回歸(locally weighted regression LWR)法，它們都假定實例可以被表示為歐氏空間中的點?；趯嵗膶W習方法還包括基于案例的推理(case-based reasoning CBR）它對實例采用更復雜的符號表示。2022/10/44 8.1簡介（3/3）基于實例方法的一個不足是，分類新實例的開銷可能很大。這是因為幾乎所有的計算都發(fā)生在分類時，而不是在第一次遇到訓練樣

3、例時。所以如何有效地索引訓練樣例，以減少查詢時所需的計算是一個重要的實踐問題。第二個不足是(尤其對于最近鄰法)，當從存儲器中檢索相似的訓練樣例時，它們一般考慮實例的所有屬性。如果目標概念僅依賴于很多屬性中的幾個時，那么真正最“相似”的實例之間很可能相距甚遠。2022/10/45 8.2 k一近鄰算法（1/5）k一近鄰算法假定所有的實例對應于n維空間Rn中的點。一個實例的最近鄰是根據標準歐氏距離定義的。即把任意實例x表示為下面的特征向量: 其中,ar(x)表示實例x的第r個屬性值。那么，兩個實例xi和xj 間的距離定義為d(xi,xj)，其中:2022/10/478.2 k一近鄰算法（2/5）

4、下圖圖解了一種簡單情況下的k一近鄰算法，在這里實例是二維空間中的點，目標函數具有布爾值。正反訓練樣例用“+”和“-”分別表示。圖中也畫出了一個查詢點xq 。1一近鄰算法把xq分類為正例，然而5一近鄰算法把xq分類為反例。2022/10/488.2 k一近鄰算法（3/5） k-近鄰算法隱含考慮的假設空間H的特性:k-近鄰算法并不形成關于目標函數f的明確的一般假設。它僅在需要時計算每個新查詢實例的分類。隱含的一般函數是什么?或者說，如果保持訓練樣例不變，并用X中的每個可能實例查詢算法，會得到什么樣的分類?2022/10/4108.2 k一近鄰算法（5/5） 對k一近鄰算法作簡單的修改，它可被用于逼

5、近連續(xù)值的目標函數。讓算法計算k個最接近樣例的平均值，而不是計算其中的最普遍的值。更精確地講，為了逼近一個實值目標函數 ，我們使用公式:2022/10/4118.2.1距離加權最近鄰算法（1/3） 對k一近鄰算法的一個改進是對k個近鄰的貢獻加權，根據它們相對查詢點xq的距離，將較大的權值賦給較近的近鄰。在逼近離散目標函數的算法中，可以根據每個近鄰與xq的距離平方的倒數加權這個近鄰的“選舉權”: 當xq=xi ，將導致分母d(xq xi)2為0，此時令 。如果有多個這樣的訓練樣例，我們使用它們中占多數的分類。2022/10/4128.2.1距離加權最近鄰算法（2/3）對實值目標函數進行距離加權，

6、用下式： 其中，wi的定義與前式中相同。注意該式中的分母是一個常量，它將不同權值的貢獻歸一化(例如，它保證如果對所有的訓練樣例xi，f(xi)c，那么， 。2022/10/4148.2.2對k-近鄰算法的說明（1/6） 按距離加權的k一近鄰算法是一種非常有效的歸納推理方法。它對訓練數據中的噪聲有很好的健壯性，而且當給定足夠大的訓練集合時也非常有效。注意，通過取k個近鄰的加權平均，可以消除孤立的噪聲樣例的影響。k一近鄰算法的歸納偏置對應于假定:一個實例的分類xq與在歐氏空間中它附近的實例的分類相似。2022/10/4158.2.2對k-近鄰算法的說明（2/6）應用k一近鄰算法的一個實踐問題是，實

7、例間的距離是根據實例的所有屬性(也就是包含實例的歐氏空間的所有坐標軸)計算的?？紤]把k一近鄰算法應用到這樣一個問題: 每個實例由20個屬性描述，但在這些屬性中僅有2個與它的分類有關。在這種情況下，這兩個相關屬性的值一致的實例可能在這個20維的實例空間中相距很遠。結果，依賴這20個屬性的相似性度量會誤導k一近鄰算法的分類。2022/10/4178.2.2對k-近鄰算法的說明（4/6）具體做法如下：首先，假定使用加權因子zj，伸展(乘)第j個根坐標軸，選擇zj的各個值z1 zn ，以使學習算法的真實分類錯誤率最小化。其次，這個真實錯誤率可以使用交叉驗證來估計。交叉驗證:隨機選取現有數據的一個子集作

8、為訓練樣例，然后決定z1 zn 的值使剩余樣例的分類錯誤率最小化。通過多次重復這個處理過程，可以使加權因子的估計更加準確。這種伸展坐標軸以優(yōu)化k一近鄰算法的過程，提供了一種抑制無關屬性影響的機制。2022/10/4188.2.2對k-近鄰算法的說明（5/6）另外一種更強有力的方法從實例空間中完全消除最不相關的屬性。這等效于設置某個縮放因子zj為0。注意，上面的兩種方法都可以被看作以某個常量因子伸展坐標軸。另外一種可選的做法是使用一個在實例空間上變化的值伸展坐標軸。這樣增加了算法重新定義距離度量的自由度，然而也增加了過度擬合的風險。所以，局部伸展坐標軸的方法是不太常見的。2022/10/4198

9、.2.2對k-近鄰算法的說明（6/6）應用k一近鄰算法的另外一個實踐問題是如何建立高效的索引。因為k一近鄰算法推遲所有的處理，直到接收到一個新的查詢，所以處理每個新查詢可能需要大量的計算。一種索引方法是kd-tree，它把實例存儲在樹的葉結點內，鄰近的實例存儲在同一個或附近的結點內。通過測試新查詢xq的選定屬性，就可以把查詢xq排列到相關的葉結點。2022/10/4208.2.3術語注解回歸(Regression)的含義是逼近一個實數值的目標函數。殘差(Residual)是逼近目標函數時的誤差核函數(Kernel function)是一個距離函數，它用來決定每個訓練樣例的權值。換句話說，核函數

10、就是使 wi=K(d(xi,xq)的函數K。2022/10/4218.3局部加權回歸（1/2）最近鄰方法可以被看作在單一的查詢點x= xq上逼近目標函數f(x)。（沒有明確的目標函數，只有目標值）局部加權回歸是最近鄰方法的推廣。它在環(huán)繞xq的局部區(qū)域內為目標函數f建立明確的逼近。使用附近的或距離加權的訓練樣例來形成這種對f的局部逼近?？梢允褂镁€性函數、二次函數、多層神經網絡或者其他函數形成在環(huán)繞xq的鄰域內逼近目標函數?！熬植考訖嗷貧w”名稱中，“局部”是指目標函數的逼近僅僅根據查詢點附近的數據; “加權”是指每一個訓練樣例的貢獻是由它與查詢點間的距離加權的; “回歸”表示逼近實數值函數。202

11、2/10/4228.3局部加權回歸（2/2） 給定一個新的查詢實例，局部加權回歸的一般方法是：建立一個逼近 ，使 擬合環(huán)繞xq的鄰域內的訓練樣例。(可以使用歸納學習等方法）然后用這個逼近來計算 的值，也就是為查詢實例估計的目標值輸出。然后， 的描述被刪除，因為對于每一個獨立的查詢實例都會計算不同的局部逼近。2022/10/4248.3.1局部加權線性回歸(2/3) 修改這個過程來推導出局部逼近方法是:重新定義誤差準則E以著重于擬合局部訓練樣例。下面給出了三種可能的誤差準則。1)只對在k個近鄰上的誤差平方最小化:2)使整個訓練樣例集合D上的誤差平方最小化，但對每個訓練樣例加權，權值為關于相距xq

12、距離的某個遞減函數K:3)綜合1和2:2022/10/4258.3.1局部加權線性回歸(3/3) 使用上面的準則3，并使用與第4章相同的推理方式重新推導梯度下降法則，可以得到以下訓練法則: 注意，這個新的法則和全局逼近給出的法則的差異是:實例x對權值更新的貢獻現在乘上了一個距離懲罰項K( d(xq，x)僅對k個最鄰近的訓練實例的誤差求和。2022/10/4278.4徑向基函數（1/7） 在使用徑向基函數方法中，最常用所待學習的假設是一個以下形式的函數: 其中，每個xu是X中一個實例，核函數K（ d(xu，x)被定義為隨距離d(xu，x) 的增大而減小。這里的k是用戶提供的常量，用來指定要包含的

13、核函數的數量。盡管 是對f(x)的全局逼近，但來自每個Ku(d(xu,x) 項的貢獻被局部化到點xu附近的區(qū)域。2022/10/428 一種很常見的做法是選擇每個核函數Ku（d(xu，x)為高斯函數,高斯函數的中心點為xu，方差是 。每個核函數Ku（d(xu，x)取為高斯函數時，函數：能夠以任意小的誤差逼近任何函數，只要高斯的核數量足夠大，并且可以分別制定每個核的寬度。8.4徑向基函數（2/7）2022/10/4298.4徑向基函數（3/7）函數：可以被看作是描述了一個兩層的網絡：第一層計算不同的Ku（d(xu，x) 第二層計算第一層單元值的線性組合。2022/10/4308.4徑向基函數（4

14、/7） 輸入第一步選取xu和 ，按下式計算： 使用 ，訓練wu：下圖畫出了一個徑向基函數(RRF)網絡的例子。2022/10/4318.4徑向基函數（5/7） 人們已經提出了幾種方法來選取適當的隱藏單元或者說核函數的數量。第一種方法是為每一個訓練樣例分配一個高斯核函數，此高斯核函數的中心點被設為xi。所有高斯函數的寬度2可被賦予同樣的值。選擇核函數的一個優(yōu)點是它允許RBF網絡精確地擬合訓練數據。即，對于任意m個訓練樣例集合，合并m個高斯核函數的權值w0 wm可以被設置為使得對于每一個訓練樣例都滿足 ，此時也可以有m個輸出。 2022/10/4328.4徑向基函數（6/7）第二種方法是選取一組數

15、量少于訓練樣例數量的核函數。這種方法在訓練樣例的數量巨大的時候比第一種方法更有效。核函數被分布在整個實例空間X上，它們的中心之間有均勻的間隔?；蛘撸部梢苑蔷鶆虻胤植己撕瘮抵行?，特別是在實例本身在X上非均勻分布的時候?；蛘?，先求出訓練樣例的原始聚類，然后以每個聚類為中心加入一個核函數。第6.12.1節(jié)討論的EM算法提供了一種從k個高斯函數的混合中選擇均值，以最佳擬合觀測到實例的方法。2022/10/4338.4徑向基函數（7/7）用多個局部核函數的線性組合表示的徑向基函數網絡提供了一種目標函數的全局逼近。僅當輸入x落入某個核函數的中心和寬度所定義的區(qū)域內時，這個核函數的值才是不可忽略的。因此，

16、RBF網絡可以被看作目標函數的多個局部逼近的平滑線性組合。RBF網絡的一個重要優(yōu)點是，與反向傳播算法訓練的前饋網絡相比，它的訓練更加高效。這是因為RBF網絡的輸入層和輸出層可以被分別訓練。RBF網絡是一種積極的學習方法。2022/10/4348.5基于案例的推理（1/6）k一近鄰算法和局部加權回歸都是基于實例的方法，它們具有三個共同的關鍵特性。第一，是消極學習方法，都把在訓練數據之外的泛化推遲至遇到一個新的查詢實例時才進行。第二，通過分析相似的實例來分類新的查詢實例，而忽略與查詢極其不同的實例。第三，把實例表示為n維歐氏空間中的實數點?；诎咐耐评?case-based reasoning,

17、 CBR) 基于前兩個原則，但不包括第3個原則。在CBR中，一般使用更豐富的符號描述來表示實例;相應地，用來檢索實例的方法也更加復雜。2022/10/4358.5基于案例的推理（2/6） 考慮基于案例的推理系統的一個例子。2022/10/4368.5基于案例的推理（3/6） 2022/10/4378.5基于案例的推理（4/6） 給定新設計問題的功能說明，CADET從它的案例庫中搜索存儲的案例，使它的功能描述和新設計問題相匹配。如果發(fā)現了一個精確的匹配，那么可以返回這個案例作為新設計問題的建議方案。如果沒有發(fā)現精確的匹配，CADET可能找到匹配所需功能的不同子圖的案例。使它匹配設計規(guī)格說明的相應

18、部分。通過檢索匹配不同子圖的多個案例，有時可以拼接得到整個設計。一般來說，從多個檢索到的案例產生最終方案的過程可能很復雜。需要從頭設計系統的各個部分，也可能需要回溯以前的設計子目標，從而丟棄前面檢索到的案例。系統還可以根據領域或一般知識加工原始的功能說明圖，產生等價的子圖以匹配更多的案例。如：A B重寫為：A x B2022/10/4388.5基于案例的推理（5/6）基于案例的推理系統與k一近鄰方法的區(qū)別:實例或案例可以用豐富的符號描述表示，就像CADET中使用的功能圖。這需要不同于歐氏距離的相似性度量，比如兩個功能圖的最大可共享子圖的大小。檢索到的多個案例可以合并形成新問題的解決方案。這與k

19、一近鄰方法相似多個相似的案例用來構成對新查詢的回答。然而，合并多個檢索到的案例的過程與k一近鄰有很大不同，它依賴于知識推理，而不是統計方法。案例檢索、基于知識的推理和問題求解間是緊密藕合在一起的。例如CADET系統在嘗試找到匹配的案例過程中，它使用有關物理感應的一般知識重寫了功能圖。案例檢索和合并過程依賴于知識推理和搜索密集的問題求解方法。2022/10/4398.5基于案例的推理（6/6）目前關于基于案例的推理研究的一個課題是改進索引案例的方法?；诎咐耐评碇行膯栴}是句法相似度量(例如，功能圖之間的子圖同構)僅能近似地指出特定案例與特定問題的相關度。當CBR系統試圖復用檢索到的案例時，它可

20、能遇到句法相似度量中沒有捕捉到的難點。此時，CBR系統可回溯搜索另外的案例以適應現有的案例，或者求助于其他的問題求解方法。2022/10/4408.6對消極學習和積極學習的評論(1/4)三種消極學習(lazy learning)方法:k一近鄰算法、局部加權回歸和基于案例的推理。之所以稱這些方法是消極的，是因為它們延遲了如何從訓練數據中泛化的決策，直到遇到一個新的查詢案例時才進行。一種積極學習方法:學習徑向基函數網絡的方法。之所以稱這種方法是積極的(eager)，是因為它在見到新的查詢之前就做好了泛化的工作在訓練時提交了定義其目標函數逼近的網絡結構和權值。根據同樣的理解，本書其他章節(jié)討論的所有其

21、他算法都是積極學習算法(例如，反向傳播算法、C4.5 )。2022/10/4418.6對消極學習和積極學習的評論(2/4)在算法能力方面，消極方法和積極方法有重要兩種差異:計算時間的差異和對新查詢的分類差異。在計算時間方面：消極方法在訓練時一般需要較少的計算，但在預測新查詢的目標值時需要更多的計算時間。積極方法正好相反。在新查詢的分類方面：消極方法在決定如何從訓練數據D中泛化時考慮查詢實例xq；積極方法不能做到這一點，因為在見到查詢實例xq前，它們已經選取了對目標函數的(全局)逼近。2022/10/4428.6對消極學習和積極學習的評論(3/4)對學習器的泛化精度的影響如果要求消極的和積極的學

22、習器采用同一個假設空間H，那么答案是肯定的。消極的學習器可以通過很多局部逼近的組合(隱含地)表示目標函數。積極的學習器必須在訓練時提交單個的全局逼近。積極學習和消極學習之間的差異意味著對目標函數的全局逼近和局部逼近的差異。2022/10/4438.6對消極學習和積極學習的評論(4/4)使用多個局部逼近的積極方法（如RBF)，可以產生與消極方法（局部加權回歸）的局部逼近同樣的效果嗎? 消極學習方法可以對于每一個查詢實例選擇不同的假設(或目標函數的局部逼近)。使用同樣假設空間的積極方法是更加受限制的，因為它們必須提交一個覆蓋整個實例空間的單一假設。當然，積極的方法可以使用合并了多個局部逼近的假設空間，就像RBF網絡可以被看作是對這個目標的嘗試。RBF學習方法是在訓練時提交目標函數全局逼近的積極方法。2022/10/4448.7小結 (1)基于實例的學習方法不同于其他的函數逼近方法，因為它們推遲處理訓練樣例，直到必須分類一個新查詢實例