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

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

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

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

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

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

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

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

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

9、nce 是用戶提供的子程序，以評估規(guī)則的質(zhì)量。當算法再也不能學習到一個性能超過給定閾值Threshold 的規(guī)則時，該算法終止。Sequential-covering(Target_attribute, Attributes, Examples, Threshold)n Learned_rulesn Rulelearn-one-rule(Target_attribute, Attributes, Examples)n 當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 一般到特殊柱狀搜索實現(xiàn) learn-one-rule 的一個有效途徑是將假設(shè)空間搜索過程設(shè)計為與ID3 算法中相似的方式，但在每一步只沿著最有希望的分支向下。如圖1-3 所示的搜索樹，搜索開始于最一般的規(guī)則前件（即能匹配所有實例的空測試），然后貪婪地加入那些在訓練樣例上性能改進最大

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

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

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

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

15、不一致的或非極大特殊化的假設(shè)2.更新Best_hypothesisn 對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個最佳成員，按照performance度量n 返回一個如下形式

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的熵下面是對表 1-3 中的learn-one-rule 算法的一些說明。首先，注意在算法主循環(huán)中考慮的每個假設(shè)是屬性-值約束的合取。每個合取假設(shè)對應(yīng)于待學習規(guī)

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

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

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

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

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

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

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

24、，考慮一個學習任務(wù)，目標概念很簡單，為Daughter(x,y)，定義在所有的人x 和y 上。Danghter(x,y)的值在x 是y 的女兒時為真，否則為假。假定每個人被描述為屬性Name, Mother, Father, Male 和Female。因此每個訓練樣例將包含以這些屬性進行的描述的兩個人，以及目標屬性Daughter 的值。例如，下面為一個正例，其中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>其中每個屬性名上的下標是為了區(qū)分這兩個人?，F(xiàn)在，如果搜集許多這樣的目標概念Daughter1,2 的訓練樣例，并將它們提供給一個命題規(guī)則學習器，如CN2 和C4.5，結(jié)果將為一組非常特殊的規(guī)則如：IF (Father1=Bob)(Name2=Bob)(Female1=True)THEN Daughter1,2=True雖然這個規(guī)則是正確的，但它過于特殊了，因此它對今后的分類幾乎毫無用處。問題在于，命題表示方法不能夠描述屬性值之間實質(zhì)關(guān)系。與此不同，使用一階表示的程序?qū)W到下面的一

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

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

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

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

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

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

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