FOIL算法的可視化演示和領(lǐng)域定制

1、FOIL算法的可視化演示和領(lǐng)域定制1 FOIL算法綜述FOIL 由 Quinlan 于1989年開(kāi)發(fā)，采用自上而下的算法。在一個(gè)既有正又有反的事實(shí)的訓(xùn)練集中，先找出一個(gè)只覆蓋正例而不涉及反例的邏輯子句 (clause) ，然后把這個(gè)子句覆蓋的事實(shí)從訓(xùn)練集中刪除。如此直到訓(xùn)練集中沒(méi)有正例為止。FOIL是較早的序列覆蓋和learn-one-rule 算法在一階表示上的自然擴(kuò)展。在 FOIL 與序列覆蓋和learn-one-rule 算法之間有兩個(gè)最實(shí)質(zhì)的不同，它來(lái)源于此算法對(duì)一階規(guī)則處理的需求。形式化地講，由FOIL 學(xué)習(xí)的假設(shè)為一階規(guī)則集，其中的規(guī)則類似于Horn 子句，但有兩個(gè)不同：首先由FO

2、IL 學(xué)習(xí)的規(guī)則比一般的Horn子句更受限，因?yàn)槲淖植辉试S包含函數(shù)符號(hào)（這減小了假設(shè)空間搜索的復(fù)雜度）。其次，F(xiàn)OIL規(guī)則比Horn 子句更有表征力，因?yàn)橐?guī)則體中的文字也可為負(fù)文字。FOIL 已被應(yīng)用于多種問(wèn)題領(lǐng)域。例如，它已用于學(xué)習(xí)快速排序算法Quicksort 的遞歸定義，以及學(xué)習(xí)從合法棋盤狀態(tài)中區(qū)分出非法狀態(tài)。下面我們先介紹主要的一些相關(guān)知識(shí)和算法。1.1 基本的決策樹(shù)學(xué)習(xí)算法大多數(shù)已開(kāi)發(fā)的決策樹(shù)學(xué)習(xí)算法是一種核心算法的變體。該算法采用自頂向下的貪婪搜索遍歷可能的決策樹(shù)空間。這種方法是ID3 算法（Quinlan 1986）和后繼的C4.5算法（Quinlan 1993）的基礎(chǔ)。下面將給

3、出決策樹(shù)學(xué)習(xí)的基本算法，大致相當(dāng)于ID3 算法?；镜?ID3 算法通過(guò)自頂向下構(gòu)造決策樹(shù)來(lái)進(jìn)行學(xué)習(xí)。構(gòu)造過(guò)程是從“哪一個(gè)屬性將在樹(shù)的根結(jié)點(diǎn)被測(cè)試？”這個(gè)問(wèn)題開(kāi)始的。為了回答這個(gè)問(wèn)題，使用統(tǒng)計(jì)測(cè)試來(lái)確定每一個(gè)實(shí)例屬性單獨(dú)分類訓(xùn)練樣例的能力。分類能力最好的屬性被選作樹(shù)的根結(jié)點(diǎn)的測(cè)試。然后為根結(jié)點(diǎn)屬性的每個(gè)可能值產(chǎn)生一個(gè)分支，并把訓(xùn)練樣例排列到適當(dāng)?shù)姆种Вㄒ簿褪牵瑯永脑搶傩灾祵?duì)應(yīng)的分支）之下。然后重復(fù)整個(gè)過(guò)程，用每個(gè)分支結(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例來(lái)選取在該點(diǎn)被測(cè)試的最佳屬性。這形成了對(duì)合格決策樹(shù)的貪婪搜索（greedy search），也就是算法從不回溯重新考慮以前的選擇。下表描述了該算法的一個(gè)簡(jiǎn)化版本

4、專門用來(lái)學(xué)習(xí)布爾值函數(shù)（即概念學(xué)習(xí)）。表 1-1 專用于學(xué)習(xí)布爾函數(shù)的ID3 算法概要ID3 是一種自頂向下增長(zhǎng)樹(shù)的貪婪算法，在每個(gè)結(jié)點(diǎn)選取能最好地分類樣例的屬性。繼續(xù)這個(gè)過(guò)程直到這棵樹(shù)能完美分類訓(xùn)練樣例，或所有的屬性都使用過(guò)了。ID3(Examples，Target_attribute，Attributes)Examples即訓(xùn)練樣例集。Target_attribute是這棵樹(shù)要預(yù)測(cè)的目標(biāo)屬性。Attributes是除目標(biāo)屬性外供學(xué)習(xí)到的決策樹(shù)測(cè)試的屬性列表。返回能正確分類給定Examples的決策樹(shù)。l 創(chuàng)建樹(shù)的Root結(jié)點(diǎn)l 如果Examples都為正，那么返回label =+ 的單結(jié)點(diǎn)

5、樹(shù)Rootl 如果Examples都為反，那么返回label =- 的單結(jié)點(diǎn)樹(shù)Rootl 如果Attributes為空，那么返回單結(jié)點(diǎn)樹(shù)Root，label=Examples中最普遍的Target_attribute值l 否則l AAttributes中分類Examples能力最好*的屬性l Root的決策屬性Al 對(duì)于A的每個(gè)可能值vil 在Root下加一個(gè)新的分支對(duì)應(yīng)測(cè)試A= vil 令為Examples中滿足A屬性值為vi的子集l 如果為空l(shuí) 在這個(gè)新分支下加一個(gè)葉子結(jié)點(diǎn)，結(jié)點(diǎn)的label=Examples中最普遍的Target_attribute值l 否則在這個(gè)新分支下加一個(gè)子樹(shù)ID3

6、（, Target_attribute, Attributes-A）l 結(jié)束l 返回Root*根據(jù)公式的定義，具有最高信息增益（information gain）的屬性是最好的屬性。1.2 序列覆蓋算法序列覆蓋算法它的學(xué)習(xí)規(guī)則集的策略為：學(xué)習(xí)一個(gè)規(guī)則，移去它覆蓋的數(shù)據(jù)，再重復(fù)這一過(guò)程。這樣的算法被稱為序列覆蓋（sequential covering）算法。想象我們已有了一個(gè)子程序learn-one-rule，它的輸入為一組正例和反例，然后輸出單個(gè)規(guī)則，它能夠覆蓋許多正例，并且覆蓋很少的反例。我們要求這一輸出的規(guī)則有較高的精確度，但不必有較高的覆蓋度。較高的精確度說(shuō)明它所做出的預(yù)測(cè)應(yīng)為正確的?？?/p>

7、接受較低的覆蓋度，表示它不必對(duì)每個(gè)訓(xùn)練樣例都作出預(yù)測(cè)。有了這樣一個(gè)學(xué)習(xí)單個(gè)規(guī)則的 learn-one-rule 子程序，要學(xué)習(xí)規(guī)則集，一個(gè)明顯的方法是在所有可用訓(xùn)練樣例上執(zhí)行l(wèi)earn-one-rule，再移去由其學(xué)到的規(guī)則覆蓋的正例，再在剩余的訓(xùn)練樣例上執(zhí)行它以學(xué)習(xí)第二個(gè)規(guī)則。該過(guò)程可重復(fù)若干次，直到最后學(xué)習(xí)到析取規(guī)則集，它們共同覆蓋正例，覆蓋程度達(dá)到所希望的比例。算法被稱為序列覆蓋算法是因?yàn)樗创涡驅(qū)W習(xí)到一組規(guī)則，它們共同覆蓋了全部正例。最終的規(guī)則集可被排序，這樣分類新實(shí)例時(shí)可先應(yīng)用精度最高的規(guī)則。序列覆蓋算法的一個(gè)原型在表1-2 中陳述。序列覆蓋算法是廣泛使用的學(xué)習(xí)析取規(guī)則集算法的其中之

8、一。它將學(xué)習(xí)析取規(guī)則集的問(wèn)題化簡(jiǎn)為一系列更簡(jiǎn)單的問(wèn)題，每個(gè)子問(wèn)題只需學(xué)到單個(gè)合取規(guī)則。由于它執(zhí)行的是一種貪婪搜索，形成序列化的規(guī)則且沒(méi)有回溯，所以它不能保證找到能覆蓋樣例的最小的或最佳的規(guī)則。如何設(shè)計(jì) learn-one-rule 程序以達(dá)到序列覆蓋算法的要求？我們需要一個(gè)算法能夠形成有較高精度的規(guī)則，但不必覆蓋所有的正例。在本節(jié)中展示了各種算法，并描述了它們?cè)趯W(xué)術(shù)研究上已探索的主要差別。本節(jié)只考慮命題規(guī)則。后面的節(jié)中將把這些算法擴(kuò)展到一階Horn 子句。表 1-2 學(xué)習(xí)析取的規(guī)則集的序列覆蓋算法。learn-one-rule 必須返回單個(gè)的能覆蓋某些Examples 的規(guī)則。performa

9、nce 是用戶提供的子程序，以評(píng)估規(guī)則的質(zhì)量。當(dāng)算法再也不能學(xué)習(xí)到一個(gè)性能超過(guò)給定閾值Threshold 的規(guī)則時(shí)，該算法終止。Sequential-covering(Target_attribute, Attributes, Examples, Threshold)n Learned_rulesn Rulelearn-one-rule(Target_attribute, Attributes, Examples)n 當(dāng)performance(Rule, Examples) > Threshold，做：n Learned_rulesLearned_rules + Rulen Exampl

10、esExamples-被Rule正確分類的樣例n Rulelearn-one-rule(Target_attribute, Attributes, Examples)n Learned_rules按照在Examples上的performance排序的Learned_rulesn 返回Learned_rules1.3 一般到特殊柱狀搜索實(shí)現(xiàn) learn-one-rule 的一個(gè)有效途徑是將假設(shè)空間搜索過(guò)程設(shè)計(jì)為與ID3 算法中相似的方式，但在每一步只沿著最有希望的分支向下。如圖1-3 所示的搜索樹(shù)，搜索開(kāi)始于最一般的規(guī)則前件（即能匹配所有實(shí)例的空測(cè)試），然后貪婪地加入那些在訓(xùn)練樣例上性能改進(jìn)最大

11、的屬性測(cè)試。一旦該測(cè)試被加入，該過(guò)程重復(fù)，貪婪地加入第二個(gè)屬性測(cè)試，依此類推。如ID3 那樣，該過(guò)程通過(guò)貪婪地增加新的屬性測(cè)試來(lái)獲得假設(shè)，直到該假設(shè)的性能到達(dá)一可接受的程度。與ID3 不同的是，此learn-one-rule 的實(shí)現(xiàn)在每一步沿著單個(gè)分支即產(chǎn)生最佳性能的屬性-值對(duì)，而不是用增長(zhǎng)子樹(shù)的辦法覆蓋所選屬性的所有可能值。這種實(shí)現(xiàn) learn-one-rule 的途徑執(zhí)行的是對(duì)可能存在的規(guī)則的一般到特殊搜索，以得到一個(gè)有較高精度但不一定完全覆蓋數(shù)據(jù)的規(guī)則。如在決策樹(shù)學(xué)習(xí)中那樣，有許多方法可以定義選擇“最佳”分支的度量標(biāo)準(zhǔn)。與在ID3 中類似，我們可定義最佳分支為它覆蓋的樣例有最低的熵（）。

12、圖 1-3 Learn-one-rule 從一般到特殊過(guò)程中的規(guī)則前件搜索在每一步，最佳規(guī)則的前件被以各種可能方式特化。規(guī)則后件是由滿足前件的樣例所決定的。該圖顯示的是寬度為1 的柱狀搜索。上面推薦的一般到特殊搜索是一種不帶回溯的貪婪深度優(yōu)先搜索。如其他貪婪搜索一樣，它所帶來(lái)的危險(xiǎn)是每一步可能作出了次優(yōu)的選擇。為減小這種風(fēng)險(xiǎn)，可將此算法擴(kuò)展為一種柱狀搜索（beam search），即每一步算法保留k 個(gè)最佳候選的列表，在每一搜索步對(duì)這k 個(gè)最佳候選生成分支（特化），并且結(jié)果集再被削減至k 個(gè)最可能成員。柱狀搜索跟蹤當(dāng)前最高分值假設(shè)的最有希望的替代者，以使每一步中它們的所有后繼都被考慮到。該一般

13、到特殊柱狀搜索用于CN2 程序，它由Clark& Niblett（1989）提出。該算法在表1-3 中描述。表 1-3 learn-one-rule 的一種實(shí)現(xiàn)是一般到特殊柱狀搜索。當(dāng)前假設(shè)的邊緣表示為變量 Candidate_hypotheses。該算法與Clark & Niblett（1989）描述的CN2 程序相類似。Learn-one-rule(Target_attribute, Attributes, Examples, k)返回一個(gè)覆蓋若干樣例的規(guī)則。實(shí)施一般到特殊貪婪柱狀搜索以得到最佳規(guī)則，由performance度量來(lái)引導(dǎo)。n 初始化Best_hypothesi

14、s為最一般的假設(shè)Æn 初始化Candidate_hypotheses為集合Best_hypothesisn 當(dāng)Candidate_hypotheses不空，做以下操作：1.生成緊鄰更特殊的候選假設(shè)n All_constraints所有形式為(a=v)的約束集合，其中a為Attributes的成員，而v為出現(xiàn)在當(dāng)前Examples集合中的a值n New_candidate_hypothese對(duì)Candidate_hypotheses中每個(gè)h，對(duì)All_constraints中每個(gè)cn 通過(guò)加入約束c創(chuàng)建一個(gè)h的特化式n 從New_candidate_hypothese中移去任意重復(fù)的、

15、不一致的或非極大特殊化的假設(shè)2.更新Best_hypothesisn 對(duì)New_candidate_hypotheses中所有h做以下操作：n 如果(performance(h, Examples, Target_attribute) > performance(Best_hypothesis, Examples, Target_attribute) 則Best_hypothesish3.更新Candidate_hypothesesn Candidate_hypothesesNew_candidate_hypotheses中k個(gè)最佳成員，按照performance度量n 返回一個(gè)如下形式

16、的規(guī)則：“如果Best_hypothesis，則prediction”其中prediction為在與Best_hypothesis匹配的Examples中最頻繁的Target_attribute值performance(h, Examples, Target_attribute)n h_examples與h匹配的Examples子集n 返回-Entropy(h_examples)，其中Entropy是關(guān)于Target_attribute的熵下面是對(duì)表 1-3 中的learn-one-rule 算法的一些說(shuō)明。首先，注意在算法主循環(huán)中考慮的每個(gè)假設(shè)是屬性-值約束的合取。每個(gè)合取假設(shè)對(duì)應(yīng)于待學(xué)習(xí)規(guī)

17、則的候選前件集合，它由其覆蓋的樣例的熵來(lái)評(píng)估。搜索過(guò)程不斷特化候選假設(shè)，直到到達(dá)一個(gè)極大特殊假設(shè)，它包含所有可用的屬性。由該算法輸出的規(guī)則為搜索過(guò)程中遇到的性能最佳（performance 最大）的規(guī)則不一定是搜索最終產(chǎn)生的假設(shè)。規(guī)則的后件輸出只在算法的最后一步產(chǎn)生，在其前件（表示為變量Best_hypothesis）確定之后，算法構(gòu)造出的規(guī)則后件用于預(yù)測(cè)在規(guī)則前件所能覆蓋的樣例中最常見(jiàn)的目標(biāo)屬性值。最后，還應(yīng)注意盡管使用了柱狀搜索以減小風(fēng)險(xiǎn)，貪婪搜索仍可能產(chǎn)生次優(yōu)的規(guī)則。然而，即使這樣，序列覆蓋算法仍能學(xué)到一組規(guī)則，它們共同覆蓋訓(xùn)練樣例，因?yàn)樗鼘?duì)剩余的未覆蓋樣例重復(fù)調(diào)用了learn-one-

18、rule。下面討論一下上述規(guī)則學(xué)習(xí)算法設(shè)計(jì)中的關(guān)鍵思想。首先，序列覆蓋算法每次學(xué)習(xí)一個(gè)規(guī)則，移去覆蓋的樣例然后在剩余樣例上重復(fù)這一過(guò)程。相反，如ID3 那樣的決策樹(shù)算法使用單個(gè)搜索過(guò)程來(lái)搜索可接受決策樹(shù)，每步并行學(xué)習(xí)整個(gè)析取項(xiàng)的集合。因此，我們也可將ID3 這樣的算法稱為并行覆蓋算法，對(duì)應(yīng)于CN2這樣的序列覆蓋算法。哪一種算法比較好？答案關(guān)鍵在于搜索中最基本步驟之間的差別。ID3 在每一搜索步中根據(jù)它對(duì)數(shù)據(jù)產(chǎn)生的劃分選擇不同的屬性。相反，CN2 選擇的是不同的屬性-值對(duì)，方法是通過(guò)比較它們覆蓋的數(shù)據(jù)子集。要看出這種差別的意義所在，需要比較兩種算法為學(xué)習(xí)到相同的規(guī)則集合所作出的不同選擇的次數(shù)。為

19、了學(xué)習(xí)到n 個(gè)規(guī)則的集合，每個(gè)規(guī)則前件包合k 個(gè)屬性值測(cè)試，序列覆蓋算法需要執(zhí)行n· k 次基本搜索步，為每個(gè)規(guī)則的每個(gè)前件做獨(dú)立的選擇，而并行覆蓋算法的獨(dú)立選擇次數(shù)遠(yuǎn)遠(yuǎn)少于此，因?yàn)樵跊Q策樹(shù)中每個(gè)決策結(jié)點(diǎn)的選擇都對(duì)應(yīng)了與該結(jié)點(diǎn)相關(guān)聯(lián)的多個(gè)規(guī)則的前件選擇。換言之，如果決策結(jié)點(diǎn)測(cè)試一個(gè)有m 種可能值的屬性，每次決策結(jié)點(diǎn)的選擇都對(duì)應(yīng)了對(duì)m 個(gè)相應(yīng)的規(guī)則中每個(gè)規(guī)則的前件選擇。這樣，序列覆蓋算法（如CN2）作出的獨(dú)立選擇次數(shù)高于ID3 這樣的并行覆蓋算法。但哪一種算法更好的問(wèn)題依然存在。其解答依賴于有多少訓(xùn)練數(shù)據(jù)是可用的。如果數(shù)據(jù)非常豐富，那么它可以支持序列覆蓋算法所要求的較大數(shù)量的獨(dú)立選擇。

20、然而若數(shù)據(jù)較缺乏，對(duì)于不同規(guī)則前件的決策“共享”則更有效。另一考慮在于特定的任務(wù)中是否希望不同的規(guī)則測(cè)試相同的屬性。在并行覆蓋決策樹(shù)學(xué)習(xí)算法中會(huì)出現(xiàn)這樣的情況。在序列覆蓋算法中則不存在。不同方法的第二個(gè)相異之處在于 learn-one-rule 搜索的方向。在上面描述的算法中，搜索是從一般到特殊的。其他已討論的算法是從特殊到一般的。在此情況下，從一般到特殊搜索的一個(gè)優(yōu)點(diǎn)在于只有一個(gè)極大一般假設(shè)可作為搜索起始點(diǎn)，而在多數(shù)假設(shè)空間中有很多特殊假設(shè)（如對(duì)每個(gè)實(shí)例有一假設(shè)）。因?yàn)橛性S多極大特殊假設(shè)，就不能確知選擇哪一個(gè)作為搜索的開(kāi)始點(diǎn)。執(zhí)行從特殊到一般搜索的一個(gè)稱為Golem(Muggleton &a

21、mp; Feng 1990)的程序解決此問(wèn)題的方法是隨機(jī)選擇多個(gè)正例，以此為初始來(lái)進(jìn)行搜索。在多個(gè)隨機(jī)選擇中的最佳假設(shè)作為最后結(jié)果。第三個(gè)要考慮的是 learn-one-rule 是為一個(gè)生成再測(cè)試（generate then test）搜索，范圍為所有合法的假設(shè)，如我們推薦的實(shí)現(xiàn)中那樣；還是一個(gè)樣例驅(qū)動(dòng)（example-driven）搜索，以使訓(xùn)練樣例個(gè)體約束假設(shè)的生成。樣例驅(qū)動(dòng)搜索算法包括Find-S、候選消除、AQ 算法，以及本章后面要討論的Cigol 算法。在這些算法中，對(duì)假設(shè)的生成或修正是由單獨(dú)的訓(xùn)練樣例驅(qū)動(dòng)的，而且結(jié)果是一個(gè)已修正的假設(shè)，使對(duì)此單個(gè)樣例的性能得到改善。這不同于表1-

22、3 中l(wèi)earn-one-rule 算法的生成再測(cè)試搜索，其中后續(xù)的假設(shè)的生成只基于假設(shè)表示的語(yǔ)法。在這些候選假設(shè)生成之后再分析訓(xùn)練數(shù)據(jù)，然后基于這些假設(shè)在全部樣例上的性能來(lái)進(jìn)行選擇。生成再測(cè)試的一個(gè)重要優(yōu)點(diǎn)是搜索中每一步的選擇都基于在許多樣例上的假設(shè)性能，因此噪聲數(shù)據(jù)的影響被最小化。相反，樣例驅(qū)動(dòng)算法基于單個(gè)的樣例改進(jìn)假設(shè)，它更容易被一些噪聲訓(xùn)練樣例影響，因此對(duì)訓(xùn)練數(shù)據(jù)中差錯(cuò)的魯棒性較差。第四個(gè)要考慮的是是否需要對(duì)規(guī)則進(jìn)行后修剪以及怎樣修剪。如在決策樹(shù)學(xué)習(xí)中一樣，learn-one-rule 也有可能形成在訓(xùn)練數(shù)據(jù)上性能很好，但在以后的數(shù)據(jù)中很差的規(guī)則。解決的辦法也是在得到每個(gè)規(guī)則后進(jìn)行后修

23、剪。確切地講，可以移去某些前件，只要這導(dǎo)致不同于訓(xùn)練樣例的用于修剪的一個(gè)樣例集合上的性能提高。1.4 學(xué)習(xí)一階規(guī)則前面討論的算法針對(duì)學(xué)習(xí)命題規(guī)則集（即無(wú)變量的規(guī)則）。本節(jié)中將考慮帶有變量的規(guī)則，確切地講為一階Horn 子句。之所以考慮這樣的規(guī)則，是因?yàn)樗鼈儽让}規(guī)則更有表征能力。對(duì)于一階段規(guī)則的歸納學(xué)習(xí)通常被稱為歸納邏輯編程（Inductive Logic Programming，簡(jiǎn)寫(xiě)ILP），因?yàn)檫@一過(guò)程可看作從樣例中自動(dòng)推論出Prolog 程序。Prolog 是一個(gè)通用的、圖靈等價(jià)的編程語(yǔ)言，其中程序被表示為一組Horn 子句。一階Horn 子句為說(shuō)明一階表示比命題（無(wú)變量）表示的優(yōu)越之處

24、，考慮一個(gè)學(xué)習(xí)任務(wù)，目標(biāo)概念很簡(jiǎn)單，為Daughter(x,y)，定義在所有的人x 和y 上。Danghter(x,y)的值在x 是y 的女兒時(shí)為真，否則為假。假定每個(gè)人被描述為屬性Name, Mother, Father, Male 和Female。因此每個(gè)訓(xùn)練樣例將包含以這些屬性進(jìn)行的描述的兩個(gè)人，以及目標(biāo)屬性Daughter 的值。例如，下面為一個(gè)正例，其中Sharon 為Bob 的女兒。<Name1=Sharon, Mother1=Louise, Father1=Bob,Male1=False, Female1=True,Name2=Bob, Mother2=Nora, Fath

25、er2=Victor,Male2=True, Female2=False, Daughter1,2=True>其中每個(gè)屬性名上的下標(biāo)是為了區(qū)分這兩個(gè)人?，F(xiàn)在，如果搜集許多這樣的目標(biāo)概念Daughter1,2 的訓(xùn)練樣例，并將它們提供給一個(gè)命題規(guī)則學(xué)習(xí)器，如CN2 和C4.5，結(jié)果將為一組非常特殊的規(guī)則如：IF (Father1=Bob)(Name2=Bob)(Female1=True)THEN Daughter1,2=True雖然這個(gè)規(guī)則是正確的，但它過(guò)于特殊了，因此它對(duì)今后的分類幾乎毫無(wú)用處。問(wèn)題在于，命題表示方法不能夠描述屬性值之間實(shí)質(zhì)關(guān)系。與此不同，使用一階表示的程序?qū)W(xué)到下面的一

26、般規(guī)則：IF Father(y,x) Female(y) THEN Daughter(x,y)其中x 和y 為變量，它們可指代任意人。一階 Horn 子句還可指定前件中的變量不出現(xiàn)在后件中的規(guī)則。例如對(duì)GrandDaughter的規(guī)則為：IF Father(y,z) Mother(z,y) Female(y)THEN GrandDaughter(x,y)注意該規(guī)則中的變量z，它指代y 的父親，在規(guī)則后件中沒(méi)有出現(xiàn)。當(dāng)一個(gè)變量只在前件中出現(xiàn)時(shí)，假定它是被存在量化（existentially quantified）的，即只要存在該變量的一個(gè)約束能滿足對(duì)應(yīng)的文字，那么規(guī)則前件就滿足。還可能在規(guī)則的后

27、件和前件中使用相同的謂詞，描述遞歸的規(guī)則。如在本章開(kāi)頭的兩個(gè)規(guī)則提供了概念A(yù)ncestor(x,y)的遞歸定義。以下將描述的ILP 學(xué)習(xí)方法已可以學(xué)習(xí)幾種簡(jiǎn)單的遞歸函數(shù)，包括如上面的Ancestor 函數(shù)以及其他一些函數(shù)，如對(duì)列表中元素進(jìn)行排序；從列表中移去一特定元素；拼接兩個(gè)列表。1.5 規(guī)則后修剪實(shí)踐中，一種用來(lái)發(fā)現(xiàn)高精度假設(shè)的非常成功的方法為“規(guī)則后修剪(rulepost-pruning）”。這種修剪方法的一個(gè)變體被用在C4.5 中（Quinlan 1993），C4.5 是從原始的ID3 算法的派生出來(lái)的。規(guī)則后修剪包括下面的步驟：1. 從訓(xùn)練集合推導(dǎo)出決策樹(shù)，增長(zhǎng)決策樹(shù)直到盡可能好地?cái)M

28、合訓(xùn)練數(shù)據(jù)，允許過(guò)度擬合發(fā)生。2. 將決策樹(shù)轉(zhuǎn)化為等價(jià)的規(guī)則集合，方法是為從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的每一條路徑創(chuàng)建一條規(guī)則。3. 通過(guò)刪除任何能導(dǎo)致估計(jì)精度提高的前件（preconditions）來(lái)修剪（泛化）每一條規(guī)則。4. 按照修剪過(guò)的規(guī)則的估計(jì)精度對(duì)它們進(jìn)行排序；并按這樣的順序應(yīng)用這些規(guī)則來(lái)分類后來(lái)的實(shí)例。如同前面提出的，估計(jì)規(guī)則精度的一種方法是使用與訓(xùn)練集和不相交的驗(yàn)證集合。另一種被C4.5 使用的方法是基于訓(xùn)練集合本身評(píng)估性能，但使用一種保守估計(jì)（pessimistic estimate）來(lái)彌補(bǔ)訓(xùn)練數(shù)據(jù)有利于當(dāng)前規(guī)則的估計(jì)偏置。更準(zhǔn)確地講，C4.5通過(guò)以下方法計(jì)算保守估計(jì)，先計(jì)算規(guī)則在它應(yīng)

29、用的訓(xùn)練樣例上的精度，然后假定此估計(jì)精度為二項(xiàng)分布，并計(jì)算它的標(biāo)準(zhǔn)差（standard deviation）。對(duì)于一個(gè)給定的置信區(qū)間，采用下界估計(jì)作為規(guī)則性能的度量（例如，對(duì)于一個(gè)95%的置信區(qū)間，規(guī)則精度被保守估計(jì)為：在訓(xùn)練集合上的觀察精度減去1.96 乘估計(jì)的標(biāo)準(zhǔn)差）。這樣做的效果是，對(duì)于大的數(shù)據(jù)集，保守預(yù)測(cè)非常接近觀察精度（也就是標(biāo)準(zhǔn)差非常?。欢S著數(shù)據(jù)集合的減小，它開(kāi)始離觀察精度越來(lái)越遠(yuǎn)。雖然這種啟發(fā)式方法不是統(tǒng)計(jì)有效（statisticallyvalid）的，但是已經(jīng)發(fā)現(xiàn)它在實(shí)踐中是有用的。為什么修剪之前要把決策樹(shù)轉(zhuǎn)化成規(guī)則集呢？這樣做主要有三個(gè)好處：1轉(zhuǎn)化為規(guī)則集可以區(qū)分決策結(jié)

30、點(diǎn)使用的不同上下文。因?yàn)樨灤Q策結(jié)點(diǎn)的每條不同路徑產(chǎn)生一條不同的規(guī)則，所以對(duì)于不同路徑，關(guān)于一個(gè)屬性測(cè)試的修剪決策可以不同。相反，如果直接修剪樹(shù)本身，只有兩個(gè)選擇，要么完全刪除決策結(jié)點(diǎn)，要么保留它的本來(lái)狀態(tài)。2轉(zhuǎn)化為規(guī)則集消除了根結(jié)點(diǎn)附近的屬性測(cè)試和葉結(jié)點(diǎn)附近的屬性測(cè)試的區(qū)別。于是避免了零亂的記錄問(wèn)題，比如若是根結(jié)點(diǎn)被修剪了但保留它下面的部分子樹(shù)時(shí)如何重新組織這棵樹(shù)。3轉(zhuǎn)化為規(guī)則提高了可讀性。對(duì)于人來(lái)說(shuō)規(guī)則總是更容易理解的。1.6 學(xué)習(xí)一階規(guī)則集：FOIL有許多算法已被提出用于學(xué)習(xí)一階規(guī)則或Horn 子句。下面將介紹FOIL 程序（Quinlan1990），它使用的方法非常類似于前面介紹的序列

31、覆蓋和learn-one-rule 算法。實(shí)際上，F(xiàn)OIL是這些較早的算法在一階表示上的自然擴(kuò)展。形式化地講，由FOIL 學(xué)習(xí)的假設(shè)為一階規(guī)則集，其中的規(guī)則類似于Horn 子句，但有兩個(gè)不同：首先由FOIL 學(xué)習(xí)的規(guī)則比一般的Horn子句更受限，因?yàn)槲淖植辉试S包含函數(shù)符號(hào)（這減小了假設(shè)空間搜索的復(fù)雜度）。其次，F(xiàn)OIL規(guī)則比Horn 子句更有表征力，因?yàn)橐?guī)則體中的文字也可為負(fù)文字。FOIL 已被應(yīng)用于多種問(wèn)題領(lǐng)域。例如，它已用于學(xué)習(xí)快速排序算法Quicksort 的遞歸定義，以及學(xué)習(xí)從合法棋盤狀態(tài)中區(qū)分出非法狀態(tài)。FOIL 算法在表1-6 中列出。注意外層循環(huán)對(duì)應(yīng)于前面描述的序列覆蓋算法。它每

32、次學(xué)習(xí)一個(gè)新規(guī)則，然后將此規(guī)則覆蓋的正例移去，然后學(xué)習(xí)下一規(guī)則。算法的內(nèi)層循環(huán)是前面的learn-one-rule 的另一種形式，它已被擴(kuò)展以適合處理一階規(guī)則。還要注意FOIL 和前面算法的一些微小的不同。確切地講，F(xiàn)OIL 只搜尋那些預(yù)測(cè)目標(biāo)文字何時(shí)為True 的規(guī)則，而前面的算法既搜尋預(yù)測(cè)何時(shí)為True 的規(guī)則，也搜尋預(yù)測(cè)何時(shí)為False 的規(guī)則。FOIL 還應(yīng)用了一個(gè)簡(jiǎn)單的爬山搜索，而不是柱狀搜索（即它執(zhí)行的搜索等價(jià)于寬度為1 的柱狀搜索）表1-6 基本的FOIL算法其中給出了生成候選文字 Candidate-literal 的方法和FOIL 增益Foil_Gain 的定義。該基本算法可稍做修改以更好地處理有噪聲數(shù)據(jù)，如文中所描述的。FOIL(Target_predicate, Predicates, Examples)n PosExamples中Ta