人工智能教案05章機(jī)器學(xué)習(xí)5.4實(shí)例學(xué)習(xí)方法

1、54實(shí)例學(xué)習(xí)方法基于實(shí)例的學(xué)習(xí)是典型的歸納學(xué)習(xí)方法。該方法的學(xué)習(xí)過程基于環(huán)境提供的大量特殊的實(shí)例，系統(tǒng)通過對事先標(biāo)注了正例、反例的示教例子的分析，進(jìn)行歸納推理，得到一般的規(guī)則。機(jī)器將系統(tǒng)的低水平的信息歸納成為高水平的信息，一般情況下，用這些信息（規(guī)則）指導(dǎo)執(zhí)行環(huán)節(jié)。整個(gè)過程有一整套比較完善的算法。實(shí)例方法早在50年代就引起了人工智能學(xué)者的注意，是在機(jī)器學(xué)習(xí)領(lǐng)域中研究最充分成果最豐富的一個(gè)分支。實(shí)例學(xué)習(xí)在某些系統(tǒng)中的應(yīng)用已經(jīng)成為機(jī)器學(xué)習(xí)走向?qū)嵱玫南葘?dǎo)。541實(shí)例學(xué)習(xí)的基本理論如上一節(jié)所述，實(shí)例學(xué)習(xí)是一種歸納學(xué)習(xí)方法，從大量的學(xué)習(xí)樣本中歸納總結(jié)出相應(yīng)的規(guī)則、概念。首先我們使用Winston（197

2、5年開發(fā)）提出的結(jié)構(gòu)化概念學(xué)習(xí)程序的例子作為模型來說明實(shí)例學(xué)習(xí)的過程。Winston的程序是對簡單的積木世界領(lǐng)域中進(jìn)行操作，其目的是要建立積木世界中物體概念定義的結(jié)構(gòu)化表示，例如學(xué)習(xí)房子、帳篷和拱的概念，構(gòu)造出這些概念定義的結(jié)構(gòu)化描述。系統(tǒng)的輸入是積木世界某物體（或景象）的線條圖，使用語義網(wǎng)絡(luò)來表示該物體結(jié)構(gòu)化的描述。例如，系統(tǒng)要學(xué)習(xí)拱橋的概示，這個(gè)結(jié)構(gòu)化的描述就是拱橋概念的定義。接著再向程序輸入第二個(gè)拱橋示例，其描述如圖2所示。這時(shí)學(xué)習(xí)程序可歸納出圖3所示的描述。念，就給學(xué)習(xí)程序輸入第一個(gè)拱橋示例，得到的描述如下圖1所假定下一步向程序輸入一個(gè)拱橋概念的近似樣品，并告知程序，這不是拱橋（即拱橋

3、的反例），則比較程序會發(fā)現(xiàn)當(dāng)前的定義描述（圖）與近似樣品的描述只是在和節(jié)點(diǎn)之間，不接觸”的鏈接弧有區(qū)別。由于近似樣品不是拱橋，不是推廣當(dāng)前定義描述去概括它，而是要限制該定義描述適用的范圍，因而就要把“不接觸”鏈接修改為“必須不接觸”，這是拱橋概念的描述如圖4所示。這就是機(jī)器最后學(xué)習(xí)得到的拱橋概念。圖5-拱4橋概念的歸納學(xué)習(xí)過程下圖是實(shí)例學(xué)習(xí)的兩個(gè)空間模型。實(shí)例空間是所有示教例子的集合，而規(guī)則空間是所有規(guī)則的集合。實(shí)例學(xué)習(xí)應(yīng)在規(guī)則空間中搜索、匹配所求的規(guī)則，并在實(shí)例空間中選擇一些示教例子，以便解決規(guī)則空間中某些規(guī)則的歧義性，系統(tǒng)就是這樣在實(shí)例空間和規(guī)則空間中交替進(jìn)行搜索，直到找到所要求的規(guī)則。圖

4、5-實(shí)5例學(xué)習(xí)的兩個(gè)空間模型首先由示教者給實(shí)例空間提供一些初始示教例子，由于示教例子的形式往往不同于規(guī)則的形式，程序必須對示教例子進(jìn)行解釋，然后再利用被解釋的示教例子去搜索規(guī)則空間。一般情況下，不能一次就從規(guī)則空間中搜索到要求的規(guī)則，因此還要尋找一些新的示教例子，這個(gè)過程就是選擇示教例子。解釋例子和選擇例子這兩個(gè)過程如此循環(huán)，直到搜索到要求的規(guī)則。實(shí)例空間和規(guī)則空間的例子：下面考慮教計(jì)算機(jī)程序撲克牌中“同花”概念的問題，同花是指五張牌同一花色所組成的一手牌。在這個(gè)學(xué)習(xí)問題中，實(shí)例空間是五張牌的全部各手牌的集合。我們把這個(gè)空間中單個(gè)的點(diǎn)表示為一組五個(gè)有序?qū)?，比如?梅花），（3梅花），（5梅花）

5、，（J梅花），（,梅花）每一有序?qū)χ该饕粡埮频狞c(diǎn)數(shù)和花色。整個(gè)實(shí)例空間是所有這樣的五張牌集合的空間。這個(gè)問題的規(guī)則空間是描述一手牌的全部謂詞表達(dá)式的集合。這些表達(dá)式使用下列符號描述：謂詞：（花色）、（點(diǎn)數(shù)）表示牌的變量：，和某些必要的自由變量：x,yz,某些必要的常量：梅花、方塊、紅心、黑桃、4、5、6、7、8、9、10、J、Q、K1.1.15223.3.22323235,222.規(guī)則的表示形式應(yīng)適應(yīng)歸納推理542實(shí)例學(xué)習(xí)方法的分類實(shí)例學(xué)習(xí)的方法有幾種，可以根據(jù)搜索策略的不同進(jìn)行分類，也可以根據(jù)所處理的任務(wù)的復(fù)雜度的不同進(jìn)行分類。1按搜索方法分類1按搜索方法分類：也就是搜索規(guī)則空間的方法，可分

6、為數(shù)據(jù)驅(qū)動(dòng)方法和模型驅(qū)動(dòng)方法。主要有：變形空間法、改進(jìn)假設(shè)法、產(chǎn)生與測試法、方案示例法。學(xué)習(xí)的最終目的是為了搜索，有了假設(shè)空間H的基礎(chǔ)，在該空間中進(jìn)行搜索。改進(jìn)假設(shè)空間的假設(shè)規(guī)則集，以便得到所要求的規(guī)則。下面介紹幾種搜索規(guī)則空間的方法。這些方法都具有一個(gè)假設(shè)規(guī)則集合H，不同的僅僅是對H的改進(jìn)方法?？谧冃涂臻g法：變型空間法(version-spacmeethod)是一種數(shù)據(jù)驅(qū)動(dòng)方法（data-drivemethod）。這種方法對規(guī)則和實(shí)例都采用同一種表示形式。初始的假設(shè)規(guī)則集H包括滿足第一個(gè)示教例子和全部規(guī)則。在得到下一個(gè)示教例子時(shí)，對集合H進(jìn)行一般化或特殊化處理，最后使集合H收斂為僅含要求的規(guī)

7、則?？诟倪M(jìn)假設(shè)法：改進(jìn)假設(shè)皿hypothesis-refinememnethod)也是一種數(shù)據(jù)驅(qū)動(dòng)方法。這種方法表示規(guī)則和實(shí)例的形式不統(tǒng)一。程序根據(jù)例子選擇一種操作，用該操作去改進(jìn)假設(shè)規(guī)則集H中的規(guī)則。產(chǎn)生與測試法：產(chǎn)生與測試法(generateandtes)t是一種模型驅(qū)動(dòng)方法(model-drivenmethod)。這種方法針對示教例子反復(fù)產(chǎn)生和測試假設(shè)的規(guī)則。在產(chǎn)生假設(shè)規(guī)則時(shí)，使用基于模型的知識，以便只產(chǎn)生可能合理的假設(shè)。方案示例法：方案示例皿schemainstantiat)也是一種模型驅(qū)動(dòng)方法。該方法使用規(guī)則方案的集合來約束可能合理的規(guī)則的形式，其中最符合示教例子的規(guī)則方案被認(rèn)為是最

8、合理的規(guī)則。數(shù)據(jù)驅(qū)動(dòng)方法的優(yōu)點(diǎn)是可以逐步接受示教例子，以漸進(jìn)方H，因此一個(gè)錯(cuò)誤實(shí)例就會造成集合式學(xué)習(xí)，特別是變型空間法，它很容易修改集合回溯就可以考慮新的實(shí)例。模型驅(qū)動(dòng)方法難以逐步學(xué)習(xí)，假設(shè)。在使用新假設(shè)時(shí)，它必須回溯或重新搜索規(guī)則空間。因?yàn)樵瓉韺僭O(shè)的測試已不適用于新實(shí)例加入后的情況。模型驅(qū)動(dòng)方法的優(yōu)點(diǎn)是抗干擾性良好。合，程序就可以對假設(shè)進(jìn)行統(tǒng)計(jì)測量。它不因一、二個(gè)錯(cuò)誤實(shí)例而放棄正確的假設(shè)。當(dāng)前新的實(shí)例去修改集合的混亂。解決的方法是每次用新實(shí)例去修改集合小的修改，這樣可以減少錯(cuò)誤實(shí)例帶來的影響，得學(xué)習(xí)的進(jìn)程變慢了。H，不要求程序它是通過檢查全部實(shí)例來測試由于使用整個(gè)實(shí)例集在用錯(cuò)誤實(shí)例測試假設(shè)

9、時(shí)，而數(shù)據(jù)驅(qū)動(dòng)方法用HH時(shí)，只作較當(dāng)然這也同時(shí)使2按任務(wù)復(fù)雜程度55系統(tǒng)的任務(wù)不同，相應(yīng)的學(xué)習(xí)方法的目的、方法也不同。可以分為：學(xué)習(xí)單個(gè)概念、學(xué)習(xí)多個(gè)概念、學(xué)習(xí)執(zhí)行多步任務(wù)。學(xué)習(xí)單個(gè)概念是最基本的理論方法，本節(jié)只介紹學(xué)習(xí)單個(gè)概念的方法步驟。學(xué)習(xí)多個(gè)概念是在學(xué)習(xí)單個(gè)概念的基礎(chǔ)上進(jìn)行的，但不僅僅是簡單的運(yùn)算次數(shù)的增加。學(xué)習(xí)執(zhí)行多步任務(wù)時(shí)，執(zhí)行環(huán)節(jié)對任務(wù)要進(jìn)行規(guī)劃，這也是學(xué)習(xí)的目標(biāo)之一。對于單概念學(xué)習(xí)，學(xué)習(xí)的目的是從概念空間（即規(guī)則空間）中尋找某個(gè)與實(shí)例空間一致的概念；對于多概念學(xué)習(xí)，任務(wù)是在概念空間中找出若干概念描述，對于每一概念描述，實(shí)例空間中均有相應(yīng)的空間與之相應(yīng)。下圖給出了兩種學(xué)習(xí)方法實(shí)例空

10、間劃分上的差異。圖5-單6個(gè)概念與多個(gè)概念學(xué)習(xí)空間劃分示意圖單概念學(xué)習(xí)系統(tǒng)實(shí)例空間劃分多概念學(xué)習(xí)系統(tǒng)實(shí)例空間劃分單個(gè)概念的學(xué)習(xí)是提供給系統(tǒng)一個(gè)概念的若干正例和若干反例，系統(tǒng)由此構(gòu)成規(guī)則空間，并可得到在這個(gè)規(guī)則空間中的一個(gè)概念。這個(gè)概念應(yīng)包含所有的正例，但不包含任何反例。該學(xué)習(xí)方法有兩個(gè)假設(shè)，其一是示教例子必須是系統(tǒng)所學(xué)的概念的例子，要么是正例，要么是反例（如果違反了這一假設(shè)，那么就變55543變型空間法15.4.3.155少有一張梅花牌且至少有一張紅心牌，它比前兩個(gè)概念更特殊。圖中的箭頭用來指向從特殊概念到一般概念。圖中最下面一行的各點(diǎn)是正例直接對應(yīng)的概念，每一個(gè)點(diǎn)的概念只符合一個(gè)正例?，F(xiàn)在一

11、手牌，例子是每張牌的花色和點(diǎn)數(shù)，比如：SUIT(CLUBS.JARANK7)這是一個(gè)正例，一個(gè)最特殊的概念。而概念是規(guī)則空間中的點(diǎn)，它比沒有描述要特殊，比示教正例要一般。示教例子應(yīng)該是有具體花色、具體點(diǎn)數(shù)的某一張或一組牌。規(guī)則空間結(jié)構(gòu)圖如下：圖5-規(guī)8則空間的結(jié)構(gòu)如圖所示，規(guī)則空間中最一般的元素構(gòu)成子集；規(guī)則空間中最特殊的元素構(gòu)成的子集為。在假設(shè)規(guī)則集合是以為上確界和以為下確界的一段。因此，可以用和來表示集合。學(xué)習(xí)過程就是向下、向上變化的過程，也就是說學(xué)習(xí)時(shí)規(guī)則空間的形狀在發(fā)生變化，所以稱為變形空間法。最后，成為一個(gè)點(diǎn)，學(xué)習(xí)結(jié)束。上圖中規(guī)則空間初始時(shí)，最上邊是一般規(guī)則(概念)，沒有描述、沒有條

12、件的一個(gè)點(diǎn)。滿足所有例子，如。最下面一行是各個(gè)具體的正例直接對應(yīng)的概念。如撲克牌的某一張或一組牌。下面要討論的就是如何修改規(guī)則空間，降低G，提升S，使縮小成一點(diǎn)的方法。34345.4.3.2下面給出一個(gè)消除候選元素法的實(shí)例。在這個(gè)例子中，用特征向量描述物體，每個(gè)物體有兩個(gè)特征，即大小和形狀。物體的大小用大（）或小（）來描述。物體的形狀用圓（i方（）或三角（）來描述。若用表示大小，表示形狀，那么要教給程序圓的概念，就可以表示為（）。我們按消除候選元素法的步驟學(xué)習(xí)概念。步驟：把集合初始化為最一般的概念，把集合初始化為包含所有可能的情況，現(xiàn)在提供第一個(gè)示教正例，表示小圓是圓。由于集合滿足正例的要求，所以不發(fā)生變化，而集合原有的元素太多，先將其刪去，僅保留符合該次正例的元素，接下來的學(xué)習(xí)過程中，再由陸續(xù)示教的正例進(jìn)行補(bǔ)充集合S。步驟：接受新的示教例子，這個(gè)例子是。這表示大三角不是圓。這個(gè)是反例，必須刪去中符合反例的元素，使得集合特殊化。在規(guī)則空間中的變化是下降。由于示教的是反例，所以集合沒有變化。得到：如圖所示，此時(shí)僅含有二個(gè)概念。這二個(gè)概念是滿足第一個(gè)例子，但不滿足第二個(gè)例子的全部概念。接受第二個(gè)示教例子,這是一個(gè)正例，表示大圓是圓。首先從中刪除不滿足此正例的概念，再對中原有的元素和本示教例子的做一般化操作（將常量變成變量），得到：步驟：由于此時(shí)，且兩個(gè)集合中僅包