?

15.規則學習

15.1基本概念

機器學習中的規則（rule）通常是指語義明確、能描述數據分布所隱含的客觀規律或領域概念、可寫成若…則…形式的邏輯規則。規則學習（rulelearning）是從訓練數據中學習出一組能用于對未見示例進行判別的規則。

顯然，規則集合中的每天規則都可看作一個子模型，規則集合是這些子模型的一個集成。當同一個示例被判別結果不同的多條規則覆蓋時，稱發生了沖突（conflict），解決沖突的辦法稱為沖突消解（conflict resolution）。常用的沖突消解策略有投票法、排序法、元規則法等。投票法是將判別相同的規則數最多的結果作為最終結果。排序法是在規則結合上定義一個順序，在發生沖突時使用排序最前的規則；相應的規則學習過程稱為帶序規則（ordered rule）學習或優先級規則（priority rule）學習。元規則法是根據領域知識事先設定一些元規則（meta-rule），即關于規則的規則，例如發生沖突時使用長度最小的規則，然后根據元規則的指導來使用規則集。

此外，從訓練集學得的規則集合也許不能覆蓋所有可能的未見示例；對此，規則學習算法通常惠設置一條默認規則（default rule），由它來處理規則集合未覆蓋的樣本。

從形式語言表達能力而言，規則可分類兩類：

1）命題規則（propositionalrule）

由原子命題（propositionalatom）和邏輯連接詞（與、或、非、蘊含）構成的簡單陳述句。

2）一階規則（first-orderrule）

基本成分是能描述事物的屬性或關系的原子公式（atomic formula）。如表達父子關系的謂詞（predicate）父親(X,Y)就是原子公式；再比如加一操作add(x)=x+1。

一階規則能表達復雜的關系，因此也被稱為關系型規則（relational rule）。

以西瓜集為例，簡單地把屬性當作謂詞來定義示例與屬性值之間的關系，則命題規則集R可改寫為一階規則集R*：

顯然，從形式語言系統的角度來看，命題規則是一階規則的特例。因此一階規則的學習比命題規則要復雜得多。

?

15.2序貫覆蓋

規則學習的目標是產生一個能覆蓋盡可能多的樣例的規則集。最直接的做法是序貫覆蓋（sequential covering），即逐條歸納：在訓練集上每學到一條規則，就將該規則覆蓋的訓練樣例去除，然后以剩下的訓練樣例組成訓練集重復上述過程。由于每次只處理一部分數據，因此也稱為分治（separate-and-conquer）策略。

以命題規則學習為例來考察序貫覆蓋法。命題規則的規則體是對樣例屬性值進行評估的布爾函數，如色澤=青綠、漢唐率≤0.2等，規則頭是樣例類別。序貫覆蓋法的關鍵是如何從訓練集學出單條規則。

這種基于窮盡搜索的做法在屬性和候選值較多時會由于組合爆炸而不可行。現實任務中一般有兩種策略來產生規則：

1）自頂向下（top-down），即從比較一般的規則開始，逐漸增加新文字以縮小規則覆蓋范圍，直到滿足預定條件為止，也稱為生成-測試（generate-then-test）法，是規則逐漸特化（specialization）的過程，是從一般到特殊的過程；

2）自底向上（bottom-up），即從比較特殊的規則開始，逐漸刪除文字以擴大覆蓋范圍，直到滿足條件為止；也稱為數據驅動（data-driven）法，是規則逐漸泛化（generalization）的過程，是從特殊到一般的過程。

自頂向下是覆蓋范圍從大到小搜索規則，自底向上則正好相反；前者更容易產生泛化性能較好的規則，而后者更適合于訓練樣本較少的情形；另外，前者對噪聲的魯棒性比后者要強；因此，在命題規則學習中通常使用前者，而后者則在一階規則學習這類假設空間非常復雜的任務使用較多。

以命題規則學習為例，對于自頂向下的規則生成方法，文中給出了西瓜集例子。例子中規則生成過程設計一個評估規則優劣的標準，例子中給出的標準是：先考慮規則準確率，準確率同時考慮覆蓋樣例數，再相同時考慮屬性次序?，F實應用中可根據具體任務情況設計適當的標準。例子中每次僅考慮一個最優文字，過于貪心，容易陷入局部最優，為緩解這個問題，采用集束搜索（beam search），即每輪保留最優的b個邏輯文字，在下一輪均用于構建候選集，再把候選集中最優的b個留待下一輪使用。

序貫覆蓋法簡單有效，幾乎所有規則學習算法都以其為基本框架，也能方便地推廣到多分類問題上，只需將每類分別處理即可：當學習關于第c類的規則時，將所有屬于類別c的樣本作為正例，其他類別的樣本作為反例。

?

15.3剪枝優化

規則生成本質上是一個貪心搜索過程，需要一定的機制來緩解過擬合的風險，最常見的做法是剪枝（pruning）。與決策樹相似，剪枝可發生在規則生長過程中，即預剪枝；也可發生在規則產生后，即后剪枝。通常是基于某種性能度量指標來評估增/刪邏輯文字前后的規則性能，或增/刪規則前后的規則集性能，從而判斷是否要進行剪枝。

RIPPER中的后處理機制是為了在剪枝的基礎上進一步提升性能，對R中的每條規則r_i，RIPPER為它產生兩個變體：

第一：r*_i：基于r_i覆蓋的樣例，用IREP*重新生成一條規則r*_i，該規則稱為替換規則（replacement rule）；

第二：r**_i：基于r_i增加文字進行特化，然后再用IREP*剪枝生成一條規則r**_i，該規則稱為修訂規則（revised rule）。

接下來，把r*_i和r**_i分別于R中除r_i之外的規則放在一起，組成規則集R*和R**，將它們與R一起進行比較，選擇最優的規則集保留下來。

RIPREP更有效的原因是：最初生成R時，規則是按序生成的，每條規則都沒有對其后產生的規則加以考慮，這樣的貪心算法本質常導致算法陷入局部最優；而RIPPER的后處理優化過程將R中的所有規則放在一起重新加以優化，恰是通過全局的考慮來緩解貪心算法的局部性，從而往往能獲得更好的效果。

?

15.4一階規則學習

受限于命題邏輯表達能力，命題規則學習難以處理對象之間的關系（relation），而關系信息再很多任務中是很重要的，要用一階邏輯表示，使用一階規則學習。

描述了樣例間關系的數據稱為關系數據（relational data），有原樣本屬性轉化而來的原子公式稱為背景知識（backgroundknowledge），而由樣本類別轉化而來的原子公式稱為關系數據樣例（examples）。如從西瓜集學出的一階規則：

若允許將目標謂詞作為候選文字加入規則體，則FOIL能學出遞歸規則；若允許將否定形式的文字作為候選，則往往能得到更簡潔的規則集。

FOIL可大致看作是命題規則學習與歸納邏輯程序設計之間的過度，其自頂向下的規則生成過程不能支持函數和邏輯表達式嵌套，因此規則表達能力仍有不足；但它是把命題規則學習過程通過變量替換等操作直接轉化為一階規則學習，因此比一般歸納邏輯程序設計技術更高效。

?

15.5歸納邏輯程序設計

歸納邏輯程序設計（Inductive Logic Programming，ILP）在一階規則學習中引入了函數和邏輯表達式嵌套。這使得，一方面機器學習系統具備了更為強大的表達能力；另一方面ILP可看作用機器學習技術來解決基于背景知識的邏輯程序（logic program）貴南，其學得的規則可被PROLOG等邏輯程序設計語言直接使用。

然后，函數和邏輯表達式嵌套的引入也帶來了計算上的巨大挑戰。例如，給給定一元謂詞P和一元函數f，能組成的文字有P(X)，P(f(X))，P(f(f(X)))等無窮多個，這就是使得規則學習過程中可能的候選原子公式有無窮多個。若仍采用命題邏輯規則或FOIL學習那樣自頂向下的規則生成過程，則在增加規則長度時將因無法列舉所有候選文字而失敗。實際困難還包括，在計算FOIL增益時需對規則覆蓋的全部正反例計數，而在引入函數和邏輯表達式嵌套之后也變得不可行。

1）最小一般泛化

歸納邏輯程序設計采用自底向上的規則生成策略，直接將一個或多個正例所對應的具體事實（grounded fact）作為初始規則，再對規則逐步進行泛化以增加對樣例的覆蓋率。泛化操作主要是兩個動作：將規則中的常量替換為邏輯變量，刪除規則體中的某個文字。

例子：

更好（1,10）<—根蒂更蜷（1,10）∩聲音更沉（1,10）∩臍部更凹（1,10）∩觸感更硬（1,10）

更好（1,15）<—根蒂更蜷（1, 15）∩臍部更凹（1, 15）∩觸感更硬（1, 15）

這兩條是事實，說明西瓜1比西瓜10、15的特征比較，是特殊的關系數據樣例，不具有泛化能力。需要將這樣的特殊規則轉變為更一般的規則，采用的最基礎技術就是最小一般泛化（Least General Generalization，LGG）。

給定一階公式r1和r2，LGG先找出設計相同謂詞的文字，然后對文字中每個位置的常量逐一進行考察，若常量在兩個文字中相同則保持不變，記LGG(t,t)=t；否則將它們替換為同一個新變量，并將該替換應用關于公式的所有其他位置，假定這兩個不同的常量分別為s、t，新變臉為V，則記為LGG(s,t)=V，并在以后所有出現的LGG(s,t)的位置用V來代替。一句話，常量換變量。

更好（1,Y）<—根蒂更蜷（1,Y）∧聲音更沉（1,10）∧臍部更凹（1,Y）∧觸感更硬（1,Y）

更好（1,Y）<—根蒂更蜷（1, Y）∧臍部更凹（1, Y）∧觸感更硬（1, Y）

接著，LGG忽略r1和r2中不含共同謂詞的文字。顯然上面這個例子中，聲音更沉謂詞就要忽略了。最終兩條規則經過LGG的兩個步驟，常量換變量和保留交集謂詞，就變成：

更好（1,Y）<—根蒂更蜷（1, Y）∧臍部更凹（1, Y）∧觸感更硬（1, Y）

這條規則就是可以判斷西瓜1是否比其他瓜更好。為提高泛化能力，結合西瓜2的初始規則：

更好（2,10）<—顏色更深（2,10）∧根蒂更蜷（2,10）∧敲聲更沉（2,10）∧臍部更凹（2,10）∧觸感更硬（2,10）

對這兩個規則進行LGG，還是常量換變量和保留交集謂詞，最后就變成：

更好（X,Y）<—根蒂更蜷（X, Y）∧臍部更凹（X, Y）∧觸感更硬（X, Y）

這條規則就可以用來比較任何兩個西瓜的優劣了。

如果在規則中引入非符號，LGG還能進行更復雜的泛化操作。另外，上面例子的初始規則僅包含變量同為（X,Y）的關系，而背景知識應該包含更多的關系，故此ILP系統常采用不用的初始規則選擇方法。最常用的是RLGG(relative leastgeneral generalization,RLGG)，在計算LGG時考慮所有的背景知識，將樣例e的初始規則定義為e<-K，其中K是背景知識中所有原子的合取。

容易證明，LGG能特化為r1和r2的所有一階公式中最特殊的一個：不存在既能特化為r1和r2，也能泛化為它們的LGG的一階公式r*。在歸納邏輯程序設計中，獲得LGG之后，可將其看作單條規則加入規則集，并可采用對規則集進行后剪枝來進一步優化。

2）逆歸結

在邏輯學中，演繹（deduction）與歸納（induction）是人類認識世界的兩種基本方式。演繹是從一般性規律出發來探討具體事務，而歸納則是從個別事物出發概括出一般性規律。一般數學定理證明是演繹實踐的代表，而機器學習顯然是屬于歸納的范疇。1965年邏輯學家J.A.Robinson提出，一階謂詞演算中的演繹推理能用一條十分簡潔的規則描述，這就是數理邏輯中著名的歸結原理（resolution principle）；二十年后，計算機科學家S.Muggleton和W.Butine針對歸納推理提出了逆歸結（inverse resolution），這對歸納邏輯程序設計的發展起到了重要作用。

基于歸結原理，可將復雜的邏輯規則與背景知識聯系起來化繁為簡，從一般到特殊；基于逆歸結，可依托背景知識發明新概念和關系，從特殊到一般。以命題演算為例，來說明歸結和逆歸結。

假設兩個邏輯表達式C₁和C₂成立，其分別包含了互補項L₁與L₂；不是一般性，令L=L₁=﹁L₂，C₁=A∨L，C₂=B∨﹁L。

歸結原理是通過演繹消去L而得到歸結項C=A∨B。

逆歸結的過程相反，是研究在已知C和某個C_i的情況下如何得到C_j（i≠j）：C₂=(C-( C₁-{L}))∨{﹁L }。

在邏輯推理實踐中如何實現逆歸結呢？有四種完備的逆歸結操作。若以規則形式p←q等價地表達 p∨﹁q，并假定用小寫字母表示邏輯文字、大寫字母表示合取式組成的邏輯子句，則這四類操作是：

這里X/Y表示X蘊含Y，即X推出Y。上述規則中，X的子句或是Y的歸結項，或是Y的某個子句的等價項；而Y中出現的新邏輯文字則可看作通過歸納學到的新命題。

歸結、逆歸結都能容易地擴展為一階邏輯形式，與命題邏輯的主要不同之處在于，一階邏輯的歸結、逆歸結通常需進行合一置換操作。

置換（substitution）是用某些項來替換邏輯表達式中的變量。如用⊙={1/X,2/Y}置換C=色澤更深(X,Y)∧敲聲更沉(X,Y)可得到C*=C⊙=色澤更深(1,2) ∧敲聲更沉(1,2)，其中{X,Y}稱為⊙的作用域（domain）。與代數中的置換類似，一階邏輯中也有復合置換和逆置換。

合一（unification）是用一種變量置換令兩個或多個邏輯表達式相等。如對A=色澤更深(1,X)和B=色澤更深(Y,2)，可用⊙={2/X,1/Y}使A⊙=B⊙=色澤更深（1,2），此時稱A和B是可合一的（unifiable），稱⊙為A和B的合一化子（unifer）。若δ是一組一階邏輯表達式W的合一化子，且對W的任意合一化子Θ均存在相應的置換λ使Θ=δoλ，則稱δ為W的最一般合一置換或最一般合一化子（most general unifier，記為MGU），這是歸納邏輯程序中最重要的概念之一。如色澤更深（1,Y）和色澤更深(X,Y)能被Θ1={1/X}，Θ2={1/X,2/Y}，Θ3={1/Z,Z/X}合一，但僅有Θ1是它們的MGU。

一階邏輯進行歸結時，需利用合一操作來搜索互補項L₁與L₂。對兩個一階邏輯表達式C₁=A∨L₁和C₂=B∨L₂，若存在合一化子Θ使得L₁Θ=﹁L₂Θ，則可對其進行歸結：C=( C₁-{ L₁})Θ∨( C₂-{L₂})Θ。

類似地，可利用合一化子將逆歸結項擴展到一階邏輯的逆歸結。定義C₁=C/ C₂和C₂=C/C₁為歸結商（resolution quotient），于是，逆歸結的目標就是在已知C和C₁時求出歸結商C₂。對某個L₁∈C₁，假設?1是一個置換，可使( C₁-{ L₁}) ?1蘊含C，即推出C。這里?1的作用域是C₁中所有變量，記vars(C₁)，其作用是使C₁-{L₁}與C中的對應文字能合一。令?2為作用域是vars(L₁)-vars(C₁-{L₁})的置換，L₁為歸結商C₂中將被消去的文字，Θ2是以vars(L₂)為作用域的置換，?1和?2共同作用域L₁，使得﹁L₁ ?1o ?2= L₂Θ2，于是?1o ?2oΘ2為﹁L₁與L₂的MGU。將前兩步的復合置換?1o ?2記為Θ1，用Θ2^-1表示Θ2的逆置換，則有(﹁L₁Θ1) Θ2^-1=L₂，可得一階逆歸結：C₂=(C-( C₁-{ L₁})Θ1∨{﹁L₁Θ1})Θ2^-1。在一階情形下L₁、L₂、Θ1和Θ2的選擇通常都不唯一，需通過其他判斷標準來取舍，如覆蓋率、準確率、信息熵等。例子可看文中的西瓜集。

逆歸結的一大特點就是能自動發明新謂詞，這些新謂詞可能對應于樣例屬性和背景知識中不存在的新知識，對知識發現和精化有重要意義。但自動發明的新謂詞究竟對應于什么語義，要在任務領域中進一步理解。在現實任務中，ILP系統通常先自底向上生成一組規則，然后再結合最小一般泛化與逆歸結進一步學習。

本章總結，規則學習是符號主義學習（symbolism learning）的主要代表，是最早開始研究的機器學習技術之一。規則學習主要提出了命題規則學習、一階規則學習和歸納邏輯程序設計，并給出序貫覆蓋、剪枝優化等技術。ILP復雜度很高，問題規模稍大難以處理，隨著統計學習的興起，規則學習被邊緣化；不過在富含結構信息和領域知識的任務中，邏輯表達的重要性凸顯，因此結合規則學習和統計學習又抬頭。實際上，規則學習應該是最早的機器學習方法，典型就是知識工程與專家系統，而統計學習后面崛起，究竟最終機器學習的根本在規則還在統計，顯然仍未有定論。

總結

以上是生活随笔為你收集整理的机器学习笔记(十五)规则学习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。