學習規(guī)則集合

學習規(guī)則集合1第一頁，共五十三頁，2022年，8月28日2概述對學習到的假設，最具有表征力的和最能為人類所理解的表示方法之一是if-then規(guī)則的集合本章探索若干能學習這樣的規(guī)則集合的算法其中，最重要的是學習包含變量的規(guī)則集合，或稱一階Horn子句集合由于一階Horn子句集合可被解釋為邏輯編程語言Prolog中的程序，學習的過程常被稱為歸納邏輯編程本章考察了多種學習規(guī)則集合的途徑，其中一種是基于機器定理證明器中演繹算子的逆轉第二頁，共五十三頁，2022年，8月28日3簡介在許多情況下，有必要學習一個由若干if-then規(guī)則共同定義的目標函數(shù)，比如決策樹遺傳算法本章我們討論一組不同的算法，它們直接學習規(guī)則集合，與前面算法有兩點關鍵的不同可學習包含變量的一階規(guī)則集合（一階子句的表達能力比命題規(guī)則要強得多）使用序列覆蓋算法，一次學習一個規(guī)則，以遞增的方式形成最終的規(guī)則集合第三頁，共五十三頁，2022年，8月28日4簡介（2）一階規(guī)則集合的例子ifParent(x,y)thenAncestor(x,y)ifParent(x,z)Ancestor(z,y)thenAncestor(x,y)這個規(guī)則集合很緊湊地描述了一個遞歸函數(shù)，它很難用決策樹或其他命題的方法來表示Prolog程序就是一階規(guī)則的集合，因此一個可以學習這種規(guī)則集合的通用算法，可被看作是從樣例中自動推導出Prolog程序的算法一階表示的學習系統(tǒng)在實踐中的應用在質譜儀中學習哪一個化學藥品能粘合碎片學習哪一個化學亞結構會產生誘導有機體突變的放射性物質學習有限單元網以分析物理結構中的應力第四頁，共五十三頁，2022年，8月28日5內容安排先介紹能夠學習命題規(guī)則集的算法（命題規(guī)則可看作不含變量的一階規(guī)則），算法搜尋假設空間學習析取規(guī)則集合將上面算法擴展到一階規(guī)則討論歸納邏輯的兩種通用途徑以及歸納和演繹推理的基本關系第五頁，共五十三頁，2022年，8月28日6序列覆蓋算法序列覆蓋算法學習一個規(guī)則，移去它覆蓋的數(shù)據，再重復這一過程假定已有一個子程序Learn-One-Rule，它的輸入是一組正例和反例，輸出是單個規(guī)則，它能夠覆蓋許多正例而覆蓋很少的反例我們要求輸出的規(guī)則有較高的精確度，但不必有較高的覆蓋度第六頁，共五十三頁，2022年，8月28日7序列覆蓋算法（2）序列覆蓋算法的過程在所有可用訓練樣例上執(zhí)行Learn-One-Rule再移去由其學到的規(guī)則覆蓋的正例重復上面的過程，直到規(guī)則集覆蓋正例達到希望的程度序列覆蓋算法按次序學習到一組規(guī)則，它們共同覆蓋了全部正例規(guī)則集中的規(guī)則可排序，分類新實例時可先應用精度最高的規(guī)則第七頁，共五十三頁，2022年，8月28日8表10-1學習析取規(guī)則集的序列覆蓋算法（CN2）Sequential-Covering(Target_attribute,Attributes,Examples,Threshold)Learned_rules{}RuleLearn-One-Rule(Target_attribute,Attributes,Examples)當Performance(Rule,Examples)>ThresholdLearned_rulesLearned_rules+RuleExamplesExamples-{被Rule正確分類的樣例}RuleLearn-One-Rule(Target_attribute,Attributes,Examples)Learned_rules按照在Examples上的Performance排序的Learned_rules返回Learned_rules第八頁，共五十三頁，2022年，8月28日9序列覆蓋算法（3）序列覆蓋算法將問題化簡為一系列簡單的問題，執(zhí)行的是一種貪婪搜索，它不能保證找到能覆蓋樣例的最小或最佳規(guī)則集下面重點討論Learn-One-Rule的設計，我們希望算法能夠得到較高精度的規(guī)則集，但不必覆蓋所有的正例第九頁，共五十三頁，2022年，8月28日10一般到特殊的柱狀搜索一種方法是，將假設空間搜索過程設計為與ID3算法中相似的方式，但在每一步只沿著最有希望的分支進行，即產生最佳性能的屬性-值對，而不是用增長子樹的辦法覆蓋所選屬性的所有可能值與ID3類似，可定義最佳分支，它覆蓋的樣例有最低的熵與其他貪婪算法一樣，上面算法的缺陷是，它的每一步都可能做出次優(yōu)的選擇用柱狀搜索來減小風險，即每一步保留k個最佳候選分支，每一步對k個候選分支進行處理，然后再將結果集削減至k個最可能成員第十頁，共五十三頁，2022年，8月28日11表10-2Learn-One-Rule的一種實現(xiàn)：一般到特殊柱狀搜索Learn-One-Rule(Target_attribute,Attributes,Examples,k)初始化Best_hypothesis為最一般的假設初始化Candidate_hypotheses為集合{Best_hypothesis}當Candidate_hypotheses不空，做以下操作生成下一個更特殊的候選假設All_constraints所有形式為(a=v)的約束集合，其中，a為Attributes的成員，v為出現(xiàn)在當前Examples集合中的a的值New_candidate_hypotheses對Candidate_hypotheses中每個h，循環(huán)對All_constraints中每個c，循環(huán) 通過加入約束c創(chuàng)建一個h的特化式New_candidate_hypotheses中移去任意重復的、不一致的或非極大特殊化的假設更新Best_hypothesis對New_candidate_hypotheses中所有h做以下操作如果Performance(h,Examples,Target_attribute)>Performance(Best_hypothesis,Examples,Target_attribute)

則Best_hypothesish更新Candidate_hypothesesCandidate_hypothesesCandidate_hypotheses中k個Performance最佳成員返回如下形式的一個規(guī)則“如果Best_hypothesis”，則prediction其中，prediction為在與Best_hypothesis匹配的Examples中最頻繁的Target_attribute值第十一頁，共五十三頁，2022年，8月28日12表10-2Learn-One-Rule的一種實現(xiàn)：一般到特殊柱狀搜索（2）Performance(h,Examples,Target_attribute)h_examples與h匹配的Examples子集返回-Entropy(h_examples)，Entropy是關于Target_attribute的熵第十二頁，共五十三頁，2022年，8月28日13對表10-2的Learn-One-Rule算法的說明算法主循環(huán)中考慮的每個假設都是屬性-值約束的合取每個合取假設對應于待學習規(guī)則的候選前件集合，它由其覆蓋的樣例的熵來評估搜索算法不斷特化候選假設，直到得到一個極大特殊假設，它包含所有可用的屬性規(guī)則的后件在算法的最后一步產生，在其前件確定后，算法構造出的規(guī)則后件用于預測在前件所能覆蓋的樣例中最常見的目標屬性值盡管使用了柱狀搜索，貪婪搜索仍可能產生次優(yōu)的規(guī)則第十三頁，共五十三頁，2022年，8月28日14序列覆蓋算法的幾種變型只學習覆蓋正例的規(guī)則，對該規(guī)則沒有覆蓋的實例默認地賦予其反例分類正例在整個群體中所占比例很小，所以規(guī)則集只標定正例的類別，而對其他樣例默認分類為反例，這樣規(guī)則集更簡潔易懂這一方法對應于Prolog中的失敗否定策略，其中不能證明為真的表達式都默認為假需要修改Learn-One-Rule算法增加輸入變量，指定感興趣的目標值Performance使用假設覆蓋正例的比例第十四頁，共五十三頁，2022年，8月28日15序列覆蓋算法的幾種變型（2）AQ算法AQ明確地尋找覆蓋特定目標值的規(guī)則，然后，對每個目標值學習一個析取規(guī)則集AQ算法學習單個規(guī)則的方法也不同于Learn-One-Rule，當它對每個規(guī)則執(zhí)行一般到特殊柱狀搜索時，他圍繞單個正例來進行搜索中只考慮被某正例滿足的屬性，以得到逐漸特殊的假設，每次學一個新規(guī)則時，它從那些未覆蓋的樣例中也選擇一個新的正例，以指引新析取項的搜索第十五頁，共五十三頁，2022年，8月28日16學習規(guī)則集：小結串行與并行的差異序列學習算法（CN2）每次學習一個規(guī)則，而ID3每一步并行學習整個析取項的集合，ID3可稱為并行覆蓋算法ID3在每一搜索步中根據它對數(shù)據產生的劃分選擇不同的屬性，CN2選擇的是不同的屬性-值對為了學習到n個規(guī)則的集合，每個規(guī)則前件包含k個屬性值測試，CN2需要nk次基本搜索步，而ID3獨立選擇次數(shù)要少得多CN2需要較大數(shù)量的訓練數(shù)據第十六頁，共五十三頁，2022年，8月28日17學習規(guī)則集：小結（2）搜索方向的差異Learn-One-Rule的搜索方向是從一般到特殊，而其他算法是從特殊到一般從一般到特殊的一個優(yōu)點是只有一個極大一般假設可作為搜索起始點而多數(shù)假設空間中有很多特殊假設，因此有許多極大特殊假設，從特殊到一般的算法難以確定搜索的起點第十七頁，共五十三頁，2022年，8月28日18學習規(guī)則集：小結（3）生成再測試與樣例驅動搜索的差異樣例驅動搜索算法包括：Find-S、候選消除、AQ算法、Gigol樣例驅動算法中，對假設的生成或修正是由單獨的訓練樣例驅動的，而且結果是一個已修正的假設，它對此單個樣例的性能得到改善Learn-One-Rule是生成再測試搜索生成再測試搜索方法中，后續(xù)的假設的生成只基于假設表示的語法，然后基于這些假設在全部樣例上的性能來進行選擇生成再測試的一個優(yōu)點是搜索中每一步的選擇都基于在許多樣例上的假設性能，因此噪聲數(shù)據的影響被最小化第十八頁，共五十三頁，2022年，8月28日19學習規(guī)則集：小結（4）規(guī)則的后修剪和后修剪的方法Learn-One-Rule也有可能形成過度擬合，解決的方法也可以是后修剪性能函數(shù)的定義相對頻率：令n代表規(guī)則所匹配的樣例數(shù)目，nc代表其中它能正確分類的數(shù)目，則規(guī)則性能的相對頻率估計為精度的m-估計：令p為從整個數(shù)據集中隨機抽取的樣例與該規(guī)則賦予的分類相同的先驗概率，令m為權，或稱對此先驗概率p進行加權的等效樣例數(shù)目熵：令S為匹配規(guī)則前件的樣例集合，熵衡量的是該樣例集合中目標函數(shù)的均一性第十九頁，共五十三頁，2022年，8月28日20學習一階規(guī)則本節(jié)考慮帶有變量的規(guī)則，即一階Horn子句，它們比命題規(guī)則有強得多的表征能力一階規(guī)則的歸納學習通常被稱為歸納邏輯編程，因為這一過程可看作從樣例中自動推導出Prolog程序命題規(guī)則過于特殊了，不能描述屬性值之間的實質關系，對今后的分類幾乎不起作用，一階規(guī)則能夠表示更一般的規(guī)則一階Horn子句還可指定前件中的變量不出現(xiàn)在后件中的規(guī)則，這種變量可以被存在量詞或全稱量詞修飾還可能在規(guī)則的后件和前件中使用相同的謂詞描述遞歸的規(guī)則第二十頁，共五十三頁，2022年，8月28日21術語所有的一階表達式由常量、變量、謂詞符號以及函數(shù)符號組成謂詞和函數(shù)的區(qū)別是謂詞只能取真或假（特殊的函數(shù)），而函數(shù)的取值可為任意常量通常用小寫符號表示函數(shù)，大寫符號表示謂詞術語：項：任意常量、任意變量、應用到任意項上的任意函數(shù)文字：應用到項上的任意謂詞或其否定，如果包含否定符號，稱為負文字，否則稱為正文字，不包含任何變量的稱為基本文字子句：多個文字的任意析取，其中所有的變量假定是全稱量化的Horn子句：至多包含一個正文字的子句，Horn子句的前件被稱為子句體或子句先行詞，后件被稱為子句頭或子句推論置換：將文字L的某些變量替換為某些項的函數(shù)，記為L。如果置換使得L1=L2，那么稱為L1和L2的合一置換第二十一頁，共五十三頁，2022年，8月28日22學習一階規(guī)則集：FOILFOIL學習的規(guī)則類似Horn子句，但有兩個不同：比Horn子句更受限，因為文字不允許包含函數(shù)符號比Horn子句更有表征力，因為規(guī)則體中的文字可以是負文字第二十二頁，共五十三頁，2022年，8月28日23表10-4基本的FOIL算法FOIL(Target_predicate,Predicates,Examples)PosExamples中Target_predicate為True的成員NegExamples中Target_predicate為False的成員Learned_rules{}當Pos不空，學習NewRuleNewRule沒有前件的謂詞Target_predicate規(guī)則NewRuleNeg當NewRuleNeg不空，增加新文字以特化NewRuleCandidate_literature對NewRule生成候選新文字，基于PredicateBest_literal把Best_literal加入到NewRule的前件NewRuleNegNewRuleNeg中滿足NewRule前件的子集Learned_rulesLearned_rules+NewRulePosPos-{被NewRule覆蓋的Pos成員}返回Learned_rules第二十三頁，共五十三頁，2022年，8月28日24FOIL算法的解釋FOIL外層循環(huán)中每次加入一條新的規(guī)則到其析取式假設Learned_rules中去每個新規(guī)則的效果是通過加入一個析取項泛化當前的析取假設這是假設空間的特殊到一般的搜索過程，它開始于最特殊的空析取式，在假設足夠一般以至覆蓋所有正例時終止FOIL內層循環(huán)執(zhí)行的是細粒度較高的搜索，以確定每個新規(guī)則的確切定義內層循環(huán)在另一假設空間中搜索，它包含文字的合取，以找到一個合取式形成規(guī)則的前件內層循環(huán)執(zhí)行一般到特殊的爬山搜索，開始于最一般的前件，然后增加文字以使規(guī)則特化直到避開所有的反例第二十四頁，共五十三頁，2022年，8月28日25FOIL算法的解釋（2）FOIL與前面的序列覆蓋和Learn-One-Rule算法之間有兩個最實質的不同，來源于算法對一階規(guī)則處理的需求在學習每個新規(guī)則的一般到特殊搜索中，F(xiàn)OIL使用了不同的細節(jié)步驟來生成規(guī)則的候選特化式，這一不同是為了處理規(guī)則前件中含有的變量FOIL使用的性能度量FOIL_Gain不同于表10-2中的熵度量，這是為了區(qū)別規(guī)則變量的不同約束，以及由于FOIL只搜尋覆蓋正例的規(guī)則第二十五頁，共五十三頁，2022年，8月28日26FOIL中的候選特化式的生成FOIL生成多個不同的新文字，每個可被單獨地加到規(guī)則前件中更精確地，假定當前規(guī)則為：

P(x1,...,xk)L1...Ln FOIL生成該規(guī)則的候選特化式的方法是考慮符合下列形式的新文字Ln+1Q(v1,...,vr)，其中Q為在Predicates中出現(xiàn)的任意謂詞名，vi既可為新變量，也可為規(guī)則中已有的變量，至少有一個是當前規(guī)則中已有的Equal(xj,xk)，其中xj和xk為規(guī)則中已有的變量以上兩種文字的否定第二十六頁，共五十三頁，2022年，8月28日27FOIL中的候選特化式的生成（2）舉例：待學習的規(guī)則的目標文字是GrandDaughter(x,y)，即

GrandDaughter(x,y)生成下列候選文字Equal(x,y)Female(x)Female(y)Father(x,y)Father(y,x)Father(x,z)Father(y,z)Father(z,y)上面文字的否定假定FOIL貪婪地選擇了Father(y,z)作為最有希望的文字，得到一個較特殊的規(guī)則

GrandDaughter(x,y)Father(y,z)第二十七頁，共五十三頁，2022年，8月28日28FOIL中的候選特化式的生成（3）生成進一步特化該規(guī)則的候選文字Female(z)Equal(z,x)Equal(x,z)Father(z,w)Father(w,z)上面文字的否定如果FOIL選擇了Father(z,x)，然后又選擇了Female(y)，將得到下面的規(guī)則，它只覆蓋正例，因此終止了進一步搜索該規(guī)則的特化式的過程

GrandDaughter(x,y)Father(y,z)Father(z,x)Female(y)FOIL移去被該規(guī)則覆蓋的所有樣例，如果還有未覆蓋的正例，算法將開始搜索下一個規(guī)則第二十八頁，共五十三頁，2022年，8月28日29引導FOIL的搜索（選擇文字）要在每一步中從候選文字中選擇最有希望的文字，F(xiàn)OIL在訓練數(shù)據上測量規(guī)則的性能在此過程中，考慮當前規(guī)則中每個變量的可能的約束FOIL使用評估函數(shù)以估計增加新文字的效用，它基于加入新文字前后的正例和反例的約束數(shù)目考慮某個規(guī)則R和一個可能被加到R的規(guī)則體的候選文字L，令R’為加入文字L到規(guī)則R后生成的規(guī)則，則按照信息論理論，F(xiàn)oil_Gain(L,R)可看作，為了編碼R的所有正例約束的分類所需的全部位數(shù)由于L帶來的減少第二十九頁，共五十三頁，2022年，8月28日30學習遞歸規(guī)則集如果在表10-4的算法輸入參數(shù)Predicates中包含目標謂詞（即規(guī)則頭的謂詞），那么FOIL在生成候選文字時必須考慮它，這允許產生遞歸的規(guī)則遞歸規(guī)則是否能被FOIL發(fā)現(xiàn)，取決于它在FOIL的貪婪搜索中是否比其他候選評分更高避免在學習規(guī)則集中產生無限遞歸第三十頁，共五十三頁，2022年，8月28日31FOIL小結FOIL擴展了CN2的序列覆蓋算法，執(zhí)行一般到特殊的搜索，每步增加一個新的文字到規(guī)則前件中，新文字可是規(guī)則前件或后件中已有的變量，或為新變量FOIL在每一步使用Foil_Gain函數(shù)在候選新文字中進行選擇，如果新文字可指向目標謂詞，那么FOIL可能學習到遞歸規(guī)則在訓練數(shù)據無噪聲的情況下，F(xiàn)OIL可持續(xù)地增加新文字到規(guī)則中，直到不覆蓋任何反例為處理有噪聲數(shù)據，搜索的終止需要在規(guī)則精度、覆蓋度和復雜性之間做出折中FOIL使用最小描述長度的方法終止規(guī)則增長，新的文字只在它們的描述長度短于它們所解釋的數(shù)據的描述長度時才被加入第三十一頁，共五十三頁，2022年，8月28日32作為逆演繹的歸納歸納邏輯編程，基于一個簡單的事實：歸納是演繹的逆過程一般來說，機器學習涉及的是如何建立能解釋觀察數(shù)據的理論，給定某些數(shù)據D和一些不完整的背景知識B，學習過程被描述為生成一個假設h，它與B一起解釋了D，即基于背景知識擴展謂詞集合的過程，稱為建設性歸納可以利用演繹推理的逆過程，以使歸納泛化的過程自動化第三十二頁，共五十三頁，2022年，8月28日33作為逆演繹的歸納（2）我們感興趣的是設計一個逆涵蘊算子O(B,D)，它使用訓練數(shù)據D和背景知識B作為輸入，輸出一個滿足式子10.2的假設h滿足式子10.2的假設很多，一般依賴最小描述長度準則來進行選擇逆演繹的歸納方法有許多有吸引力的特點：包含了一種普遍的學習定義方法，即尋找某個一般概念，它與給定的訓練樣例相擬合通過引入背景知識，可以對一個假設何時可被稱作“擬合”訓練數(shù)據進行更充分的定義通過引入背景知識B，該公式要求學習算法使用這一背景信息來引導h的搜索，而不是只搜索語法上合法的假設空間第三十三頁，共五十三頁，2022年，8月28日34作為逆演繹的歸納（3）不能處理有噪聲的數(shù)據，不允許在觀察到實例xi和其目標值f(xi)中出現(xiàn)差錯的可能性，這樣的差錯可能產生對h的不一致約束，但是多數(shù)形式邏輯框架完全沒有處理不一致斷言的能力一階邏輯語言的表征力太強，而且滿足式子10.2的假設很多，以至于假設空間的搜索在一般情形下難以執(zhí)行盡管直覺上背景知識有助于限制假設的搜索，但在多數(shù)ILP系統(tǒng)中，搜索的復雜度隨著背景知識的增加而增高第三十四頁，共五十三頁，2022年，8月28日35逆歸納自動演繹的一般方法是Robinson提出的歸納規(guī)則，歸納規(guī)則是一階邏輯中一個合理且完備的演繹推理規(guī)則算法Gigol通過反轉歸納規(guī)則來形成逆涵蘊算子命題歸納規(guī)則是歸納算子給定初始子句C1和C2，從子句C1中尋找一個文字L，并且L出現(xiàn)在C2中通過合并C1和C2中的除了L和L的所有文字，形成歸納式C，即C=(C1-{L})(C2-{L})給定兩個子句，歸納算子首先確定文字L是否以正文字出現(xiàn)在一個子句中，以負文字出現(xiàn)在另一個子句中，然后使用上面的歸納規(guī)則，見圖10-2第三十五頁，共五十三頁，2022年，8月28日36逆歸納（2）歸納算子根據初始子句C1和C2，得到歸納式C，逆涵蘊算子O(C,C1)根據C和C1得到另一個初始子句C2逆歸納是不確定的，即可能有多個子句C2，使得C1和C2產生C，在其中進行選擇的一個啟發(fā)式方法是偏好更短的子句，即假定C2和C1沒有共同的文字逆歸納算子給定初始子句C1和C，尋找一個文字L，它出現(xiàn)在子句C1中但不出現(xiàn)在C中通過包含下列的文字，形成第二個子句C2=(C-(C1-{L})){L}第三十六頁，共五十三頁，2022年，8月28日37逆歸納（3）可以基于逆歸納這樣的逆涵蘊算子開發(fā)出規(guī)則學習算法來一種策略是使用序列覆蓋算法，循環(huán)地以這種方法學習Horn子句集每次循環(huán)中，算法選擇沒有被以前學習到的子句覆蓋的一個訓練樣例<xi,f(xi)>，然后應用歸納規(guī)則來生成滿足(Bhixi)f(xi)的候選假設hi這是一個樣例驅動的搜索，因為每個候選假設的建立是為了覆蓋一特定樣例如果存在多個候選假設，那么選擇的策略是選取在其他樣例上也有最高精度的假設Gigol程序使用了結合這種序列覆蓋算法的逆歸納，通過它與用戶交互，獲得訓練樣例并引導它在可能的歸納推理步驟的巨大空間中的搜索，Gigol使用了一階表示而不是命題表示第三十七頁，共五十三頁，2022年，8月28日38一階歸納歸納規(guī)則可以很容易地擴展到一階表示，與命題歸納的關鍵不同是：這個過程基于合一置換操作定義置換為變量到項的任意映射，符號W表示應用置換到表達式W上的結果置換的例子L=Father(x,Bill)={x/Bob,y/z}L=Father(Bob,Bill)合一置換：如果L1=L2，則為兩個文字L1和L2的合一置換第三十八頁，共五十三頁，2022年，8月28日39一階歸納（2）合一置換的意義在于可用來推廣命題的歸納規(guī)則，在一階歸納中，從子句C1中尋找一文字L1和在C2中尋找一文字L2，使得存在L1和L2的合一置換，則歸納式計算方法如下

C=(C1-{L1})(C2-{L2})表10-7一階形式的歸納規(guī)則尋找C1中的文字L1，C2中的文字L2，以及置換，使得L1=L2通過包含C1和C2中，除了L1和L2以外的文字，形成歸納式C，見式子10.3第三十九頁，共五十三頁，2022年，8月28日40一階歸納（3）一階形式的歸納的舉例C1=White(x)Swan(x),C2=Swan(Fred)首先表示成子句形式C1=White(x)Swan(x)找到C1中的文字L1=Swan(x)和C2中的文字L2=Swan(Fred)，存在它們的合一置換={x/Fred}因此歸納結果C=White(Fred)=White(Fred)第四十頁，共五十三頁，2022年，8月28日41一階情況的逆歸納式子10.3中的合一置換可被為唯一地分解為1和2，即=12，1包含涉及C1中變量的所有置換，2包含涉及C2中變量的所有置換由于C1和C2是全稱量化陳述，可以使用不同的變量名，因此上面的分解是合理的使用這種分解，式子10.3可重新表達為：C=(C1-{L1})1(C2-{L2})2使用歸納規(guī)則的定義L2=L112-1，解出C2為

C2=(C-(C1-{L1}1)2{L112-1}第四十一頁，共五十三頁，2022年，8月28日42一階情況的逆歸納（2）式子10.4表示的逆涵蘊算子是非確定的，在應用過程中，一般可找到待歸納的子句C1和置換1和2的多種選擇，每組不同的選擇都產生一個不同的C2第四十二頁，共五十三頁，2022年，8月28日43一階情況的逆歸納（3）圖10-3顯示了此逆歸納規(guī)則應用在一個簡單例子上的多個步驟訓練數(shù)據D=GrandChild(Bob,Shannon)背景知識B={Father(Shanon,Tom),Father(Tom,Bob)}學習目標謂詞GrandChild(y,x)的規(guī)則第一步設置結論C為訓練樣例GrandChild(Bob,Shannon)從背景知識中選擇子句C1=Father(Shannon,Tom)選擇逆置換1-1={}，2-1={Shannon/x}得到C2=GrandChild(Bob,x)Father(x,Tom)第二步設置結論為上步得到的C=C2從背景知識中選擇C1=Father(Tom,Bob)得到GrandChild(y,x)Father(x,z)Father(z,y)第四十三頁，共五十三頁，2022年，8月28日44逆歸納小結逆歸納提供了一種一般的途徑以自動產生滿足式子10.2的假設與FOIL方法的差異逆歸納是樣例驅動，F(xiàn)OIL是生成再測試逆歸納在每一步只考慮可用數(shù)據中的一小部分，F(xiàn)OIL考慮所有的可用數(shù)據看起來基于逆歸納的搜索更有針對性且更有效，但實際未必如此第四十四頁，共五十三頁，2022年，8月28日45泛化、-包容于和涵蘊考慮如下的定義more_general_than：給定兩布爾值函數(shù)hj(x)和hk(x)，稱hjghk，當且僅當(x)hk(x)hj(x)（參見第2章）-包容于：考慮兩個子句Cj和Ck，稱Cj-包容于Ck，當且僅當存在一個置換，使得CjCk涵蘊：考慮兩個子句Cj和Ck，子句Cj被稱為涵蘊Ck，當且僅當Ck從Cj中演繹派生第四十五頁，共五十三頁，2022年，8月28日46泛化、-包容于和涵蘊（2）三個定義之間的關系泛化和-包容于的關系：如果h1gh2，則子句C1:c(x)h1(x)-包容于子句C2:c(x)h2(x)-包容于是涵蘊的一種特殊形式，即如果子句A-包容于子句B，則AB，然而反之不一定成立因此，泛化是-包容于的一種特殊情況，而-包容于又是涵蘊的特殊情況通過泛化和特化假設來搜索假設空間比用一般的逆涵蘊算子來搜索更局限遺憾的是，逆涵蘊這種最一般的形式可產生無法處理的搜索中間的-包容于提供了位于泛化和涵蘊之間的一種概念和方法第四十六頁，共五十三頁，2022年，8月28日47Progol在實踐中，逆歸納容易導致候選假設的組合爆炸另一種途徑（Progol的思想）是：只使用逆涵蘊來生成一個最特殊假設，它與背景信息一起涵蘊觀察的數(shù)據然后，這個最特殊假設可用于確定假設空間的一般到特殊搜索邊界，只考