1、第11章分析學(xué)習(xí) 簡(jiǎn)介 用完美的領(lǐng)域理論學(xué)習(xí)：PROLOG-EBG 對(duì)基于解釋的學(xué)習(xí)的說(shuō)明 搜索控制知識(shí)和基于解釋的學(xué)習(xí) 小結(jié)和補(bǔ)充讀物 神經(jīng)網(wǎng)絡(luò)和決策樹(shù)這樣的學(xué)習(xí)方法需要一定數(shù)目的訓(xùn)練樣例才能達(dá)到一定級(jí)別的泛化精度。前面討論的理論界限和實(shí)驗(yàn)結(jié)果反映出了這一事實(shí)。 分析學(xué)習(xí)適用先驗(yàn)知識(shí)和演繹推理來(lái)擴(kuò)大訓(xùn)練樣例提供的信息， 因此它不受同樣的界限制約。 本章考慮了一種稱(chēng)為基于解釋的學(xué)習(xí)（EBL）的分析學(xué)習(xí)方法。在基于解釋的學(xué)習(xí)中，先驗(yàn)知識(shí)用于分析（或者解釋?zhuān)┯^察到的學(xué)習(xí)樣例是怎樣滿足目標(biāo)概念的。然后這個(gè)解釋被用于區(qū)分訓(xùn)練樣例中哪些是相關(guān)的特征，哪些是不相關(guān)的。這樣，樣例就可基于邏輯推理進(jìn)行泛化，而

2、不是基于統(tǒng)計(jì)推理。 基于解釋的學(xué)習(xí)已被成功地用于在各種規(guī)劃和調(diào)度任務(wù)中學(xué)習(xí)搜 索控制規(guī)則。11.1 簡(jiǎn)介 歸納學(xué)習(xí)器在實(shí)踐中的一個(gè)關(guān)鍵限制是，它們?cè)诳捎脭?shù)據(jù)不足時(shí) 性能較差。理論分析顯示，從給定數(shù)目的訓(xùn)練樣例中學(xué)習(xí)時(shí)精度存在基本的上下界。 能否開(kāi)發(fā)出這樣的學(xué)習(xí)方法，它們訓(xùn)練精度上的基本限制不受可 用訓(xùn)練數(shù)據(jù)的數(shù)量所制約？答案是肯定的。 一種辦法是使學(xué)習(xí)算法能接受顯式的先驗(yàn)知識(shí)，與訓(xùn)練數(shù)據(jù)一同作為輸入。基于解釋的學(xué)習(xí)是這樣的一種方法。它使用先驗(yàn)知識(shí)來(lái)分析或解釋每個(gè)訓(xùn)練樣例，以推理出樣例的哪些特征與目標(biāo)函數(shù)相關(guān)，哪些不相關(guān)。這些解釋能使學(xué)習(xí)器比單獨(dú)依靠數(shù)據(jù)進(jìn)行泛化有更高的精度。例如，歸納邏輯系統(tǒng)使

3、用先驗(yàn)背景知識(shí)來(lái)指 導(dǎo)學(xué)習(xí)。然而它們使用背景知識(shí)推理出的特征擴(kuò)大了輸入實(shí)例的 描述，因此增加了待搜索假設(shè)空間的復(fù)雜度。 相反，基于解釋的學(xué)習(xí)使用先驗(yàn)知識(shí)來(lái)減小待搜索假設(shè)空間的復(fù) 雜度，減小了樣本復(fù)雜度并提高了學(xué)習(xí)器的泛化精度。11.1 簡(jiǎn)介(續(xù)1) 在下棋（以及其他搜索密集的問(wèn)題，如調(diào)度和規(guī)劃）這樣的人類(lèi)學(xué)習(xí)中，包含了一個(gè)很長(zhǎng)的發(fā)現(xiàn)先驗(yàn)知識(shí)的過(guò)程，它是由下棋時(shí)遇到的特定樣例所引導(dǎo)的。 在歸納學(xué)習(xí)中，學(xué)習(xí)器被賦予一個(gè)假設(shè)空間H，它必須從中選擇 一個(gè)輸出假設(shè)。還有一個(gè)訓(xùn)練樣例集合D=, 其中f(xi)為實(shí)例的xi目標(biāo)值。學(xué)習(xí)器所希望的輸出為H中與這些訓(xùn)練樣例一致的假設(shè)h。 在分析學(xué)習(xí)中，學(xué)習(xí)器的輸

4、入包含與歸納學(xué)習(xí)同樣的假設(shè)空間H 和訓(xùn)練樣例D。學(xué)習(xí)器還有另一輸入：一個(gè)領(lǐng)域理論（domain theory）B，它由可用于解釋訓(xùn)練樣例的背景知識(shí)組成。學(xué)習(xí)器希望的輸出為H中的假設(shè)h，它既與訓(xùn)練樣例D一致，也與領(lǐng)域理 論B一致。11.1 簡(jiǎn)介（續(xù)2） 如學(xué)習(xí)到的假設(shè)一樣，領(lǐng)域理論由一組Horn子句描述，它使系統(tǒng)在訓(xùn)練樣例的描述中，但是由更原子的實(shí)例屬性如Material, Density和Volume使用領(lǐng)域中其它規(guī)則推理得出。11.2 用完美的領(lǐng)域理論學(xué)習(xí)：PROLOG-EBG 當(dāng)領(lǐng)域理論中的每個(gè)斷言都是客觀的真實(shí)描述時(shí)，該領(lǐng)域理論是 正確的。 當(dāng)領(lǐng)域理論覆蓋了實(shí)例空間中所有正例時(shí)，該領(lǐng)域理

5、論被稱(chēng)為完 整的（對(duì)應(yīng)給定的目標(biāo)概念和實(shí)例空間）。 換言之，其完整性說(shuō)明，每個(gè)滿足目標(biāo)概念的實(shí)例都可由領(lǐng)域理論證明其滿足性。 注意：完整性的定義可包含全部正例和反例。PROLOG-EBG（續(xù)1） 對(duì)于學(xué)習(xí)器假定有這樣的完美領(lǐng)域理論是否合理？既然學(xué)習(xí)器有 一個(gè)完美的領(lǐng)域理論，還有何必要再去學(xué)習(xí)？ 首先，某些情形下是有可能提供完美領(lǐng)域理論的。前面的下棋問(wèn)題就是這樣的一個(gè)例子。進(jìn)一步講，雖然很容易寫(xiě)出構(gòu)成領(lǐng)域理論的棋子合法步子，要寫(xiě)出最優(yōu)下棋策略仍然很難。 第二，在許多情況下不能夠有完美的領(lǐng)域理論。比如很難為前面這個(gè)相對(duì)簡(jiǎn)單的SafeToStack問(wèn)題給出完整而正確的領(lǐng)域理論。更實(shí)際的方法是假定必須

6、使用基于不完美領(lǐng)域理論的近似合理的解釋?zhuān)皇腔谕昝乐R(shí)做出確切證明。11.2 用完美的領(lǐng)域理論學(xué)習(xí)：PROLOG-EBG （續(xù)2） 基于解釋的學(xué)習(xí)算法PROLOG-EBG PROLOG-EBG(TargetConcept, TrainingExamples, DomainTheory) LearnedRules Pos TrainingExamples中的正例 對(duì)Pos中沒(méi)有被Learnedrules覆蓋的每個(gè)PositiveExample，做以下操作 解釋Explanation 以Domain Theory表示的解釋?zhuān)ㄗC明），說(shuō)明PositiveExample滿足TargetConcep

7、t分析SufficientConditions 按照Explanation能夠充分滿足TargetConcept的PositiveExample的最一般特征集合改進(jìn)LearnedRules LearnedRules+NewHornClause，其中NewHornClause形式為： TargetConcept SufficientConditions返回LeanedRules.11.2 用完美的領(lǐng)域理論學(xué)習(xí)：PROLOG-EBG （續(xù)3） 這里展示一個(gè)稱(chēng)為PROLOG-EBG的算法，用它作為幾種基于解釋的學(xué)習(xí)的代表。 PROLOG-EBG是一序列覆蓋算法。換言之，它的過(guò)程是學(xué)習(xí)單個(gè)Horn子句

8、規(guī)則，移去此規(guī)則覆蓋的正例，然后在剩余正例上重復(fù)這一過(guò)程。直到?jīng)]有未被覆蓋的正例為止。 若給定一完整并正確的領(lǐng)域理論，PROLOG-EBG保證輸出一個(gè)假設(shè)（規(guī)則集），它本身是正確的并能覆蓋觀察到的正例。 對(duì)任意正例集合，由PROLOG-EBG輸出的假設(shè)包含一組對(duì)應(yīng)于領(lǐng)域理論的目標(biāo)概念的邏輯充分條件。 PROLOG-EBG是由Michell et al.介紹的EBG算法的改進(jìn)。11.2 用完美的領(lǐng)域理論學(xué)習(xí)：PROLOG-EBG （續(xù)4） 運(yùn)行舉例：對(duì)每個(gè)新正例，若它還沒(méi)被一個(gè)學(xué)到的Horn子句覆蓋， 算法通過(guò)下列步驟生成一新的Horn子句（）解釋新的正例；（）分析該解釋以確定一合適的泛化；（）

9、通過(guò)加入一新的Horn子句以覆蓋該正例以及其他相似實(shí)例改進(jìn)當(dāng)前假設(shè) （）解釋訓(xùn)練樣例。處理每個(gè)新樣例的第一步是按照領(lǐng)域理論建立解釋?zhuān)f(shuō)明該正例如何滿足目標(biāo)概念。當(dāng)領(lǐng)域理論正確且完整時(shí)，此解釋構(gòu)成了訓(xùn)練樣例滿足目標(biāo)概念的證明（proof） 。如果先驗(yàn)知識(shí)不完美，解釋中的記號(hào)必須被擴(kuò)展以允許近似的參數(shù)， 而不是完美的證明。 （）分析解釋。在泛化訓(xùn)練樣例時(shí)面臨的關(guān)鍵問(wèn)題是“在當(dāng)前樣例中許多正好為真的特征中，哪一個(gè)是在一般情況下與目標(biāo)概念相關(guān)的？”11.2 用完美的領(lǐng)域理論學(xué)習(xí)：PROLOG-EBG （續(xù)5） 連同這個(gè)學(xué)到的規(guī)則，程序還可以提供其論證：對(duì)訓(xùn)練樣例的解釋形成了對(duì)此規(guī)則正確性的證明。雖然此

10、解釋是為了覆蓋觀察到的訓(xùn)練樣例，同樣的解釋將適用于任何與此一般規(guī)則匹配的實(shí)例。 PROLOG-EBG可計(jì)算能由解釋論證的最一般的規(guī)則，方法是通過(guò) 計(jì)算解釋的最弱前像（weakest preimage），定義如下： 定義：結(jié)論C對(duì)應(yīng)于證明P的最弱前像（weakest preimage）為最一般的初始斷言集合A，使得A按照P涵蘊(yùn)C 。例如，目標(biāo)概念SafeToStack(x,y)對(duì)應(yīng)表中解釋的最弱前像由下面規(guī)則體給出。SaftToStack(x,y)Volume(x,vx)Density(x,dx) Equal(wx, times(vx,dx) LessThan(wx,5) Type(y,Endt

11、able) 注意這個(gè)更一般的規(guī)則不要求給出Volume和Density的特定值，但前一個(gè)規(guī)則需要，它只是對(duì)這些屬性的值進(jìn)行更一般的約束。11.2 用完美的領(lǐng)域理論學(xué)習(xí)：PROLOG-EBG （續(xù)6） (3)改進(jìn)當(dāng)前假設(shè)：每一階段的當(dāng)前假設(shè)由當(dāng)時(shí)學(xué)習(xí)到的Horn子句 集組成。每一階段，序列覆蓋算法選取一個(gè)還沒(méi)被當(dāng)前Horn子句覆蓋的新正例，解釋該正例并按照上面的過(guò)程形成新規(guī)則。此算法的要點(diǎn)如下：11.3對(duì)基于解釋的學(xué)習(xí)的說(shuō)明 PROLOG-EBG不像歸納的方法，它通過(guò)運(yùn)用先驗(yàn)知識(shí)分析單個(gè)樣例以產(chǎn)生合理的（justified）一般假設(shè)。 對(duì)樣例如何滿足目標(biāo)概念的解釋?zhuān)_定了樣例的哪些屬性是相關(guān) 的

12、：即在解釋中提及的屬性。 對(duì)解釋的進(jìn)一步分析，即回歸目標(biāo)概念以確定其對(duì)應(yīng)解釋的最弱前像，可推導(dǎo)出相關(guān)特征值的一般約束。 每個(gè)學(xué)習(xí)到的Horn子句對(duì)應(yīng)于滿足目標(biāo)概念的一個(gè)充分條件。學(xué)習(xí)到的Horn子句集覆蓋了學(xué)習(xí)器遇到的正例，以及其它與此共享同樣解釋的實(shí)例。明（續(xù)1） 學(xué)習(xí)到的Horn子句的泛化將依賴(lài)于領(lǐng)域理論的形式以及訓(xùn)練樣例被考慮的序列。 PROLOG-EBG隱含假定了領(lǐng)域理論是正確且完整的，如果領(lǐng)域理論不正確或不完整，學(xué)習(xí)到的概念也將不正確。11.3 對(duì)基于解釋的學(xué)習(xí)的說(shuō)明（續(xù)2） 在基于解釋的學(xué)習(xí)中有一些相關(guān)的觀點(diǎn)，可有助于理解其能力和限制： EBL作為理論引導(dǎo)的樣例泛化（theory-

13、guided generalization of examples）EBL使用給定的領(lǐng)域理論以從樣例中合理泛化，區(qū)分出相關(guān)和不相關(guān)的屬性，因此可以避免用于純歸納推理中的樣本復(fù)雜度界限。 EBL作為訓(xùn)練引導(dǎo)的理論重建（example-guided reformulation of theories）PROLOG-EBG算法被看做是一種重建領(lǐng)域理論到一種可 操作形式的方法。重建領(lǐng)域理論是通過(guò)創(chuàng)建這樣的規(guī)則(a)能從領(lǐng)域理論中演繹派生。(b)在一個(gè)推理步內(nèi)分類(lèi)觀察到的訓(xùn)練樣例。這樣學(xué)習(xí)到的規(guī)則可被看做是將領(lǐng)域理論重建為一組特殊情況下的規(guī)則，它能在一個(gè)推理步內(nèi)對(duì)目標(biāo)概念的實(shí)例分類(lèi)。11.3 對(duì)基于解釋

14、的學(xué)習(xí)的說(shuō)明（續(xù)3） EBL作為“僅僅”重述學(xué)習(xí)器已經(jīng)“知道”的（“just” restating what the learner already “knows”）在某種程度上，在SaftToStack例子中的學(xué)習(xí)器開(kāi)始于其目標(biāo)概念的全部知識(shí)。 因此，純粹的EBL致力于重建領(lǐng)域理論，產(chǎn)生可單步推理出訓(xùn)練 樣例分類(lèi)的一般規(guī)則。這種知識(shí)重建的過(guò)程有時(shí)被成為知識(shí)匯編（knowledge compilation），表示這種轉(zhuǎn)換是為了增加效率，而不改變系統(tǒng)知識(shí)的正確性。11.3.1 發(fā)現(xiàn)新特征 自動(dòng)學(xué)習(xí)有用特征以擴(kuò)大實(shí)例表示的問(wèn)題是機(jī)器學(xué)習(xí)的一個(gè)重要問(wèn)題。在基于解釋的學(xué)習(xí)中推導(dǎo)新特征和在神經(jīng)網(wǎng)絡(luò)的隱藏

15、單元 中歸納推導(dǎo)新特征提供了兩種不同的途徑。 因此它們依賴(lài)的信息來(lái)源不同（一個(gè)是在許多樣例上的統(tǒng)計(jì)規(guī)則， 另一個(gè)是使用領(lǐng)域理論的單個(gè)樣例分析），有可能結(jié)合兩種來(lái)源探索出新的方法。11.3.2 演繹學(xué)習(xí) 純粹的PROLOG-EBG是一個(gè)演繹的而不是歸納的學(xué)習(xí)過(guò)程。也 就是說(shuō)，通過(guò)計(jì)算解釋的最弱前像，它產(chǎn)生一個(gè)可從領(lǐng)域理論B 中演繹派生的假設(shè)h，而且覆蓋訓(xùn)練樣例D 。更精確地講， PROLOG-EBG輸出一個(gè)假設(shè)h滿足下面的約束：(D)(h xi )f(xi) D B h 第二個(gè)約束描述了領(lǐng)域理論的作用：輸出假設(shè)被進(jìn)一步約束以使其派生領(lǐng)域理論和數(shù)據(jù)。第二個(gè)約束減少了學(xué)習(xí)器在必須選擇假設(shè)時(shí)面臨的歧義

16、性。因此領(lǐng)域理論的作用是減少假設(shè)空間的有效規(guī)模并降低學(xué)習(xí)的樣本復(fù)雜度。 使用相似的記號(hào)可描繪出PROLOG-EBG所需的領(lǐng)域理論的知識(shí)類(lèi)型。確切地講假定領(lǐng)域理論B涵蘊(yùn)訓(xùn)練數(shù)據(jù)中實(shí)例的分類(lèi)：(D)(B xi )f(xi)11.3.3 基于解釋的學(xué)習(xí)的歸納偏置 輸出的假設(shè)h從D B 中演繹派生。因此領(lǐng)域理論B為一組斷言， 它們與訓(xùn)練樣例一起涵蘊(yùn)輸出假設(shè)。由于學(xué)習(xí)器的假設(shè)從此假設(shè)h 中派生，似乎PROLOG-EBG的歸納偏置就是輸入學(xué)習(xí)器的領(lǐng)域理論B 。 領(lǐng)域理論可涵蘊(yùn)多個(gè)可選的Horn子句集。因此，歸納偏置還需包含PROLOG-EBG在這些可選的Horn子句集中做出選擇的內(nèi)容。因此可以將PROLO

17、G-EBG的偏置刻畫(huà)為對(duì)極大一般化Horn子句的小集合的偏好。 近似的PROLOG-EBG歸納偏置：領(lǐng)域理論B，加上對(duì)極大一般 化Horn子句的小集合的偏好。 一個(gè)自治agent如何隨著時(shí)間改進(jìn)它的學(xué)習(xí)能力，那么最好是有一個(gè)算法，它的泛化能力可在其獲得更多的領(lǐng)域知識(shí)后增強(qiáng)。11.3.4 知識(shí)級(jí)的學(xué)習(xí) 通 察PROLOG-EBG算法，h直接從單獨(dú)的B中派生，而與D無(wú)關(guān)。 假想有一個(gè)稱(chēng)為條目枚舉器（LEMMA-ENUMERATOR）的算法。這個(gè)算法基于領(lǐng)域理論B中的斷言簡(jiǎn)單地枚舉能得到目標(biāo)概念的 所有證明樹(shù)。 第一，如果假設(shè)單獨(dú)從領(lǐng)域理論中派生，那么PROLOG-EBG中訓(xùn)練數(shù)據(jù)有什么作用？答案是

18、，訓(xùn)練樣例使PROLOG-EBG關(guān)注覆蓋實(shí)際出現(xiàn)的樣例分布的生成規(guī)則。 第二，PROLOG-EBG能否學(xué)習(xí)到一個(gè)超出隱含在領(lǐng)域理論中的 知識(shí)的假設(shè)？答案是不能。11.3.4知識(shí)級(jí)的學(xué)習(xí)（續(xù)1） 術(shù)語(yǔ)“知識(shí)級(jí)的學(xué)習(xí)”有時(shí)被用于稱(chēng)這種類(lèi)型的學(xué)習(xí)，其中學(xué)習(xí) 到的假設(shè)涵蘊(yùn)的預(yù)測(cè)超出了能被領(lǐng)域理論涵蘊(yùn)的范圍。由斷言集合Y涵蘊(yùn)的所有預(yù)測(cè)的集合稱(chēng)為Y的演繹閉包（deductive closure） 。 關(guān)鍵的區(qū)別在于，知識(shí)級(jí)的學(xué)習(xí)中B的演繹閉包是B+h演繹閉包的真子集。 學(xué)習(xí)器能夠演繹（deduce）出一個(gè)合理的假設(shè)，它既不能從領(lǐng)域理論中單獨(dú)派生，也不能從訓(xùn)練數(shù)據(jù)中單獨(dú)派生。11.4 搜索控制知識(shí)的基于解釋的學(xué)習(xí) PROLOG-EBG算法的實(shí)際能力受領(lǐng)域理論必須正確且完整這一要 求限制。能夠滿足這一要求的學(xué)習(xí)問(wèn)題的一個(gè)重要類(lèi)別為通過(guò)學(xué)習(xí)使復(fù)雜的搜索程序速度加快。實(shí)際上，應(yīng)用基于解釋的學(xué)習(xí)的最大規(guī)模的嘗試已經(jīng)開(kāi)始解決學(xué)習(xí)控制搜索的問(wèn)題，它有時(shí)又被稱(chēng)為“加速”學(xué)習(xí)。 例如，像棋類(lèi)這樣的對(duì)弈中，對(duì)合法搜索操作的定義以及搜索目 標(biāo)的定義提供了學(xué)習(xí)搜索控制知識(shí)的一個(gè)完整且正確的領(lǐng)域理論。 SOAR使用另一種不同的基于解釋的學(xué)習(xí)，稱(chēng)為Chunking，以抽出可應(yīng)用相同解釋的一般條件。SOAR已被應(yīng)用于多數(shù)的學(xué)習(xí)問(wèn)題，并被提議為人類(lèi)學(xué)習(xí)過(guò)程中一種心理學(xué)上可行的模型。的學(xué)習(xí)（續(xù)1） 為改