學(xué)習(xí)規(guī)則集合

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

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

P(x1,...,xk)L1...Ln FOIL生成該規(guī)則的候選特化式的方法是考慮符合下列形式的新文字Ln+1Q(v1,...,vr)，其中Q為在Predicates中出現(xiàn)的任意謂詞名，vi既可為新變量，也可為規(guī)則中已有的變量，至少有一個(gè)是當(dāng)前規(guī)則中已有的Equal(xj,xk)，其中xj和xk為規(guī)則中已有的變量以上兩種文字的否定第26頁，課件共53頁，創(chuàng)作于2023年2月2003.12.1827FOIL中的候選特化式的生成（2）舉例：待學(xué)習(xí)的規(guī)則的目標(biāo)文字是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)作為最有希望的文字，得到一個(gè)較特殊的規(guī)則

GrandDaughter(x,y)Father(y,z)第27頁，課件共53頁，創(chuàng)作于2023年2月2003.12.1828FOIL中的候選特化式的生成（3）生成進(jìn)一步特化該規(guī)則的候選文字Female(z)Equal(z,x)Equal(x,z)Father(z,w)Father(w,z)上面文字的否定如果FOIL選擇了Father(z,x)，然后又選擇了Female(y)，將得到下面的規(guī)則，它只覆蓋正例，因此終止了進(jìn)一步搜索該規(guī)則的特化式的過程

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

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

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