基于實(shí)例的學(xué)習(xí)機(jī)器學(xué)習(xí)

機(jī)器學(xué)習(xí)第8章基于實(shí)例的學(xué)習(xí)2003.12.181機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬基于實(shí)例的學(xué)習(xí)K-近鄰算法局部加權(quán)回歸徑向基函數(shù)基于案例的推理2003.12.182機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬基于實(shí)例的學(xué)習(xí)方法有時被稱為消極學(xué)習(xí)法，因?yàn)樗烟幚砉ぷ餮舆t到必須分類新實(shí)例的時候。

理解：已知一系列的訓(xùn)練樣例，很多學(xué)習(xí)方法（如決策樹，神經(jīng)網(wǎng)絡(luò)，貝葉斯學(xué)習(xí)）為目標(biāo)函數(shù)建立起明確的一般化描述。與此不同，基于實(shí)例的學(xué)習(xí)方法只是簡單地把訓(xùn)練樣例儲存起來，當(dāng)遇到待分類實(shí)例時，建立不同的逼近函數(shù)來進(jìn)行分類。這種延遲的學(xué)習(xí)方法有一個優(yōu)點(diǎn)：不是在整個實(shí)例空間上一次性地估計(jì)目標(biāo)函數(shù)，而是針對每個待分類新實(shí)例作出局部的和相異的估計(jì)。2003.12.183機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬簡介基于實(shí)例的學(xué)習(xí)方法的學(xué)習(xí)過程只是簡單地存儲已知的訓(xùn)練數(shù)據(jù)，當(dāng)遇到新的查詢實(shí)例時，一系列相似的實(shí)例從存儲器中取出，用來分類新的查詢實(shí)例與其他方法相比，基于實(shí)例的學(xué)習(xí)方法的一個關(guān)鍵差異是：可以為不同的待分類查詢實(shí)例建立不同的目標(biāo)函數(shù)逼近這樣做的好處是：有時目標(biāo)函數(shù)很復(fù)雜，但卻可以用不太復(fù)雜的局部逼近描述時，這樣做有明顯的優(yōu)勢2003.12.184機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬簡介（2）基于實(shí)例的方法的不足：分類新實(shí)例的開銷可能很大。幾乎所有的計(jì)算都發(fā)生在分類時，而不是在第一次遇到訓(xùn)練樣例時。如何有效地索引訓(xùn)練樣例是一個重要的問題當(dāng)從存儲器中檢索相似的訓(xùn)練樣例時，一般考慮實(shí)例的所有屬性，如果目標(biāo)概念僅依賴于很多屬性中的幾個，那么真正最“相似”的實(shí)例之間可能相距甚遠(yuǎn)。理解：待分類實(shí)例<a1,a2,a3……an>,但是它的分類只依賴與a1，a2，那么如果有一個訓(xùn)練樣例<b1,b2……bn>，其中a1=b1,a2=b2，其他的屬性值完全不等。因?yàn)榉诸悓?shí)例的屬性只依賴于a1，a2，所以待分類實(shí)例的分類應(yīng)該和這個訓(xùn)練樣例一致，但是根據(jù)距離d的公式，它的值會很大，則它們兩個在歐式空間中相距很遠(yuǎn)。2003.12.185機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬k-近鄰算法k-近鄰算法是最基本的基于實(shí)例的學(xué)習(xí)方法k-近鄰算法：假定所有的實(shí)例對應(yīng)于n維空間Rn中的點(diǎn)，任意的實(shí)例表示為一個特征向量<a1(x),...,an(x)>根據(jù)歐氏空間定義實(shí)例的距離。兩個實(shí)例xi和xj的距離d(xi,xj)定義為在最近鄰學(xué)習(xí)中，目標(biāo)函數(shù)值可以是離散的也可以是實(shí)值的，本節(jié)先考慮離散的情況。2003.12.186機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬k-近鄰算法（2）考慮離散目標(biāo)函數(shù)f:RnV，V={v1,...,vs}表8-1逼近離散值函數(shù)f:RnV的k-近鄰算法訓(xùn)練算法將每個訓(xùn)練樣例<x,f(x)>加入到訓(xùn)練列表training_examples分類算法給定一個要分類的查詢實(shí)例xq在training_examples中選出最靠近xq的k個實(shí)例，并用x1...xk表示返回其中2003.12.187機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬k-近鄰算法（3）表8-1的算法返回值是對f(xq)的估計(jì)，它是距離xq最近的k個訓(xùn)練樣例中最普遍的f值，結(jié)果與k的取值相關(guān)。圖8-1圖解了一種簡單情況下的k-近鄰算法，實(shí)例是二維空間中的點(diǎn)，目標(biāo)函數(shù)具有布爾值，1-近鄰算法把xq分類為正例，5-近鄰算法把xq分類為反例,所以說，結(jié)果與K的取值有關(guān)。圖8-1中右圖畫出了1-近鄰算法在整個實(shí)例空間上導(dǎo)致的決策面形狀。這種圖稱為訓(xùn)練樣例集合的Voronoi圖MATLAB：voronoi(x,y)分別標(biāo)出x、y的坐標(biāo)2003.12.188機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬k-近鄰算法（4）離散的k-近鄰算法作簡單修改后可用于逼近連續(xù)值的目標(biāo)函數(shù)。即計(jì)算k個最接近樣例的平均值，而不是計(jì)算其中的最普遍的值，逼近的實(shí)值目標(biāo)函數(shù)f:RnR，計(jì)算式如下：2003.12.189機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬在K-近鄰算法中，與待分類實(shí)例相鄰的K個樣例（不管遠(yuǎn)近），對該實(shí)例的作用程度（貢獻(xiàn)率）都是一樣的。那么，對k-近鄰算法做一個改進(jìn)：對k個近鄰的貢獻(xiàn)加權(quán)，離待分類實(shí)例越近的訓(xùn)練樣例賦予大的權(quán)值，離待分類實(shí)例遠(yuǎn)的樣例賦予小的權(quán)值。2003.12.1810機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬距離加權(quán)最近鄰算法我們根據(jù)K個訓(xùn)練樣例與xq的距離平方的倒數(shù)加權(quán)這個訓(xùn)練樣例2003.12.1811機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬為了處理查詢點(diǎn)xq恰好匹配某個訓(xùn)練樣例xi，即導(dǎo)致d(xq,xi)為0的情況，令這種情況下的

等于f(xi)，如果有多個這樣的訓(xùn)練樣例，我們使用它們占多數(shù)的分類也可以用類似的方式對實(shí)值目標(biāo)函數(shù)進(jìn)行距離加權(quán)（距離加權(quán)的平均），用下式替代表8-1中的計(jì)算式，wi的定義與前相同2003.12.1812機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬距離加權(quán)最近鄰算法（2）k-近鄰算法的所有變體都只考慮k個近鄰用以分類查詢點(diǎn)，如果使用按距離加權(quán)，那么可以允許所有的訓(xùn)練樣例影響xq的分類，因?yàn)榉浅＿h(yuǎn)的實(shí)例的影響很小考慮所有樣例的唯一不足是會使分類運(yùn)行得更慢簡單介紹：如果分類一個新實(shí)例時，考慮所有的訓(xùn)練樣例，我們稱為全局法；如果僅考慮靠近的訓(xùn)練樣例，稱為局部法2003.12.1813機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬對k-近鄰算法的說明距離加權(quán)的k-近鄰算法對訓(xùn)練數(shù)據(jù)中的噪聲有很好的健壯性，通過取k個近鄰的加權(quán)平均，可以消除孤立的噪聲樣例的影響k-近鄰的歸納偏置是：一個實(shí)例的分類xq與在歐氏空間中它附近的實(shí)例的分類相似2003.12.1814機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬k-近鄰方法的兩個實(shí)踐問題：（1）維度災(zāi)害許多學(xué)習(xí)方法，比如決策樹方法，選擇部分屬性來作出判斷，但是k-近鄰方法中實(shí)例間的距離是根據(jù)實(shí)例的所有屬性計(jì)算的（P166）實(shí)例間距離會被大量的不相關(guān)屬性所支配，可能導(dǎo)致相關(guān)屬性的值很接近的實(shí)例相距很遠(yuǎn)理解：待分類實(shí)例<a1,a2,a3……an>,但是它的分類只依賴與a1，a2，那么如果有一個訓(xùn)練樣例<b1,b2……bn>，其中a1=b1,a2=b2，其他的屬性值完全不等。因?yàn)榉诸悓?shí)例的屬性只依賴于a1，a2，所以待分類實(shí)例的分類應(yīng)該和這個訓(xùn)練樣例一致，但是根據(jù)距離d的公式，它的值會很大，則它們兩個在歐式空間中相距很遠(yuǎn)。2003.12.1815機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬維度災(zāi)害的解決方法：對屬性加權(quán)，相當(dāng)于按比例縮放歐氏空間中的坐標(biāo)軸，縮短對應(yīng)不太相關(guān)的屬性的坐標(biāo)軸（縮小權(quán)值），拉長對應(yīng)更相關(guān)屬性的坐標(biāo)軸（增加權(quán)值）。每個坐標(biāo)軸應(yīng)伸展的數(shù)量可以通過交叉驗(yàn)證的方法自動決定：一種做法是隨機(jī)選取現(xiàn)有數(shù)據(jù)的一個子集作為訓(xùn)練樣例，然后決定z1……zn的值使剩余樣例的分類錯誤率最小化?？梢远啻沃貜?fù)這個處理過程，使得加權(quán)因子的估計(jì)更加準(zhǔn)確這種伸展坐標(biāo)軸以優(yōu)化K-近鄰算法的過程，提供了一種抑制無關(guān)因子的機(jī)制另一種解決維度災(zāi)害的方法是從實(shí)例空間中完全消除最不相關(guān)的屬性，等效于設(shè)置某個縮放因子為02003.12.1816機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬對k-近鄰算法的說明（3）（2）實(shí)踐問題：如何建立高效的索引。k-近鄰算法推遲所有的處理，直到接收到一個新的查詢時才開始需要大量的計(jì)算，這個大量的計(jì)算就是從所有訓(xùn)練樣例中尋找最接近的鄰點(diǎn)。那么這個難題的就是如何高效的搜索出最近的鄰點(diǎn)。目前已經(jīng)開發(fā)出了很多對存儲的訓(xùn)練樣例進(jìn)行高效地索引的方法。比如kd樹。kd-tree把實(shí)例存儲在樹的葉結(jié)點(diǎn)內(nèi)，鄰近的實(shí)例存儲在同一個或附近的節(jié)點(diǎn)內(nèi)，通過測試新查詢xq的選定屬性，樹的內(nèi)部節(jié)點(diǎn)把查詢xq排列到相關(guān)的葉結(jié)點(diǎn)2003.12.1817機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬這一小節(jié)留下的問題就是，根據(jù)K近鄰算法，由于K值的不同，確定待分類實(shí)例的分類也不同，那么K是如何選取的？2003.12.1818機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬術(shù)語解釋來自統(tǒng)計(jì)模式識別領(lǐng)域的術(shù)語回歸：逼近一個實(shí)數(shù)值的目標(biāo)函數(shù)殘差：逼近目標(biāo)函數(shù)時的誤差核函數(shù)：一個距離函數(shù)，用來決定每個訓(xùn)練樣例的權(quán)值，就是使wi=K(d(xi,xq))的函數(shù)K（核函數(shù)就是關(guān)于距離的函數(shù)）2003.12.1819機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬局部加權(quán)回歸前面描述的最近鄰方法可以被看作在單一的查詢點(diǎn)x=xq上逼近目標(biāo)函數(shù)f(x)理解：最近鄰算法目標(biāo)函數(shù)的建立只與xq有關(guān)局部加權(quán)回歸是上面方法的推廣，它在環(huán)繞xq的局部區(qū)域內(nèi)為目標(biāo)函數(shù)f建立明確的逼近局部加權(quán)回歸，對于要查詢的實(shí)例xq，找到它附近的K個訓(xùn)練樣例，通過這些訓(xùn)練樣例來訓(xùn)練的權(quán)值，形成對f的局部逼近，再刪除；對于新的待分類實(shí)例，再根據(jù)它的最近訓(xùn)練樣例建立新的目標(biāo)函數(shù)。其中可以使用線性函數(shù)、二次函數(shù)、多層神經(jīng)網(wǎng)絡(luò)在環(huán)繞xq的鄰域內(nèi)逼近目標(biāo)函數(shù)2003.12.1820機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬局部加權(quán)回歸的名稱解釋局部：目標(biāo)函數(shù)的逼近僅僅根據(jù)查詢點(diǎn)附近的數(shù)據(jù)加權(quán)：每個訓(xùn)練樣例的貢獻(xiàn)由它與查詢點(diǎn)間的距離加權(quán)得到回歸：表示逼近實(shí)數(shù)值函數(shù)的問題2003.12.1821機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬局部加權(quán)線性回歸本節(jié)，使用如下形式的線性函數(shù)來逼近xq鄰域的目標(biāo)函數(shù)f第4章我們討論了梯度下降方法，在擬合以上形式的線性函數(shù)到給定的訓(xùn)練集合時，它被用來找到使誤差最小化的系數(shù)w0...wn，當(dāng)時我們感興趣的是目標(biāo)函數(shù)的全局逼近，所以建立了誤差準(zhǔn)則，即 得到的梯度下降訓(xùn)練法則是2003.12.1822機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬局部加權(quán)線性回歸（2）三種重新定義誤差準(zhǔn)則E，以著重于擬合局部訓(xùn)練樣例，記為E(xq)（1）只對在k個近鄰上的誤差平方最小化（2）使整個訓(xùn)練樣例集合D上的誤差平方最小化，但對每個訓(xùn)練樣例加權(quán)，權(quán)值為關(guān)于相距xq距離的某個遞減函數(shù)K（3）綜合1和22003.12.1823機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬局部加權(quán)線性回歸（3）準(zhǔn)則2或許最令人滿意，但是它所需的計(jì)算量隨著訓(xùn)練樣例數(shù)量線性增長準(zhǔn)則3很好地近似了準(zhǔn)則2，并且具有如下優(yōu)點(diǎn)：計(jì)算開銷獨(dú)立于訓(xùn)練樣例總數(shù)，僅依賴于最近鄰數(shù)k對應(yīng)準(zhǔn)則3的梯度下降法則是2003.12.1824機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬局部加權(quán)回歸的說明大多數(shù)情況下，通過一個常量、線性函數(shù)或二次函數(shù)來局部逼近目標(biāo)函數(shù)，更復(fù)雜的函數(shù)形式不太常見，原因是：對每個查詢實(shí)例用更復(fù)雜的函數(shù)來擬合，其代價十分高昂在足夠小的實(shí)例空間子域上，使用這些簡單的近似已能很好地模擬目標(biāo)函數(shù)2003.12.1825機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬徑向基函數(shù)徑向基函數(shù)是另一種實(shí)現(xiàn)函數(shù)逼近的方法，它與距離加權(quán)回歸和人工神經(jīng)網(wǎng)絡(luò)都有著緊密聯(lián)系（積極的學(xué)習(xí)方法）待學(xué)習(xí)的假設(shè)是一個以下形式的函數(shù)

xu是X中一個實(shí)例，核函數(shù)Ku(d(xu,x))被定義為隨距離d(xu,x)的增加而減小的函數(shù)，k是用戶提供的常量，用來指定要包含的核函數(shù)的數(shù)量盡管

是對f(x)的全局逼近，但來自每個Ku(d(xu,x))項(xiàng)的貢獻(xiàn)被局部化到點(diǎn)xu附近的區(qū)域2003.12.1826機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬徑向基函數(shù)（2）一種很常見核函數(shù)的做法是選擇每個核函數(shù)Ku(d(xu,x))為高斯函數(shù)（表示正態(tài)分布的函數(shù)）Hartmanetal.1990指出，這種形式的核函數(shù)能夠以任意小的誤差逼近任何函數(shù)，只要以上高斯核的數(shù)量足夠大，并且可以分別指定每個核的寬度圖8-2徑向基函數(shù)網(wǎng)絡(luò)（RBF），式子8.8給出的函數(shù)可以看作是描述了一個兩層的網(wǎng)絡(luò)，第一層計(jì)算不同的Ku(d(xu,x))，第二層計(jì)算第一層單元值的線性組合2003.12.1827機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬給定了目標(biāo)函數(shù)的訓(xùn)練樣例集合，一般分兩個階段來訓(xùn)練RBF網(wǎng)絡(luò)首先，決定隱藏單元的數(shù)量k，并通過定義核函數(shù)中心點(diǎn)xu和方差來定義每個隱藏單元其次，使用下面式子給出的全局誤差準(zhǔn)則來訓(xùn)練權(quán)值wu，使網(wǎng)絡(luò)擬合訓(xùn)練數(shù)據(jù)程度最大化2003.12.1828機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬徑向基函數(shù)（3）已經(jīng)提出了幾種方法來選取適當(dāng)?shù)碾[藏單元或核函數(shù)的數(shù)量（1）為每一個訓(xùn)練樣例<xi,f(xi)>分配一個高斯核函數(shù)，中心點(diǎn)設(shè)為xi，所有高斯函數(shù)的寬度可被賦予同樣的值RBF網(wǎng)絡(luò)學(xué)習(xí)目標(biāo)函數(shù)的全局逼近，其中每個訓(xùn)練樣例<xi,f(xi)>都只在xi的鄰域內(nèi)影響

的值（理解：根據(jù)高斯核函數(shù)的定義，根據(jù)d，它的貢獻(xiàn)被局部化到xi點(diǎn)附近的區(qū)域）這種核函數(shù)的一個優(yōu)點(diǎn)是允許RBF網(wǎng)絡(luò)精確地擬合訓(xùn)練數(shù)據(jù)。也就是說，對于任意m個訓(xùn)練樣例集合，合并m個高斯核函數(shù)的權(quán)值w0...wm，這些權(quán)值可以被設(shè)置為使得對于每個訓(xùn)練樣例<xi,f(xi)>都滿足2003.12.1829機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬徑向基函數(shù)（4）（2）選取一組數(shù)量少于訓(xùn)練樣例數(shù)量的核函數(shù)，這種方法更有效，特別是訓(xùn)練樣例數(shù)量很多的時候。核函數(shù)分布在整個實(shí)例空間X上，它們中心之間有均勻的間隔或者也可以非均勻地分布核函數(shù)中心，特別是在實(shí)例本身在X上非均勻分布的時候可以隨機(jī)選取訓(xùn)練樣例的一個子集作為核函數(shù)的中心，從而對實(shí)例的基準(zhǔn)分布進(jìn)行采樣或者可以標(biāo)識出實(shí)例的原始聚類，然后以每個聚類為中心加入一個核函數(shù)把訓(xùn)練實(shí)例擬合到混合高斯，6.12.1節(jié)討論的EM算法提供了一種從k個高斯函數(shù)的混合中選擇均值，以最佳擬合觀察到實(shí)例的方法2003.12.1830機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬徑向基函數(shù)（5）總而言之，用多個局部核函數(shù)的線性組合表示的徑向基函數(shù)網(wǎng)絡(luò)提供了一種目標(biāo)函數(shù)的全局逼近僅當(dāng)輸入落入某個核函數(shù)的中心和寬度所定義的區(qū)域時，這個核函數(shù)的值才是不可忽略的（不在這個區(qū)域時，由于距離太遠(yuǎn)即核函數(shù)的值很小時，可以忽略）RBF網(wǎng)絡(luò)可以被看作目標(biāo)函數(shù)的多個局部逼近的平滑線性組合RBF網(wǎng)絡(luò)的一個優(yōu)點(diǎn)是，與反向傳播算法訓(xùn)練的前饋網(wǎng)絡(luò)相比，它的訓(xùn)練更加高效，這是因?yàn)镽BF網(wǎng)絡(luò)的輸入層和輸出層可以被分別訓(xùn)練2003.12.1831機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬基于案例的推理k-近鄰算法和局部加權(quán)回歸具有三個共同的關(guān)鍵特性：消極學(xué)習(xí)方法通過分析相似的實(shí)例來分類新的查詢實(shí)例，而忽略與查詢極其不同的實(shí)例實(shí)例表示為n維歐氏空間中的實(shí)數(shù)點(diǎn)基于案例的推理（CBR）滿足前2個原則，但不滿足第3個CBR使用更豐富的符號描述來表示實(shí)例，用來檢索實(shí)例的方法也更加復(fù)雜2003.12.1832機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬基于案例的推理（2）CBR已被用于解決很多問題根據(jù)數(shù)據(jù)庫中存儲的以前的設(shè)計(jì)圖紙，來進(jìn)行機(jī)械設(shè)備的總體設(shè)計(jì)根據(jù)以前的裁決來對新的法律案件進(jìn)行推理通過對以前的相似問題的解決方案的復(fù)用或合并，解決規(guī)劃和調(diào)度問題2003.12.1833機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬基于案例的推理（3）一個例子：CADET系統(tǒng)采用基于案例的推理來輔助簡單機(jī)械設(shè)備的總體設(shè)計(jì)（圖8-3）目的使用一個數(shù)據(jù)庫，其中包含大約75個以前的設(shè)計(jì)或設(shè)計(jì)片斷，來推薦符合新的設(shè)計(jì)規(guī)格的總體設(shè)計(jì)。內(nèi)存中每一個實(shí)例是通過它的結(jié)構(gòu)和定性的功能來表示的。2003.12.1834機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬方法給定新設(shè)計(jì)問題的功能說明，CADET從它的案例庫中搜索存儲的案例，使它的功能描述和新設(shè)計(jì)問題相匹配如果發(fā)現(xiàn)了一個精確的匹配，表明某個存儲案例精確地實(shí)現(xiàn)了所要求的功能，那么可以返回這個案例作為新設(shè)計(jì)問題的建議方案否則，CADET可能找到匹配所需功能的不同子圖的案例在兩個功能圖間搜索同構(gòu)子圖，以發(fā)現(xiàn)一個案例的某部分，使它匹配更多的案例系統(tǒng)還可以加工原始的功能說明圖，產(chǎn)生等價的子圖以匹配更多的案例2003.12.1835機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬基于案例的推理（4）通過檢索匹配不同子圖的多個案例，有時可以拼接得到整個設(shè)計(jì)但是，從多個檢索到的案例產(chǎn)生最終方案的過程可能很復(fù)雜為了合并存儲案例中檢索到的部分，可能需要從頭設(shè)計(jì)系統(tǒng)的各個部分，也可能需要回溯以前的設(shè)計(jì)子目標(biāo)，從而丟棄前面檢索到的案例CADET合并和自適應(yīng)已檢索到案例并形成最終設(shè)計(jì)的能力有限，它主要依賴用戶來做自適應(yīng)階段的處理。CADET本身不具備用來把這些抽象的總體設(shè)計(jì)提煉成最終設(shè)計(jì)的分析算法。2003.12.1836機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬基于案例的推理（5）CADET的問題框架在CADET中每個存儲的訓(xùn)練樣例描繪了一個功能圖以及實(shí)現(xiàn)該功能的結(jié)構(gòu)實(shí)例空間定義為所有功能圖的空間，目標(biāo)函數(shù)f就是把功能映射到實(shí)現(xiàn)這些功能的結(jié)構(gòu)每個存儲訓(xùn)練樣例<x,f(x)>是一個序偶，描述某個功能圖x和實(shí)現(xiàn)x的結(jié)構(gòu)f(x)系統(tǒng)通過學(xué)習(xí)訓(xùn)練樣例，以輸出滿足功能圖查詢輸入xq的結(jié)構(gòu)f(xq)2003.12.1837機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬基于案例的推理（6）CADET系統(tǒng)區(qū)別于k-近鄰方法的一般特征實(shí)例（或稱案例）可以用豐富的符號描述表示，因此可能需要不同于歐氏距離的相似性度量檢索到的多個案例可以合并形成新問題的解決方案，合并案例的過程與k-近鄰方法不同，依賴于知識推理而不是統(tǒng)計(jì)方法案例檢索、基于知識的推理、問題求解是緊密耦合在一起的一個研究課題：改進(jìn)索引案例的方法句法相似度量僅能近似地指出特定案例與特定問題的相關(guān)度，而不能捕捉其他難點(diǎn)，比如多個設(shè)計(jì)片斷的不兼容性發(fā)現(xiàn)這些難點(diǎn)后，可以回溯搜索另外的案例以適應(yīng)現(xiàn)有的案例（重新搜索）；或者換一種方法解決。2003.12.1838機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬對消極學(xué)習(xí)和積極學(xué)習(xí)的評價三種消極學(xué)習(xí)方法：k-近鄰、局部加權(quán)回歸、基于案例的推理一種積極學(xué)習(xí)方法：學(xué)習(xí)徑向基函數(shù)網(wǎng)絡(luò)的方法消極方法和積極方法的差異：計(jì)算時間的差異消極算法在訓(xùn)練時需要較少的計(jì)算，但在預(yù)測新查詢的目標(biāo)值時需要更多的計(jì)算時間對新查詢的分類的差異（歸納偏置的差異）消極方法在決定如何從訓(xùn)練數(shù)據(jù)D中泛化時考慮查詢實(shí)例xq積極方法在見到xq之前，就完成了泛化核心觀點(diǎn)：消極學(xué)習(xí)可以通過很多局部逼近的組合表示目標(biāo)函數(shù)，積極學(xué)習(xí)必須在訓(xùn)練時提交單個的全局逼近2003.12.1839機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬對消極學(xué)習(xí)和積極學(xué)習(xí)的評價（2）使用多個局部逼近的積極方法，可以產(chǎn)生與消極方法的局部逼近同樣的效果嗎？徑向基函數(shù)網(wǎng)絡(luò)是對這個目標(biāo)的嘗試RBF學(xué)習(xí)方法是在訓(xùn)練時提交目標(biāo)函數(shù)全局逼近的積極方法，然而，一個RBF網(wǎng)絡(luò)把這個全局函數(shù)表示為多個目標(biāo)局部核函數(shù)的線性組合RBF學(xué)習(xí)方法創(chuàng)建的局部逼近不能達(dá)到像消極學(xué)習(xí)方法中那樣特別針對查詢點(diǎn)2003.12.1840機(jī)器學(xué)習(xí)-基于實(shí)例的學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬小結(jié)基于實(shí)例的學(xué)習(xí)方法推遲處理訓(xùn)練樣例，直到必須分類一個新查詢實(shí)例時才進(jìn)行。它