【正文】 portation mid car conventional transportation micro jetfast plane Tiny jetfast plane Mid jetfast plane 正例樣本 size type class Huge bicycle giant 2wheeler Huge motorcycle giant 2wheeler 2022年 3月 13日星期日 DMKD Sides By MAO 69 CN2算法描述 ? CN2使用一種基于噪音估計的啟發(fā)式方法 ， 使用這種方法可以不用對所有的訓(xùn)練樣本進(jìn)行正確的區(qū)分 ， 但是規(guī)約出的規(guī)則在對新數(shù)據(jù)的處理上有很好的表現(xiàn) 。 算法 47 CN2 輸入： E /*E為訓(xùn)練樣本 */ 輸出： RULE_LIST /*返回一個覆蓋若干樣例的規(guī)則 */ （ 1） Let RULE_LIST be the empty list； /* 初始化 RULES_LIST為空； */ （ 2） REPEAT （ 3） Let BEST_CPX be Find_Best_Complex（ E）； /*尋找最佳的規(guī)則 Find_Best_Complex（ E）并將其結(jié)果放入 BEST_CPX中； */ （ 4） IF BEST_CPX is not nil THEN BEGIN （ 5） Let E’ be the examples covered by BEST_CPX； /*令 E’為 BEST_CPX覆蓋的所有樣例 */ （ 6） Remove from E the examples E′ covered by BEST_CPX； /*從訓(xùn)練樣本 E中除去 E’，即 E=EE’； */ （ 7） Let C be the most mon class of examples in E’； /*令 C為樣本子集 E’中最頻繁的分類標(biāo)號； */ （ 8） Add the rule ‘if BEST_CPX then class=C’ to the end of RULE_LIST； /*將規(guī)則‘ if BEST_CPX then class=C’添加到 RULES_LIST中 */ （ 9） END （ 10） UNTIL BEST_CPX is nil or E is empty. /*直到 BEST_CPX為空或者訓(xùn)練樣本 E為空 */ （ 11） RETURN RULE_LIST 算法 CN2需要通過調(diào)用函數(shù) Find_Best_Complex，它的描述寫成下面算法 48。 2022年 3月 13日星期日 DMKD Sides By MAO 70 CN2算法描述 (續(xù) ) 算法 48 Find_Best_Complex 輸入： E /*E為訓(xùn)練樣本 */ 輸出： BEST_CPX /*返回最佳的規(guī)則 BEST_CPX */ （ 1） Let the set STAR contain only the empty Complex； /*初始化集合 STAR為空 Complex； */ （ 2） Let BEST_CPX be nil； /*初始化 BEST_CPX為空 */ （ 3） Let SELECTORS be the set of all possible Selectors； /*集合 SELECTOR為所有可能的選擇 */ （ 4） WHILE STAR is not empty DO BEGIN （ 5） Let NEWSTAR be the set {x∧ y|x∈ STAR， y∈ EXTENSION}； /*令 NEWSTAR= {x∧ y|x∈ STAR， y∈ EXTENSION}； */ （ 6） Remove all Complexes in NEWSTAR that are either in STAR or are null； /*從 NEWSTAR中除去包括在 STAR中的 Complex或者為空的 Complex*/ （ 7） FOR every plex Ci in NEWSTAR （ 8） IF Ci is statistically significant when tested on E and better than BEST_CPX according to userdefined criteria when tested on E /*如果 Ci在統(tǒng)計上有意義， 并且對訓(xùn)練集 E測試后符合用戶定義的條件且優(yōu)于 BEST_CPX*/ （ 9） THEN replace the current value of BEST_CPX by Ci； /*將 BEST_CPX替換為 Ci*/ （ 10） REPEAT remove worst Complexes from NEWSTAR （ 11） UNTIL size of NEWSTAR is = userdefined maximum maxstar； /*逐步移去在 NEWSTAR中最壞的 plex直到 NEWSTAR的大小等于或小于用戶 定義的最大數(shù)目 maxstar*/ （ 12） Let STAR be NEWSTAR； /*令 STAR=NEWSTAR*/ （ 13） END （ 14） RETURN BEST_CPX。 /*返回 BEST_CPX*/ 2022年 3月 13日星期日 DMKD Sides By MAO 71 FOIL算法 ? FOIL學(xué)習(xí)系統(tǒng)已經(jīng)被廣泛地應(yīng)用在邏輯規(guī)約領(lǐng)域。 FOIL是用來對無約束的一階 Horn子句進(jìn)行學(xué)習(xí)。一個概念的定義是由一系列的子句組成，而其中每一個子句描述了一種證明一個樣本是這個概念的實(shí)例的唯一方法。每個子句由一些文字的析取組成。 ? FOIL由一系列的外部定義的斷言開始，其中之一被確定為當(dāng)前學(xué)習(xí)的概念，而其他作為背景文字。 FOIL從這些外部定義的斷言中獲取一系列包括文字的子句。 ? FOIL算法由一個空子句開始查找，其不斷的向當(dāng)前的子句中追加文字直到?jīng)]有負(fù)樣例被子句所覆蓋。之后， FOIL重新開始一個子句的查找，直到所有的正樣例均被已經(jīng)生成的子句所覆蓋。 FOIL計算每一個外部定義斷言的信息熵（ Information Gain）和合法的變量（ Legal Variabilization）用來決定哪一個文字添加到子句中。 2022年 3月 13日星期日 DMKD Sides By MAO 72 一階 Horn子句的主要術(shù)語 ? 一階 Horn子句 所涉及的主要術(shù)語有： ? 所有表達(dá)式由 常量 （如 Mary、 23或 Joe）、變量（如 x）、謂詞（如在 Female（ Mary）中的 Female和函數(shù)（如在 age（ Mary）中的age）組成； ? 項(xiàng) （ Term）為任意常量、任意變量或任意應(yīng)用到項(xiàng)集合上的函數(shù)。例如， Mary， x， age（ Mary）， age（ x）； ? 文字 （ Literal）是應(yīng)用到項(xiàng)集合上的任意謂詞或其否定。例如，F(xiàn)emale（ Mary）， Greater_than（ age（ Mary）， 20）； ? 基本文字 （ Ground Literal）是不包括任何變量的文字； ? 負(fù)文字 （ Negative Literal）是包括否定謂詞的文字； ? 正文字 （ Positive Literal）是不包括否定謂詞的文字； ? 子句 （ Clause）是多個文字的析取式， M1∨??∨ Mn，其中所有變量是全程量化的； 2022年 3月 13日星期日 DMKD Sides By MAO 73 一階 Horn子句的表達(dá) ? Horn子句是一個如下形式的表達(dá)式： H?(L1∧ ……∧ Ln）。 其中， H， L1， L2， …， Ln為正文字。 H被稱為 Horn子句的頭（ Head）或推論（ Consequent）。文字合取式 L1∧ L2∧...∧ Ln被稱為 Horn子句的體（ Body）或者先行詞（ Antecedents）。 ? 臵換（ Substitution）是一個將某些變量替換為某些項(xiàng)的函數(shù)。例如，臵換 {x/3， y/z}把變量 x替換為項(xiàng) 3并且把變量 y替換為項(xiàng) z。給定一個臵換 θ 和一個文字 L，我們使用 Lθ 代表應(yīng)用臵換 θ 到 L得到的結(jié)果。 2022年 3月 13日星期日 DMKD Sides By MAO 74 FOIL算法描述 算法 49 FOIL （ Target_predicate， Predicates， Examples） 輸入： Examples /*樣本數(shù)據(jù) */ Predicates /*斷言集合 */ Target_predicate /*目標(biāo)斷言 */ 輸出：規(guī)則 （ 1） Pos?Examples中 Target_predicate為 Ture的成員； （ 2） Neg?Examples中 Target_predicate為 False的成員； （ 3） Learen_rules?{}； （ 4） WHILE Pos不空 DO BEGIN /*學(xué)習(xí) NewRule*/ （ 5） NewRules?沒有前件的謂詞 Target_predicate規(guī)則； （ 6） NewRuleNeg?Neg； （ 7） WHILE NewRuleNeg不空 BEGIN /*增加新文字以特化 NewRule*/ （ 8） Candidate_literals?對 NewRule生成后選新文字，基于 Predicates； （ 9） Best_literal?argmax Foil_Gain （ L， NewRule）； /*獲取最佳文字 */ （ 10） 把 Best_literal加入到 NewRule的前件； （ 11） NewRuleNeg?NewRuleNeg中滿足 NewRule前件的子集 （ 12） END； （ 13） Learned_rules?Learned_rules+NewRule； （ 14） Pos?Pos{被 NewRule覆蓋的 Pos成員 } （ 15） END； （ 16） 返回 Learned_rules 2022年 3月 13日星期日 DMKD Sides By MAO 75 FOIL算法介紹 ? FOIL中的候選特征化式的生成： 為生成當(dāng)前規(guī)則的候選特征式， FOIL生成多個不同的新文字，每個可被單獨(dú)地加到規(guī)則前件中。更精確地講，假定當(dāng)前規(guī)則為： P(x1， x2， … ， xk)? L1… L 其中， L1， …， Ln為當(dāng)前規(guī)則前件中的文字，而 P(x1， x2， …，xk)為規(guī)則頭（或后件）。 FOIL生成該規(guī)則的候選特征化式的方法是考慮符合下列形式的新文字 Ln+1： ? Q(v1， ? ， vr)，其中 Q為在 Predicates中出現(xiàn)的任意謂詞名，并且 vi既可 為新變量，也可為規(guī)則中已有的變量。 vi中至少一個變量必須是當(dāng)前規(guī)則中已有的。 ?Equal(xj， xk)，其中 xj和 xk為規(guī)則中已有的變量。 ?上述兩種文字的否定。 2022年 3月 13日星期日 DMKD Sides By MAO 76 FOIL算法介紹 (續(xù) ) ? Foil_Gain函數(shù) ? FOIL使用評估函數(shù)以估計增加新文字的效用，它基于加入新文字前后的正例和反例的約束數(shù)目。更精確地講，考慮某規(guī)則 R和一個可能被加到 R的規(guī)則體的后選文字 L。令 R′為加入文字 L到規(guī)則 R后生成的規(guī)則。 Foil_Gain(L， R)的值定義為： 其中， p0為規(guī)則 R的正例約束數(shù)目， n0為 R的反例約束數(shù)目，p1是規(guī)則 R′ 的正例約束數(shù)， n1為規(guī)則 R′ 的反例約束數(shù)目。最后， t是在加入文字 L到 R后仍舊能覆蓋的規(guī)則 R的正例約束數(shù)目。當(dāng)加入 L引入了一個新變量到 R中時，只要在 R′ 的約束中的某些約束擴(kuò)展了原始的約束，它們?nèi)匀荒鼙桓采w。 )l o g( l o g),(_00021112nppnpptRLG a inF o il????2022年 3月 13日星期日 DMKD Sides By MAO 77 FOIL算法舉例 假設(shè)學(xué)習(xí)目標(biāo)文字 fathe(A， B)的規(guī)則集例子。訓(xùn)練數(shù)據(jù)包括下列簡單的斷言集合： Examp